This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2021-12-09
Channels
- # adventofcode (132)
- # announcements (19)
- # babashka (7)
- # babashka-sci-dev (6)
- # beginners (46)
- # calva (25)
- # chlorine-clover (5)
- # cider (2)
- # clara (17)
- # clj-kondo (93)
- # clojure (2)
- # clojure-dev (4)
- # clojure-europe (12)
- # clojure-losangeles (3)
- # clojure-nl (7)
- # clojure-uk (4)
- # clojurescript (29)
- # conjure (6)
- # core-async (8)
- # cursive (16)
- # data-science (7)
- # datomic (1)
- # exercism (4)
- # figwheel-main (8)
- # fulcro (9)
- # graphql (2)
- # helix (1)
- # introduce-yourself (3)
- # jobs (3)
- # lsp (4)
- # malli (20)
- # minecraft (3)
- # nextjournal (62)
- # off-topic (16)
- # overtone (34)
- # pathom (5)
- # polylith (10)
- # portal (1)
- # re-frame (104)
- # reagent (29)
- # reitit (1)
- # remote-jobs (2)
- # rum (3)
- # shadow-cljs (22)
- # spacemacs (2)
- # sql (10)
- # tools-deps (17)
- # vim (13)
🧵Day 9 answers thread: post your answers here
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
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
https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2021/day09.clj
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 nonsense, I wasn’t memoizing properly
31ms/91ms
https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2021/09.cljbasin
in memoize… which made it actually slower. I suppose the savings don’t offset the overhead of the map lookups.
@U01HL2S0X71 check out this: https://stackoverflow.com/questions/3906831/how-do-i-generate-memoized-recursive-functions-in-clojure
Day 9 in #babashka and #clojure https://gist.github.com/borkdude/b5cf0e9d2d8ab7c678d88e27a3357b33#file-aoc21_d09-clj
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
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.
@U1NDXLDUG It's a sunk cost once you start typing right. But with Rebel Readline you might stay there forever ;)
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
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 :)
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
time for the annual spike in traffic to https://www.redblobgames.com/grids/hexagons/ ?
same with http://oeis.org
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
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).
i struggled a lot with stackoverflows a bad recursion 😄 https://gist.github.com/antbbn/5907c3c2f733e5156140420b2cb49568#file-day9-clj
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 +)))
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)))
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
> (str some-char \u0333)
will print this char with a double underscore directly under
Woah! Nice!
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:
today I flooded basins with loop/recur: https://github.com/euccastro/advent-of-code-2021/blob/main/day9.clj
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
super mutable flood fill https://github.com/FelipeCortez/advent-of-code/blob/master/2021/09.clj
https://github.com/benjamin-asdf/advent-of-code-2021/blob/master/src/day9.clj man your solutions are so simple. Learning a lot
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
Are you doing in SQL too? 😄
@U0532BYNC my solution in SQL is incredibly faster than Clojure, to be honest: https://gitlab.com/mauricioszabo/advent-of-code-2021/blob/master/src/day-06.sql
No, I'm doing Clojure. And wow, your solution seems much less noisy than the one I linked. Impressive.
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)
Honestly I very rarely do more than select, insert, update, delete in the most basic ways.
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
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...
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
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
.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
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 ?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
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?
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
but given the 10 examples on that row, you can work out what the 10 examples are then just match them to the 4
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
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
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"?
but a 1 should be
....
. c
. c
....
. f
. f
....
So you need to figure out if a
is c
or f
hint: Certain numbers are subsets of other numbers, and some numbers are supersets of other numbers.
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
the left side represents the digits 0->9 (in some order), in that lines’ particular cipher
Ah, ok, thanks 🙂.
sorry peeps, i need some help with day 9 potential spoilers in thread
for part 2 I ended up with this recursive function
(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)))
get-basin-neighbors
returns a list of neighbors that can be in the basin, ie no 9 and not the point itself
the heightmap
is a nested vector of the numbers
works for the example input but i get a stack overflow error on the large input
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
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?
i only get the neighbors where the number is higher than the current one
it's true that it does some unnecessary calculations
but it should end up in an infinite loop
I wonder if the big one just has too big basins, then, for the recursion to work (without using loop
/`recur` )
does the fact that I pass the heightmap
as an argument make things worse?
With mapcat in play, I don't have super clear feel about the recursion depth but seems like it could work :man-shrugging:
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
yeah @U1EP3BZ3Q i thought it would be harmless, but maybe not ..
i'll try a loop/recur refactor and to make it less wasteful
Oh, the problem statement says that each point belongs to only one basin, so what I said is not an issue
maybe this it the problem > i only get the neighbors where the number is higher than the current one
on your code @U01HY37QQUA
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))))))
turns out visting the same place many times was really messing with the recursion!
@U0C5L73ST that's a very valid concern, but I think the input is simpler for today
ah wait the second if is not necessary! refactored
@U067R559Q is that similar to what you pointed me to with BFS?
ah yeah that's where I ended up
but didn't see any solution using queues
Once, I implemented my own a minesweeper game. Does it look similar to today’s problem? 🙂
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 ?
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?
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.
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.
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).
I did all the stars last year while being busy because I failed at giving up.
That's addictive after a couple of weeks.