From f4fc692fbc9b6784563f0f6360004c92c3c4c23d Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Fri, 8 Dec 2023 13:34:22 +0100 Subject: 2023-08 in haskell --- 2023/08-Haunted_Wasteland/example | 9 + 2023/08-Haunted_Wasteland/example2 | 10 + 2023/08-Haunted_Wasteland/first.hs | 74 ++++ 2023/08-Haunted_Wasteland/input | 760 ++++++++++++++++++++++++++++++++++++ 2023/08-Haunted_Wasteland/second.hs | 76 ++++ 5 files changed, 929 insertions(+) create mode 100644 2023/08-Haunted_Wasteland/example create mode 100644 2023/08-Haunted_Wasteland/example2 create mode 100644 2023/08-Haunted_Wasteland/first.hs create mode 100644 2023/08-Haunted_Wasteland/input create mode 100644 2023/08-Haunted_Wasteland/second.hs (limited to '2023/08-Haunted_Wasteland') diff --git a/2023/08-Haunted_Wasteland/example b/2023/08-Haunted_Wasteland/example new file mode 100644 index 0000000..9029a1b --- /dev/null +++ b/2023/08-Haunted_Wasteland/example @@ -0,0 +1,9 @@ +RL + +AAA = (BBB, CCC) +BBB = (DDD, EEE) +CCC = (ZZZ, GGG) +DDD = (DDD, DDD) +EEE = (EEE, EEE) +GGG = (GGG, GGG) +ZZZ = (ZZZ, ZZZ) diff --git a/2023/08-Haunted_Wasteland/example2 b/2023/08-Haunted_Wasteland/example2 new file mode 100644 index 0000000..5b3fa58 --- /dev/null +++ b/2023/08-Haunted_Wasteland/example2 @@ -0,0 +1,10 @@ +LR + +11A = (11B, XXX) +11B = (XXX, 11Z) +11Z = (11B, XXX) +22A = (22B, XXX) +22B = (22C, 22C) +22C = (22Z, 22Z) +22Z = (22B, 22B) +XXX = (XXX, XXX) diff --git a/2023/08-Haunted_Wasteland/first.hs b/2023/08-Haunted_Wasteland/first.hs new file mode 100644 index 0000000..54b773f --- /dev/null +++ b/2023/08-Haunted_Wasteland/first.hs @@ -0,0 +1,74 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 2 + +data Direction = L | R deriving (Eq, Show) +type Branch = (String, String) +type Map = M.Map String Branch +data Input = Input [Direction] Map deriving Show + +type Parser = Parsec Void String + +parseDirection :: Parser Direction +parseDirection = char 'L' $> L + <|> char 'R' $> R + +parseNode :: Parser String +parseNode = some letterChar + +parseBranch :: Parser Branch +parseBranch = (,) <$> (char '(' *> parseNode) + <*> (string ", " *> parseNode <* char ')') + +parseMapElt :: Parser (String, Branch) +parseMapElt = (,) <$> (parseNode <* string " = ") + <*> (parseBranch <* eol) + +parseInput' :: Parser Input +parseInput' = Input <$> some parseDirection <* eol <* eol + <*> (M.fromList <$> some parseMapElt <* eof) + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> error $ errorBundlePretty bundle + Right input' -> return input' + +compute :: Input -> Int +compute (Input directions m) = compute' "AAA" 0 + where + compute' :: String -> Int -> Int + compute' node i | node == "ZZZ" = i + | otherwise = compute' (nextOne node) (i+1) + where + nextOne :: String -> String + nextOne = next . (m M.!) + next :: Branch -> String + next | directions L.!! (i `mod` l) == L = fst + | otherwise = snd + l = length directions + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input diff --git a/2023/08-Haunted_Wasteland/input b/2023/08-Haunted_Wasteland/input new file mode 100644 index 0000000..90be217 --- /dev/null +++ b/2023/08-Haunted_Wasteland/input @@ -0,0 +1,760 @@ +LRRRLRRLRRLRRLLLRRRLRRLLRRRLRLLLRRLRLRLRLRLRLRLRRRLLLRRLRRRLRLLRRRLRRRLRRRLLRRRLRLRRRLRRLRRRLLRLLRLLRRRLRRRLRRLRLRLLRLRRLRRRLRRRLRLRLRLRRLRLRLLLRRRLRLRLRRRLRRRLRRRLRLLLRRLRLRLRLRLLLRRRLRRLRRLRLRLRRRLRLRRRLRRRLRRRLRLRRRLLLRRLRRRLRRLLRLRRLRRLRRRLLLRRLRRLRRLRLRRRLLLRLRRRR + +PND = (LHJ, NLX) +KPD = (HMV, DLD) +GBD = (QFL, XNG) +QGL = (BPR, XTJ) +XTJ = (VCQ, TBJ) +BQT = (NXD, SCD) +QJK = (TKT, CTC) +MMP = (VMB, NGD) +DDN = (JRC, JRC) +CFM = (HCK, CCB) +FNX = (XHK, GCP) +JFP = (XMD, QTS) +LJL = (DCT, PGF) +TPH = (GLJ, DBV) +BNH = (JCB, KBQ) +KJM = (GBD, JDP) +CGX = (VGJ, VCP) +LFK = (XSM, SHM) +RSP = (GRS, SRF) +CMH = (TRC, JXX) +FXX = (FRM, QVN) +MSS = (TCG, CQC) +DFC = (MSS, FQM) +LVJ = (JJG, TFC) +FRK = (NDQ, CDN) +BCF = (TCF, MFR) +KGJ = (MVN, VKK) +FHK = (MLK, PCS) +VFP = (QGX, NHF) +FMR = (MKH, QKN) +XRG = (DJB, MXG) +VMG = (JNC, XCN) +MSC = (KBR, HPP) +TFC = (GXJ, JSF) +PSV = (BPN, QTG) +CPK = (HMH, MRQ) +SRF = (KMV, BSM) +KVV = (DHF, PGX) +PJL = (JHL, CPK) +MVS = (VRJ, NTP) +VMB = (XBQ, PVS) +DXS = (RKB, KPD) +BJX = (MCK, LCL) +BNZ = (QRF, PQL) +SJT = (DDD, RMR) +BBS = (MTL, MTL) +RMG = (CDN, NDQ) +KFG = (XNS, HGP) +BPN = (RKQ, GVC) +KCN = (CVH, XCH) +JPS = (VMG, RTR) +LDX = (LVF, BSD) +PSQ = (BKM, MGZ) +GXJ = (JHM, LKQ) +VPC = (LBJ, HDD) +DDB = (PNL, NFH) +TVD = (PJL, FMJ) +TQH = (PCX, JSQ) +MPP = (CHR, XCP) +CRQ = (FKG, JQJ) +PVT = (NMK, HKH) +DSH = (LDN, BMR) +XND = (NPQ, BKV) +SHM = (MSC, JNS) +FLV = (TVT, HSM) +GJN = (FTC, XFX) +HKX = (BCF, FHJ) +DBJ = (TLN, CVP) +CVR = (KFC, LQP) +VRJ = (QMB, XLV) +LSS = (MCK, LCL) +GPH = (TSV, FKN) +MLF = (BBS, BBS) +CTN = (MML, SXC) +NMR = (DCS, XQN) +VNP = (SFF, QSD) +TBJ = (XPG, XHV) +VCP = (SCV, TDB) +KMK = (MLK, PCS) +CSJ = (PNK, JQP) +RSN = (JRC, PSQ) +HLL = (KVJ, QTX) +KXM = (RJC, BKQ) +KCR = (MSM, SPN) +BFA = (CMB, RSV) +KHB = (SFH, MVS) +PXT = (KLV, NRC) +VSF = (XLG, XLG) +XJK = (LRN, HXB) +LCR = (RMJ, QLD) +FCR = (QFF, CVG) +DPM = (SDM, DGQ) +TXQ = (LPK, JML) +RLK = (DMM, KBS) +DXQ = (KPD, RKB) +TSV = (KGJ, HCH) +GXQ = (SXC, MML) +BMC = (XND, CLT) +LBL = (TKM, HSD) +FQS = (DSH, HML) +MJM = (CQK, DFC) +CJH = (XHK, XHK) +HHM = (HJK, RKF) +SDM = (MDD, DVL) +NDR = (CTH, HVN) +XVF = (PSV, KFK) +FTV = (HFF, VXH) +KDK = (BNK, JTB) +AAA = (FTV, NDS) +RDQ = (FTC, XFX) +GSC = (BHJ, JJD) +QBV = (BMC, JVX) +SRJ = (RQS, BXQ) +TRC = (JVM, QNL) +RMR = (BSB, HBV) +DCM = (RRF, RFJ) +KGF = (NHF, QGX) +PBF = (RCT, JBQ) +XRQ = (DGP, DKR) +CND = (DSF, VTJ) +CCB = (SLH, HRF) +SMS = (NDR, PTT) +DCT = (JXQ, KQP) +QTX = (JPH, MPK) +MRP = (CGG, JPS) +KQP = (BNL, VDV) +XDR = (DRQ, FXV) +RRL = (JVT, PGM) +LKQ = (MTN, JRG) +NBF = (RBB, CNK) +CQL = (XCG, GNB) +GLT = (JQM, KCN) +FFN = (FLV, FVS) +BPR = (TBJ, VCQ) +JBN = (DXQ, DXS) +KKN = (PQF, VGK) +RCT = (RSB, KDK) +MKL = (RVB, LBL) +DDD = (BSB, HBV) +RHX = (SQB, SHB) +NSV = (KLF, KQG) +MNC = (HRJ, DBS) +QGJ = (XVL, RKD) +KMN = (FHJ, BCF) +VHL = (MGD, CXM) +RVJ = (BNH, GRQ) +QHD = (FLK, QGB) +CQK = (MSS, FQM) +GQT = (FXX, HVC) +JNC = (TFD, NCS) +SFL = (FFN, DMD) +CTC = (CSJ, HPQ) +TCG = (MTD, JTS) +RTN = (QGJ, QGJ) +VGF = (KBS, DMM) +JNL = (RGC, CLB) +THG = (GSV, VSJ) +VDV = (HCL, FLT) +QGB = (DRN, CBG) +VPP = (RTD, GQT) +DHF = (FQS, GNH) +PTR = (KJN, XRG) +DQF = (CTN, GXQ) +VLN = (GNF, TKV) +JBC = (SFL, CVK) +LQR = (JML, LPK) +JPH = (THG, SVP) +CVP = (JFM, VLN) +VXT = (HMF, FFR) +HHK = (QGJ, SSZ) +MLK = (LVD, KPB) +QJF = (QVC, FBM) +KTS = (XRC, MQS) +HSM = (SGR, BKG) +DBN = (TKB, XJK) +QRF = (HHX, TSH) +FMJ = (CPK, JHL) +HLK = (PJV, SBH) +FNB = (MCV, NHG) +HPQ = (JQP, PNK) +RDN = (QXH, VGC) +SHB = (KXM, TFJ) +MDD = (QGD, VRM) +NTP = (QMB, XLV) +MKH = (VCX, FRC) +DGK = (LCH, MGJ) +TKV = (VFH, DXK) +NHX = (GPH, KRT) +GVC = (MGQ, JNH) +MQS = (VXT, KSH) +XFM = (SMX, PTR) +KCH = (KVR, PXF) +RKB = (HMV, DLD) +PTN = (TVJ, PXC) +LQP = (PKV, DBJ) +MGJ = (JTG, SMG) +FNS = (QLD, RMJ) +KVR = (VNF, CDH) +RXV = (XSF, XXL) +TFJ = (BKQ, RJC) +KNK = (JBN, VTC) +QKK = (CHR, XCP) +HXB = (VBD, HLP) +KGL = (PCX, JSQ) +KSR = (CMH, JLT) +PJT = (DRQ, FXV) +DSS = (SKK, XQQ) +VXH = (CVR, TMC) +RGJ = (TKT, CTC) +FVK = (SFQ, TVD) +BKD = (QTX, KVJ) +HHX = (DVD, GTG) +NFH = (PLM, PDC) +DBS = (KJM, RVG) +QFN = (CMX, JSR) +GVK = (CMH, JLT) +VGJ = (SCV, TDB) +VVD = (HBX, GTC) +HNX = (PLF, RBG) +HFF = (CVR, TMC) +JSR = (DFV, FDT) +HMH = (CFN, FCT) +XFF = (HHM, DRV) +CML = (RVJ, VPD) +HFL = (HVB, GML) +HST = (RMG, FRK) +JVX = (XND, CLT) +DMD = (FVS, FLV) +XLV = (VHL, NBP) +HJK = (QHD, GHG) +HCH = (MVN, VKK) +JTF = (HVB, GML) +PLM = (BMM, DST) +FKD = (FBL, KNK) +FVS = (HSM, TVT) +GNH = (DSH, HML) +CBL = (GLQ, XBC) +KBK = (QJG, GGJ) +PXF = (CDH, VNF) +VRM = (NPL, CVT) +LKR = (XCG, XCG) +VXV = (DVN, KHM) +VNF = (HST, RMC) +FKG = (XFG, LCQ) +QGX = (RXJ, LXN) +PNL = (PDC, PLM) +DVL = (VRM, QGD) +SQB = (TFJ, KXM) +PCX = (TTS, MKL) +FDT = (SJT, KQN) +QTS = (CRQ, DKM) +MJG = (CVK, SFL) +BXP = (HGM, QJF) +MCK = (NJM, MMP) +KLV = (PJT, XDR) +RKD = (JNB, KTS) +FLT = (FCR, RHH) +QGS = (DPM, PHJ) +LVB = (RSF, HJV) +XCH = (XBX, XFM) +FTG = (DPM, PHJ) +RGC = (SNM, LJJ) +QCC = (NRD, HNK) +LJM = (SRJ, CCP) +SFQ = (PJL, FMJ) +NRX = (MVP, RSP) +PKC = (XFD, NMR) +SPB = (JTF, HFL) +BVM = (MCS, FVK) +DRQ = (LKR, CQL) +PCS = (KPB, LVD) +HLP = (GPP, PND) +HVN = (KHB, TBT) +SCD = (GQH, NKP) +NPB = (PJV, SBH) +XQQ = (CJP, JLG) +CHX = (KSJ, GJD) +RGQ = (GLV, GLV) +DCS = (KHQ, DTB) +MCV = (SFK, CFM) +SCS = (RXV, MGV) +TKM = (XFF, TMV) +BSD = (GTB, VPC) +RPC = (SRJ, CCP) +TLN = (JFM, VLN) +MTN = (GFP, JFP) +FVP = (HGP, XNS) +JQX = (TQH, KGL) +LQG = (CSV, DFR) +SKK = (JLG, CJP) +MVN = (MJG, JBC) +RKT = (GLT, QRM) +STV = (FBL, KNK) +MQC = (BBS, XGG) +FFR = (LJL, DQP) +BDF = (MSM, SPN) +FQM = (TCG, CQC) +HNK = (NRF, CPT) +VKL = (DCM, DTS) +GDF = (JQX, PJX) +FBL = (VTC, JBN) +JDP = (XNG, QFL) +NLX = (CLM, DGK) +NRD = (CPT, NRF) +HKH = (FNS, LCR) +TRR = (DTM, DTM) +SGR = (LSS, BJX) +DSN = (DDB, TQZ) +KPB = (FXT, PBF) +DQP = (PGF, DCT) +SMX = (KJN, XRG) +GDG = (VPP, PXQ) +KKT = (CSV, DFR) +GPP = (NLX, LHJ) +DTS = (RRF, RFJ) +HXV = (JVX, BMC) +JCB = (VDK, QLF) +PRR = (FQH, DSN) +TFD = (RTV, TGX) +DMM = (FKD, STV) +KMV = (PPH, RSJ) +HGP = (QMM, DCC) +NCS = (RTV, TGX) +VCQ = (XPG, XHV) +QSD = (RFX, XHH) +SPN = (HND, DJN) +DBR = (CSD, LFG) +DST = (GDG, KKR) +BGV = (NRD, HNK) +KQN = (DDD, RMR) +CNP = (HGM, QJF) +MFR = (DHV, NSV) +VSJ = (JJJ, RFR) +CXF = (CXQ, SRV) +SCF = (CTN, GXQ) +HVB = (CML, SQT) +QHN = (MVP, RSP) +HGM = (FBM, QVC) +XGG = (MTL, BNZ) +JMT = (DKH, PNP) +MVK = (KRT, GPH) +BTC = (PNH, PRJ) +MLL = (TRR, RVQ) +VPD = (GRQ, BNH) +XBC = (FSC, KGX) +SFK = (HCK, CCB) +PNK = (QFN, VHD) +SQT = (VPD, RVJ) +QXH = (KCR, BDF) +JQM = (CVH, XCH) +QGD = (CVT, NPL) +JXX = (JVM, QNL) +RTR = (XCN, JNC) +BMM = (GDG, KKR) +MTF = (FVK, MCS) +DJB = (DDN, DDN) +GDQ = (SKK, XQQ) +NRF = (QKK, MPP) +CFN = (RCG, SRH) +BSB = (LQG, KKT) +FJX = (DSF, VTJ) +RMJ = (VQG, CPJ) +LFG = (VNC, RKT) +TKT = (HPQ, CSJ) +JRC = (BKM, BKM) +XNG = (FTS, RDK) +RRR = (JJD, BHJ) +CVK = (FFN, DMD) +TVT = (SGR, BKG) +KSJ = (LDF, SPB) +XSM = (JNS, MSC) +PRJ = (SSF, HNG) +MSG = (CSD, LFG) +TMV = (DRV, HHM) +BKQ = (VFP, KGF) +SQR = (NML, HNX) +SRH = (FNB, XRL) +CBG = (PXT, JSM) +MSM = (HND, DJN) +SCV = (SML, CLH) +QFS = (TKB, XJK) +CLB = (LJJ, SNM) +FRM = (QGS, FTG) +KVX = (CQK, DFC) +QFL = (RDK, FTS) +DSF = (CDG, XLF) +HML = (BMR, LDN) +LVF = (GTB, VPC) +XLF = (CNP, BXP) +HMF = (DQP, LJL) +MGZ = (RSV, CMB) +TGX = (XRQ, XGL) +RMC = (RMG, FRK) +PNH = (SSF, HNG) +PDC = (DST, BMM) +PGF = (JXQ, KQP) +BHJ = (DSS, GDQ) +VNC = (QRM, GLT) +MTL = (PQL, QRF) +XFJ = (NRX, QHN) +TBT = (SFH, MVS) +HSD = (TMV, XFF) +SSJ = (PSV, KFK) +HXP = (GJN, RDQ) +GRV = (GFN, CBL) +BNL = (HCL, FLT) +FTS = (NPB, HLK) +PXQ = (GQT, RTD) +RJM = (HMS, RDN) +SPV = (JJG, TFC) +SVP = (GSV, VSJ) +LCL = (NJM, MMP) +CTH = (KHB, TBT) +JBQ = (KDK, RSB) +XGL = (DGP, DKR) +RRF = (QFS, DBN) +SFF = (XHH, RFX) +GLQ = (KGX, FSC) +RKQ = (JNH, MGQ) +TMF = (LQR, TXQ) +DRN = (PXT, JSM) +TVJ = (PLL, SQR) +GRS = (KMV, BSM) +FRC = (BTL, DVB) +PLF = (FRQ, LCF) +NMK = (FNS, LCR) +XCN = (NCS, TFD) +JTB = (MQN, LDX) +CSD = (VNC, RKT) +MGD = (HRN, LHP) +RJG = (HXP, RQH) +HQV = (QBV, HXV) +NJM = (NGD, VMB) +CBR = (GGJ, QJG) +TMC = (LQP, KFC) +JRH = (KVR, PXF) +KBQ = (VDK, QLF) +HBV = (KKT, LQG) +RFJ = (QFS, DBN) +CFS = (JQX, PJX) +LNP = (QSD, SFF) +DKM = (JQJ, FKG) +CXR = (PKL, CHX) +KBR = (LGJ, PTN) +GNF = (DXK, VFH) +DKR = (KMK, FHK) +XQG = (CFS, GDF) +DFA = (PNL, NFH) +CXM = (HRN, LHP) +XLG = (TRR, TRR) +TTS = (RVB, LBL) +PVS = (KVX, MJM) +VDK = (PBX, KML) +XHH = (FJX, CND) +PKL = (KSJ, GJD) +LJJ = (BVB, PRL) +DTB = (RGP, RJG) +HND = (MLF, MLF) +FLK = (DRN, CBG) +BKZ = (BLG, LVB) +RDK = (HLK, NPB) +MCS = (SFQ, TVD) +HNG = (RLK, VGF) +LGJ = (TVJ, PXC) +LNV = (QGL, NQN) +PKG = (XLG, MLL) +FTC = (BKD, HLL) +HRN = (VSF, PKG) +MGV = (XSF, XXL) +VTJ = (CDG, XLF) +KSH = (FFR, HMF) +SBH = (SPV, LVJ) +RVG = (GBD, JDP) +PGM = (MSG, DBR) +JTJ = (SRV, CXQ) +XFA = (LVB, BLG) +BLN = (PRJ, PNH) +QVN = (FTG, QGS) +PRH = (FQH, FQH) +HDD = (PRH, PRR) +KLF = (XVF, SSJ) +LXN = (XNL, KKN) +QJA = (PQL, QRF) +KVJ = (MPK, JPH) +GRD = (CFS, GDF) +LPK = (TKS, CXR) +KRT = (TSV, FKN) +XRL = (MCV, NHG) +CGG = (RTR, VMG) +DTM = (FTV, NDS) +CCP = (BXQ, RQS) +JHM = (JRG, MTN) +RFX = (CND, FJX) +HCL = (FCR, RHH) +RTV = (XGL, XRQ) +PPL = (CBL, GFN) +ZZZ = (NDS, FTV) +HNR = (KHM, DVN) +NHF = (RXJ, LXN) +JLT = (JXX, TRC) +JNS = (HPP, KBR) +VGC = (BDF, KCR) +LCH = (SMG, JTG) +LHJ = (CLM, DGK) +NNC = (QGL, NQN) +GSV = (RFR, JJJ) +TDB = (SML, CLH) +LBJ = (PRH, PRH) +MKG = (HBX, GTC) +VLB = (QKN, MKH) +GQH = (QLG, RHX) +KGQ = (SCS, XKL) +RSJ = (GRD, XQG) +CVT = (RRR, GSC) +FCT = (RCG, SRH) +XFX = (HLL, BKD) +CPT = (QKK, MPP) +DVN = (MCT, RRL) +PHJ = (DGQ, SDM) +HVC = (FRM, QVN) +RCG = (FNB, XRL) +FXT = (JBQ, RCT) +JVT = (MSG, DBR) +NGD = (XBQ, PVS) +BMR = (MTF, BVM) +CSV = (XFJ, KMM) +SLH = (HKX, KMN) +JPM = (RPC, LJM) +QLG = (SQB, SHB) +QVC = (JVQ, MNC) +VGK = (RJM, BTM) +NDQ = (QKM, KGQ) +GCP = (RGQ, SKJ) +DLD = (CGX, LXG) +SFH = (NTP, VRJ) +CVH = (XFM, XBX) +RJC = (KGF, VFP) +VQG = (CBR, KBK) +CMX = (DFV, FDT) +RHH = (CVG, QFF) +RFR = (MKG, VVD) +HRJ = (KJM, RVG) +RBB = (NHX, MVK) +JXQ = (VDV, BNL) +PLB = (MLM, SMS) +HMV = (CGX, LXG) +RVB = (TKM, HSD) +XBQ = (MJM, KVX) +FBM = (MNC, JVQ) +XFD = (DCS, XQN) +TSH = (GTG, DVD) +GHG = (QGB, FLK) +LHP = (VSF, PKG) +RVV = (RGJ, QJK) +FKN = (KGJ, HCH) +LCQ = (CJH, FNX) +PNP = (LFK, HTB) +MCT = (JVT, PGM) +GFP = (XMD, QTS) +SNM = (BVB, PRL) +DRV = (HJK, RKF) +VKK = (JBC, MJG) +BTL = (PLB, PNB) +SSZ = (RKD, XVL) +XQN = (DTB, KHQ) +RSV = (HQV, NNP) +XNP = (GLJ, DBV) +BVB = (PPL, GRV) +QJG = (MGT, PKC) +TSJ = (RGC, CLB) +HPP = (LGJ, PTN) +LVD = (FXT, PBF) +DFR = (XFJ, KMM) +GNB = (RTN, HHK) +NKP = (RHX, QLG) +CQC = (MTD, JTS) +FRQ = (GVK, KSR) +GLV = (LVB, BLG) +MGT = (XFD, NMR) +JJG = (GXJ, JSF) +GJD = (LDF, SPB) +DBV = (BLN, BTC) +RXJ = (KKN, XNL) +NRC = (PJT, XDR) +SBA = (XVL, RKD) +LDF = (JTF, HFL) +KGX = (QNS, TMF) +QFF = (RVV, QRG) +HRF = (HKX, KMN) +JRG = (JFP, GFP) +SSF = (RLK, VGF) +QMM = (HDP, PVT) +PKV = (TLN, CVP) +XPG = (BGV, QCC) +JML = (CXR, TKS) +XKL = (MGV, RXV) +MXG = (DDN, RSN) +GLJ = (BTC, BLN) +NML = (RBG, PLF) +RQS = (CXF, JTJ) +KMM = (QHN, NRX) +NQN = (BPR, XTJ) +XNL = (PQF, VGK) +JJJ = (VVD, MKG) +CDG = (CNP, BXP) +PBX = (TPH, XNP) +XNS = (DCC, QMM) +RQH = (RDQ, GJN) +BLG = (HJV, RSF) +BTM = (RDN, HMS) +GRQ = (KBQ, JCB) +JHL = (MRQ, HMH) +DGQ = (MDD, DVL) +GGJ = (PKC, MGT) +QNS = (TXQ, LQR) +XFG = (CJH, FNX) +QMB = (VHL, NBP) +PPH = (GRD, XQG) +DVB = (PNB, PLB) +NXD = (NKP, GQH) +LDN = (BVM, MTF) +XBX = (SMX, PTR) +DGP = (KMK, FHK) +JJD = (GDQ, DSS) +CJP = (NMD, VKL) +CVG = (QRG, RVV) +QKM = (XKL, SCS) +HMS = (VGC, QXH) +CMB = (NNP, HQV) +GTB = (LBJ, HDD) +QKN = (VCX, FRC) +GML = (CML, SQT) +DVD = (DQF, SCF) +MLM = (NDR, PTT) +BNK = (LDX, MQN) +MQN = (BSD, LVF) +MPK = (THG, SVP) +DJN = (MLF, MQC) +SXC = (JMT, LNK) +MVP = (SRF, GRS) +CLM = (MGJ, LCH) +JVM = (BQT, KTX) +DCC = (HDP, PVT) +JFM = (TKV, GNF) +JSF = (JHM, LKQ) +CDN = (QKM, KGQ) +KQG = (XVF, SSJ) +CLH = (LNV, NNC) +KTX = (SCD, NXD) +HBX = (MPG, MRP) +JTG = (FVP, KFG) +RSF = (LKL, KVV) +MRQ = (FCT, CFN) +JSM = (KLV, NRC) +QLF = (PBX, KML) +MTD = (KRB, JPM) +RBG = (FRQ, LCF) +QTG = (RKQ, GVC) +NPL = (GSC, RRR) +XVL = (KTS, JNB) +PQL = (HHX, TSH) +CDH = (RMC, HST) +XSF = (JDV, NBF) +RKF = (GHG, QHD) +XMD = (DKM, CRQ) +RVQ = (DTM, ZZZ) +VHD = (CMX, JSR) +RTD = (HVC, FXX) +KFC = (PKV, DBJ) +NHG = (CFM, SFK) +JTS = (KRB, JPM) +BSM = (RSJ, PPH) +VBD = (PND, GPP) +TKS = (PKL, CHX) +TQZ = (NFH, PNL) +SML = (LNV, NNC) +HCK = (HRF, SLH) +PXC = (SQR, PLL) +JLG = (VKL, NMD) +SRV = (VLB, FMR) +PTT = (CTH, HVN) +PLL = (HNX, NML) +TKB = (HXB, LRN) +CXQ = (VLB, FMR) +NBP = (CXM, MGD) +HDP = (NMK, HKH) +LCF = (GVK, KSR) +DKH = (LFK, HTB) +LXG = (VGJ, VCP) +QRG = (RGJ, QJK) +KRB = (LJM, RPC) +JDV = (RBB, CNK) +PGX = (GNH, FQS) +DHV = (KQG, KLF) +QNL = (BQT, KTX) +XCP = (HNR, VXV) +JVQ = (HRJ, DBS) +QLD = (CPJ, VQG) +CLT = (BKV, NPQ) +QRM = (JQM, KCN) +RGP = (RQH, HXP) +PRL = (GRV, PPL) +KBS = (FKD, STV) +XXL = (NBF, JDV) +MML = (LNK, JMT) +VFH = (JRH, KCH) +PQF = (RJM, BTM) +JNB = (MQS, XRC) +VTC = (DXQ, DXS) +XCG = (RTN, RTN) +MGQ = (LNP, VNP) +BXQ = (CXF, JTJ) +JNH = (LNP, VNP) +BKM = (CMB, RSV) +PJX = (KGL, TQH) +SMG = (FVP, KFG) +LRN = (HLP, VBD) +XRC = (KSH, VXT) +MPG = (JPS, CGG) +XHV = (QCC, BGV) +KHM = (RRL, MCT) +RSB = (BNK, JTB) +PNB = (MLM, SMS) +XHK = (RGQ, RGQ) +NNP = (HXV, QBV) +GTC = (MPG, MRP) +LNK = (PNP, DKH) +FHJ = (TCF, MFR) +HJV = (KVV, LKL) +GFN = (XBC, GLQ) +JQP = (VHD, QFN) +CPJ = (CBR, KBK) +NMD = (DCM, DTS) +KML = (TPH, XNP) +CHR = (HNR, VXV) +JSQ = (MKL, TTS) +FQH = (DDB, DDB) +CNK = (MVK, NHX) +VCX = (BTL, DVB) +KHQ = (RGP, RJG) +BKG = (LSS, BJX) +KKR = (PXQ, VPP) +LKL = (DHF, PGX) +PJV = (SPV, LVJ) +SKJ = (GLV, BKZ) +TCF = (DHV, NSV) +DXK = (JRH, KCH) +DFV = (KQN, SJT) +KJN = (DJB, MXG) +BKV = (TSJ, JNL) +JQJ = (XFG, LCQ) +HTB = (XSM, SHM) +NPQ = (TSJ, JNL) +FXV = (LKR, CQL) +NDS = (HFF, VXH) +KFK = (BPN, QTG) +GTG = (DQF, SCF) +FSC = (QNS, TMF) diff --git a/2023/08-Haunted_Wasteland/second.hs b/2023/08-Haunted_Wasteland/second.hs new file mode 100644 index 0000000..656367a --- /dev/null +++ b/2023/08-Haunted_Wasteland/second.hs @@ -0,0 +1,76 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 6 + +data Direction = L | R deriving (Eq, Show) +type Branch = (String, String) +type Map = M.Map String Branch +data Input = Input [Direction] Map deriving Show + +type Parser = Parsec Void String + +parseDirection :: Parser Direction +parseDirection = char 'L' $> L + <|> char 'R' $> R + +parseNode :: Parser String +parseNode = some alphaNumChar + +parseBranch :: Parser Branch +parseBranch = (,) <$> (char '(' *> parseNode) + <*> (string ", " *> parseNode <* char ')') + +parseMapElt :: Parser (String, Branch) +parseMapElt = (,) <$> (parseNode <* string " = ") + <*> (parseBranch <* eol) + +parseInput' :: Parser Input +parseInput' = Input <$> some parseDirection <* eol <* eol + <*> (M.fromList <$> some parseMapElt <* eof) + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> error $ errorBundlePretty bundle + Right input' -> return input' + +compute :: Input -> Int +compute (Input directions m) = L.foldr (lcm . pathLength 0) 1 startingNodes + where + startingNodes = L.filter ((==) 'A' . last) $ M.keys m + pathLength :: Int -> String -> Int + pathLength i node | last node == 'Z' = i + | otherwise = pathLength (i+1) (nextOne node) + where + nextOne :: String -> String + nextOne = next . (m M.!) + next :: Branch -> String + next | directions L.!! (i `mod` l) == L = fst + | otherwise = snd + l = length directions + +main :: IO () +main = do + example <- parseInput "example2" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input + -- cgit v1.2.3