Fork me on GitHub
#adventofcode
<
2021-12-09
>
alekszelark04:12:08

🧵Day 9 answers thread: post your answers here

mchampine05:12:56

Part 1 quick and hacky but it works:

;; part 1
(def input
  (->> (util/load-lines "resources/day09.data")
       (util/split-lines-re #"")
       (mapv util/parse-ints)
       (map vec)
       (into [])))

(defn addpairs [[x1 y1] [x2 y2]] [(+ x1 x2) (+ y1 y2)])
(def surround [[1 0] [0 1] [-1 0] [0 -1]])
(defn neighbors [posn] (map addpairs (repeat posn) surround))

(defn adjs [brd pt]
  (remove nil? (map (partial util/getxy brd) (neighbors pt))))

(defn islowest? [brd pt]
  (< (util/getxy brd pt) (first (sort (adjs brd pt)))))

(defn low-points [brd]
  (for [x (range (count (first brd)))
        y (range (count brd))
        :when (islowest? brd [x y])] (util/getxy brd [x y])))

(reduce + (map inc (low-points input)))
;; => 530
;; part 2

(defn neighbors-on-board [brd pt]
  (filter #(util/getxy brd %) (neighbors pt)))

(defn step [brd acc-basin]
  (let [bn (map (partial neighbors-on-board brd) acc-basin)
        dac (distinct (apply concat bn))
        nn (filter #(not= 9 (util/getxy brd %)) dac)]
    (into acc-basin (set nn))))

(defn basin-size-at [brd pt]
  (count (util/fixed-point (partial step brd) (set [pt]))))

(->> (map (partial basin-size-at input) (low-ptsxy input))
     sort
     reverse
     (take 3)
     (reduce *))
;; => 1019494

Vincent Cantin07:12:29

Simple solution, nothing special ... didn't even use frequencies.

(ns aoc-2021.day-9
  (:require [ :as io]
            [clojure.string :as str]
            [aoc.util :as util :refer [comp->]]))

(def input
  (->> (io/resource "2021/day9.txt")
       slurp
       str/split-lines
       (mapv (fn [line]
               (mapv (comp-> str parse-long) line)))))

;; Part 1
(defn adjacents [[y x]]
  [[y (dec x)]
   [y (inc x)]
   [(dec y) x]
   [(inc y) x]])

(->> (for [[y row] (util/seq-indexed input)
           [x n] (util/seq-indexed row)
           :let [min-adj (->> (adjacents [y x])
                              (keep (fn [position]
                                      (get-in input position)))
                              (reduce min))]
           :when (< n min-adj)]
       (inc n))
     (reduce +))
;=> 631


;; Part 2
(->> (for [[y row] (util/seq-indexed input)
           [x n] (util/seq-indexed row)
           :let [min-adj (->> (adjacents [y x])
                              (keep (fn [position]
                                      (get-in input position)))
                              (reduce min))]
           :when (< n min-adj)]
       (loop [basin #{}
              edges #{[y x]}]
         (if (seq edges)
           (let [new-edges (into #{}
                                 (comp (mapcat adjacents)
                                       (remove (fn [pos]
                                                 (= (get-in input pos 9) 9)))
                                       (remove basin))
                                 edges)]
             (recur (into basin new-edges)
                    new-edges))
           (count basin))))
     (sort-by identity >)
     (take 3)
     (apply *))
; => 821560

alekszelark07:12:31

> didn’t even use `frequencies`

😅 5
😁 4
genmeblog08:12:27

lava!

👍 3
🌋 4
nbardiuk08:12:07

smoke settles down

👍 2
Callum Oakley09:12:14

not much to say about today. but I did use frequencies 😅 actually I did think of something. I’m technically doing some unnecessary work tracing from every point all the way to it’s corresponding low point, so tried wrapping basin in memoize… which made it actually slower. I suppose the savings don’t offset the overhead of the map lookups. nonsense, I wasn’t memoizing properly 31ms/91ms https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2021/09.clj

delaguardo09:12:45

booooring day, couldn't find how to use frequencies (

😂 6
miikka12:12:57

It was a bit too complicated to do in REPL but I did it anyway... here are the choice parts from my REPL history 😎 https://gist.github.com/miikka/48bab1596937814048d0c9fce9f1e4c2

😎 3
miikka12:12:45

One day I will start doing the thing where you have a scratch file in the editor and you send to REPL from there... but not today.

borkdude12:12:42

@U1NDXLDUG It's a sunk cost once you start typing right. But with Rebel Readline you might stay there forever ;)

miikka12:12:58

That's a good point, I should set up Rebel again. I used to use it, but then I got a new computer at some point and forgot about it

borkdude12:12:34

to be honest, I haven't used it much either. when I find myself in a console REPL, I just use load-file . But with babashka, I just run the entire file every time... The shell is my REPL :)

miikka12:12:52

Heh, yeah, that's nice about bb

tschady13:12:04

pretty psyched i was able to only need my grid library from prior years. neigbors, build-grid, connected-adjacency-map https://github.com/tschady/advent-of-code/blob/main/src/aoc/2021/d09.clj

👏 1
borkdude13:12:55

you were waiting for the grid, weren't you :)

tschady13:12:35

1 day off 🙂

genmeblog14:12:52

basins!

👍 1
2
❤️ 1
Vincent Cantin14:12:08

@U1Z392WMQ next, a bestagon-based problem

🕸️ 2
🔯 1
hexagon 1
tschady14:12:46

best shape!

Sam Adams17:12:28

Mine’s on the slower side — I didn’t realize that a basin couldn’t have more than one local minimum inside it https://samadams.dev/2021/12/09/advent-of-code-day-9.html

nice 1
AC17:12:43

I also didn't think about the "one local minimum" fact -- I would have probably done something different. instead I painted each square with a color based on what was "up" or "left" of it and occasionally merging paint colors (when connecting two previously disjoint basins).

Antonio Bibiano20:12:35

very nice write-up @U016C0EGHUN

🙂 1
thanks3 1
Stuart20:12:12

Part 1

(defn parser [s]
  (->> (str/split s #"")
       (mapv #(Integer/parseInt %))))

(defn find-low-points [input]
  (let [height (count input)
        width (count (first input))]
    (for [w (range 0 width)
          h (range 0 height)
          :let [n (get-in input [h w])
                u (get-in input [(dec h) w] 10)
                d (get-in input [(inc h) w] 10)
                l (get-in input [h (dec w)] 10)
                r (get-in input [h (inc w)] 10)]
          :when (and (< n u) (< n d) (< n l) (< n r))]
      {[h w] n})))

;; part 1
(let [input (->> (f/read-all-lines-and-parse "puzzle-inputs/2021/day9" parser))]
  (->> input
       (find-low-points)
       (mapcat vals)
       (map inc)
       (reduce +)))

Stuart20:12:02

Part 2: I find it so confusing working with 2d vectors and reversing the [x y] to [y x]

(defn get-neighbours [input [y x]]
  (let [yx' [[y (dec x)] [y (inc x)] [(dec y) x] [(inc y) x]]]
    (remove (fn [yx] (= 9 (get-in input yx 9))) yx')))

(defn walk-basins [input visited size to-visit]
  (if (empty? to-visit)
    size
    (let [yx         (first to-visit)
          neighbours (->> (get-neighbours input yx)
                          (remove (fn [yx] (or (visited yx) ((set to-visit) yx)))))]
      (recur input (conj visited yx) (inc size) (into (rest to-visit) neighbours)))))

(let [input (f/read-all-lines-and-parse "puzzle-inputs/2021/day9" parser)
      walk-basin-fn (partial walk-basins input #{} 0)]
  (->> input
       (find-low-points)
       (mapcat keys)
       (map vector)
       (map walk-basin-fn)
       (sort >)
       (take 3)
       (reduce * 1)))

karol21:12:37

https://github.com/kfirmanty/advent-of-code-2021/blob/main/src/day9.clj here is mine solution for day9, nothing fancy, but this day it helped me to do some crude drawings by using print and println to see that basins are properly covered (a protip (str some-char \u0333) will print this char with a double underscore directly under it so you can print the whole array easily and mark selected elements). It wasn't really that hard but in part 2 I had to realize that you can't too eagerly append cells to visited history as the same cell visited from different neighbours can both count as basin part and not

nice 2
Stuart21:12:42

> (str some-char \u0333) will print this char with a double underscore directly under Woah! Nice!

karol22:12:59

yeah, gotta love unicode 😄 I am developing mostly using Emacs REPL so not resorting to external tools when doing visualizations is a big plus. this is how it looked printed:

kevinc04:12:39

https://github.com/kconner/advent-of-code/blob/master/2021/9a.clj Identified low points by rows and by columns, then intersected the sets https://github.com/kconner/advent-of-code/blob/master/2021/9b.clj Flood filling with sets; each recursive step expands the complete border

samedhi05:12:06

Just finished day 6 and I think the clojure solutions definitely beat out the SQL ones -> https://github.com/mitchellh/advent-2021-sql/blob/main/day06/answer_p2.sql

mauricio.szabo12:12:42

Are you doing in SQL too? 😄

samedhi15:12:09

No, I'm doing Clojure. And wow, your solution seems much less noisy than the one I linked. Impressive.

samedhi15:12:02

I was talking more on whether I could understand it, yours is much more legible. (Though I have to squint as I am not great at SQL, haha)

samedhi05:12:42

SQL definitely had a lead on the earlier days... :]

Stuart11:12:31

SQL gives me nightmares. I've been hurt by too much bad batshit insane SQL at work.

samedhi16:12:31

Honestly I very rarely do more than select, insert, update, delete in the most basic ways.

samedhi16:12:10

I know SQL can be crazy performant if you can ask the right question, but often I just 1. pull all of the data that I need (maybe 1 WHERE clause) 2. convert them to clojure data structures (maps) 3. do some sequence processing stuff 4. write them back to the dabase 5. all within a transaction

mauricio.szabo12:12:15

Can someone help me with Day 08? I can't understand exactly the problem to be solved, why there are 10 measurements and 4 results, etc...

1
Stuart12:12:27

The ten measurements are the clues you have to use to figure out what the 4 numbers are after the | YOu don't have enough info using just the 4 values

Stuart12:12:05

acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf
So here, we know that ab is 1 since it only has 2 "segments" and we know that eafb is four, as it has 4 segments. However, we still don't know what a or b is in 1, a is c or f, and b is c or f.

Stuart12:12:45

You need to figure out what all the numbers on the left of the bar are. Once you have figured that out, you can then match them to the four parts after the bar. This will give you a 4 digit number

Stuart12:12:03

8                       7                 4          1
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf
So you know 4 of the numbers, how will you work out the rest ?

1
Stuart12:12:39

An important thing is that every line in the puzzle input is an individual problem to solve. The segments are mixed up differently for every line

mauricio.szabo12:12:28

Yeah, I still don't get it. I know that the left side is supposed to be measurements, and the right side, what's displayed. But why there are 10 measurements to 4 digits?

Stuart12:12:09

If there were only the 4 measurements I don't think you would have enough information to figure out what the four digits are. e.g. if you only had cdfeb fcadb cdfeb cdbaf , then i believe their is no way to work out which digits those are

Stuart12:12:32

but given the 10 examples on that row, you can work out what the 10 examples are then just match them to the 4

Stuart12:12:56

basically you need to only work out the 4 digits to the right, but you need the 10 digits to the left to figure that out

Stuart12:12:07

so in the example in this thread, the 4 digits after the bar are 5353. You couldn't figure that using only the 4, I mean, it could be 3535. But with those 10 you can figure out that its 5353

mauricio.szabo12:12:09

Ah, ok, so the measurements mean that "I gave this measurements, and some of these displayed these numbers, but I don't know which one displayed which number"?

Stuart12:12:34

you know ab is 1 as 1 is only the digit that has only 2 segments

Stuart12:12:40

but a 1 should be

....
.    c
.    c
 ....
.    f
.    f
 ....
So you need to figure out if a is c or f

Stuart13:12:06

hint: Certain numbers are subsets of other numbers, and some numbers are supersets of other numbers.

Stuart13:12:38

You don't actually need to figure out exactly what characters match to what segments. You can just figure out what "words" relate to what numbers

tschady13:12:48

the left side represents the digits 0->9 (in some order), in that lines’ particular cipher

1
mauricio.szabo15:12:46

Ah, ok, thanks 🙂.

Antonio Bibiano12:12:39

sorry peeps, i need some help with day 9 potential spoilers in thread

Antonio Bibiano13:12:06

for part 2 I ended up with this recursive function

Antonio Bibiano13:12:28

(defn get-basin [heightmap points]
    (into #{}
          (mapcat (fn [point]
                    (let [basin-neighbors (get-basin-neighbors heightmap point)]
                      (if (empty? basin-neighbors)
                        [point]
                        (conj (get-basin heightmap basin-neighbors) point))))
                  points)))

Antonio Bibiano13:12:37

get-basin-neighbors returns a list of neighbors that can be in the basin, ie no 9 and not the point itself

Antonio Bibiano13:12:10

the heightmap is a nested vector of the numbers

Antonio Bibiano13:12:20

works for the example input but i get a stack overflow error on the large input

miikka13:12:28

Hmm; I'm a bit surprised that it works with the small input since it looks like it would end up in an infinite loop in both cases

miikka13:12:13

If you have a point and then you call get-basin on its neighbours, doesn't that call end up calling get-basin on the original point?

Antonio Bibiano13:12:43

i only get the neighbors where the number is higher than the current one

Antonio Bibiano13:12:02

it's true that it does some unnecessary calculations

Antonio Bibiano13:12:13

but it should end up in an infinite loop

miikka13:12:59

I wonder if the big one just has too big basins, then, for the recursion to work (without using loop/`recur` )

genmeblog13:12:07

the biggest basin in my dataset is 98

Antonio Bibiano13:12:45

does the fact that I pass the heightmap as an argument make things worse?

miikka13:12:15

With mapcat in play, I don't have super clear feel about the recursion depth but seems like it could work :man-shrugging:

genmeblog13:12:16

get-basin-neigbours can return the same neighour for diffent input

genmeblog13:12:04

and you visit the same points many times

miikka13:12:49

Hmm, if get-basin-neighbors only goes uphill, seems like you'd get wrong result for a basin with two low points. But that's a separate issue from the stack overflow

Antonio Bibiano13:12:17

yeah @U1EP3BZ3Q i thought it would be harmless, but maybe not ..

Antonio Bibiano13:12:54

i'll try a loop/recur refactor and to make it less wasteful

miikka13:12:29

Oh, the problem statement says that each point belongs to only one basin, so what I said is not an issue

sarcilav14:12:08

maybe this it the problem > i only get the neighbors where the number is higher than the current one

sarcilav14:12:08

what it is the output of something like

012190
232299
111111

sarcilav14:12:37

or your basins better

Antonio Bibiano18:12:29

thanks for your help! I did it

(defn get-basin-new [heightmap points]
  (loop [ret #{} points points]
    (if (empty? points)
      ret
      (let [cur-point (first points)
            basin-neighbors (remove ret (get-basin-neighbors heightmap cur-point))]
        (recur (conj ret cur-point) (concat (rest points) basin-neighbors))))))

Antonio Bibiano18:12:47

turns out visting the same place many times was really messing with the recursion!

Antonio Bibiano18:12:27

@U0C5L73ST that's a very valid concern, but I think the input is simpler for today

Antonio Bibiano18:12:35

ah wait the second if is not necessary! refactored

Antonio Bibiano18:12:36

@U067R559Q is that similar to what you pointed me to with BFS?

Antonio Bibiano19:12:45

ah yeah that's where I ended up

Antonio Bibiano19:12:27

Looks like I could have used a queue here

💯 1
Antonio Bibiano19:12:41

but didn't see any solution using queues

alekszelark19:12:09

Once, I implemented my own a minesweeper game. Does it look similar to today’s problem? 🙂

😄 1
Stuart19:12:13

For day 9 part 2, when walking the basins, do you want to only include the squares that are within 1 of the current square, e.g. If you were at 5 here, would valid neighbours for the walk be only the 6s or the 8s too ?

Stuart20:12:40

Everytime you refresh the 2021 page the waves change 🙂

wow 3
tschady20:12:36

for extra motivation. when you complete the year you get that continual animation

lread21:12:28

This is my first year trying the Advent of Code. I am finding the puzzles tremendous good fun. For all you veterans, do you typically complete all 25 days?

tschady21:12:12

i do 50-100% depending on my schedule, then chip away at problems that interest me during the year. i think i’ve done 2/3 of all so far.

tschady21:12:04

there’s a considerable time ramp up around the 15th

Stuart21:12:34

The best I've ever done was last year, 36 stars.

Stuart21:12:51

And a chunk of those 36 were done this year

lread21:12:55

Good to know, thanks, so it is a gift that can keep on giving, even into the new year!

tschady21:12:46

2015 is the easiest year, i think. good place to start.

lread21:12:07

Oh right... I could visit puzzles of advents past. Interesting...

Phil Shapiro22:12:08

2020 seemed easier to me than 2019 and 2018. Or maybe I'm getting better at writing advent code :). Most people don't complete the full calendar, you can look at the stats for each year to see completion rates per day.

Stuart22:12:14

Yeah, I agree 2020 feels the easiest year so far.

Stuart22:12:12

This year feels easier than 2020 though, up until this point.

fingertoe00:12:05

The first year I did 7, the second year, 13, This year I am 10 for 10.. As the holidays approach, there is a lot more competition for attention.. (also my wife isn't fond of obsessed coding guy).

Vincent Cantin13:12:38

I did all the stars last year while being busy because I failed at giving up.

Vincent Cantin13:12:07

That's addictive after a couple of weeks.

miikka16:12:14

I usually do only the quick ones. If the top list times are >15 minutes, then I probably won't bother 😛

lread19:12:25

I feel kind of hooked right now. But the shine might come off after the puzzles become much more puzzling.