Advent of Code: Day 5
Looking at my post schedule, I’m starting to think that if the event will go as good as it goes right now, I’ll write more posts than I wrote since I’ve started this blog. Oh well. Maybe I need a separate section/category for this stuff. But no time for this right now, so maybe in the future.
Also, I’ve figured out why my RSS feeds for tags contained the same feed as the main one and fixed that.
So if you’re reading this blog through an RSS, and you would like to only see some specific posts, you now can subscribe to a specific tag or category.
For example, for a Clojure-specific feed, you can subscribe to https://andreyor.st/tags/clojure/feed.xml.
Or for the Emacs-specific feed https://andreyor.st/categories/emacs/feed.xml.
Hope this will be useful. Now, let’s get to the task.
Hydrothermal Venture
We’ve reached a field of hydrothermal vents on the ocean floor, and to avoid all of these to prevent our submarine from drowning. Our example puzzle input looks like this:
0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2
These are the x,y coordinates mapped to another x,y coordinates, which determine where the vent starts and ends.
Our first task requires us to find which vents overlap, considering only horizontal vents.
I wonder what will wait for us in part two.
So, for the example input, the diagram that shows which vents overlap looks like this:
.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....
Each 1 means that there’s a vent, and 2 means that two vents overlap.
Let’s write an input parsing function:
day5> (ns day5)
nil
day5> (require '[aoc-commons :refer [parse-long]]
'[clojure.string :as str])
nil
day5> (defn parse-coordinates [line]
(let [[_ x1 y1 x2 y2]
(re-matches #"(\d+),(\d+)\s+->\s+(\d+),(\d+)" line)]
[[(parse-long x1) (parse-long y1)]
[(parse-long x2) (parse-long y2)]]))
#'day5/parse-coordinates
Now, we can define the example input, and the read-input function:
day5> (def example-input
"0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2")
#'day5/example-input
day5> (defn read-input []
(->> #_"inputs/day5"
#_slurp
example-input
str/split-lines
(map parse-coordinates)))
#'day5/read-input
With that, we can get to work.
First, we need to keep only non-diagonal lines:
day5> (defn keep-non-diagonal [coordinates]
(filter (fn [[[x1 y1] [x2 y2]]]
(or (= x1 x2) (= y1 y2)))
coordinates))
#'day5/keep-non-diagonal
Next, we can build the lines. Since our lines are either horizontal or vertical, we can use a simple list comprehension to build them:
day5> (defn build-line [[[x1 y1] [x2 y2]]]
(let [[x1 x2] (sort [x1 x2])
[y1 y2] (sort [y1 y2])]
(for [x (range x1 (inc x2))
y (range y1 (inc y2))]
[x y])))
#'day5/build-line
Now, we need some kind of data structure, where we can keep all lines, and compute their overlapping parts.
Luckily for us, Clojure comes with an amazing library for data manipulation and transformation and has exactly the function we need.
This function is called frequencies.
It accepts a collection and counts how many there are entries for each element of the collection.
For example:
day5> (frequencies "ваыв")
{\в 2, \а 1, \ы 1}
You can see that the letter в is associated with 2, and it is exactly the amount of times this letter appeared in the string.
We can apply that to our vent coordinates.
Let’s write a reducing function:
day5> (defn mark-line [field line]
(let [fr (frequencies line)]
(merge-with (fnil + 1) field fr)))
#'day5/mark-line
day5> (defn mark-lines [field lines]
(reduce mark-line field lines))
#'day5/mark-lines
To illustrate how it works let’s use it with some fake coordinates:
day5> (mark-lines {} (map build-line [[[0 0] [0 5]]
[[2 0] [2 5]]
[[0 2] [5 2]]]))
{[2 2] 2,
[0 0] 1,
[2 3] 1,
[2 5] 1,
[0 5] 1,
[4 2] 1,
[5 2] 1,
[0 3] 1,
[2 4] 1,
[0 2] 2,
[2 0] 1,
[0 4] 1,
[2 1] 1,
[1 2] 1,
[3 2] 1,
[0 1] 1}
You can see that there are two overlapping vents for this input at points [2 2] and [0 2].
We can illustrate this better by writing a render function:
day5> (defn render [size points]
(let [field (vec (repeat size (vec (repeat size "."))))]
(->> points
(reduce (fn [field [[x y] val]]
(assoc-in field [x y] (str val)))
field)
(apply map vector)
(map str/join)
(map (partial str ";; "))
(str/join "\n")
println)))
#'day5/render
day5> (render 10 (mark-lines {} (map build-line [[[0 0] [0 5]]
[[2 0] [2 5]]
[[0 2] [5 2]]])))
;; 1.1.......
;; 1.1.......
;; 212111....
;; 1.1.......
;; 1.1.......
;; 1.1.......
;; ..........
;; ..........
;; ..........
;; ..........
nil
Finally, we need to calculate the number of entries greater than 1.
Let’s wrap everything into a function:
day5> (render 10 (create-field (read-input)))
;; .......1..
;; ..1....1..
;; ..1....1..
;; .......1..
;; .112111211
;; ..........
;; ..........
;; ..........
;; ..........
;; 222111....
nil
day5> (part-1 (read-input))
5
This produces the correct answer for the test input and by changing the input to the real one we get another correct answer. Now, let’s do this including the diagonal lines?
Part two
And, yes, part two really is about diagonal lines! Should be pretty straightforward.
We need a function that builds a diagonal line:
day5> (defn build-diagonale-line [[[x1 y1] [x2 y2]]]
(when (= (Math/abs (- x1 x2)) (Math/abs (- y1 y2)))
(let [xdir (if (> 0 (- x2 x1)) -1 1)
ydir (if (> 0 (- y2 y1)) -1 1)]
(loop [line [[x1 y1]]]
(let [[x y] (last line)]
(if (and (not= x x2) (not= y y2))
(recur (conj line [(+ x xdir) (+ y ydir)]))
line))))))
#'day5/build-diagonale-line
This is a total mess, but it works.
First, we determine if a pair of coordinates is strictly diagonal.
This is achieved with the ( (Math/abs (- x1 x2)) (Math/abs (- y1 y2)))= expression.
Next, if the line is diagonal, we check if the coordinates are in the correct order.
Finally, we loop, incrementing the starting position until we reach the end coordinate.
However, this function only accounts for the diagonal lines. Luckily, we’ve already created a function that creates a field with horizontal and vertical lines, so we can just merge two. Here’s an illustration:
day5> (let [input (read-input)]
(->> input
(keep build-diagonale-line)
(mark-lines (create-field input))
(render 10)))
;; 1.1....11.
;; .111...2..
;; ..2.1.111.
;; ...1.2.2..
;; .112313211
;; ...1.2....
;; ..1...1...
;; .1.....1..
;; 1.......1.
;; 222111....
nil
This looks exactly like the diagram from the task! Here’s the final solution:
day5> (defn part-2 [input]
(->> input
(keep build-diagonale-line)
(mark-lines (create-field input))
vals
(filter #(> % 1))
count))
#'day5/part-2
day5> (part-2 (read-input))
12
And it works on the real input as well. Great!
Day 5 thoughts
The second part of the task gave me some trouble initially, as I couldn’t figure out the correct way to compute diagonals. But after I’ve figured it out, it was pretty straightforward to complete!
I really like how Clojure comes with a lot of functions in the standard library for data manipulation and functional programming.
For example, another thing that you may haven’t noticed was the use of fnil.
It’s a special function, that accepts a function, and the default value, and returns a nil safe variant of the original function.
In case of the mark-line function, I’ve use (fnil + 1) which effectively created a + function that uses 1 if it gets a nil as a first argument.
Paired with frequencies and merge-with this made it really trivial to find all intersections.
That’s all from me for today, and see you tomorrow!