Today’s puzzle finds me after a late start to a busy day, so my goal here is to write my thought process as I go and hopefully make a quick solve.

(ns aoc.2021.day.09
  (:require [hyperfiddle.rcf :refer [tests]]
            [clojure.string :as str]
            [hyperfiddle.rcf :as rcf]
            [clojure.set :as set])
  (:import (clojure.lang PersistentQueue)))

(rcf/enable!)

The task is to find local minimums given a grid of integers. Easy enough!

(def input "7656798786535699986544456789569432012478910965431019876545456789456789769876598765467899898999876545\n8787988665323788999432346797698764123567899876542198765634365695345698955987679879878939767899865434\n9899876543212767898821235789789873294568976987643239874321254789234567943199798989989321656789654321\n3923997654102358987650124599899964989879465698654398765410123892123459894098987699995210345898765432\n2399898763212567986542235678989879878989354798789987654324234589019598789987676579874321256789876543\n1988799874323478987653446789876999868990123459898998765765365678998987678976543456965632369896988656\n0976598765434599998767556799985987756989244567987899876887456989987654567895432345986793578945699788\n1987439986569987899879677899999896645678955698976786987899567898996543456789321266799989999632129899\n9876521987698976989989788978998765534569766789865545698987678967987632389898735477898978789549098999\n9985410198987894577899899769987654323899987898754324569698789659876543678987649678987656678998987988\n9894321239976423456789965456976543212678999989767945789569896543989654579398758789876745567897656677\n9765432547985313345678976567987652104567893979879899893498999932198775691239769895995434456789545466\n9876557656983201235689987679876543213479932867998799912987897893249886789349878934987322345695435345\n8987698869874342345678998789987754328989421359897689909875456789345987898767989123976510656789921236\n7698799878965656756789109897899876567893210498766567897654347897656799939988991034985431267897810145\n7569944989876767969897999956798988878954321987655428989543278998767892123999432549997556348976521234\n6457123496987898978946789545987799989765459876543219878954469999878999019876553998998987899765434546\n5321012345698989989235679939876546999897597987985434569767599898989898929987969887899298969876545856\n7432345957789679892134567898765439898989986799876568978978989787898767898998879756789109456987956767\n8543469898896598743547678929899598787678965343987678989989876676789656987899998645899212347999897878\n9986598789987679654656789219988987676567894212499789993298985565696543456789865435678923456798789989\n6797987678998798765789898998767987544456789101239897894987654434589212347999876566789894567987678991\n5679876567899989876899987897658976432345678992945956989999432125679101238976989678998789679898567890\n4569875478789878987999876896549865421236989889799349878998943434678912347895498789765678998674346791\n3498764345678967898998765689432976532456898767678998767897894545789323556789329898654989876521235689\n4598854234569656989999764567941098743568999854567987654646789956896434768995434986543244987430134578\n5986543145678949876987643458942987654567987543679898743434597897987949989876949875432123986541245679\n9876543266799521965698754567894599778978987654598765432123456798999898999989898764321037897674346899\n9987654777895439874598765678985679899989398767679876541012345899998787899898789975542356798765487998\n9899875688976598753249876789876789998790129878789988652123458923987656788789654986753477899877678967\n8765989789987699842137989899987999987621245989899876543234567899876545634689543798769998998989789349\n9654499894398987652025698987698999876535367891998987654345678998765432123678932659898789987699893252\n8763210943239876543434567896539899987676498932987898765456789429876321014589991045987678997556989101\n7654329994125998754545678997645789699887569549856949987568993212987432345678989239876569895445678912\n8765498789034569875697789789856789543997678998769432198979894101298543467899878998765456789334578923\n9876989678946789976789895678977898432398789769878945239989799212999698578912567899654367890123489934\n2989878567897899987896986999898976521349898954989654349997678929886987679543489998767898921234567895\n1398765457789998798955699888789965432499987893498765498956567898765499889694678989878999432345679987\n0129874345699876549544598765679876549987976792989976987843456789874323996989989876989896587656789598\n9999985234789998632123798654578987698956985889876989876532677898765412345678999655495789698987896499\n8789892145678999321035987573237899987645234578965695997544788989974323496989998743234678919198997989\n7679789234567895492129876432056789997632123489654524598675699879865434789998987654345699909239789765\n6545678945698976989298765432178999876543234567943213469988789767987545678967998765456789898945698873\n7434567896789989978919896543469109998765445678932101979899895656997676789359889887689896787897987432\n4323458997898999869923987654569298999878576789543219898778954349898789891298763998799985656789876541\n5312367899937893998899999865678987895989687897694397654567895298789895990197652129898774345898997632\n4101456789546912987698999876989656793298798998989986743676789989643934989987642034997654234567898843\n3212345678959329898587899987898945689999899999879765432345699876542129976798543126989762104567899956\n4345696799998998765476789998967534577899987895469874321234789987659298765987654234578973213458999767\n6568989899987897654345678989754324566799876789355985432345678998998999654598987545699765454599998978\n7678978999976789543234569876543213345689989893234797645456889439987998963239987656789877667678987899\n8999867898765679652165678965432101234569998932145698776567899929876567892198998767891989788989976789\n9987954569654568969234699876543232345678987643458799897678999899865456789987589878932399899491265679\n9876543498963457898765789988664655457789398756899987998789989798954345899876476989543459954310124567\n9987632987652346789896998799765789868995459977899876789899878687993256798764345797654598765521234678\n9876521098541545678987897679876892979876569998945985456998765566789129987543254699987679876672347889\n9965432987630238989798934567987910989997678949439876567899654365678998999652123589999789987783456791\n9876549998321347897659323569999891999989989239323987698998721234599987898991012378999895498894567892\n9987678999543656789543212678998789898776590167919998789987650123499876987989423467899974349765678943\n9998799987657787899952104567987675797654321257898899899998743235789965765879436567899753267998789954\n8999893498767898999843212689978534689895592346987657978999656397897654554569945688987654379439896896\n7893912349898999789754327898767423576989989587996543567898787456899753543567898799998765998921945989\n6992101999999787689868936987653212345678978998989921456999899567997652101478949896989879887890239876\n4789219878997678545998545699743101234679567899878892367894987678976543212349932945678998776789399765\n3698998969876543434597656798656212356789456898656799468963298899987954524456891234569987675678987654\n4567897656998642323498769898768923487892345987545678979654359956999898765967890123498796454569898743\n9878998549876531014569899999878934598901399876534567899767897549898789876878921356987654343468789654\n6999989734988542123789989987989765679212988765423489939879965439767698989999932349896543232345678965\n5569878921987656245699976596799896789349876544315678921989976599654567898789865498765432101234567896\n4398767892398767656897985435678987898456985432101789439896897988773456987678976599886543272345678987\n3249656789469898967956798546789498987589996563234599598765789876562349876567897989987654365456789498\n1099545696578999898943987657892399798678949764345678997654678954341298765468999978898765566567894349\n2987656789689998789992398967901987639989434995696989896543219653210398874345698766789876678978943234\n3598967998799987689989459878929876525697549879987898789674598954331987543246987645678999899999854395\n4599878959899876578979967999698765434597659867899987678989987895567998632123498932345678989989765989\n5789999945998965464767899989569876546789797654989899569899896789789876541012349853456889879878979878\n9899989896987654323456998778457998787897987543676789456798765678999985432123459766567996767569998765\n4999878789998965434567897654349879898956799432575994349987654567899986545764569877678965453458987654\n3499765678999876575678976543298768939345698921434893298798543456798997656878978988789654312357896543\n2987654567893987689789987652129654321234997890126793129654212367897798767989989799898765501246789432\n1098743458932398789899878761098743210129876789237891019876523458965639879392495678959876712657998321\n3149894967891299893998765432129874321298765678945992323987434567894322989101234569545984327767897210\n4234989898932988992109878543299965452987654567896789456798765898943210993214345778934995456778976521\n4349878789549876789399989665989976769876543456989896567899876789765329865765478989129876568989987432\n5499865678998765678989998789876897998765432345679987678978987898765439876876568993299987679294598543\n6987654567999896789878999896545789999862101476789298789767898919878656987987978999989898989012999656\n9877783456899987894767899989434567987654212388990149897658999423989968998999899998876789992129898767\n9966432346789498943458998765623478798765323499321234998767989434599899879998798987645698989298769898\n7654321356894359954569987654310145679876434578935345999878978995698789965987657893434987678987654929\n8765210897953267895678998765321234589987547699549656789999656789987679954297645932129876567898943213\n7654326789943124999789989876432345891098678789698767995432345789876568892109434894298965458999652101\n8987534567891023988999876998763456789999789898789989654321996999987466789298746789987655357898943219\n9876545689942139877898765987654567996799899999896799765439889898994345678987657899999543234767894398\n6989876789543497766799954398965879345678958999989898976598776787898766789998789998998942123456789987\n5496997897654596545698799239986789234589546789878987897987665876799987897899899887897897545678999876\n4355698998965987639987678992197990145678935698767876799876543454689998956789998786956789656789678995\n3234579879896799998784566789298921266789123987656385689965432343467899345678987654545678987894569984\n2165689954789899876543645878999432378891012396543234799876521012378943234567898763234567898943298765\n3989798765679998765432124567896545989932123987654125689987632125489762123478969974345689989432109976\n4599899876789239854321012679998656798765434598785434578987654334599873234589659865456799876543413987\n")

(def t-in "2199943210\n3987894921\n9856789892\n8767896789\n9899965678")

First some unsavory nested mapping to parse a 2D vector (grid) from our input:

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

(def heights (parse-heightmap input))
(def t-heights (parse-heightmap t-in))

Some helpers for counting (how many times will I write these this year…):

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

Now some neighborly functions:

(defn neighbor-coords [grid [r c]]
  (for [[rd cd] [[1 0] [-1 0]
                 [0 1] [0 -1]]
        :let [r (+ r rd)
              c (+ c cd)
              coord [r c]]
        :when (and
                (every? (complement neg?) coord)
                (< r (rows grid))
                (< c (cols grid)))]
    coord))

(defn neighbors-vals [grid coord]
  (let [neighbors (neighbor-coords grid coord)]
    (map #(get-in grid %) neighbors)))

Now, to find local minimums, we’ll just check every cell of the grid:

(defn coords [grid]
  (for [r (range (rows grid))
        c (range (cols grid))]
    [r c]))

(defn local-min-coords [grid]
  (let [coords (coords grid)
        local-min? (fn [coord]
                     (every? (partial < (get-in grid coord))
                             (neighbors-vals grid coord)))]
    (filter local-min? coords)))

(defn part-1 [grid]
  (->> (local-min-coords grid)
       (map #(get-in grid %))
       (map inc)
       (reduce +)))

(rcf/tests
  (part-1 t-heights) := 15
  (part-1 heights) := 462)

Part 2 is more involved – we need to identify ‘basins,’ which are sections of the heatmap bounded by 9s (and void). This is more of a graph-search problem.

(def high-pt 9)

Next we’ll write an “explore-basin” function which, given a grid and a non-high-point, does a BFS search of the area stopping at high-point walls and edge boundaries.

(defn explore-basin-bfs [grid coord]
  (loop [acc #{}
         queue (conj (PersistentQueue/EMPTY) coord)]
    (if (empty? queue)
      acc
      (let [[c queue] ((juxt peek pop) queue)
            acc (conj acc c)
            to-visit (->> (neighbor-coords grid c)
                          (filter (complement acc))
                          (filter #(< (get-in grid %)
                                      high-pt)))]
        (recur acc (into queue to-visit))))))

And now we iterate over the grid, exploring each time we encounter an unexplored non-high-point:

(defn basins [grid]
  (first
    (reduce (fn [[basins visited] coord]
              (if (or (= high-pt (get-in grid coord))
                      (visited coord))
                [basins visited]
                (let [basin (explore-basin-bfs grid coord)]
                  [(conj basins basin)
                   (into visited basin)])))
            [#{} #{}]
            (coords grid))))

(defn part-2 [grid]
  (let [basins (basins grid)]
    (->> basins
         (map count)
         (sort-by -)
         (take 3)
         (reduce *))))

(rcf/tests
  (part-2 t-heights) := 1134
  (time (part-2 heights))) := 1397760  ; => 730.878042 ms

Onward!

⭐️⭐️