Advent of Code: Day 9
While I find the event to be awesome, I saw some negativity regarding Advent of Code noise over the internet. People are writing things like “this is just yet another code jam”, or “go build something practical and useful instead of wasting your time on pointless coding”. These complaints usually sum up that the RSS feeds, and social media are full of blog posts like the very one you’re reading right now, and they don’t like it. Well, I’d like to briefly address some of these points.
First, yes, this is just another code jam. There are lots of these during the year, and there are ones that are much harder than this one (not to suggest that AoC is easy, there are pretty challenging tasks, it’s just that the other jams are usually about a different kind of competition). The Advent of Code is a lighthearted jam that is mainly for having fun. Well, for me at least. Yes, it’s a competition, if you want to see it like that, but it’s not like the competition here is the main point.
As for building something practical instead of wasting time - guys, I’ve worked on my side project for the whole year, give me a break! I just want to put things aside and relax for a bit, solve some puzzles, especially such cool puzzles as Advent of Code provides. I really like how puzzles are written and tell you a story. And puzzles are pretty interesting on their own too. We’re just having fun, why can’t we have some more right before the holidays?
Anyway, sorry for a bit harsh intro, I just hope that there are not too many AoC haters reading me, so I don’t bother too much people.
If you are, feel free to subscribe to a particular feed you’re interested in, by going to the Tags of Categories section, selecting the section you’re interested in, and adding feed.xml to the URL.
Thank you.
Now, back to the task!
Smoke Basin
The caves we’ve entered seem to be the lava tubes. Ans some of the tubes are still active. Our puzzle input is the heightmap of the tubes, which looks like this:
2199943210
3987894921
9856789892
8767896789
9899965678
The bold numbers are the low points - the locations that are lower than any of its adjacent locations.
It means that these points are the smallest in the surrounding area (excluding diagonals).
This example has four low points, which are 1, 0, 5, and 5.
Our task is to compute the risk level, which is computed by the height of the point plus 1.
In this case risk levels are 2, 1, 6, and 6.
Adding those together produces the total risk level of 15.
Let’s start by parsing the input:
day8> (ns day9)
nil
day9> (require '[aoc-commons :refer [parse-long]]
'[clojure.string :as str])
nil
day9> (def example-input "
2199943210
3987894921
9856789892
8767896789
9899965678")
#'day9/example-input
day9> (defn read-input []
(->> example-input
str/trim
str/split-lines
(mapv #(mapv (fn [s] (parse-long (str s))) %))))
#'day9/read-input
day9> (read-input)
[[2 1 9 9 9 4 3 2 1 0]
[3 9 8 7 8 9 4 9 2 1]
[9 8 5 6 7 8 9 8 9 2]
[8 7 6 7 8 9 6 7 8 9]
[9 8 9 9 9 6 5 6 7 8]]
Sweet! Now we need to find the points that represent the lowest values and their surroundings. Let’s write a function that checks if the point in the row is the smallest from the ones near it. We’re not going to check other rows just yet:
day9> (defn find-minimum [row]
(->> row
(map-indexed #(and (< %2 (nth row (dec %1) 9))
(< %2 (nth row (inc %1) 9))
%1))
(filter number?)
(into [])))
#'day9/find-minimum
day9> (find-minimum (first (read-input)))
[1 9]
This function walks the row via the map-indexed function, which accepts the index of an element as the first argument and the element itself as the second one.
We’re abusing the fact that the largest number in the input is 9, and if we go out of bounds we simply use 9 as a fallback.
The return value is a vector of indexes that matches our criteria.
But this is only the info about a single dimension, e.g. a column, we need to populate it with the row number as well:
day9> (defn find-row-min-points [rows]
(->> rows
(mapv find-minimum)
(map-indexed #(mapv (fn [e] [%1 e]) %2))
(into [])))
#'day9/find-row-min-points
day9> (find-row-min-points (read-input))
[[[0 1] [0 9]]
[[1 0] [1 3] [1 6] [1 9]]
[[2 2] [2 7] [2 9]]
[[3 2] [3 6]]
[[4 1] [4 6]]]
Oh, this looks like a mess, but it is correct, trust me.
But, you know, you don’t have to trust me!
Instead, let’s write a render function, similarly to how we did in solution for the day 5:
day9> (defn render [rows coordinates]
(let [x (count rows)
y (count (first rows))
field (into [] (repeat x (into [] (repeat y "."))))]
(->> coordinates
(reduce (fn [field p]
(assoc-in field p (get-in rows p))) field)
(map str/join)
(map (partial str ";; "))
(str/join "\n")
println)))
#'day9/render
We can’t render things just yet, as this function accepts a flat list of coordinates, like this one: [[0 1] [1 0] [0 0].
Our current coordinate list is not flat, as it contains rows, but since we’ve incorporated the row number into the stored points, we can flatten this structure like this:
day9> (defn to-single-level [rows]
(reduce (fn [all row] (concat all row)) [] rows))
#'day9/to-single-level
day9> (to-single-level (find-row-min-points (read-input)))
([0 1]
[0 9]
[1 0]
[1 3]
[1 6]
[1 9]
[2 2]
[2 7]
[2 9]
[3 2]
[3 6]
[4 1]
[4 6])
day9> (render (read-input) (to-single-level (find-row-min-points (read-input))))
;; .1.......0
;; 3..7..4..1
;; ..5....8.2
;; ..6...6...
;; .8....5...
nil
Right now this doesn’t look like the expected result, but this is because we’re only using horizontal information, so there are some points that we need to filter out.
To do so, let’s transpose our rows, so rows would become columns and repeat the algorithm:
day9> (defn transpose [m]
(apply mapv vector m))
#'day9/transpose
day9> (let [rows (transpose (read-input))]
(render rows (to-single-level (find-row-min-points rows))))
;; 2..8.
;; 1..7.
;; ..5..
;; ..6..
;; ..7..
;; 4.8.6
;; 3...5
;; 2...6
;; 1...7
;; 0...8
nil
Now we just need to combine the two sets of coordinates, and we’ll get our points:
day9> (require '[clojure.set :as set])
nil
day9> (defn lowest-points [rows]
(let [min-rows (->> rows
find-row-min-points
to-single-level
set)
min-cols (->> rows
transpose
find-row-min-points
to-single-level
(map (fn [[x y]] [y x]))
set)]
(into [] (set/intersection min-rows min-cols))))
#'day9/lowest-points
day9> (render (read-input) (lowest-points (read-input)))
;; .1.......0
;; ..........
;; ..5.......
;; ..........
;; ......5...
nil
Bingo! Oh, wait, the wrong day. Looks around, hoping that there is no giant squid nearby.
Ahem, we got our points and these are the exact points from the example high above. All that’s left is to get their values out, increment and sum:
day9> (defn part-1 [input]
(->> input
lowest-points
(map #(get-in input %))
(map inc)
(reduce +)))
#'day9/part-1
day9> (part-1 (read-input))
15
This grants us the first gold star! Let’s see what we need to do next.
Part two
And next, we need to find the largest basins so we would know what areas are most important to avoid.
A basin is represented by a location where the numbers flow downward to the minimum one.
9 is not the part of the basin, so we need to exclude it from the data.
Here’s one of the basins in the example input data:
2199943210
3987894921
9856789892
8767896789
9899965678
You can see that it is surrounded by number 9.
The size of the basin is determined by the number of numbers in it, this particular basin has a size of 14.
We need to find the three largest basins in our input data and multiply their sizes.
Let’s start by writing a rule that will check if the point is a part of the basin:
day9> (defn part-of-basin? [val lowest]
(<= lowest val 8))
#'day9/part-of-basin?
This simply checks that the value is higher or equal to the lowest one in the basin, and is smaller than 9.
Now we need to find all coordinates that belong to a basin for a given point:
day9> (defn find-basin [coords rows [x y] val]
(when (part-of-basin? (get-in rows [x y] 10) val)
(vswap! coords conj [x y])
(doseq [coord [[(inc x) y]
[(dec x) y]
[x (inc y)]
[x (dec y)]]]
(find-basin coords rows coord (inc val)))))
#'day9/find-basin
Aah, watch out! A wild non-pure recursive function appeared!
Did I scare you? Don’t worry, this function is the simplest solution I could though of for finding all points that belong to a basin. Yes, it’s a shame that it is mutable, but I didn’t want to bother writing it in such a way that it would pass its state to subsequent calls, so bear with me. I’ll explain what it does in just a bit, but right now let me show you that it can find the example basin:
day9> (let [rows (read-input)
basin (volatile! #{})]
(find-basin basin rows [2 2] 5)
(render rows @basin))
;; ..........
;; ..878.....
;; .85678....
;; 87678.....
;; .8........
nil
As you can see it found the correct basin for the point with the coordinates of [2 2] and a value of 5.
So how does it do that?
The first thing we do in this function checks whether the point is a part of the basin, meaning that it is between the lowest point and 9.
Since our first point is the lowest one already this function returns true, we add it to the coords and go into the doseq.
It then loops through a new set of points, directly above, below, to the right, and to the left of the current one, and goes into the next recursion step, incrementing the minimum value.
This way we can check all points up until the only points left are 9 ones, and we exit this function.
And since coords is expected to be a set, there will be no duplicates, even though we visit the same points over and over again.
Now, when we can find a single basin, all that is left is to find all of them:
day9> (defn find-basins [rows]
(let [points (lowest-points rows)]
(for [p points]
(let [coords (volatile! #{})]
(find-basin coords rows p (get-in rows p))
@coords))))
#'day9/find-basins
day9> (render (read-input) (to-single-level (find-basins (read-input))))
;; 21...43210
;; 3.878.4.21
;; .85678.8.2
;; 87678.678.
;; .8...65678
nil
Here are all basins on the same coordinate field.
You can see that they’re separated by . symbols, meaning that there were 9.
Finally, we need to count all their sizes, sort, take the first three and multiply:
day9> (defn part-2 [input]
(->> input
find-basins
(map count)
(sort >)
(take 3)
(reduce *)))
#'day9/part-2
day9> (part-2 (read-input))
1134
This grants us the second gold star!
Day 9 thoughts
It may seem that this task was easy, but that’s the beauty of blogging - you never know how hard it was to me in reality. Honestly, it wasn’t as straightforward as I’ve described here, as I was uncertain how to find basins correctly. For example, there’s the following line:
Locations of height 9 do not count as being in any basin, and all other locations will always be part of exactly one basin.
I’ve assumed that there might be some basins that are connected, and thus share some lowest points, but no. However, by doing this check I got the wrong answer and was unsure why. Until I’ve accidentally removed this check and got the right one. Interestingly enough, with or without this check the code worked perfectly with the example input. So yeah…
Well, that’s all for now, see you tomorrow!