diff options
Diffstat (limited to '2023/17-Clumsy_Crucible')
| -rw-r--r-- | 2023/17-Clumsy_Crucible/example | 13 | ||||
| -rw-r--r-- | 2023/17-Clumsy_Crucible/first.hs | 108 | ||||
| -rw-r--r-- | 2023/17-Clumsy_Crucible/input | 141 |
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 |