diff options
Diffstat (limited to 'day15')
| -rw-r--r-- | day15/input.txt | 100 | ||||
| -rw-r--r-- | day15/main.hs | 92 | ||||
| -rw-r--r-- | day15/simple.txt | 3 | ||||
| -rw-r--r-- | day15/test.txt | 10 |
4 files changed, 205 insertions, 0 deletions
diff --git a/day15/input.txt b/day15/input.txt new file mode 100644 index 0000000..484b9a4 --- /dev/null +++ b/day15/input.txt @@ -0,0 +1,100 @@ +9956978467598825771298981722484596335818889199959653868179249999625599695779356228986873188891687284 +2689689264298797391119983529199959929858717969159391918681149969777492315688758986884866649397344369 +7172588131466121589783888671998218118876859987982967195137181498916455889797182194619794894661629837 +1233915929951588187849869199557858368639699117699688284859878443929999216978195119999586994518395892 +9936995927995999181961898584664489968882718885899689991948779689429318576999239788488143592176591999 +4897812918593459844917171834839975629813379971269169715938988896273649199919822997859787183217266891 +3933479167694699988319796863899446989269729449353695242844661984577961677295376286699769399319179358 +8987971987557238146557624799143829841679714886637818814698722922629981272226771789888594293727111941 +9674793972799591469997914789999881914562866899896527271538614679686339678188599786718883888297884985 +3961546999429929697613295879446959999892529586841738538988955529791599788979945996552179737819798781 +8844499362795969617994798868899899967824718292987354124929799999999618888579375128149986291724818549 +6319846159183995575829928989855577928968687494197997676113642777249672499899922998489399689953482875 +9318687755659372657924997867798988249219919195777499949395644897994967496851972899172918985191986597 +1998599789837695923861376925899583587862947979985968841769887158695968694796847698692896798761999877 +5389282482999389799417698173893793899555831488784993293489986775988887249661449988932199149826678929 +8885947487894125927844118934698315379199888789929515426975914988499896859985997738397828665929167667 +6298126815327916531712852259122155187297979818671127395658129297993863829999995739149985894397989743 +1891818878562954593599769891715178798578198418759575992878686979669849659989376719878793751989873589 +7985499598548294965777989549188571469396129839958919965359993968917797946999895164825697975265318994 +8939965352883349869987249262938897838999248787325191338911189196687898923799292934597931568686612994 +7883898892974459457272249846188161917193149598787915749973585899456996887596471274789926636819983548 +2893991266649412992998149988584297828117178919999295117889696435789899766195171297784699292989289912 +1889714497629498271876915259919916877619271584853928872546293189869749972719666595921649989796592959 +7989499773979971784991185677884772123776243315312592283695855829888699449884842589715776989991789788 +7969795549486918991741685993996689683991966793692719315219418594972994877669188497657994424741182716 +9891947169875483798968286797952944449969337387522685989126929899999186138748689929857925548689799775 +9934896897676629969846778999787616627743482859289949899173264238945619889896999992469794974489738168 +9649159979125986881692895488749887858778122897977996878266986997989985581382219174136998186328958999 +5868691619999883889799358879965896559782969287865997969412992135731371297995484417789177978999385999 +4987897118498941972858679939188913296758597957999159988899986765499688389749658649972788771194622759 +1484677635957996929559394997115194644415987837679917276568956717892651758726847486766995239622121618 +9989825558961948591989389179598799512428197998473996198491319844117397786299159926869928984999524599 +9917489296996997892917815829949821398462883759798899955315774553399987927967851318618379995454697825 +9899299512998939797198987378498237991935772689793749139688253135773898648876616593117848746989718389 +9997972916561279591989268558868997998782877967294893997282835818298696664999271999816281912219699946 +6799984995998883892269931298291819919852918918797134688842882966259814991647587815893276276818959675 +2871799844997986881319989698985799523755429889896999957822163591959924968239999854149897942628668477 +1995516921867788958199262639437657998684938999998937819965919589587365113799977817192699734182899375 +5911698839287819813698283389479956621591539915445638599938928889889999987592185459259842276386718359 +6988184995767228398797357898988136259292456271151782749739585392874599153488799986677756154921998775 +5889929568199528716917269697939589839936697973974687392391998983885167197295577686933487169797662969 +3576282138549491591775319176995538717999696588956995986695547613191839999512898715915936144392561948 +5329291717962161983227685489686918845996485997797396429999778881967959896987173997982847473369768897 +9164877781748889899469935799585918943989878977762998481869615689939727996997779688475748199844328798 +7991798237196899759673953382693927758496873888976788729351868197693796999369249969791967491137567799 +9991695968149396561848295799981998693141199398256927816469955854719769376962761743394948485552314828 +7186982892991599596272997398958488711982959664528917897576966858736399542649887128419993918518649589 +8999989998887485976988528481447878238888715919917699589959417318968677596299273377619723799734898143 +5169759894554293926482859352168158938898158397815319411261867193588842668867949888992986989912694675 +8427473979159967517766496846922999759861788196891899348748453495589395979484411832439745788998684749 +8979884898599659995653699764474992169918891845926589298187821985789331496992892739877557699399978889 +4117135275897846694979693356776419864316434198781749699399367328249826173831856819118872599887929117 +9879692658499978199599958786823949284997756118947995691794672327135471866488699919688193434735639585 +5691984588698969477979699978918969898918843129191794615781694841492886319696159938666583888649697795 +7189792431819239183896995186829891998578999466945599954117398899964997997971389145796939891639759499 +9969315998289288839685999879984999391938198897279438593919898811199693927729161249553274797871579955 +1397679395879587899999669189986964964999618829967419381999986859319416977398958959718958929978957382 +6894969894281478382719899781799987581557999826119214189196671986242299959884989979649529422543719967 +5981739475817947337868896926557129487952934635768334175511729813799968872337293512818311266539869789 +5859971281996158947896999985565894597181699999239559563991657519998757442189829991395937666836311593 +9968994867989926199441198198936757993274471923418981999389838988468878984888673962722692615494994916 +3412989194698818488388395996795357868465884171614913988853947119968999199694989575882882897788754196 +4767793319914896979199935929955397569993689616359493297947517199829987968826779949998365977814959924 +2579972398289957987898849924347928451689465791831947348756986989948598821793892916666725547789741299 +9698989769676955862992919199339895299629837998423697491249883483599482292954759887829993292627872191 +1894619155917969889918757658925899599689781921899269989427239978652658489188493949679618396136949299 +7712943759193929987161997175874316616112999266279789989697738811792676856992288912397788157897879898 +7891199595911898419259681615768959188518795943876188369392846121938555699336786418329929798119869899 +2796935459996838899793711969696999482299355989299989966798699899578998998995999694942878296779957749 +4719483381989998499982591777895592799878676851889999639599194219135897985978325759838972952973185948 +8965912619221745652577826328989598641499946592178869488499927162899585757385941597967851868197894763 +8968695392792679597328229296399468238915291348856156176658189554419981971975789178898588648216792946 +3694899896814879119881449917673689939386629993879189938479899217774991999917899821137417799198637637 +5645661179381989929244868899917199387518895199571843654858799839999745993352769499895481849381896897 +9651497219912776328185181986618747416337918889734673282681872989791999949935713999993969339279198953 +4314949398895886943322397517587556441759979499928122411997918368816918184399881141261381347876568616 +5187293161286489982862974561982928899978837649549913847496156789731291181557888959476992992881482582 +9317992939383168491917991759264246565676891875962999958999757698623183898357397767392891287912962868 +1799982437869993916939953411873913995541879869793889572866919896412765623887865749378966915413927898 +9519787945431432316313866197973328267939581218979649989439384224999472881299732999597352772753791368 +9288483569399269795915929419419136973331899194387846645998973819199773878634519282999223793324966229 +6755829165937992937993893768199949761128166811959979779699129626188827215694641186878869191698651191 +9799359993719926899876838991998368937197882188149191968977826896378899978686199548658893562678998579 +3897958689718149561892985516687895789198398548689645643884695999999847494283968756796765389139599839 +5818578147898416913367195515611597885861963578883578997187918599287756577474396983356312967793128892 +9999892769284995919972819835547962786736828152819184951161662279799894817599791878181753149877894881 +8299976964465999287197581918879685397888356594792988199697982765599427566287823683431351869995623962 +8989496693957987663678978593593738931986779777991313898594961994695949896798884139938616151819966565 +6898258912998949478473966768888494482448481939998236784669299799997816791891267967195319818818979489 +7768427926996979688996299284916648789185799693838939518998993658998919289198619735288918586275797617 +9877886949939119114117598819669599875829575673498688598163398885845347726982589975482198997862547995 +5597689771938983973982619291188793285821886981895899191372797519999399581692538649838931291961891287 +8577194549714988975998688698899479153995216852979764837138991671792834878995969442481912618443911927 +9586172919854431896891871994969319226453687499979851699789283289898959899239286739579255644212647999 +3966599598558974987689898899966735148191945177788188358719588958287189491299792478998288954884975941 +9857984259191773999893262946889397892366998191262597118924895918951469846746979119989112768998759988 +9487493194185853443118348557381979199114998581958626984133689529217198991359988198776267891998985428 +7253864979196694796646966283794927398942982897999588293398762766965949771799885768956895355878512657 +7939941892849576866851816855958734169789934758298874844919928289119988823599357892155959839679679918 +8195996699568965579198729534577878698778991795617454587967117967862889252256796526887997997398959165 diff --git a/day15/main.hs b/day15/main.hs new file mode 100644 index 0000000..cff4233 --- /dev/null +++ b/day15/main.hs @@ -0,0 +1,92 @@ +module Main where + +import Control.Monad (foldM) +import Data.Bifunctor (bimap, first, second) +import Data.Char (digitToInt) +import Data.Function (on) +import qualified Data.List as L +import Data.Map.Strict (Map, (!)) +import qualified Data.Map.Strict as M +import Data.PQueue.Prio.Min (MinPQueue) +import qualified Data.PQueue.Prio.Min as PQ +import Debug.Trace (traceShow, traceShowId) +import Utils + +type Point = (Int, Int) + +type Dim = (Int, Int) + +type WMap = Map Point Int + +type TMap = Map Point Int + +update :: WMap -> TMap -> MinPQueue Int Point -> Point -> Point -> (TMap, MinPQueue Int Point) +update wmap tmap unvisitedPQ source target = + let w = wmap ! target + oldT = tmap ! target + newT = tmap ! source + w + in if newT < oldT + then (M.insert target (min oldT newT) tmap, PQ.insert newT target unvisitedPQ) + else (tmap, unvisitedPQ) + +getNeighbors :: WMap -> Point -> [Point] +getNeighbors wmap p@(x, y) = + [(1, 0), (0, 1), (-1, 0), (0, -1)] + $> map (bimap (x +) (y +)) + .> filter (`M.member` wmap) + +recurse :: Point -> WMap -> TMap -> MinPQueue Int Point -> Int +recurse goal wmap tmap unvisitedPQ + | null unvisitedPQ = tmap ! goal + | otherwise = + let ((currentT, current), unvisitedPQ') = PQ.deleteFindMin unvisitedPQ + + -- if currentT == tmap ! current + unvisitedNeighbors = getNeighbors wmap current + (tmap', unvisitedPQ'') = + L.foldl' (\(tm_, pq_) nb -> update wmap tm_ pq_ current nb) (tmap, unvisitedPQ') unvisitedNeighbors + in if currentT > tmap ! current + then recurse goal wmap tmap unvisitedPQ' + else recurse goal wmap tmap' unvisitedPQ'' + +dijkstra :: Point -> WMap -> Point -> Int +dijkstra goal costs start = + let initTMap = M.mapWithKey (\_ _ -> maxBound :: Int) costs $> M.adjust (const 0) start + initUnvisited = PQ.fromList [(0, start)] + in recurse goal costs initTMap initUnvisited + +e1 chart (xSize, ySize) = + let start = (0, 0) + goal = (xSize - 1, ySize - 1) + in dijkstra goal chart start + +e2 chart (xSize, ySize) = + let start = (0, 0) + goal = (5 * xSize - 1, 5 * ySize - 1) + chunks = [(cx, cy) | cx <- [0 .. 4], cy <- [0 .. 4]] + chart' = + chunks + $> foldr + ( \(cx, cy) acc -> + M.foldrWithKey + ( \(x, y) v -> + M.insert (x + cx * xSize, y + cy * ySize) ((v + cx + cy - 1) `mod` 9 + 1) + ) + acc + chart + ) + M.empty + in dijkstra goal chart' start + +main :: IO () +main = + do + contents <- getContents + + let input = contents $> lines .> map (map digitToInt) + let dim@(xSize, ySize) = (length $ head input, length input) + let coords = [(x, y) | y <- [0 .. ySize - 1], x <- [0 .. xSize - 1]] + let chart = zip coords (concat input) $> M.fromList + + e1 chart dim $> print + e2 chart dim $> print diff --git a/day15/simple.txt b/day15/simple.txt new file mode 100644 index 0000000..dfdc2b9 --- /dev/null +++ b/day15/simple.txt @@ -0,0 +1,3 @@ +123 +123 +123 diff --git a/day15/test.txt b/day15/test.txt new file mode 100644 index 0000000..ab80887 --- /dev/null +++ b/day15/test.txt @@ -0,0 +1,10 @@ +1163751742 +1381373672 +2136511328 +3694931569 +7463417111 +1319128137 +1359912421 +3125421639 +1293138521 +2311944581 |