2023-17 part 1 in haskell

3 files changed, 262 insertions, 0 deletions

diff --git a/2023/17-Clumsy_Crucible/example b/2023/17-Clumsy_Crucible/example
new file mode 100644
index 0000000..f400d6e
--- /dev/null
+++ b/2023/17-Clumsy_Crucible/example
@@ -0,0 +1,13 @@
+2413432311323
+3215453535623
+3255245654254
+3446585845452
+4546657867536
+1438598798454
+4457876987766
+3637877979653
+4654967986887
+4564679986453
+1224686865563
+2546548887735
+4322674655533
diff --git a/2023/17-Clumsy_Crucible/first.hs b/2023/17-Clumsy_Crucible/first.hs
new file mode 100644
index 0000000..aa5c6d9
--- /dev/null
+++ b/2023/17-Clumsy_Crucible/first.hs
@@ -0,0 +1,108 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import           Control.Applicative.Permutations
+import           Control.Monad                    (void, when)
+import qualified Data.Char                        as C
+import           Data.Either
+import           Data.Functor
+import qualified Data.Heap                        as H
+import qualified Data.List                        as L
+import qualified Data.Map                         as M
+import           Data.Maybe
+import qualified Data.Set                         as S
+import qualified Data.Vector                      as V
+import qualified Data.Vector.Unboxed              as VU
+import           Data.Void                        (Void)
+import           Text.Megaparsec
+import           Text.Megaparsec.Char
+
+import           Debug.Trace
+
+exampleExpectedOutput = 102
+
+type Line = VU.Vector Int
+type Input = V.Vector Line
+
+type Parser = Parsec Void String
+
+parseLine :: Parser Line
+parseLine = do
+  line <- some (C.digitToInt <$> digitChar) <* eol
+  return $ VU.generate (length line) (line !!)
+
+parseInput' :: Parser Input
+parseInput' = do
+  line <- some parseLine <* eof
+  return $ V.generate (length line) (line !!)
+
+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'
+
+data Heading = NS | EW deriving (Eq, Show)
+data Position = Position Int Int Int Heading deriving (Show) -- cost x y heading
+instance Ord Position where
+  compare (Position c1 _ _ _) (Position c2 _ _ _) = c1 `compare` c2
+instance Eq Position where
+  (Position c1 _ _ _) == (Position c2 _ _ _) = c1 == c2
+type Candidates = H.MinHeap Position
+type CostsState = M.Map (Int,Int) (Int, Int) -- (x, y) (NSCost, EWCost)
+
+step :: Input -> CostsState -> Position -> [Position]
+step input costs (Position cost x y h) = L.concat [next 1 1 0, next (-1) (-1) 0]
+  where
+    next :: Int -> Int -> Int -> [Position] -- diff increment costchange
+    next 4 _ _ = []
+    next (-4) _ _ = []
+    next d i costChange = case heatLoss of
+      Just hl -> if improvement hl then (Position (cost + costChange + hl) x' y' h') : next (d+i) i (costChange + hl)
+                                   else next (d+i) i (costChange + hl)
+      Nothing -> []
+      where
+        h' | h == NS = EW
+           | otherwise = NS
+        x' | h' == NS = x
+           | otherwise = x + d
+        y' | h' == NS = y + d
+           | otherwise = y
+        improvement :: Int -> Bool
+        improvement hl = case M.lookup (x', y') costs of
+          Just (h1, h2) -> case h' of
+            NS -> cost + hl < h1
+            EW -> cost + hl < h2
+          Nothing -> undefined -- should not happen, we catch out of bound when looking for heatLoss
+        heatLoss :: Maybe Int
+        heatLoss = case input V.!? y' of
+          Just line -> line VU.!? x'
+          Nothing   -> Nothing
+
+compute :: Input -> Int
+compute input = compute' startingCosts startingCandidates
+  where
+    compute' :: CostsState -> Candidates -> Int
+    compute' costs candidates | x == size - 1 && y == size - 1 = cost
+                              | improvement = compute' costs' (H.union candidates' (H.fromList $ step input costs position))
+                              | otherwise = compute' costs candidates'
+      where
+        candidates' = H.drop 1 candidates
+        costs' = M.insert (x, y) (if h == NS then (cost, snd state) else (fst state, cost)) costs
+        improvement | h == NS = cost < fst state
+                    | otherwise = cost < snd state
+        position@(Position cost x y h) = head $ H.take 1 candidates
+        state = costs M.! (x, y)
+    infinity = maxBound :: Int
+    startingCandidates = H.fromList [Position 0 0 0 h|h <- [NS, EW]] :: Candidates
+    startingCosts = M.fromList [((x, y), (infinity, infinity))|x<-[0..size], y<-[0..size]]
+    size = V.length input
+
+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/17-Clumsy_Crucible/input b/2023/17-Clumsy_Crucible/input
new file mode 100644
index 0000000..ec67fbd
--- /dev/null
+++ b/2023/17-Clumsy_Crucible/input
@@ -0,0 +1,141 @@
+333213136361262336321612214531777457112145343436646554277834586842636477377358665483232322865545123271135255712112742775561145666154365233356
+625436214642112116663631316165754345156613447614784645884723775385422237785533457846422687888517441575665644164125345724771731422533345336535
+135464262413363523172353673663343124614327663325483447348582478365458326464522365884857228745883344645545337271265517463212456153534241544452
+463341164253235233654257664712176156221273446338438725387868466637872246443458373458772474446735864427171225417624722447465614145334226531133
+612123231364647651775663426212224226114337776577776736788424832776656343782563357835523563646643373362516426762263641757743221457544513132115
+554121446241214313746711736452662635625733462823288665545675563668763743787742653833765545345747825838821335355445434347415641445636564324243
+224451135242133732146576324716743753368865727642288276285674826268356773857358774272262757346428753268886423252537566456457145362241413235356
+312115633663242411233636615741633726487283228864835444425576777233878745223464452866553565685646725656653473162633463643521135773411433452466
+542364224173757771326524416535552277757354762743288837354468764353627364676267546484532727724264832675772357663444464333544311464653635434155
+644453415415675332722151756256718248247685882878285324462473375646475283722538546752748236463677656374757244824312452134314757122175246666133
+553335516731473766365715331215568572352758878273527332573426865584372534367686638785426548725847452264452655432363227522743746771746731616324
+133445474224722676227554462116647666753275526734788533873228633423522662378822462553685245662683348523576827224635133441463776656147576542321
+262263545476415133716375434754684868667682745356337755425335477366862483227738582326352468542752785886234837282845863613725264761734336443244
+114557561615633115446342258245858844385456266756554434328822765476533686573637497788623453646223225852468238675466763313713633227154741356245
+611315162633241542646131578684535533767564585652735786467776834489896877967363837453335767245825426445885342673428236331451157547442775237312
+362261614652576557153353266488324456657568285858237439538887578466544663574533349347999664436466843472663827648852522875316714732344324217372
+154236775775512321522263368636678482445745255477872966786867669355994753645973978496654594795457367226453428858886655252654623377164654233436
+462622424671674313226637785458826766472883676833993634453836356375787779937773696649358983467446647337585265887587723374463642735172144752645
+256461325176535257663462355464575334764872223438763949469848778946443559566434444799354636443886736785674266463345527548557615613664272723332
+624227517633531434243827827654636862345763525366656758486948446474677985365493464466378853868458497378656656647884675348243277163765174172612
+642426252112436471458742474775766555755482666556764666989755347483839876866543593833948554547649543695673778734785343556567234476436622452236
+472761551511731356577488843522288387648575847749585654676577859987674545338478446453935695888655834749368252388424646347784477427672675234731
+747257136413274266658434523648663224583865945533979664865739647394863547663534658684836947849398659354975525423267856334772333414472751271125
+574343547662773544664738635233783383586446637996489896655677988659366366569546668595949965836367778345574626644234463758638787822267745754521
+367475241771674622685256576755377256694657754777544899383684634438534485979934747656784795398385666575337783432384738285554737675522715746365
+256367447543715652882652564564844549667487979647384545688783886347534748746799385454464568597377867697868876544676868477782387732724561552121
+261235663177628353884845384445766258763957538398695337944456734653958794684775489984866453396736953989445799737336434633265843536845722326147
+431276435456537534853737352526378373785887936397348334479754963636988696675746463374338676858375353484947593688636237753457284385777117617624
+421367347552372223365324757658483977886994994547997755837953398686686495795587856558739768889585363493453579446427556683583574426622272442257
+653441321737655477657783556762464689667939878673459467647756948694579899586649949485693964996883964648379558954548747354857488783362127442566
+515161447757685543432764636463458639776554884767986333854576485676459546765778469857646486376565785857443977735796532864253257624473821333334
+336171521157845857727533754249765675378444363369739966487567564657564788675786859867955577864736596843659475696378544727675554642784241753632
+623372113877373226883677764958453497559443687766594489754655444467966644745947494698459586785645959777965677437493446724843825534677422225442
+236731618585276273353786287559939845985699963868795668657679996977589756994768598496447448576699786446978776785836952358253352634682675575162
+765546725582536686487447374798889846794833537458484957646996958598746684878684958848884578574656384796834539634597853385236344482474876472666
+235141347247436634846668336949436933994444973649584458877948958567497986597747594579955455786945889674656448794468553656367688688576238422422
+671623678362665454588528544384845379775883686557595448549476796988894494486867784996978797854689456778495488399676989768386537635625688831242
+514567273474547255558849794485665888753549445498649654858986448467857554544489744945685865544486656543767539535947995573778388352332288357236
+421323835776877754277637737948643468887899675798595548644885557689854854755598964995897678954896674945488794549443555993763265444882527744633
+354668742484843385355475877734984796958775599649956999999868487764495968495996998799544585565676488647789369959545359597757558327676228242324
+223675455323285573553448797956956995447989558679767596794986699975765799696477454587975754758775874888765498885699494634477672743525548872573
+476176284827585535382536674788367479838589886659789789675958497767575745594699578578798877588865566954496744386339878768748227448658776552362
+675625837477642733439383847993547559885769745955958866975847899547878879759976747796969499588689558956864465635487346833935452386378264867816
+472576623464266256473345754344444687595755546988945978967684649897557995775998977845644887549855889776779634755544666998999672672342225572236
+723338425874676478785895383956556476546955695985859465659544888989996856667888856697795988445756499858565899394779558798674387882836464633723
+753728823447466882883747584457899843886998789895745784456685775586887577578765568686646979944897697865577785359537559569439878872222674682675
+274684763532572374694739777585794889467744468465856969675999788859799587656669956766879888694794447678648759598739793358559772824233728356645
+115256466578823832558738735747633445985469799749547867559586775788896687689676778758799785564977797499978848453988848336553978432627386327573
+548252468286265749598354987757696464686857494949578959857786799756957966686965775569557987846877876965964586958467884766384759555228862634247
+775472876326246686637894874745853649677794865574684765688797569775786779676665589897676756784645888896665785543377644867338379482443888857873
+644246825637683644835877767347453454568867554444775599777767668577979986777676558668678688677679776689769699579869596396588947647254276727432
+675667637753876445999597848375487698587994465886656589877797669767788999875799765675659757957578557549945978889843335993675545354636824673588
+453657476346684869637675496555556899746757988568488977766655889967896758557996798965985989857698968976595894997539483568475599986552355853787
+632248555553887766398487683844487988644864579699765575897969566597999875796789796868695775556589856859985497684784986459989377837883752727386
+266885253575644787699874544547358568447586577656878599657789988877699865956869569876989796775779644456759775589884987483797956747657856577762
+723737537288886965937656574853968596447486789966589956855986786958985788878986767699969598779956745799646979669779964733354855388722376852482
+443568274582252776976439948936677979955468588859687866879589988898686988555665587768558588765557864897448688757653998979337985377854464534445
+447864347254476796783339876544897778998589886776989758966555866986869698869987597675579987966765886976856455866796939445755784944224278247282
+286764482526429646636893847639887457964499865677657686675598857859797898986769757875786568567875884684897845464566539854353669377286744552562
+884623287654836563345579989899869797774668448589998785767869696687897686898796989867595959779585698588455599575769555743843637455423642847562
+473473534468357576875845833637898889894456886876658898586788889999978988998996766667995685987759868969954665459945743358543335675522322378342
+558656456533693883798863894469449475765876655569858666587798989687787787989969897758776576759555957456874769876788793436438855695738227383863
+775323532357798584683386967869946765585998787866977987768899897967977677787668867979997875686697856578774577566474536533944646986828353322626
+636525836872783447833786838746487985757947559969566995787998789678697887868999886776987796867865978774949956548865588585333454467763683243723
+223783768826293857378738893588985777747665455658759689799898778786898798968769968866675997995587875974646549667698977489885365856652626534534
+655668564837447467734565736667964785484656976967858568999686677669768867778699977967988896858859975554449795969546794984867597638648248862288
+225343788236467744769383578758544899859678585565557767667976969786769668786977967696677777767879769879599956585486565669653579739367484637542
+835548267463785585868885946675784945686995679868879868987996776666887886779978868697689999897889796585884675744998754566869986454554226637285
+524428887552843774745688555798844499576574787766799978865898668987896987898688678969787697657777676868954858888788978685799658846625432887244
+763757348466458486656985748946874858799455676675987865666678777698899997898866986677866879785687579874469459574889673643598465975777433358366
+558623257663757383557737659894456765449758668885695585688999896679878866779769888776767959786989978696448594745469878439358857637358376632635
+528622755875457489733889333676448449454678675689757776677677989696976997989988998776976656885665797787967855898746764557993438689586832535665
+262728464482859769395553766495674944869965999668566886969668676777777997768868787977768658859995696654799457798859898374396568466488756437887
+487364277357887467848976636677547566648654786665587569798866998968969679896669978778669565988899885979674848554559648349968485933658775276677
+256557832538447785573836549555759676868974976586768988799986797966866968688667679787685978567778888955456854966856893685889888958764585648486
+855327664424565667757758383684697655957747577978978775569899977977699667776898969778876576599586557597548664594777895375789973774584645288543
+732845238734368499538864859548756666479886668687697768598879889678988699668687669688977859865889687898469679897598943336499683959942888535428
+458542434722763964465544385478485684455675996566988868659799887966987786679967897869965595997757965798487494979485589377554593895588267246482
+685847653777387636587598637367844947984698996755976878779587879698766699987897976799568875579798897684584584986654768893364665848656732765345
+762585858463375454454757776765559455786986498756689585998968787967679696669978887887688575658778696897888854989458553333897338689655835452286
+667873648672677658987454838677545846469568967886596768986598796689987767768689666768986658987869955676568588688768453475384649894476834537652
+842528743554868476638843667989678696874765796896959858759975698996797697976896867888777589667795556658457584544444987934878388869422286538442
+665343556563653997694469347978779548957944896859765588765596979887999677667789969589887866968899686678674894597485654658977459957726383878528
+328824677886664984396688493979448944877675767875999859577958979976669668997796865999595779786956688644899745994747993439474788339373534756228
+355756624245748345976656569348866554494757766868566879567996775777969987877698797776568579757957884846984866766974746746679776886436337862352
+355757567353465353488558943489856995554566447865897697675796898598867787679676599676998886658795658757497445698747499484766988999524476665632
+846657543354688449334738753488965977658866855499795568898766969857755689976595969566968775778979897599779888747778646949389737938563864722776
+222542436248338757373365596953577857876777785799965997596579779865977868956968975778576689656575877994977994789888957578689985758278542255648
+826824626578323678956737348575645548667794498456877779558696685766765996577578587987677557956655865887766685575597559586696339864465556545445
+672427854774774447537349755387458787447985567486958868665967999968578888699789679579765855665666979559547795958783794639459777774442844848878
+452738222778884766739495654588679795558448477676597569955979565868955588879678799665558655888789467848675579858647645878346849574448882222864
+758576763255686269387767336544539998768579756648557995595656978897967599569788776975596788679985698969567697489998968793955383784544678786632
+678436753644435345347447966785579845484646744646487695989759998868659588985955685776856855858876655597799764746838845569653937223437636586333
+153356642488363235694785688879876855588546969589468567687885587869879886789976696579686967894679667978785876977786753437476588524434273755854
+317882332358268727633385869964735386459785875794857867997665676899967595976585567676855598555645898564749684567698568497736368755887663276756
+553352323553345584655944375958334686544568859455468796685877879698899655875768559585886794875996949678754578849953483443664676458224858845353
+226242868452584232838385446446584795649549968885595968669559887868595888787986597867775869477996957548958997745474643897437962535233473847335
+763437726764765464384839593494346588548966488976888467686695997587595769966888579976969574885694897878495979536355474365933684556223554783653
+334278427343676884873643567798477894397499659898464896868445778678559678867597585695856677759484646474967738743563443894378377283723754866354
+364424658235542285759346854636443367549844976595677469978794477788586986958755885599989755694446697474644964964983966865983577367685328757466
+455622346675434466627968485848334339354654996796977484977857577887756998698686754756945458949654447788745764956687878957977434537343783638652
+414184424528876752586855777635698734866576769557959785596469664746649494559498845858666498789995498898658847578497464938567723887863346627657
+222772455675785688574998639973555974944766976784479574958877596999849664659945847467647789846894574575635438985969979554995728363778854553125
+677628437436684347656498938477378693894696449576775986548874779449786764447597479766688898875689864965776667499493345574866436336567337437624
+727144464542867245566869335935377934486434974797786595457564598959848687776647496647465959978878559954334348436574447499645564648783242651735
+674465558434274722483688736769576358375786454868584589888544764896746786474855594477756874777796878944535948989854563367676767484465444776326
+726533354666455265533323549584966633794448865544599665579849559497987549997649674549948764954685654349464854738689883675423622887538654821713
+535573223637762777632285839887974778679897479369667476556956869879497768758647674887896647544666687975893857695458543723255688642672675862221
+255535736242852283868554325347575397384336774436484858866587586755899486587655454967555665966975663696979486933568746833678573262445584616646
+214572456854867737354845558369476949957347579668976958674554696576744766648687859866476774777643597768347583663398885752627665835224846512477
+371732321862355823583888685844948884786873347664969678964485466654478449789884489776849689977577875398656486579666646252236884842427525351222
+755452776637557847683266785359855837945944434565975844659787695696599787667855996799896894795583563369965993837535988483426388337385551317346
+624247422144477474527542264625377545399353835655777686676558457988798589686775496667468777664876676594688543354784668676457344367483543224435
+726747757662436335676345653676447795979833784595875464445795867894945684668894664784796997383764953754343447734898852834456338785274333454615
+656524125146784236674758852648558449357375838974493447769796646554486847575545464888994338434735849538353478789986482347532782254363661472563
+741673514746232538637764537446675846398449657483463375339458595884669445554943846844543788465649464966859863755825887888234583773257611734354
+115447175112756867445654567638362867738959786833688557394833846766836963768548698489347967855973377359398374424534763322552454276872625532313
+646447735554116277864467783735634526644379536385485867549646689936365936747569865533745486769389548684434696386454368652483866265564264175517
+156357554736777347244836373377643868656397864867543567474734466399984876557668389778368878535399696963467657336387568483474722445664715556671
+676531166544312447583457363455235228663973454388438947673946746397554543958554839695589977738346656754557864443875267837373884832321325454352
+375454737124536248825826374335662725588486787449847987633835885576444673594585963544539687578738858696895377838727858622246743261771513171412
+663221374752176732356433254854467623222337544745757575986873573348797879683544358747747883345378444998345746855624868354582726326427315146522
+372672327573647444768323574353783836558756863845757974999357964793355369499865757489588866744979345496744543385375627278633243325452754777727
+274411174533334575377634754324275384762783855996735464353753454977454863488377875438734385846633365787658277884763677557882653763245234776223
+146347645243261273336652374224464433425686378576955887786883747389484868679879937578846538888495848456473877527237835533565641525351147615326
+141327513341666141456432262572624453542782332474487533834446535778573599686333378976786438944868387632546466422733238663662467436527227326373
+452334645227737122357346433753223664266624686726288755858638875989736854855937375897383455453552262745532864542645456757322527154263366545246
+564567126412756234244374586823572827374582865645538367879397839863933576769579345934496455586668763835224477367878667425336151337125473517231
+522573127256225475151321676282788662828282654287378334654664485457379835977568695853846443237655738445627723762862432252247713467242214222715
+115232137775553663237162765368267344427487347824665373483627845573784686839985736626727684228876547543784372385582862455642317132377274374326
+614413156371526427352242352155873282328737854473556666586484765738353332376774777335743758274258857326568365427873811553131613135216564354355
+253143425547637746352146673345427633575267732435583484844824334674266868882434835445546486887675482737678485652343545677362731672733355235426
+135416521244316712675247627473738882768645567522443286388764423448534575553633387378644626683283266657388887325266535244771737424147617432243
+224264636446232647421555321542226827527468366836655546266327524662542748584562245765823264636467576284785684627137242762421431155713541156551
+125223515312471412437476611237727888843547672522485265335266476756823553686844257655425377577535653447587823487447715644722565471412322644515
+466226253356466742613422245771772648283625753376568357583424862627265425238836236538423663853668245256256886743613661555715336473155535446153
+156113463546647546677356722765372325222684267767736523785588826535245724585442626474425786735443647537842265534261737657677635756761552664461
+413165222554534642614256513354313511531447235383325856686642346288744536764733824582786672755644735786636555447622131315536651514411612546144
+122656344636144672343462327767372421575444642365688282487355348223472385562684363233663426485262384645652447136253111261762331217515423142461
+625544236663123525632771524343756333375737354285885448862737335573726334374686245844372776387666268514551657774225657652271651412245212411451
+423126354124653331672162233413635177574771624528322686824883233468774665567775866376682464873886553453552265645627675251266551441231365256263