Today’s was the toughest yet for me, but after some hours spent at both ends of the candle and some helpful hints from the Clojurians Slack, I’ve finally made it.

(ns aoc.2021.day.15
  (:require [hyperfiddle.rcf :as rcf]
            [clojure.string :as str]
            [clojure.data.priority-map :as pm]))

(rcf/enable!)

Day 15 is another grid question: given a grid of “risks,” we need to find the path-of-least-risk from the top left corner to the bottom right. Diagonal moves are not allowed.

(def t-input "1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581")

(def input "6899398559981949547258793854297238998777719749798917159796618899687398467399925379577862587989991474\n5379942478988734273122988989385757497466236693289192366951834829459291799682979611288519663692596298\n8798287597929689897189697998519899536166814996869871877395181888988947899479999184396264959716187851\n3868296316264598486169599954488593277989992991991613957171593837586927879692269999584919299198529729\n7719999887667929137997159819697988999199983984946983118579886899976279796963391897163981988846896135\n6739998189663927629889269938986791869444999919267994997136897877889835991768187898799499829977988394\n7988583788649299829879981514848137294864722989699668788896499791829699377999859897635314659966261481\n9992969672797892589791491158982982492585889799536977249441763249875986327169556286251698984997749818\n9718374758574848624698919991181836656698967894599118493858464975792129225978588996976237797737894195\n1893825969777924969931987857946995882974888995731816998669193676749873968799711398866998177979689789\n3759795779766278838519949548487968384748596657715448479999877448999698477273113999976952939797999137\n3792869878699914632622973899759161375991948988793488366996769987961995611928393687767993719868399894\n9942897968869298678989516879984599626794899598717691899918359372779984892421689984859112959924689472\n8986974958287449242678124196999969497867859938139817219596259977917899879991996999997235251449992892\n9393932589987693287868871994537751739997998929291989863497289983976779984189929239897861797119974696\n7644877627835923851699265145919979549787871681487584964459776917939961517883677942691588595752298597\n7782917899979456965627993989999875893695969689956787938699999771786696989657496171872249318863992988\n9699939979999999188268818579888611984999383488981128852596652999813388975989998987488198974791621986\n8855949448389977757762785216898414926767698918989963979758999245519788976559869884922771769995695998\n6161594972855728799875239948997799599786498788998987839599389797799699385379996998569798848273881991\n8849879987995512895983617913392719961983866984975773748976999998979597796629879852188317626397354577\n9918714945968972949991887946698488358199888699313826499427999686399169695899988919319799999767473199\n5996524691383767631868413993879879289397729799167798829749158289796475719355781941897988959185871995\n3671548863949999867599962616976992189997857965187417679377989897595864996189959688921869297998639168\n9899888869899457597989991627522994397189991995699897597826952691878696997929893652899411896967929714\n7998712697173966917539799489999488829998991615298985594968978829817799698218888399495847464799892896\n8697591999289894676979499959726714169871796989826898599626691781699518598585758896419999659969796999\n1596769779967498689759885927995189958876981979299351276266375179877391588176879938818569815468999951\n9239936979789997972953675459579557995999399997824798899789819389488399998279899482891999869979466297\n9862961336489166685698953899736173894695919998296115528189181614387928771489629999856145935996999959\n9878796372687498958875478489799487856191971776591798688447913949795879947797267695974595998335766237\n3579669986295599447968388999854657533645686894697829945854677988979973948297959175943579195981329558\n9889879471197697996865286985852894979699196587598788896498174998988231138617198319985699429879936198\n2569929999497772861549279955599759948256671345237589589916773999815195699395998996819598789979214958\n2299796872747192635975872966984397912981917297947877844498981195646966824799588896388875584894887662\n8897985828526798389979415947284977849996919989826911954671364488599884946996369936998912399219399559\n9789869867396839999794988798381369977895979797377699897983873649969879997516315989217888649641593354\n9396559295496899449797995999149878148992991887655578998575948899928139657986829949982988388718488968\n1219872929688491168976392574875837678818865159629598999856821431859496974969997779589959997389869911\n8677996932758699491567769569979887967994199496193284699937779232863993395713788876689947666888699642\n6895859796959369982468161218818996999219995982889899867816999154828893696797787199799192984141799892\n9724999698987799578316156912172451755981187297873997274399973799915981163774282986481193967782445747\n6629975198595889624662945178181299389597998895999894925874697799194599458641859689691891729993275966\n9937388695852751794123981948862993181157883278997199253248199592694498999728968898493199131992897875\n8138652793591618786586782753999971993578956979797747264617698541297598388968168128848889925191821626\n9952193671689277294778995937282491895888171947796739879498547893848388899738979951915599469754998574\n5912618789999244872297919879988729117113889566994789997491998999897479714697269992876829898925722782\n6992999529957852864712993868998979828846391749534732488988799281871998854992898895999755565696235276\n1918668999887419713511881918358999837788938499119795987839895699458923699958379545795179359893659981\n6784355989968822853988782395998772939751889862487297199998138254875217989839579791569689918838658899\n9597998247788781937583528972969838997798789881799827999894798768285889889879791851473839999878691879\n9999989795754894916776297971983688114959129819988685418477379813178929998469568659199968963983768269\n9281879896799992299299871778548299974689797199999969199197279938972297719824957838991728399748196894\n7358681176989594998874889389138896285912998287398968899257759136791787297999993649458864791768965682\n5999887851998697967294538271397663967177946959996187999988882891859538977789979696896296919918999991\n7982476991893925899167897294999974788899847819989761986287999544985576888479297375999574968587795164\n7788979839695796995933973481446879998989833997777995979988298199999882181147396354994982994786949794\n8386149885499696797618975196985997479982968986499698195296791591883912991949988762748856486857617586\n1969826289965887984793739999296589399339415889778382714486729519779718418839976599868445929175989287\n5953911181958986893699968848839918692897591986992168529255885788876888466867589587748393391193596777\n4781988436596599788498955986699591717795727892878591977997174898577915614825899859214849879969946987\n7993599858969771875133776815431596997826888544169999898857168147119977935799859919518869724514947698\n6483653999998934548388893599245397184767899457972988939286667436998992114798899289398916986979988919\n8239538889562698171887886783189959593198687528889836726598985989985997974398578868599359879999179896\n5187194954785929819984975598975986868378762999749895637919879916556679887624788396869697134768988979\n9798388189853995498798991977659999779479985378697685596953999499972477435996474687499698698953551991\n8669995825358857988899699719459511999943338925868799469778759891391968767197858151487512895154964572\n7186188958519978986196789958996399498919899525667947197263297931699935947847793276917899579499221359\n8868827787956847877438899168279879828298639978975855976933446549889139796168247228469959897765693891\n1119949798597699992889737692899988983742759119263697767998868669197235699836794996428591381161567838\n2875274999282589569995398511588292924979498989525839668898996664951547671993787386498763984994859694\n9969783989199983979678473715266984596998186719185694117834684699699673598616644229921935499699291873\n7964759549738689149189129463479486738349611839919955791999939919875888998697729715298423918988984994\n2788259353899786474729989945949859275289299119759689193972999214769598979117967954989699889899958658\n9299647982219985928831575638982136781891865659193528377991845999569979779876472421966918966369372997\n5899989417956578923571378315199921978695174998689868897586389979948879896898934889736923386517989785\n9281676849959293979775182877897812493678799161757769999989969867439855125818129442971198699739557388\n4475919879957889884939813999776999818798796521879871924749725987894786994958725987778611996824696996\n8373791639774379711585898751151997858172797774919959798592979987999867752618819589785168999928696886\n9977763998889359799421949996743699894919595899999767854599494798418928495698963462927981796996767593\n7158988951987949566758968925188499741457373829952984195653893751921799866679969236327982299919497241\n9345768513794668193984199998199919944392417719896282698389649867398962677886696961487194949688797479\n9798378451999998499638318999771917477786999563599661159919563675619925415947999864782957569816689998\n1587277984899982913961539966769739738598599994764297167417799429515482921298786889996573798136998119\n6862877528497478579739956318945612999518811163785996796182641699862228949171568496389633894989134895\n9957878484798399612898659161126465965219299893719988819827935779443847419355558585882799958995983898\n4929763129667799959194379778917789115795769395671999264898987483889989999299568719389167893855936958\n8995464987982983969387667531825997461987985777758646177899688897796796899589838794968888824776649779\n8929996779279673991599994397759554491997154696789362571393813932788488169975655899459788181848485291\n7396589792884275913849564139497387916794967629367698967893989845694998649396978919889877918997773988\n9988814998686188997151816923596528719279865312987374949879598157976131559787915229226192788489999329\n7688273881987982597998165459882889534983128846998773385896914973799981259813812977684993589999188891\n9863799649697311898116929839876959427498924399396999721972869799563979891552689978998988976585177859\n9799289996298785496798779827989419913999926987298641939996735451867517785516917267959949687159335994\n2119972966591599875846979198128484976782939992378979999999991952798999819989777999489495973155789988\n5594959849679229976592899699982974976329211757419911599863898984795598389963992376969584599961994799\n9499915839187619969189833964989988773419999499845897923955958762389687319218355959753893618479513474\n9129892175976515849924478398144924927778977956489979498895991666374898686273755959556758677666987856\n3798839151427839992617983217951447499399989629999929199899777335443677372798179699999572779989927584\n9989369421519694978991559748449571799694789957167495979999319838284795345682191854697182819189591892\n")

Rewritten parsing code:

(defn parse-grid [input]
  (->> (str/split-lines input)
       (mapv #(mapv (comp parse-long str) %))))

(def t-grid (parse-grid t-input))
(def grid (parse-grid input))

Some helpers adapted from a previous day:

(defn rows [grid] (count grid))
(defn cols [grid] (count (first grid)))

(defn neighbor-coords
  ([coord]
   (for [[rd cd] [[-1 0]
                  [1 0]
                  [0 -1]
                  [0 1]]
         :when (not= 0 rd cd)]
     (mapv + coord [rd cd])))
  ([grid coord]
   (filter (fn [[r c]]
             (and (<= 0 r (dec (rows grid)))
                  (<= 0 c (dec (cols grid)))))
           (neighbor-coords coord))))

Now we just need to solve the problem. My first mistake was to lazily assume that, as in the example grid, the optimum path would consist only of downward and rightward moves. I wrote a recursive, memoized algorithm that worked for part 1; but for part 2, which basically asks us to do the same thing but with a grid five times as big, I had success with the example input but not my own.

A helpful Clojurian confirmed my suspicion that all cardinal moves were allowed.

I then spent some shameful, keyboard-banging hours trying to adapt my algorithm; I was trying to write a brute-force path-search algorithm that:

  • Used memoization
  • Pruned expensive paths early on
  • Tracked a set of visited nodes

But all of my unprincipled attempts either blew the stack or yielded the wrong answer.

I didn’t want to punt or read any solution code, so I asked the Slack channel for a hint, and was very helpfully pointed to Dijkstra’s algorithm; admittedly I’d forgotten the thing existed.

Armed with the Wikipedia article, a min-heap library and my already-written and slipshod grid-tiling code, the final stretch wasn’t too bad.

Very minimal cleanup today due to time shortage.

(defn dijkstras-algo [grid start end]
  (let [coords (for [r (range (rows grid))
                     c (range (cols grid))]
                 [r c])
        tentative-ds (-> (apply pm/priority-map
                                (mapcat identity
                                        (-> (zipmap coords
                                                    (repeat Long/MAX_VALUE))
                                            (assoc start 0))))
                         (dissoc start))]
    (loop [tentative-ds (dissoc tentative-ds start)
           curr-node start
           curr-dist 0]
      (if (= curr-node end)
        curr-dist
        (let [unvisited-neighbor-ds (->> (neighbor-coords curr-node)
                                         (filter tentative-ds)
                                         (map #(vector % (+ curr-dist
                                                            (get-in grid %)))))
              tentative-ds (-> (reduce (fn [tds [node dist]]
                                         (assoc tds node (min (tds node) dist)))
                                       tentative-ds
                                       unvisited-neighbor-ds)
                               (dissoc curr-node))
              [curr-node curr-dist] (first tentative-ds)]
          (recur tentative-ds curr-node curr-dist))))))

(defn part-1 [grid]
  (dijkstras-algo grid
                  [0 0]
                  (map dec [(rows grid) (cols grid)])))

(rcf/tests
  (part-1 t-grid) := 40
  (part-1 grid) := 824)

Aforementioned gross grid-tiling code 😬

(defn iterate-row [row]
  (mapcat identity
          (iterate (fn [row]
                     (map #(if (= 9 %)
                             1
                             (inc %))
                          row))
                   row)))

(defn iterated-grid [grid]
  (map iterate-row grid))

(defn tile-grid [grid]
  (let [new-rows (* 5 (rows grid))
        new-cols (* 5 (cols grid))
        offsets (->> (repeat (rows grid) 0)
                     (iterate #(map (partial + (cols grid))
                                    %))
                     (mapcat identity)
                     (take new-rows))
        rows (take new-rows (cycle (iterated-grid grid)))
        rows (map #(drop %1 %2) offsets rows)
        rows (mapv #(vec (take new-cols %))
                  rows)]
    rows))

(defn part-2 [grid]
  (part-1 (tile-grid grid)))

(def t-grid-tiled (parse-grid "11637517422274862853338597396444961841755517295286\n13813736722492484783351359589446246169155735727126\n21365113283247622439435873354154698446526571955763\n36949315694715142671582625378269373648937148475914\n74634171118574528222968563933317967414442817852555\n13191281372421239248353234135946434524615754563572\n13599124212461123532357223464346833457545794456865\n31254216394236532741534764385264587549637569865174\n12931385212314249632342535174345364628545647573965\n23119445813422155692453326671356443778246755488935\n22748628533385973964449618417555172952866628316397\n24924847833513595894462461691557357271266846838237\n32476224394358733541546984465265719557637682166874\n47151426715826253782693736489371484759148259586125\n85745282229685639333179674144428178525553928963666\n24212392483532341359464345246157545635726865674683\n24611235323572234643468334575457944568656815567976\n42365327415347643852645875496375698651748671976285\n23142496323425351743453646285456475739656758684176\n34221556924533266713564437782467554889357866599146\n33859739644496184175551729528666283163977739427418\n35135958944624616915573572712668468382377957949348\n43587335415469844652657195576376821668748793277985\n58262537826937364893714847591482595861259361697236\n96856393331796741444281785255539289636664139174777\n35323413594643452461575456357268656746837976785794\n35722346434683345754579445686568155679767926678187\n53476438526458754963756986517486719762859782187396\n34253517434536462854564757396567586841767869795287\n45332667135644377824675548893578665991468977611257\n44961841755517295286662831639777394274188841538529\n46246169155735727126684683823779579493488168151459\n54698446526571955763768216687487932779859814388196\n69373648937148475914825958612593616972361472718347\n17967414442817852555392896366641391747775241285888\n46434524615754563572686567468379767857948187896815\n46833457545794456865681556797679266781878137789298\n64587549637569865174867197628597821873961893298417\n45364628545647573965675868417678697952878971816398\n56443778246755488935786659914689776112579188722368\n55172952866628316397773942741888415385299952649631\n57357271266846838237795794934881681514599279262561\n65719557637682166874879327798598143881961925499217\n71484759148259586125936169723614727183472583829458\n28178525553928963666413917477752412858886352396999\n57545635726865674683797678579481878968159298917926\n57944568656815567976792667818781377892989248891319\n75698651748671976285978218739618932984172914319528\n56475739656758684176786979528789718163989182927419\n67554889357866599146897761125791887223681299833479\n"))

(rcf/tests
  (tile-grid t-grid) := t-grid-tiled
  (part-2 t-grid) := 315
  (part-2 grid) := 3063)

Don’t feel great about that one, but at least I won’t soon forget the existence of Dijkstra’s algo.

⭐️⭐️