Advent of Code 2021  full event
Originally these were all separate posts, but this generated way too many entries in the feed, so I’ve decided to put these into a single one. I’ve kept the content as is, and this very post originally contained the following message:
This is just a quick update on the upcoming posts schedule.
Last year I’ve decided to participate in Advent of Code 2020. It was a bit late decision, as I’ve started doing tasks around December 14th, and was burnt out by the pace I had to maintain to keep up with the others. It didn’t go so well, and I only completed tasks for the first 14 days, the last submission was on December 28, and I’ve got 28 gold stars total^{1}. It’s a shame that I couldn’t finish the event in time, but it was fun, and this year I’ve decided not to repeat the same mistake and join the event when it starts.
For those unfamiliar with AOC, this event usually has some pretty interesting puzzles, and some kind of story, that progresses each day, and each task leads to another task and the story continues. And since the tasks are pretty interesting, I’ve decided to start a small series of posts, where I express how I’ve approached the task, and what tricks I’ve used to accomplish it.
I hope that I’ll be able to maintain the pace, and publish one post per day through the first 25 days of December until the event is finished. My blog is mostly built around Fennel and Emacs, but I’ll be doing the tasks in Clojure, as I feel that I’m giving this language less time than I should. I’ve also thought about using another language, like Erlang/Elixir or Common Lisp, but decided to go with Clojure, because learning a new language, and going through puzzles, while writing posts about both topics, and doing normal life stuff is a bit too much to handle. So Clojure it is.
I’m not sure if I’ll be able to finish all puzzles, but we’ll see how it goes. If you’re a programmer, and you never participated in AOC, I highly recommend you to  it’s great fun and a good challenge!
That’s all for now, see you on December 1st!
Everything that follows, was taken from the posts and adjusted a bit for a better reading experience. Enjoy!
Welcome to the series of posts on this year’s Advent of Code event!
This year, to keep myself motivated, I decided to write a small post each day, in which I’ll describe the way I’ve approached this day’s AOC puzzle.
As I’ve mentioned I’ll be solving puzzles in Clojure, (usually) formatting the code as can be seen in the REPL.
So if you see a code block that starts with day1>
, it means that we’re inside the REPL, and in a day1
namespace.
And, without further ado, let’s begin!
Day 1  Sonar Sweep
The first task is about calculating the rate at which the depth is increasing. Should be pretty simple!
For the given example input:
199
200
208
210
200
207
240
269
260
263
We need to count the number of times a depth measurement increases from the previous measurement.
This means, that we need to check if 200
is greater than 199
, then that 208
is greater than 200
, and so on.
Sounds like a job for reduce
!
Let’s write such algorithm, and only partially supply the input:
user> (ns day1)
nil
day1> (reduce (fn [res [current next]]
(+ res (if (> next current) 1 0)))
0
[[199 200] [200 208]])
2
This correctly returns 2
, now let’s feed it the whole input!
But we need to regroup the input first, so there will be a group of two for each number.
Luckily we have a function just for that, called partition
:
day1> (partition 2 1 [199 200 208 210 200 207 240 269 260 263])
((199 200)
(200 208)
(208 210)
(210 200)
(200 207)
(207 240)
(240 269)
(269 260)
(260 263))
Sweet!
Let’s put our reduce
into a function that does this transformation, and plug this input into it!
day1> (defn part1 [input]
(reduce (fn [res [current next]]
(+ res (if (> next current) 1 0)))
0
(partition 2 1 input)))
#'day1/part1
day1> (part1 [199 200 208 210 200 207 240 269 260 263])
7
And it returns the correct result for the test input! Now we can try with a real one.
I’ll not be sharing the whole input in the blog, but you can always see it in my GitHub repo for AoC.
First, we need a function, that will read and parse the input file:
day1> (require '[clojure.string :as str])
nil
day1> (defn readinput []
(>> "inputs/day1"
slurp
str/splitlines
(map #(Integer/parseInt %))))
I’m putting all input files into the inputs
directory, named after the respecting day of the event.
In this case, it’s inputs/day1
.
We slurp
this file, and splitlines
so there is a sequence of strings, each representing a line of the file.
Then we map
over it with an anonymous function, that uses Integer/parseInt
a Java method that parses the string as an integer.
This may throw a NumberFormatException
of course, but I trust that the author of the event provides a valid input.
Now, let’s plug this input into our part1
function:
day1> (part1 (readinput))
1215
And we surely get the right answer!
I’ve also realized that instead of reduce
we can use filter
and just count the amount of remaining numbers, like this:
day1> (defn part1 [input]
(>> input
(partition 2 1)
(filter (partial apply <))
count))
#'day1/part1
day1> (part1 (readinput))
1215
It yields the same result but is much more concise. I’ll keep this solution.
Time for part two.
Part two
Part two changes how the calculations are done a bit.
Now we need to do a sliding sum of groups of three.
This means, that for the test input, we need to check if the sum of the first three numbers, in our case these are 199
, 200
, 208
, is smaller than the sum of three numbers, starting from the second number: 200
, 208
, 210
.
This grouping is again can be achieved by partitioning:
day1> (partition 3 1 [199 200 208 210 200 207 240 269 260 263])
((199 200 208)
(200 208 210)
(208 210 200)
(210 200 207)
(200 207 240)
(207 240 269)
(240 269 260)
(269 260 263))
Now we just need to sum these subsequences with a map:
day1> (>> [199 200 208 210 200 207 240 269 260 263]
(partition 3 1)
(map (partial apply +)))
(607 618 618 617 647 716 769 792)
And we can apply our part1
function on the new input:
day1> (>> [199 200 208 210 200 207 240 269 260 263]
(partition 3 1)
(map (partial apply +))
(part1))
5
Again, we get a correct answer for the test input, so let’s put this into a function, and pass it a real one:
day1> (defn part2 [input]
(>> input
(partition 3 1)
(map (partial apply +))
part1))
#'day1/part2
day1> (part2 (readinput))
1150
And we get a correct answer!
Day 1 thoughts
This wasn’t hard, but no need to relax yet. More complex tasks are surely on the way!
I hope you’ve liked this short post of me describing the thought process for solving this day’s task. I’ll (hopefully) be publishing such posts each day, up to the event’s end. We’ll see how far I’ll manage to get!
Day 2  Dive!
This task is about navigating a submarine. If I remember correctly, something similar was in the last year’s AoC. This year, we’re given a set of instructions in the following form:
forward 5
down 5
forward 8
up 3
down 8
forward 2
Where forward
increases the horizontal position, and up
and down
decrease and increase depth respectively.
Our goal is to compute the end coordinate and then compute its product, after following all these commands.
Let’s write a function that accepts the current position, direction, and the amount we need to move as a vector.
day1> (ns day2)
nil
day2> (defmulti move (fn [_ [direction _]] direction))
#'day2/move
I’ve decided to use a multimethod here. Multimethods in Clojure are simple functions, that dispatch to a concrete body based on the dispatching function. This can be done by hand in any other language, in Clojure, the dispatching process is automated for you. I’ve chosen a multimethod without any particular reason, I just thought that it will be handy if we will be able to add new behavior to already existing function.
So let’s write movement methods. Since our input is a string, we will dispatch on strings, representing the direction:
day2> (defmethod move "forward" [[x y] [_ amount]] [(+ x amount) y])
#multifn[move 0x23444b67]
day2> (defmethod move "up" [[x y] [_ amount]] [x ( y amount)])
#multifn[move 0x23444b67]
day2> (defmethod move "down" [[x y] [_ amount]] [x (+ y amount)])
#multifn[move 0x23444b67]
We’re simply expressing the movement rules from the task. Let’s try it on the example input:
day2> (> [0 0]
(move ["forward" 5])
(move ["down" 5])
(move ["forward" 8])
(move ["up" 3])
(move ["down" 8])
(move ["forward" 2]))
[15 10]
This gives us the correct coordinate and multiplying its x
and y
parts produces the expected result of 150
.
Now we need to read the real input and transform it into such form: [[direction amount] ...]
, but this time, let’s write a proper parselong
function:
day2> (ns aoccommons)
nil
aoccommons> (defn parselong [s]
(if (string? s)
(try
(Long/valueOf s)
(catch NumberFormatException _ nil))
(throw (IllegalArgumentException.
(format "Expected string, got %s" (some> s class .getName))))))
I’m putting it to the aoccommons
namespace, so I could reuse it in another days.
Luckily this function will soon be available in the next Clojure release.
aoccommons> (inns 'day2)
#namespace[day2]
day2> (require '[commons :refer [parselong]]
'[clojure.string :as str])
nil
day2> (>> "inputs/day2"
slurp
str/splitlines
(map #(str/split % #"\s+"))
(map #(update % 1 parselong))
(take 3))
(["forward" 7] ["forward" 9] ["forward" 9])
Seems to work so far  let’s put it into the function readinput
.
Now we need to automate the computation we did earlier.
Again, similarly to the previous day’s task, reduce
is the function we need:
day2> (defn part1 [input]
(>> input
(reduce move [0 0])
(apply *)))
#'day2/part1
Let’s plug the input, and see if it produces the correct answer:
day2> (part1 (readinput))
2036120
And this is indeed the answer we’re expected to get! Let’s move to part two.
Part two
Last year, we misinterpreted the movement instructions, which required us to rework the algorithm a bit, and accord for the rotation.
This year the situation is very similar.
Turns out that up
and down
change the aim
parameter, and forward
moves accordingly to it, by multiplying aim
to the amount we need to move forward and adding it to the depth.
Let’s rewrite the moving function:
day2> (defn moveandaim [[x y aim] [direction amount]]
(case direction
"up" [x y ( aim amount)]
"down" [x y (+ aim amount)]
"forward" [(+ x amount) (+ y (* aim amount)) aim]))
#'day2/moveandaim
Since we know, that we won’t need to expand our movement, and we only needed to change how we move.
Multimethod was overkill after all, but, well, you never know.
The main difference between this way of doing the dispatch, and when using the multimethod, is that we can extend the behavior of the multimethod without modifying the existing code.
In the case of this function, if we were to add, say, backward
, we would need to change the source code of this function.
With multimethods, we would just add another defmethod
.
But in the case of this particular situation there’s no need for it, so case
will do.
Let’s plug it into reduce
:
day2> (>> (readinput)
(reduce moveandaim [0 0 0])
(apply *))
2196947010440
And… this is not the correct result. Why? let’s see, we’re producing seemingly correct coordinates on the test input:
day2> (reduce moveandaim
[0 0 0]
[["forward" 5] ["down" 5] ["forward" 8] ["up" 3] ["down" 8] ["forward" 2]])
[15 60 10]
And multiplying 15
and 60
produces the correct answer for the example input.
So why it is not correct when applied to the real input?
Let’s plug the test input into our previous code:
day2> (>> [["forward" 5] ["down" 5] ["forward" 8] ["up" 3] ["down" 8] ["forward" 2]]
(reduce moveandaim [0 0 0])
(apply *))
9000
It is indeed incorrect.
But now I see the issue, I forgot that we’re multiplying all elements in the resulting vector, and now this vector has a third element  the aim
.
And in the case of the test input, it is equal to 10
, thus the result is ten times bigger than the expected one.
Let’s remove it before computing the result with take
:
day2> (defn part2 [input]
(>> input
(reduce moveandaim [0 0 0])
(take 2)
(apply *)))
#'day2/part2
day2> (part2 (readinput))
2015547716
Now, that’s the correct result.
Day 2 thoughts
The task wasn’t hard.
I’ve made a simple mistake at the end when I’ve computed the product of depth and horizontal coordinate and forgot to remove the aim
from the equation.
Multimethod was a bit overkill, but I think it’s still a nice way to show that the same thing can be achieved in two ways, and one is a more general version of another.
Now, when I think of it, it seems that I tend to use tuples far more than dictionaries.
For example, I could use an associative structure with :depth
, and :horizontal
keys in it, and completely avoid the bug with multiplication, and any calls to apply
for that matter.
Maybe I should think more in terms of associative structures for the next tasks.
Other than that, the task was pretty straightforward, and I’m curious to see what’s coming next.
Day 3  Binary Diagnostic
This task is once again themed around the submarine, we’re using to find the keys. But today we need to perform diagnostics of the submarine systems. The diagnostics came as the following example input:
00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010
It’s a list of binary numbers, and we need to work with those via a specific set of rules.
First, we need to take only the first column of each row, and count how many zeroes and ones are there to compute the most common bit.
In the case of the first column, there are seven ones, and five zeroes, and the most common bit is 1
.
We need to repeat that for each column, and the resulting bits will be the number we’re looking for.
Let’s prepare the data.
For the data format, I think a sequence of vectors of integers will do. We can transform the test input string to such format as follows:
day2> (ns day3)
nil
day3> (require '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day3> (>> "00100\n11110\n10110\n10111\n10101\n01111\n00111\n11100\n10000\n11001\n00010\n01010"
str/splitlines
(map seq)
(map #(mapv (fn [c] (parselong (str c))) %)))
([0 0 1 0 0]
[1 1 1 1 0]
[1 0 1 1 0]
[1 0 1 1 1]
[1 0 1 0 1]
[0 1 1 1 1]
[0 0 1 1 1]
[1 1 1 0 0]
[1 0 0 0 0]
[1 1 0 0 1]
[0 0 0 1 0]
[0 1 0 1 0])
day3> (def testdata *1)
#'day3/testdata
OK, this appears to look correct. Now, we need to write an algorithm that will count bits in the given column:
day3> (>> testdata
(map #(get % 0))
sort
(splitwith (partial = 0))
(map count))
(5 7)
This should do it.
We map the get
function over each of the vectors to get the 0th bit.
Then, we sort the result, so all zeroes go before all ones, and split it with the (partial = 0)
function, which gives us the result of [(0 0 0 0 0) (1 1 1 1 1 1 1)]
.
Finally, we map
the count
function, to compute the amount of each bit, producing the final result of (5 7)
.
But it’s hard to remember what these numbers are, e.g. you can’t say if there’s 5
zeroes of 5
ones, by looking at the code.
Your only hint is a call to sort
, which sorts zeroes before ones, but it’s hard to grasp at a glance, so let’s put this into a table.
We also need to make 0
argument to get
a parameter, so here’s our function:
day3> (defn countbits [bitn input]
(>> input
(map #(get % bitn))
sort
(splitwith (partial = 0))
(map count)
(zipmap [:ones :zeroes])))
#'day3/countbits
Finally, to get the most common bit we need to map
this function for every index in our vectors.
To obtain the size of the vector we can count
the first
vector from the input, and use it to create a range
, that we will map
over:
day3> (defn mostcommonbits [input]
(>> input
first
count
range
(map #(countbits % input))))
#'day3/mostcommonbits
Calling this function with our test input produces the following sequence of maps:
day3> (mostcommonbits testdata)
({:ones 5, :zeroes 7}
{:ones 7, :zeroes 5}
{:ones 4, :zeroes 8}
{:ones 5, :zeroes 7}
{:ones 7, :zeroes 5})
This appears to be correct, but we’re missing the final step of converting this to a vector of the most common bits.
To do this, we just need one extra map
over this list, that compares ones and zeroes, and chooses the most common one:
day3> (defn mostcommonbits [input]
(>> input
first
count
range
(map #(countbits % input))
(map (fn [{:keys [zeroes ones]}]
(if (> zeroes ones) 1 0)))))
#'day3/mostcommonbits
day3> (mostcommonbits testdata)
(1 0 1 1 0)
This number is the correct one for the given example input. But it’s not it yet.
We need to compute another number, which consists of the lest common bits.
We could change the predicate in the mostcommonbits
function, and create the leastcommonbits
function, but it would be a waste.
All we need is to flip all bits in the number we got:
day3> (defn flipbit [b]
(if (= b 0) 1 0))
#'day3/flipbit
day3> (map flipbit *2)
(0 1 0 0 1)
And this is indeed the correct number.
Finally, we need to compute their product. To do so, we need to parse the binary representation into a decimal first. Let’s concatenate our lists to string and use default Java method for parsing:
day3> (* (Long/parseLong (str/join '(1 0 1 1 0)) 2)
(Long/parseLong (str/join '(0 1 0 0 1)) 2))
198
This is the correct result. Let’s just wrap the whole thing into a function, and test with the real input:
day3> (defn readinput []
(>> "inputs/day3"
slurp
str/splitlines
(map seq)
(map #(mapv (fn [c] (parselong (str c))) %))))
#'day3/readinput
day3> (defn part1 [input]
(let [gamma (mostcommonbits input)
epsilon (map flipbit gamma)]
(* (Long/parseLong (str/join gamma) 2)
(Long/parseLong (str/join epsilon) 2))))
#'day3/part1
day3> (part1 (readinput))
3885894
And we got the correct result! Time for part two.
Part two
Whoa.. that’s a lot of text! And numbers… Anyway, let’s see what’s up with all of this new information.
The idea is that we need to compute two more numbers, but now, we need to filter out some numbers based on a condition. To get the first number, we need to determine the most common bit for the given position and keep only such rows, that contain that number in the same position. The second number is exactly the same, except we need to use the least common bit. Should be pretty easy. Let’s start by writing a function, that determines which bit we need to use as criteria for filtering:
day3> (defn bitcriteria [type {:keys [ones zeroes]}]
(case type
:oxygen (if (< zeroes ones) 0 1)
:CO2 (if (< zeroes ones) 1 0)))
#'day3/bitcriteria
Interestingly enough, the task explicitly mentions, that if we got the same amount of ones and zeroes, we need to choose 1
for oxygen, and 0
for CO2.
I haven’t accounted for this case in the first part, and I haven’t even thought about it, to be frank.
And even though the logic above doesn’t have an explicit check for this case as well, it works perfectly along with the rules:
day3> (bitcriteria :oxygen {:zeroes 4 :ones 4})
1
day3> (bitcriteria :CO2 {:zeroes 4 :ones 4})
0
I’m using the same format as returned by the countbits
function here.
Now, all we need is to implement the algorithm:
day3> (defn calculate [type input]
(let [total (count (first input))] ; ①
(loop [n 0
numbers input]
(let [bits (countbits n numbers)
criteria (bitcriteria type bits) ; ②
res (filter #(= (get % n) criteria) numbers)] ; ③
(if (= 1 (count res))
(first res)
(when (< n total)
(recur (inc n) res)))))))
#'day3/calculate
That’s a lot of code, but the job this function does is pretty simple.
We compute the total amount of bits we need to check at ①.
Then we go into the loop
, where we will check each bit n
, starting from 0
.
We count all bits in a given position and compute the criteria
②.
Finally, we filter only those rows, that have the same bit as the criteria
bit in the position of n
③.
At this point, we have all rows that match the criteria. If we only got 1 row, that’s the result we need. If not, we go into the next iteration with the current amount of rows and check the next bit.
Let’s plug this into a function, and see if it’s correct for the test input:
day3> (defn part2 [input]
(let [oxygen (calculate :oxygen input)
co2 (calculate :CO2 input)]
(* (Long/parseLong (str/join oxygen) 2)
(Long/parseLong (str/join co2) 2))))
#'day3/part2
day3> (part2 testdata)
230
And it is correct! Now we can check this with the real input:
day3> (part2 (readinput))
4375225
And we get another gold star, as this is the right answer for my input!
Day 3 thoughts
Definitively was a bit harder than the previous day, but still a lot of fun! After I looked at my solution at the end of the day, I’ve realized that it wasn’t necessary to convert strings to numbers, as I could compare everything that way. But it wasn’t too much extra works, so that’s that.
Overall, I think my code is a bit complex, but I’m not sure how to improve it.
Funnily enough, while writing this I’ve noticed that the implementation of mostcommonbits
was wrong, as I’ve used <
instead of >
, but the resulting answer was still correct, as the second number is just the inverse of the first one.
Day 4  Giant Squid
The winter just has started, and it’s already the first weekend! The time goes pretty fast this time of the year. I guess it’s because there’s so much going on! There’s always some kind of rush at the end of the year at work. Everyone is preparing for the upcoming holidays, purchasing gifts, and buying delicious food and drinks upfront. I’m also preparing for the upcoming talk at this year’s Fennel conf. And of course, there’s Advent of Code to spice everything up, hehe!
Speaking of which, here’s our next game!
Today we’re got ourselves into some wild situation  a giant squid has attached itself to the outside of your submarine and wants to play bingo!
I’m sure that everyone is familiar whit this kind of game, though this particular one usually has several names in various countries. The closest alternative, widely known in my country is Lotto (Italiano)^{2}.
The test puzzle input looks like this:
7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1
22 13 17 11 0
8 2 23 4 24
21 9 14 16 7
6 10 3 18 5
1 12 20 15 19
3 15 0 2 22
9 18 13 17 5
19 8 7 25 23
20 11 10 24 4
14 21 16 12 6
14 21 17 24 4
10 16 15 9 19
18 8 23 26 20
22 11 13 6 5
2 0 12 3 7
The first row determines the order in which we need to mark numbers on the board. The twist is that we have several boards, and we need to find the first one that wins. Let’s parse this input into a data structure that will allow us to work with it.
day3> (ns day4)
nil
day4> (require '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day4> (def testinput "7,4,9,5,11,17,23...") ; rest of the input is omitted
#'day4/testinput
First, let’s parse the first line:
day4> (defn parsedraws [lines]
(map parselong (str/split lines #",")))
#'day4/parsedraws
day4> (parsedraws (> testinput str/splitlines first))
(7 4 9 5 11 17 23 2 0 14 21 24 10 16 13 6 15 25 12 22 18 20 8 19 3 26 1)
Next we should parse the boards. I’m thinking of vector of vectors of numbers, like this:
[[ 2 13 17 11 0]
[ 8 2 23 4 24]
[21 9 14 16 7]
[ 6 10 3 18 5]
[ 1 12 20 15 19]]
For a single board. And since we have many boards, we would have another vector around them. Let’s write a function that does that:
day4> (defn preparerow [row]
(mapv parselong
(> row
str/trim
(str/split #"\s+"))))
#'day4/preparerow
day4> (defn parseboards [lines]
(>> lines
(remove empty?)
(partition 5)
(mapv (partial mapv preparerow))))
#'day4/parseboards
day4> (parseboards (>> testinput str/splitlines (drop 1)))
[[[22 13 17 11 0]
[8 2 23 4 24]
[21 9 14 16 7]
[6 10 3 18 5]
[1 12 20 15 19]]
[[3 15 0 2 22]
[9 18 13 17 5]
[19 8 7 25 23]
[20 11 10 24 4]
[14 21 16 12 6]]
[[14 21 17 24 4]
[10 16 15 9 19]
[18 8 23 26 20]
[22 11 13 6 5]
[2 0 12 3 7]]]
Now, we just need to combine the two and return a table, where we will have our draws, and boards under the respecting keys:
day4> (defn readinput []
(let [lines (>> #_#_"inputs/day4" ; We'll need this when we
slurp ; will work with real input
testinput
str/splitlines)]
{:draws (parsedraws (first lines))
:boards (parseboards (drop 1 lines))}))
#'day4/readinput
day4> (readinput)
{:draws
(7 4 9 5 11 17 23 2 0 14 ...),
:boards
[[[22 13 17 11 0]
[8 2 23 4 24]
[21 9 14 16 7]
[6 10 3 18 5]
[1 12 20 15 19]]
...]}
Parsing the input itself was a neat task, isn’t it? Now, we can play Bingo!
To mark the number on a board, I’ll be replacing the number with a nil
.
Anything but nil will do, of course, but we don’t really care about numbers we’ve marked, so it’s OK to replace them with something that we can easily distinguish.
day4> (defn markboard [number board]
(mapv #(mapv (fn [x] (if (= number x) nil x)) %) board))
#'day4/markboard
day4> (markboard 5 [[1 2 3]
[4 5 6]
[7 8 9]])
[[1 2 3] [4 nil 6] [7 8 9]]
I hope you get the idea.
Next, we need to check if the board won.
The board wins, when any of the rows have all numbers marked, which in our case means, a vector with every element equal to nil
.
However, the board also wins, when any of the columns are marked, which means we need to check columns as well.
But since this is a simple matrix, we can just rotate it, and check if any of the rows, that previously were columns are fully marked.
To rotate the board we can use this trick:
day4> (apply mapv vector [[1 2 3]
[4 5 6]
[7 8 9]])
[[1 4 7]
[2 5 8]
[3 6 9]]
As you can see, the board is rotated!
This happens because when we apply
the mapv
function to a vector of vectors we essentially get this:
(mapv vector [1 2 3] [4 5 6] [7 8 9])
This means that vector
will be called with 1
, 4
, and 7
, then with 2
, 5
, and 8
, and finally whit 3
, 6
, 9
, producing a new matrix, which is a rotated version of the original.
Knowing that, we can implement the checkboard
function as follows:
day4> (defn rotate [board]
(apply mapv vector board))
#'day4/rotate
day4> (defn checkboard [board]
(when (or (some (partial every? nil?) board)
(some (partial every? nil?) (rotate board)))
board))
#'day4/checkboard
day4> (checkboard [[1 2]
[3 4]])
nil
day4> (checkboard [[nil nil]
[3 4]])
[[nil nil] [3 4]]
day4> (checkboard [[nil 2]
[nil 4]])
[[nil 2] [nil 4]]
As you can see, this function returns nil
when the board doesn’t have any winning rows or columns, and returns the board itself, if it has any rows or columns that are fully marked.
Finally, we need a function, that will draw the numbers, and fill our boards, checking if any of the boards won. Should be pretty simple:
day4> (defn findwinningboard [draws boards]
(loop [[number & draws] draws
boards boards]
(let [boards (mapv (partial markboard number) boards)]
(iflet [winningboard (some checkboard boards)]
{:winnumber number
:board winningboard}
(recur draws
boards)))))
#'day4/findwinningboard
Now, we can feed this function our draws
and boards
, and see which board wins, and which number was the last one:
day4> (defn calculateresult [{:keys [winnumber board]}]
(* winnumber
(>> board
flatten
(filter number?)
(apply +))))
#'day4/calculateresult
day4> (defn part1 [{:keys [draws boards]}]
(>> boards
(findwinningboard draws)
(calculateresult)))
#'day4/part1
day4> (part1 (readinput))
4512
This is the correct result for the example input from the puzzle. Trying it on the real input yields another correct result, which means we did everything correctly. Let’s see what twist waits for us in part two!
Part two
The gimmick of the second part is that we want to let the giant squid win this time. Perhaps it would be pleased and leave our submarine.
In order to do that, we just need to find the board that wins the last. This is a relatively small change from our existing algorithm  we need to keep all nonwinning boards, and repeat games with them until nothing is left. Once no boards are left, we can take the last board from the previous game, and it will be the board that wins last:
day4> (defn findlastwinningboard [draws boards]
(loop [[number & draws] draws
boards boards]
(let [boards (mapv (partial markboard number) boards)
nonwinning (remove checkboard boards)]
(if (empty? nonwinning)
{:winnumber number
:board (last boards)}
(recur draws
nonwinning)))))
#'day4/findlastwinningboard
day4> (defn part2 [{:keys [draws boards]}]
(>> boards
(findlastwinningboard draws)
(calculateresult)))
#'day4/part2
day4> (part2 (readinput))
1924
The result is correct for the test data, and when tried with the real one, it remains correct, which is great!
Day 4 thoughts
This task was daunting at first, given that the giant squid could drag the submarine anywhere in the ocean, and we’d be completely lost, but we’ve made it through! When I saw the boards, I’ve immediately thought: “yeah, we’re going to rotate some matrix today”, but then I’ve realized it’s quite easy to do. The code feels a bit too imperative for my liking, but I don’t see how I can improve it right now. And it works so for now, I think that will do.
Day 5  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 '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day5> (defn parsecoordinates [line]
(let [[_ x1 y1 x2 y2]
(rematches #"(\d+),(\d+)\s+>\s+(\d+),(\d+)" line)]
[[(parselong x1) (parselong y1)]
[(parselong x2) (parselong y2)]]))
#'day5/parsecoordinates
Now, we can define the example input, and the readinput
function:
day5> (def exampleinput
"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/exampleinput
day5> (defn readinput []
(>> #_"inputs/day5"
#_slurp
exampleinput
str/splitlines
(map parsecoordinates)))
#'day5/readinput
With that, we can get to work.
First, we need to keep only nondiagonal lines:
day5> (defn keepnondiagonal [coordinates]
(filter (fn [[[x1 y1] [x2 y2]]]
(or (= x1 x2) (= y1 y2)))
coordinates))
#'day5/keepnondiagonal
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 buildline [[[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/buildline
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 markline [field line]
(let [fr (frequencies line)]
(mergewith (fnil + 1) field fr)))
#'day5/markline
day5> (defn marklines [field lines]
(reduce markline field lines))
#'day5/marklines
To illustrate how it works let’s use it with some fake coordinates:
day5> (marklines {} (map buildline [[[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]]
(associn field [x y] (str val)))
field)
(apply map vector)
(map str/join)
(map (partial str ";; "))
(str/join "\n")
println)))
#'day5/render
day5> (render 10 (marklines {} (map buildline [[[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 (createfield (readinput)))
;; .......1..
;; ..1....1..
;; ..1....1..
;; .......1..
;; .112111211
;; ..........
;; ..........
;; ..........
;; ..........
;; 222111....
nil
day5> (part1 (readinput))
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 builddiagonaleline [[[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/builddiagonaleline
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 (readinput)]
(>> input
(keep builddiagonaleline)
(marklines (createfield 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 part2 [input]
(>> input
(keep builddiagonaleline)
(marklines (createfield input))
vals
(filter #(> % 1))
count))
#'day5/part2
day5> (part2 (readinput))
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 markline
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 mergewith
this made it really trivial to find all intersections.
Day 6  Lanternfish
New task!
Today we’re watching how a massive school of glowing lanternfish swims past our submarine.
There are a lot of them, so their reproduction rate must be growing really fast, or, as the task explicitly mentions, exponentially fast.
Our task is to find out how many of the species there will be after 80
days, based on these rules:
 Each fish is represented as a number of days before reproduction, for example,
3,4,3,1,2
 Each day we subtract
1
from such counter:2,3,2,0,1
 Each time a fish goes below
0
it’s counter get’s reset to6
, and a new fish added to the list with the counter value of8
:1,2,1,6,0,8
After 18
days we’ll get such generation: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8
, total of 26 fish.
Now, this seems to grow very fast, but let’s play dumb and solve this directly following these rules. First, as usual, let’s parse the input:
day5> (ns day6)
nil
day6> (require '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day6> (def exampleinput "3,4,3,1,2")
#'day6/exampleinput
day6> (defn readinput []
(map parselong
(> #_#_"inputs/day6"
slurp
exampleinput
str/trimnewline
(str/split #","))))
#'day6/readinput
Now, we can write a function that will tick
each fish:
day6> (defn tick [generation]
(map dec generation))
#'day6/tick
day6> (tick (readinput))
(2 3 2 0 1)
day6> (tick *1)
(1 2 1 1 0)
You can see that it doesn’t do any special logic regarding negative values.
We handle these in the populate
function:
day6> (defn populate [generation]
(concat (map #(if (neg? %) 6 %) generation)
(repeat (count (filter neg? generation)) 8)))
#'day6/populate
day6> (populate (tick (readinput)))
(2 3 2 0 1)
day6> (populate (tick *1))
(1 2 1 6 0 8)
day6> (populate (tick *1))
(0 1 0 5 6 7 8)
As can be seen, after first tick
no new fish were added, but on the next tick
, populate
changed fourths fish to 6
, and added a new fish of 8
.
Finally, we need a function that will wait
a certain amount of days, effectively looping through these steps:
day6> (defn wait [days generation]
(if (= days 0)
generation
(recur (dec days) (>> generation tick populate))))
#'day6/wait
day6> (wait 18 (readinput))
(6 0 6 4 5 6 0 1 1 2 6 0 1 1 1 2 2 3 3 4 6 7 8 8 8 8)
day6> (count *1)
26
As you can see, it yields the correct result. Yay! Let’s check with 80 days!
day6> (count (wait 80 (readinput)))
5934
It works, of course it does.
Now let’s plug our real input and wait
…
day6> (time (count (wait 80 (readinput))))
"Elapsed time: 1998.554897 msecs"
372300
Not too bad! This solution grants us the first gold start of the current day. Let’s see what awaits us in part two.
Part two
The only change is that we need to compute 256
days instead of 80
.
Should be easy, right?
day6> (count (wait 256 (readinput)))
Cc Cc
day6>
OK, it doesn’t work. In fact, it doesn’t work even with the example input. Let’s see how fast the required time grows:
day6> (doseq [n (range 20 140 10)]
(print (str ";; " n ": "))
(time (count (wait n (readinput))))
nil)
;; 20: "Elapsed time: 14.215826 msecs"
;; 30: "Elapsed time: 26.630702 msecs"
;; 40: "Elapsed time: 55.405953 msecs"
;; 50: "Elapsed time: 142.670344 msecs"
;; 60: "Elapsed time: 322.692136 msecs"
;; 70: "Elapsed time: 762.395619 msecs"
;; 80: "Elapsed time: 1909.748014 msecs"
;; 90: "Elapsed time: 4356.629415 msecs"
;; 100: "Elapsed time: 10715.898879 msecs"
;; 110: "Elapsed time: 31755.26834 msecs"
;; 120: "Elapsed time: 109995.207696 msecs"
;; 130: "Elapsed time: 349632.859801 msecs"
nil
Plotting this with GNUPlot shows the following graph:
It indeed looks like exponential growth, so we need another approach. Calculating this on a modern PC with enough RAM and fast enough CPU is theoretically possible, I guess, but I’d not try that myself. It’d be a waste of CPU time and electricity.
Let’s look at our first generation again: 3,4,3,1,2
.
We have five fish, and on the next day, there still will be five fish, as there’s no fish with a counter of 0
.
Let’s group today’s fish by their counter:
day6> (frequencies [3 4 3 1 2])
{3 2,
4 1,
1 1,
2 1}
So you can see that the total sum of values from this map equals 5
, which is a total fish count.
On the next generation this remains the same:
day6> (frequencies (populate (tick [3 4 3 1 2])))
{2 2,
3 1,
0 1,
1 1}
But on the next generation we get this:
day6> (frequencies (populate (tick (populate (tick [3 4 3 1 2])))))
{1 2,
2 1,
6 1,
0 1,
8 1}
We got ourselves a new fish with a counter of 8
, and now the total sum equals 6
.
By the end of day 18
there are 26
fish:
day6> (frequencies (wait 18 [3 4 3 1 2]))
{0 3,
7 1,
1 5,
4 2,
6 5,
3 2,
2 3,
5 1,
8 4}
day6> (reduce + (vals (frequencies (wait 18 [3 4 3 1 2]))))
26
So this shows that we can simply maintain such a table ourselves without adding fish to the end of the list, as original rules suggest. Let’s write such function:
day6> (defn solve [days input]
(reduce (fn [generation _]
(reduce (fn [newgen [tick conut]] ; ❸
(if (> tick 0)
(update newgen (dec tick) (fnil + 0) conut) ; ❹
(> newgen
(update 6 (fnil + 0) conut)
(update 8 (fnil + 0) conut)))) ; ❺
{} generation)) ; ❷
(frequencies input) ; ❶
(range days)))
#'day6/solve
day6> (solve 18 [3 4 3 1 2])
{0 3, 7 1, 1 5, 4 2, 6 5, 3 2, 2 3, 5 1, 8 4}
There’s a lot that’s going on, so let me explain it.
First, we compute the initial counts of each fish ❶.
Then we reduce into this generation over the number of days we need to wait computed with (range days)
.
The reducing function accepts a generation
and a day, but we only need the generation itself.
Then we reduce over this generation
into a new empty one ❷.
The inner reducing function accepts newgen
 a new generation to compute, and a fish, immediately destructured to tick
and fish count
❸.
If the tick
is greater than zero, this fish goes into new generation with the tick
value decreased by 1
.
Otherwise, we add another fish with the counter of 6
to the new generation, and a new fish with the counter of 8
❺.
On each iteration of the inner reduce
we update fish similarly to our tick
and populate
functions, but without generating longer list.
And as you can see, calling this function returns the same result as our previous implementation, but the time needed is significantly lower:
day6> (= (frequencies (wait 80 [3 4 3 1 2]))
(solve 80 [3 4 3 1 2]))
true
day6> (do (time (wait 80 [3 4 3 1 2]))
(time (solve 80 [3 4 3 1 2]))
nil)
"Elapsed time: 43.779213 msecs"
"Elapsed time: 0.585191 msecs"
nil
Computing 256
days finishes in an instant, even with the real input:
day6> (reduce + (vals (solve 256 [3 4 3 1 2])))
26984457539
day6> (reduce + (vals (solve 256 (readinput))))
1675781200288
And this gives us the second gold star.
Day 6 thoughts
This was an interesting task! It shows that the most obvious approach is not always the most optimal one, and I’ve intentionally solved it in a nonoptimal way to show that. And using this solution helped us to see how to do it the proper way.
Day 7  The Treachery of Whales
Remembering last year’s AoC, I can tell that solving one puzzle per day is much more pleasant than solving a bunch of puzzles in a single day. Last year I felt the burden of unsolved days, and an eternal race with the clock to keep up with others. Thankfully, this year is different!
Today a giant whale wants to eat us, but a swarm of crabs in tiny submarines wants to help us escape.
In order to do that, we need to help crabs to align in a straight line with the least amount of fuel.
The example input resembles a horizontal position of each crab, and goes as follows: 16,1,2,0,4,2,7,1,2,14
.
When crab moves from position 0
to position 1
its submarine looses 1
unit of fuel.
So to move from position 16
to 5
, the crab needs to spend 11
units of fuel.
We need to find such a position that total fuel unit loss is as small as possible.
Let’s start with the example input:
day6> (ns day7)
nil
day7> (require '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day7> (def exampleinput [16,1,2,0,4,2,7,1,2,14])
#'day7/exampleinput
Now we just need to compute fuel consumption for a given position:
day7> (defn fuelconsumption [input pos]
(>> input
(map #(Math/abs ( % pos)))
(reduce +)))
#'day7/fuelconsumption
day7> (fuelconsumption exampleinput 2)
37
As can be seen, computing fuel consumption for position 2
yields a correct result.
Now we only need to check what position is the most optimal one, meaning that it uses the least amount of fuel:
day7> (defn solve [input]
(let [min (apply min input)
max (apply max input)]
(>> (range min (inc max))
(map (partial fuelconsumption input))
sort
first)))
#'day7/solve
day7> (solve exampleinput)
37
We only care for the positions in range
of our numbers.
So if the minimum position is 10
and the maximum is 15
there’s no point going below 10
or above 15
.
Since the range
yields a noninclusive range, we need to inc
the upper bound.
This again yields 37
, as it is the least amount of fuel we can use to align everyone.
It also works for the real input, but it is quite slow:
day7> (time (solve (readinput)))
"Elapsed time: 6545.965142 msecs"
343468
While slowness may be an issue in the second part, as the previous day clearly illustrated, let’s hope it will not cause too much trouble.
Part two
OK, we’ve got it slightly wrong, and crab submarines use a lot more fuel to move.
So to move from position 1
to 5
, the submarine uses 1+2+3+4+5
amount of fuel.
This is called a triangular number, and is computed with the following formula: n(n+1)/2
:
day7> (defn trianglenumber [n]
(/ (* n (inc n)) 2))
#'day7/trianglenumber
day7> (trianglenumber 5)
15
Now, all we need to do is to plug this function into our solution.
Instead of duplicating the code, let’s rewrite our two functions to support an additional modifier
argument:
day7> (defn fuelconsumption [input modifier pos]
(>> input
(map #(modifier (Math/abs ( % pos))))
(reduce +)))
#'day7/fuelconsumption
day7> (defn solve
([input] (solve input identity))
([input modifier]
(let [min (apply min input)
max (apply max input)]
(>> (range min max)
(map (partial fuelconsumption input modifier))
sort
first))))
#'day7/solve
The solve
function now optionally accepts a second argument.
When only one argument is given, the arity dispatcher goes to the first body ([input] (solve input identity))
, which calls the same function but with two arguments.
The default value for modifier
is identity
, which is a function that returns the argument it was given as is.
Now we can use our trianglenumber
as a modifier to compute the result:
day7> (solve exampleinput)
37
day7> (solve exampleinput trianglenumber)
168
This works for real input data as well:
day7> (time (solve (readinput) trianglenumber))
"Elapsed time: 6256.100167 msecs"
96086265
The required time hasn’t changed much, as we just added one small formula to an already working solution. I’m fine with the current results.
Day 7 thoughts
Today’s task was quite simple. Perhaps there’s a more optimal solution to it, but I can’t think of one to be honest. Luckily, today the speed was not a blocker, just a minor inconvenience.
Day 8  Seven Segment Search
After escaping from the giant whale we’ve entered a cave and noticed that our submarine’s fourdigit sevensegment display is malfunctioning. The digits on the display are meant to look like this:
0: 1: 2: 3: 4:
aaaa .... aaaa aaaa ....
b c . c . c . c b c
b c . c . c . c b c
.... .... dddd dddd dddd
e f . f e . . f . f
e f . f e . . f . f
gggg .... gggg gggg ....
5: 6: 7: 8: 9:
aaaa aaaa aaaa aaaa aaaa
b . b . . c b c b c
b . b . . c b c b c
dddd dddd .... dddd dddd
. f e f . f e f . f
. f e f . f e f . f
gggg gggg .... gggg gggg
However, random gibberish is displayed, due to the fact that the signals are generated randomly. Our test input consists of rows that are divided into two segments  the signals and the numbers:
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab  cdfeb fcadb cdfeb cdbaf
Everything before the 
character are the patterns produced by our system, and everything after is the number meant to be displayed.
The task goes into great detail on how this works, but the first part doesn’t use anything of it so let’s just skip it for now. Our task for the first part is to find all unique numbers, which can be determined by lengths, and find how many they’re appearing. Let’s start by parsing the example input first:
day7> (ns day8)
nil
day8> (require '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day8> (def exampleinput
"be cfbegad cbdgef fgaecd cgeb fdcge agebfd fecdb fabcd edb  fdgacbe cefdb cefbgd gcbe ...")
#'day8/exampleinput
day8> (defn readinput []
(>> #_#_"inputs/day8"
slurp
exampleinput
str/splitlines
(map (fn [line]
(let [[signals digits] (str/split line #"\s+\\s+")]
{:signals (str/split signals #"\s+")
:digits (str/split digits #"\s+")})))))
#'day8/readinput
This transforms each row into a hashmap that holds :signals
and :digits
keys:
day8> (readinput)
({:signals ["be" "cfbegad" "cbdgef" "fgaecd" "cgeb"
"fdcge" "agebfd" "fecdb" "fabcd" "edb"],
:digits ["fdgacbe" "cefdb" "cefbgd" "gcbe"]}
...)
Our task is to find only the digits that have a unique size, meaning only 1
, 4
, 7
, and 8
, with the respective sizes of 2
, 3
, 4
, and 7
:
day8> (defn part1 [input]
(>> input
(map :digits)
(mapcat #(map count %))
(keep #{2 3 4 7})
count))
#'day8/part1
day8> (part1 (readinput))
381
Nothing fancy here, just counting all digit code lengths and keeping only those that match the predicate. Now for the real thing.
Part two
I’ve thought I went insane. The second part starts off with the brief explanation that after a short period of time we’ve figured out how the signals are wired:
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab  cdfeb fcadb cdfeb cdbaf
The signals can be wired as follows:
dddd aaaa
e a b c
e a b c
ffff dddd
g b e f
g b e f
cccc gggg
our correct
mapping mapping
Which means that the patterns for all numbers are:
Signal  Digit 

acedgfb 
8 
cdfbe 
5 
gcdfa 
2 
fbcad 
3 
dab 
7 
cefabd 
9 
cdfgeb 
6 
eafb 
4 
cagedb 
0 
ab 
1 
And now I feel very stupid, but at first, I’ve thought that this is the thing I need to use to complete the task. I wrote a small function that uses these patterns as a decoder and run it over the example input and got the wrong answer.
I know, it may sound ridiculous but I’ve spent 20 minutes trying to figure out why the second line has the one digit represented as gc
and the fourths one uses cb
.
Only after I’ve realized that my task is to compute such patterns for all rows, and there’s no universal one.
Well, I guess I was misled by this sentence:
Following this same process for each entry in the second, larger example above, the output value of each entry can be determined:
I’ve understood it as if I don’t need to figure out the wiring first. But now that the task is clear to me let’s try to think of how it can be accomplished.
First things first, we know four digits from the get go: 1
, 4
, 7
, and 8
, so we can compute their patterns easily enough:
 one:
c
,f
 four:
b
,c
,d
,f
 seven:
a
,c
,f
 eight:
a
,b
,c
,d
,e
,f
And we need to find the remaining numbers using only this information. Except no. Remember the diagram at the start of the puzzle? We can use it to find which letters we can compute by overlaying digits one on another and removing those that we’re not interested in. This basically means, we need to use mathematical sets to solve this task. Luckily for us, Clojure comes with a built in set library:
day8> (require '[clojure.set :as set])
nil
day8> (def signals (map set ["acedgfb" "cdfbe" "gcdfa" "fbcad" "dab" "cefabd" "cdfgeb" "eafb" "cagedb" "ab"]))
#'day8/signals
Now we can start by finding the patterns. First, let’s determine the patterns for the known digits:
day8> (def one one (some #({2 %} (count %)) signals))
#'day8/one
day8> (def four (some #({4 %} (count %)) signals))
#'day8/four
day8> (def seven (some #({3 %} (count %)) signals))
#'day8/seven
day8> (def eight (some #({7 %} (count %)) signals))
#'day8/eight
The first thing we can do is find what letter a
is mapped to.
To do so, we can take the difference between seven and one, as this will leave only the topmost row:
7777
. 1
. 1
....
. 1
. 1
....
day8> (def a (first (set/difference seven one)))
#'day8/a
day8> a
\d
As can be seen, for the given signals the topmost row is mapped to the character d
.
With the digits we know so far we can find another character g
:
day8> (def g (some #(whenlet [c (and (= 6 (count %))
(set/difference % (set/union seven four)))]
(when (= 1 (count c))
(first c)))
signals))
#'day8/g
day8> g
\c
We’re using the fact that there’s only one digit with the length of 6
, that has exactly one extra line from the union of seven and four, which looks like an unfinished nine:
7777 9999
4 7 9 9
4 7 9 9
4444 9999
. 7 . 9
. 7 . 9
.... 9999
And the bottom line corresponds to the g
letter in the correct mapping.
We now can actually define nine
by using union
of seven
, four
, and newly found g
:
day8> (def nine (set/union #{g} seven four))
#'day8/nine
day8> nine
#{\a \b \c \d \e \f}
And with nine
available, we can find e
by taking a difference with eight
:
....
. .
. .
....
8 .
8 .
....
day8> (def e (first (set/difference eight nine)))
#'day8/e
day8> e
\g
There’s another number we can find by only knowing 8
and 1
, it is six
.
We can do this similarly to how we’ve found letter g
, except now we’re finding whole number instead:
day8> (def six (some #(and (= (count %) 6)
(seq (set/intersection
one
(set/difference eight (set %))))
%)
signals))
#'day8/six
day8> six
#{\b \c \d \e \f \g}
This works because there’s only one number that has 6 segments, and when we difference
it with eight the remaining segment will intersect with 1
:
....
. 6
. 6
....
. 1
. 1
....
That’s how we know that this is truly six.
And with six
in place, we are able to find letters c
and f
:
day8> (def c (first (set/difference eight six)))
#'day8/c
day8> c
\a
day8> (def f (first (disj one c)))
#'day8/f
day8> f
\b
I hope you get why this is like this, as I’m a bit tired to draw these numbers, haha…
Speaking of number, now, that we know both six
and letter c
, we can compute five
, by removing c
from six
:
day8> (def five (disj six e))
#'day8/five
day8> five
#{\b \c \d \e \f}
And five
is the key point of finding two
:
day8> (def two (some #(and (= (count %) 5)
(= #{c e}
(set/difference
%
five))
%)
signals))
#'day8/two
day8> two
#{\a \c \d \f \g}
Knowing two
grants us access to three
by merging two
with f
and removing e
.
And while we’re there, we can actually find letter d
from two
as well:
day8> (def three (conj (disj two e) f))
#'day8/three
day8> three
#{\a \b \c \d \f}
day8> (def d (first (disj two a c e g)))
#'day8/d
day8> d
\f
Finally, we went through all this trouble to find the last digit:
day8> (def zero (disj eight d))
#'day8/zero
day8> zero
#{\a \b \c \d \e \g}
Now, if you remember, we have the example mapping:
Signal  Digit 

acedgfb 
8 
cdfbe 
5 
gcdfa 
2 
fbcad 
3 
dab 
7 
cefabd 
9 
cdfgeb 
6 
eafb 
4 
cagedb 
0 
ab 
1 
Let’s compare it to ours:
day8> {zero 0, one 1, two 2, three 3, four 4, five 5, six 6, seven 7, eight 8, nine 9}
{#{\a \c \e \d \g \f \b} 8,
#{\c \d \f \b \e} 5,
#{\g \c \d \f \a} 2,
#{\f \b \c \a \d} 3,
#{\d \a \b} 7,
#{\c \e \f \a \b \d} 9,
#{\c \d \f \g \e \b} 6,
#{\e \a \f \b} 4,
#{\c \a \g \e \d \b} 0,
#{\a \b} 1}
As you can see it’s exactly the same^{3}.
All that is left to do is to put all this logic into a function and use this function to decode the numbers.
I won’t repeat the whole code from above again, as this post is already a bit long, so the function I wrote is called mapsignalstodigits
, and here’s the solution:
day8> (defn decode [row]
(let [{:keys [signals digits]} row
signals>digits (mapsignalstodigits signals)]
(>> digits
(map set)
(map signals>digits)
(str/join)
parselong)))
#'day8/decode
day8> (defn part2 [input]
(>> input
(map decode)
(reduce + )))
#'day8/part2
day8> (part2 (readinput))
1023686
Day 8 thoughts
This task was really tricky. I’ve spent a lot of time mapping numbers by hand before I’ve managed to find a sequence of letters/digits that works to find all of them. The solution is a bit too imperative for my liking, but hey, it works, and I’m already exhausted enough, so I can take it in its current state.
Technically speaking, I’ve finished this task after midnight at my local time, but there still was time until the next task, so I think this counts, as a win.
Day 9  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 '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day9> (def exampleinput "
2199943210
3987894921
9856789892
8767896789
9899965678")
#'day9/exampleinput
day9> (defn readinput []
(>> exampleinput
str/trim
str/splitlines
(mapv #(mapv (fn [s] (parselong (str s))) %))))
#'day9/readinput
day9> (readinput)
[[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 findminimum [row]
(>> row
(mapindexed #(and (< %2 (nth row (dec %1) 9))
(< %2 (nth row (inc %1) 9))
%1))
(filter number?)
(into [])))
#'day9/findminimum
day9> (findminimum (first (readinput)))
[1 9]
This function walks the row via the mapindexed
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 findrowminpoints [rows]
(>> rows
(mapv findminimum)
(mapindexed #(mapv (fn [e] [%1 e]) %2))
(into [])))
#'day9/findrowminpoints
day9> (findrowminpoints (readinput))
[[[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]
(associn field p (getin 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 tosinglelevel [rows]
(reduce (fn [all row] (concat all row)) [] rows))
#'day9/tosinglelevel
day9> (tosinglelevel (findrowminpoints (readinput)))
([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 (readinput) (tosinglelevel (findrowminpoints (readinput))))
;; .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 (readinput))]
(render rows (tosinglelevel (findrowminpoints 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 lowestpoints [rows]
(let [minrows (>> rows
findrowminpoints
tosinglelevel
set)
mincols (>> rows
transpose
findrowminpoints
tosinglelevel
(map (fn [[x y]] [y x]))
set)]
(into [] (set/intersection minrows mincols))))
#'day9/lowestpoints
day9> (render (readinput) (lowestpoints (readinput)))
;; .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 part1 [input]
(>> input
lowestpoints
(map #(getin input %))
(map inc)
(reduce +)))
#'day9/part1
day9> (part1 (readinput))
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 partofbasin? [val lowest]
(<= lowest val 8))
#'day9/partofbasin?
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 findbasin [coords rows [x y] val]
(when (partofbasin? (getin rows [x y] 10) val)
(vswap! coords conj [x y])
(doseq [coord [[(inc x) y]
[(dec x) y]
[x (inc y)]
[x (dec y)]]]
(findbasin coords rows coord (inc val)))))
#'day9/findbasin
Aah, watch out! A wild nonpure 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 (readinput)
basin (volatile! #{})]
(findbasin 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 findbasins [rows]
(let [points (lowestpoints rows)]
(for [p points]
(let [coords (volatile! #{})]
(findbasin coords rows p (getin rows p))
@coords))))
#'day9/findbasins
day9> (render (readinput) (tosinglelevel (findbasins (readinput))))
;; 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 part2 [input]
(>> input
findbasins
(map count)
(sort >)
(take 3)
(reduce *)))
#'day9/part2
day9> (part2 (readinput))
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…
Day 10  Syntax Scoring
After we’ve determined which basins to avoid we ask our submarine to find a safe route, but it reports that there’s an error:
Syntax error in navigation subsystem on line: all of them
And here’s our navigation subsystem that we need to fix:
[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]
So all lines are incorrect but for two different reasons. Some lines are just unfinished, e.g. all parentheses and brackets are stacked logically, there’s just not enough closing characters to match them. Other lines are indeed incorrect, because the closing paren doesn’t match the opening one, like here:
{([(<{}[<>[]}>{[]{[(<()>
We’ve expected a matching ]
but instead found the }
, which is not right.
The puzzle claims that all syntax checkers have a scoring system, and in our case, the scores are like this:
)
: 3 points,]
: 57 points,}
: 1197 points,>
: 25137 points.
Our task is to find all nonmatching parentheses in the input, and compute the total score.
day9> (ns day10)
nil
day10> (require '[clojure.string :as str])
nil
day10> (def exampleinput "
[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]")
#'day10/exampleinput
day10> (def incorrectscore
{\) 3
\] 57
\} 1197
\> 25137})
#'day10/incorrectscore
day10> (defn readinput []
(>> exampleinput
str/trim
str/splitlines))
I’ve defined the score map as described in the task, but I’m using characters instead of strings, as it’s easier to work with them because strings in Clojure can be represented as sequences of characters. Now, we need a way to find what character is not the matching one.
The solution is pretty simple  a stack. We add opening characters to the stack, and when we get a closing one, we check if there’s a matching parenthesis is on the top of the stack. If it matches, we remove it from the stack and continue. If it doesn’t match, we’ve found the culprit.
day10> (def matching
{\( \),
\{ \},
\[ \],
\< \>})
#'day10/matching
day10> (defn tostackorerrorchar [line]
(loop [stack ()
[paren & parens] line]
(case paren
(\( \[ \{ \<) (recur (cons paren stack) parens)
(\) \] \} \>) (if (= (matching (first stack)) paren)
(recur (rest stack) parens)
paren)
stack)))
#'day10/tostackorerrorchar
This function builds the stack and if there were no mismatching chars it returns it, otherwise, it returns the mismatched character.
I’ve also created the matching
table, to quickly convert opening parens into the matching closing ones.
Here’s how it works:
day10> (tostackorerrorchar "[({(<(())[]>[[{[]{<()<>>")
(\{ \{ \[ \[ \( \{ \( \[)
day10> (tostackorerrorchar "{([(<{}[<>[]}>{[]{[(<()>")
\}
Pretty universal, but maybe a bit inconvenient to use. Now, all that’s left is to find mismatches for all lines, and calculate the score:
day10> (defn part1 [input]
(>> input
(keep tostackorerrorchar)
(filter char?)
(map incorrectscore)
(reduce +)))
#'day10/part1
day10> (part1 (readinput))
26397
I’m filtering results, only keeping those that are single characters as the (keep tostackorerrorchar input)
call returns a list of both stacks and chars.
Part two
This solves only half of our problems. We still have a lot of lines that are valid, but unfinished, and our second task is to finish those and compute a completion score:
The completing score is a bit different from the mismatch score:
day10> (def correctscore
{\) 1
\] 2
\} 3
\> 4})
#'day10/correctscore
To calculate the score, we need to fill the stack first.
Except not, we can just use the valid stack and swap all opening parentheses to the closing ones.
Then we can score those and calculate the total score.
Total score is calculated by this formula (scoresofar * 5) + parenscore
for each parenthesis.
Sounds like a job for reduce
:
day10> (defn scorecompletionstack [stack]
(>> stack
(map matching)
(map correctscore)
(reduce (fn [total score]
(+ (* total 5) score)))))
#'day10/scorecompletionstack
day10> (scorecompletionstack (tostackorerrorchar "(((({<>}<{<{<>}{[]{[]{}"))
1480781
In the example above I’m passing the correct line, but this function will fail on incorrect inputs. Thankfully we can filter these out by simply checking that elements are collections, similarly to our check in the first part. One last bit we need to make is that to get the correct result we must sort the scores and take exactly the middle one:
day10> (defn getmiddle [list]
(first (drop (quot (count list) 2) list)))
#'day10/getmiddle
day10> (defn part2 [input]
(>> input
(map tostackorerrorchar)
(filter coll?)
(map scorecompletionstack)
sort
getmiddle))
#'day10/part2
day10> (part2 (readinput))
288957
Clojure doesn’t have a function to get the middle element of the collection directly, but it’s quite easy to do, so it’s not a problem.
And the quot
function helps avoiding direct use of java.lang.Math/floor
or casting fractions to int with int
.
Day 10 thoughts
This day’s task was easy.
I think this was mostly due to the fact that I’ve already written a Schemelike language before, where I solved exactly the same problem.
Except there I’ve used a bit simpler solution as I’ve only needed to check the last character, as was not planning to automatically complete the stack.
InterLisp mapped the ]
key to a shortcut that closed all opened parentheses before the cursor.
I think this could be possible to be done in the Reader, though it would annoy a lot of text editors as they expect parentheses to be balanced.
Today’s puzzle was fun, and I think it’s even practical as it teaches you how to parse structured data with a stack.
Day 11  Dumbo Octopus
After figuring out the deadliest basins, we enter another cave full of dumbo octopuses, officially named as Grimpoteuthis.
There are 100 octopuses arranged in a 10 by 10 grid, and each one has an energy level from 0
to 9
.
Each discrete moment, every octopus gets one additional power to their power level, and after an octopus got more than 9
power, it flashes red.
Flashing makes all neighbor octopuses obtain one extra energy unit, with a catch that an octopus that already flashed will not flash twice in a single step.
After flashing, the energy level of that octopus is reset to 0
.
So it goes like this. Suppose we have these octopuses:
1 1 1 1 1
1 9 9 9 1
1 9 1 9 1
1 9 9 9 1
1 1 1 1 1
After the first step, all inner one flashed and increased the surrounding levels by 1
.
This makes the innermost octopus to also flash:
3 4 5 4 3
4 0 0 0 4
5 0 0 0 5
4 0 0 0 4
3 4 5 4 3
After the next step, no octopus needs to flash, so their levels just increase:
4 5 6 5 4
5 1 1 1 5
6 1 1 1 6
5 1 1 1 5
4 5 6 5 4
This is how the task puts it. Let’s see if we can implement such an algorithm. This actually looks like a cellular automaton, except neighbor cells just change their levels upon flashing. Let’s start by parsing the input, as usual:
day10> (ns day11)
nil
day11> (require '[aoccommons :refer [parselong]]
'[clojure.string :as str])
nil
day11> (def exampleinput "
11111
19991
19191
19991
11111")
#'day11/exampleinput
day11> (defn readinput []
(>> exampleinput
str/trim
str/splitlines
(mapv (partial mapv parselong))))
#'day11/readinput
day11> (readinput)
[[1 1 1 1 1] [1 9 9 9 1] [1 9 1 9 1] [1 9 9 9 1] [1 1 1 1 1]]
Note that I’ve changed the parselong
function to work with not only strings but characters as well.
Now we can define a simple tick
function, that will take our world state, and return a new one, where each octopus has increased their level:
day11> (defn tick [rows]
(mapv (partial mapv inc) rows))
#'day11/tick
day11> (tick (readinput))
[[2 2 2 2 2] [2 10 10 10 2] [2 10 2 10 2] [2 10 10 10 2] [2 2 2 2 2]]
As can be seen, this yields us a new world, where some octopuses are basically ready to flash. So let’s write a function that finds all cells that need to flash, and returns their coordinates, similarly to how we did in day 9:
day11> (defn findflashingcells [rows]
(>> rows
(keepindexed
(fn [i row]
(keepindexed
(fn [j oct]
(when (> oct 9)
[i j]))
row)))
flatten
(partition 2)
(keep seq)))
#'day11/findflashingcells
day11> (findflashingcells (tick (readinput)))
((1 1) (1 2) (1 3) (2 1) (2 3) (3 1) (3 2) (3 3))
I’ve realized, that since coordinates go in pairs, it’s much easier to bring them to the single level by using flatten
and partition
, than writing something like day nine’s tosinglelevel
.
Now we just need to update each cell in our world that flashes, and also their neighbors.
Let’s start with a function that will update the cell if it belongs to our world:
day11> (defn safeupdate [rows point f]
(if (getin rows point)
(updatein rows point f)
rows))
#'day11/safeupdate
day11> (safeupdate [0 1 2] [10] inc)
[0 1 2]
day11> (safeupdate [0 1 2] [1] inc)
[0 2 2]
Here, for a onedimensional example, we first try to update a cell at position 10
, but it is out of bounds, so nothing happens.
Next, we successfully update the cell at position 1
.
This will work as good for a twodimensional world we’re dealing with.
Yes, this function will not work in its current state with worlds that have false
or nil
in any of the cells, but our world doesn’t, so it’s not a problem.
Just something we need to keep in mind.
Now we can flash
all cells:
day11> (defn flash
([rows] (flash rows #{}))
([rows flashed]
(reduce (fn [[rows flashed] [x y]]
(if (not (flashed [x y]))
[(> rows
(safeupdate [(inc x) y] inc)
(safeupdate [(dec x) y] inc)
(safeupdate [x (inc y)] inc)
(safeupdate [x (dec y)] inc)
(safeupdate [(inc x) (inc y)] inc)
(safeupdate [(dec x) (inc y)] inc)
(safeupdate [(inc x) (dec y)] inc)
(safeupdate [(dec x) (dec y)] inc))
(conj flashed [x y])]
[rows flashed]))
[rows flashed] (findflashingcells rows))))
#'day11/flash
Now, this function is pretty big, but its promise is very simple  find all points that need to flash and update all neighbors. Note, that we’re incrementing all neighbor cells, unless the cell already flashed before, which is done by storing all flashed cells into a set. This function then returns a new world’s state, among all cells that have flashed in this step. However, this function doesn’t turn any cells to zero, as it helps with calculation a bit, and we’ll do it later with the following function:
day11> (defn tozero [rows]
(reduce (fn [rows [x y]] (associn rows [x y] 0))
rows (findflashingcells rows)))
#'day11/tozero
Finally, we need to define the step
function, that combines all these and produces a new world state:
day11> (defn step [rows]
(loop [rows rows
[rows* flashed] (flash (tick rows))]
(if (not= rows rows*)
(recur rows* (flash rows* flashed))
[(tozero rows*)
(count (filter #(> % 9) (flatten rows*)))])))
#'day11/step
Since our task is to count how many octopuses have flashed, we count the set of flashed cells and accumulate it into our result.
So this works like that. We start with the world like the one from the example:
1 1 1 1 1
1 9 9 9 1
1 9 1 9 1
1 9 9 9 1
1 1 1 1 1
First we tick
each cell, and world is now in the following state:
2 2 2 2 2
2 10 10 10 2
2 10 2 10 2
2 10 10 10 2
2 2 2 2 2
Now each octopus with the energy level greater than 9
flashes, adding 1
to the energy level of each neighbor:
3 4 5 4 3
4 12 14 12 4
5 14 10 14 5
4 12 14 12 4
3 4 5 4 3
We’ve remembered that on the previous step all octopuses that had 10 already flashed, so on this step only the single one in the very middle needs to flash. And to determine that our world needs another flash, we compare its current state with its previous state:
3 4 5 4 3
4 13 15 13 4
5 15 10 15 5
4 13 15 13 4
3 4 5 4 3
After this step, no other octopus need to flash, so we can replace every power level that is greater than 9
with zero:
3 4 5 4 3
4 0 0 0 4
5 0 0 0 5
4 0 0 0 4
3 4 5 4 3
Now we can repeat this process 100
times, and count how many times there was a flash:
day11> (defn part1 [input]
(second (reduce (fn [[rows flashed] _]
(let [[rows flashed*] (step rows)]
[rows (+ flashed flashed*)]))
[input 0] (range 100))))
#'day11/part1
day11> (part1 (readinput))
1656
And we get a gold star! Time for part two.
Part two
Now our task is to find the step on which all octopuses flash immediately.
Since we already count how many octopuses flashed on each step, all we need is to check if this number equals to 100
, as there are one hundred octopuses total:
day11> (defn part2 [input]
(reduce (fn [[rows flashed] i]
(let [[rows flashed] (step rows)]
(if (= 100 flashed)
(reduced i)
[rows 0])))
[input 0] (rest (range))))
#'day11/part2
day11> (part2 (readinput))
195
And we get another gold star by doing that!
Day 11 thoughts
The second part was very easy, as it just requires us to run our simulation until all of the octopuses flashed. Well, the first part wasn’t too hard as well. I remember the previous year’s task Seating System, which was another example of a cellular automaton, and it was a bit harder than this year.
Day 12  Passage Pathing
The cave story seems to come to an end, as we’re finally heading out of the cave system! However, in order to do that, we need to determine the best path out, and the only way to do that is to find all paths. Our input looks like this:
dcend
HNstart
startkj
dcstart
dcHN
LNdc
HNend
kjsa
kjHN
kjdc
Which is a directed graph, that we can visualize like this:
Our task is to find all paths from start
to end
for this graph, but we can’t go twice through the caves that are marked with lowercase letters.
For the example graph above, all such possible paths are:
start,HN,dc,HN,end
start,HN,dc,HN,kj,HN,end
start,HN,dc,end
start,HN,dc,kj,HN,end
start,HN,end
start,HN,kj,HN,dc,HN,end
start,HN,kj,HN,dc,end
start,HN,kj,HN,end
start,HN,kj,dc,HN,end
start,HN,kj,dc,end
start,dc,HN,end
start,dc,HN,kj,HN,end
start,dc,end
start,dc,kj,HN,end
start,kj,HN,dc,HN,end
start,kj,HN,dc,end
start,kj,HN,end
start,kj,dc,HN,end
start,kj,dc,end
Let’s start by parsing the input:
(ns day12)
nil
day12> (require '[clojure.string :as str])
nil
day12> (def exampleinput "
startA
startb
Ac
Ab
bd
Aend
bend")
#'day12/exampleinput
day12> (defn readinput []
(>> exampleinput
str/trim
str/splitlines
(map #(str/split % #""))
(reduce
(fn [map [start end]]
(> map
(update start (fnil conj #{}) end)
(update end (fnil conj #{}) start)))
{})))
#'day12/readinput
day12> (readinput)
{"start" #{"b" "A"},
"A" #{"start" "b" "end" "c"},
"b" #{"d" "start" "A" "end"},
"c" #{"A"},
"d" #{"b"},
"end" #{"b" "A"}}
We parse the input into the hashmap, where keys are all caves, and values are the sets of connections. This way we can easily query for the next step we need to make.
Since the task specifically mentions that we need to visit lowercased caves only once, it would be nice to have a predicate for this kind of check:
day12> (defn lowercase? [s]
(= s (str/lowercase s)))
#'day12/lowercase?
day12> (lowercase? "A")
false
day12> (lowercase? "a")
true
Now we can start building paths. To do so, let’s start with a function, that when given a path, will determine all possible steps, depending on our routes:
day12> (defn allpossiblesteps [routes path]
(let [seen (frequencies (filter lowercase? path))]
(filter some? (for [end (routes (last path))]
(when (not (seen end))
(str/join "," (conj path end)))))))
#'day12/allpossiblesteps
day12> (allpossiblesteps (readinput) ["start"])
("start,b" "start,A")
I’m using strings here because I’ll be using flatten
a bit later, so I can’t use vectors here, unfortunately.
This is definitively a hack, but I couldn’t figure out a proper way.
Now we can build all possible paths:
day12> (defn buildpaths [routes]
(loop [paths [["start"]]
done []]
(let [paths (>> paths
(map #(allpossiblesteps routes %))
flatten
(filter some?)
(map #(str/split % #",")))]
(if (seq paths)
(recur (remove #(= (last %) "end") paths)
(concat done (filter #(= (last %) "end") paths)))
done))))
#'day12/buildpaths
This function loops until we exhaust all possible combinations.
Each path that ends with the end
cave is moved to a separate list of paths, named done
, which is returned upon end.
Here’s an example:
day12> (defn buildpaths [routes]
(loop [paths [["start"]]
done []]
(let [paths (>> paths
(map #(allpossiblesteps routes %))
flatten
(filter some?)
(map #(str/split % #",")))]
(if (seq paths)
(recur (remove #(= (last %) "end") paths)
(concat done (filter #(= (last %) "end") paths)))
done))))
#'day12/buildpaths
day12> (buildpaths (readinput))
(["start" "b" "end"]
["start" "A" "end"]
["start" "b" "A" "end"]
["start" "A" "b" "end"]
["start" "A" "b" "A" "end"]
["start" "A" "c" "A" "end"]
["start" "b" "A" "c" "A" "end"]
["start" "A" "c" "A" "b" "end"]
["start" "A" "b" "A" "c" "A" "end"]
["start" "A" "c" "A" "b" "A" "end"])
This method correctly works for all examples and on the real input.
We only need to count
the result, and we get the first gold star for this day.
Part two
Part two suggests that we might want to enter a single small cave twice. I’m not sure why would we want this, as we’re searching for the sorest path out of the caves, but, well, OK I guess.
In order to do that, we need to tweak allpossiblesteps
to check how many lowercased letters there were.
To do that, we can count each letter, and see if their sum is equal to the amount of letters:
day12> (let [letters ["a" "b" "c" "d"]
counts (frequencies letters)]
(= (count (keys counts)) (reduce + (vals counts))))
true
This would work for the unique case, but we’re allowed to enter a single lowercased cave twice.
Which just means that we can compare if the amount of counts is greater than amount of letters by 1
:
day12> (let [letters ["a" "b" "c" "d" "b" "b"]
counts (frequencies letters)]
(or (= (count (keys counts)) (reduce + (vals counts)))
(= (inc (count (keys counts))) (reduce + (vals counts)))))
false
day12> (let [letters ["a" "b" "c" "d" "b"]
counts (frequencies letters)]
(or (= (count (keys counts)) (reduce + (vals counts)))
(= (inc (count (keys counts))) (reduce + (vals counts)))))
true
Now we just need to add this logic to allpossiblesteps
:
day12> (defn allpossiblesteps2 [routes path]
(let [seen (frequencies (filter lowercase? path))
vn (reduce + (vals seen))
kn (count (keys seen))]
(when (or (= vn kn)
(= vn (inc kn)))
(>> path
last
routes
(map #(when (not= % "start")
(str/join "," (conj path %))))))))
#'day12/allpossiblesteps2
We’re not interested in paths that lead back to the start
, but since we don’t check for visited nodes anymore, we need to accommodate this specific case.
Now we just need to update buildpaths
to use this function instead of the previous variant.
But instead, let’s pass this function as an argument:
day12> (defn buildpaths [routes steps]
(loop [paths [["start"]]
done []]
(let [paths (>> paths
(map #(steps routes %))
flatten
(filter some?)
(map #(str/split % #",")))]
(if (seq paths)
(recur (remove #(= (last %) "end") paths)
(concat done (filter #(= (last %) "end") paths)))
done))))
#'day12/buildpaths
The smallest test example produces 36 paths, which is a bit too much for the blog post lengths, so here’s a smaller example:
day12> (buildpaths {"start" #{"A" "b"}
"A" #{"start" "b" "end"}
"b" #{"start" "A" "end"}
"end" #{"A" "b"}}
allpossiblesteps2)
(["start" "b" "end"]
["start" "A" "end"]
["start" "b" "A" "end"]
["start" "A" "b" "end"]
["start" "b" "A" "b" "end"]
["start" "A" "b" "A" "end"]
["start" "b" "A" "b" "A" "end"]
["start" "A" "b" "A" "b" "end"]
["start" "A" "b" "A" "b" "A" "end"])
As can be seen, this works exactly how we need, and grants us another gold star when used on the real input data.
Day 12 thoughts
This task was tough. It may not look like it, but I don’t like combinationbased tasks too much. It was pretty hard to figure out the optimal strategy to discover all possible paths, and don’t go into infinite loops. But I’ve made it through, and still maintaining the streak!
Day 13  Transparent Origami
It seems I’ve celebrated early, and the cave story goes on still. Our submarine reached another volcanically active part of the cave! In order to progress, we need to use our onboard thermal camera, which, unfortunately, wasn’t activated ever since it was installed. To activate the camera we need to input a code, which can be found in the manual.
However, the code is protected from copying by being marked on transparent paper with dots. By folding this paper accordingly to the instructions, we will be able to decipher the code.
Our example puzzle input looks like this:
6,10
0,14
9,10
0,3
10,4
4,11
6,0
6,12
4,1
0,13
10,12
3,4
3,0
8,4
1,10
2,14
8,10
9,0
fold along y=7
fold along x=5
Let’s start by parsing it:
day12> (ns day13
(:require [clojure.string :as str]
[aoccommons :refer [parselong]]))
nil
day13> (def exampleinput "
6,10
0,14
9,10
0,3
10,4
4,11
6,0
6,12
4,1
0,13
10,12
3,4
3,0
8,4
1,10
2,14
8,10
9,0
fold along y=7
fold along x=5")
#'day13/exampleinput
day13> (defn readinput []
(let [lines (>> exampleinput
str/trim
str/splitlines)
points (takewhile seq lines)
folds (rest (dropwhile seq lines))]
{:points (mapv #(mapv parselong (str/split % #",")) points)
:folds (mapv #(update (> (str/replace % #"fold along\s+" "")
(str/split #"="))
1 parselong) folds)}))
#'day13/readinput
Today the input parsing function is a bit more involved. We need to not only parse the points but the tasks as well. The resulting data structure simply holds the vector of points and a vector of actions:
day13> (readinput)
{:points
[[6 10] [0 14] [9 10] [0 3]
[10 4] [4 11] [6 0] [6 12]
[4 1] [0 13] [10 12] [3 4]
[3 0] [8 4] [1 10] [2 14]
[8 10] [9 0]],
:folds [["y" 7] ["x" 5]]}
Now, the task shows us that if we render these points to a grid, we’ll get something like this:
...#..#..#.
....#......
...........
#..........
...#....#.#
...........
...........
...........
...........
...........
.#....#.##.
....#......
......#...#
#..........
#.#........
Let’s write a render
function, and see if that’s right.
Luckily for us, we’ve already implemented this exact function several times before, in days 9 and 5, so we can reuse it with some small tweaks:
day13> (defn render [points]
(let [x (inc (apply max (map first points)))
y (inc (apply max (map second points)))
field (into [] (repeat x (into [] (repeat y "."))))]
(>> points
(reduce (fn [field p] (associn field p "#")) field)
(apply map vector)
(map str/join)
(map (partial str ";; "))
(str/join "\n")
println)))
#'day13/render
day13> (render (:points (readinput)))
;; ...#..#..#.
;; ....#......
;; ...........
;; #..........
;; ...#....#.#
;; ...........
;; ...........
;; ...........
;; ...........
;; ...........
;; .#....#.##.
;; ....#......
;; ......#...#
;; #..........
;; #.#........
nil
That seems about right! Now, the task suggests that we need to fold this transparent paper once, producing the following transformation:
...#..#..#. #.##..#..#.
....#...... #...#......
........... ......#...#
#.......... => #...#......
...#....#.# .#.#..#.###
........... ...........
........... ...........
8<8<
...........
........... ^
.#....#.##. 
....#...... 
......#...#
#..........
#.#........
So essentially all coordinated below the line are flipped exactly above it. This seems not hard to calculate  we just need to subtract the point’s respecting coordinate from the fold coordinate, only if it is greater than the fold coordinate. Otherwise we return the same coordinate:
day13> (defn fold [point along coord]
(case along
"x" (let [[x y] point]
(if (> x coord)
[( coord ( x coord)) y]
[x y]))
"y" (let [[x y] point]
(if (> y coord)
[x ( coord ( y coord))]
[x y]))))
#'day13/fold
day13> (render (mapv #(fold % "y" 7) (:points (readinput))))
;; #.##..#..#.
;; #...#......
;; ......#...#
;; #...#......
;; .#.#..#.###
nil
Looks like in the example, so hopefully, we got everything right. The final transformation looks like this:
#.##.#..#. #####
#...#..... #...#
.....#...# #...#
#...#..... => #...#
.#.#.#.### #####
.......... .....
.......... .....
<
Let’s try folding it this way:
day13> (render (mapv #(fold % "x" 5) (mapv #(fold % "y" 7) (:points (readinput)))))
;; #####
;; #...#
;; #...#
;; #...#
;; #####
nil
Great! This shows that our algorithm behaves at least the same way as the one from the example.
The task for the first part is to only do the first fold, and count amount of unique points. Seems easy:
day13> (count (distinct (mapv #(fold % "y" 7) (:points (readinput)))))
17
For the example input, the correct answer is indeed 17
.
Let’s run this against the real input, but actually automate getting the first fold coordinate and axis:
day13> (defn part1 [input]
(let [{:keys [points folds]} input
[along coord] (first folds)]
(>> points
(mapv #(fold % along coord))
distinct
count)))
#'day13/part1
day13> (part1 (readinput))
631
This is the correct answer! Let’s see what’s in the second part.
Part two
We’re asked to finish the rest of the folding, and the code should be represented as eight capital letters.
But wait, there are no letters, in this transparent paper!
I wonder if we’re required to render
it?!
day13> (defn part2 [input]
(let [{:keys [points folds]} input]
(>> folds
(reduce (fn [paper [along coord]]
(mapv #(fold % along coord) paper)) points)
render)))
#'day13/part2
day13> (part2 (readinput))
;; ####.####.#....####...##..##..###..####
;; #....#....#....#.......#.#..#.#..#.#...
;; ###..###..#....###.....#.#....#..#.###.
;; #....#....#....#.......#.#.##.###..#...
;; #....#....#....#....#..#.#..#.#.#..#...
;; ####.#....####.#.....##...###.#..#.#...
nil
No way!
Are you kidding me!^{4}
So the code is EFLFJGRF
!
Entering the code from above grants us the second gold star for this day. Thankfully, we’re no longer required to figure out how to properly display things on the sevensegment display!
Day 13 thoughts
This task wasn’t hard, but I found it quite fun still! Finally our rendering paid off and proven to be useful.
Funnily enough, I can easily imagine such kind of protection from a device. This was a huge pain in my childhood  my parents often bought games for Dendy a Nintendo Entertainment System clone that was (as everybody thought) the original game console. I’m not sure if this was exactly on Dendy, but I remember that we had black and white displays, and some games required to enter a code to play them, and the code was encrypted via some colorful pallet, and you we’re supposed to enter the code. And some games were bought without manuals, or boxes, which contained the code, thus becoming unplayable. So today’s puzzle brought back some warm memories about my childhood, which is really great! And hey, the half of the event is already over, and I wonder what’s coming next!
Day 14  Extended Polymerization
Unfortunately, I wasn’t able to solve today’s puzzle myself, so I’ve asked my friend for help. The task was again about exponential growth, very similar to the day 6 puzzle. However, I wasn’t able to grasp how to keep things from growing this time.
As you may remember, in the lanternfish puzzle, I’ve figured out, that if we use frequencies
on current fish, we obtain their counters, and counts of fish with those counters respectively.
It was only a matter of time to notice the pattern with which lanternfish counters change.
Today’s task was very similar, but the puzzle itself lead me in the wrong direction. To explain what’ve happened let’s parse the input, as I initially did:
day13> (ns day14 (:require [clojure.string :as str]))
nil
day14> (def exampleinput "NNCB
CH > B
HH > N
CB > H
NH > C
HB > C
HC > B
HN > C
NN > C
BH > H
NC > B
NB > B
BN > B
BB > N
BC > B
CC > N
CN > C")
#'day14/exampleinput
day14> (defn readinput []
(let [lines (>> exampleinput
str/splitlines)
polymer (first lines)
recipes (drop 2 lines)]
{:polymer (seq polymer)
:recipes (reduce #(let [[pattern replacement] (str/split %2 #"\s+>\s+")]
(conj %1 [(seq pattern) (seq (str (first pattern) replacement))]))
{} recipes)}))
#'day14/readinput
day14> (readinput)
{:polymer (\N \N \C \B),
:recipes
{(\C \H) (\C \B),
(\N \N) (\N \C),
(\H \C) (\H \B),
(\N \C) (\N \B),
(\N \H) (\N \C),
(\C \N) (\C \C),
(\N \B) (\N \B),
(\B \C) (\B \B),
(\B \B) (\B \N),
(\B \H) (\B \H),
(\C \C) (\C \N),
(\H \N) (\H \C),
(\C \B) (\C \H),
(\H \B) (\H \C),
(\B \N) (\B \B),
(\H \H) (\H \N)}}
As you can see, I’ve precomputed the replacements. I did it because the task said, that the patterns overlap, and “the second element of one pair is the first element of the next pair”. So I’ve realized, that we can ditch the third letter completely, and we’ll be “fine”. You can see that this assumption is correct:
day14> (def recipes (:recipes (readinput)))
#'day14/recipes
day14> (str/join (mapcat #(recipes % %) (partitionall 2 1 (:polymer (readinput)))))
"NCNBCHB"
day14> (str/join (mapcat #(recipes % %) (partitionall 2 1 *1)))
"NBCCNBBBCBHCB"
day14> (str/join (mapcat #(recipes % %) (partitionall 2 1 *1)))
"NBBBCNCCNBBNBNBBCHBHHBCHB"
day14> (str/join (mapcat #(recipes % %) (partitionall 2 1 *1)))
"NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB"
However, it is also growing exponentially.
Now, in order to fix this, we need to look at this polymer string as a set of pairs.
We’re already working with it as a set of pairs here, since we’re using partitioning, but these pairs grow with the string, and as you may remember from the lanterfish task, we were able to solve it with frequencies
function:
day14> (frequencies (partition 2 1 "NNCB"))
{(\N \N) 1, (\N \C) 1, (\C \B) 1}
day14> (frequencies (partition 2 1 "NCNBCHB"))
{(\N \C) 1, (\C \N) 1, (\N \B) 1, (\B \C) 1, (\C \H) 1, (\H \B) 1}
day14> (frequencies (partition 2 1 "NBBBCNCCNBBNBNBBCHBHHBCHB"))
{(\C \H) 2, (\N \C) 1, (\C \N) 2, (\N \B) 4, (\B \C) 3, (\B \B) 4,
(\B \H) 1, (\C \C) 1, (\H \B) 3, (\B \N) 2, (\H \H) 1}
day14> (frequencies (partition 2 1 "NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB"))
{(\H \C) 3, (\N \C) 1, (\N \H) 1, (\C \N) 3, (\N \B) 9, (\B \C) 4, (\B \B) 9,
(\B \H) 3, (\C \C) 2, (\H \N) 1, (\C \B) 5, (\B \N) 6, (\H \H) 1}
day14> (frequencies (partition 2 1 "NBBNBBNBBBNBBNBBCNCCNBBBCCNBCNCCNBBNBBNBBNBBNBBNBNBBNBBNBBNBBNBBCHBHHBCHBHHNHCNCHBCHBNBBCHBHHBCHB"))
{(\C \H) 6, (\H \C) 1, (\N \C) 3, (\N \H) 1, (\C \N) 6, (\N \B) 19, (\B \C) 8,
(\B \B) 19, (\B \H) 3, (\C \C) 3, (\H \N) 1, (\H \B) 8, (\B \N) 15, (\H \H) 3}
day14> (frequencies (partition 2 1 "NBBNBBNBBNBBNBBNBNBBNBBNBBNBBNBBCCNBCNCCNBBNBNBBCNCCNBBBCCNBCNCCNBBNBBNBBNBBNBBNBBNBBNBBNBBNBBNBBBNBBNBBNBBNBBNBBNBBNBBNBBNBBNBBCBHCBHHNHCBBCBHCBHHNHCNCHBCCNBCBHCBBCBHCBBNBBNBBCBHCBHHNHCBBCBHCB"))
{(\C \H) 1, (\H \C) 9, (\N \C) 4, (\N \H) 3, (\C \N) 10, (\N \B) 41, (\B \C) 12, (\B \B) 42,
(\B \H) 9, (\C \C) 6, (\H \N) 3, (\C \B) 14, (\H \B) 1, (\B \N) 34, (\H \H) 3}
As can be seen, even though the polymer string grows exponentially, the result of partitioning and counting all of them grows much slower in size. This was the first thing I’ve thought about when I saw the growth rate, and remembered day 6. And even though such a bruteforce approach worked on the input, it was a wrong approach, as part two asked to compute 40 iterations. So I’ve kinda knew how to fix it, I mean, we just need to find a way to maintain such kind of table by hand, and we’ll be done in no time. But my earlier mistake prevented me from doing it. And that mistake was in the algorithm I’ve written for parsing the input.
Part two (struggle)
As you can see, I’ve precomputed all input and output patterns, but the task specifically mentioned that the letters are inserted in between, and I totally forgot that. Let’s look into the pairs again:
day14> (partition 2 1 "NNCB")
((\N \N) (\N \C) (\C \B))
Now, if we replace these patterns, with our old method, we’ll get these patterns:
day14> (partition 2 1 "NCNBCHB")
((\N \C) (\C \N) (\N \B) (\B \C) (\C \H) (\H \B))
Now, let’s replace original patterns, as suggested by the task:
day14> (>> "NNCB"
(partition 2 1)
(mapcat '{(\N \N) (\N \C \N)
(\N \C) (\N \B \C)
(\C \B) (\C \H \B)})
(partition 2 1))
((\N \C) (\C \N) (\N \N) (\N \B) (\B \C) (\C \C) (\C \H) (\H \B))
By doing it this way we get extra pairs that should not be there.
These pairs are (N N)
and (C C)
, as these are the points of overlapping, which can be illustrated like this:
NCN
NBC
CHB

vvvvvvv
NCNBCHB
If we remove overlapping pairs we’ll get the correct result:
((\N \C) (\C \N) (\N \B) (\B \C) (\C \H) (\H \B))
What we need to notice here, is that this method above can be used to generate all possible pairs without overlapping.
To do so we need to translate a pair into two pairs.
For example, the (N C)
pair is transformed into two pairs (N B)
and (B C)
as this is just the same as (N [B) C]
.
Doing it this way, we get the correct amount of pairs from the getgo:
day14> (>> "NNCB"
(partition 2 1)
(map '{(\N \N) [(\N \C) (\C \N)]
(\N \C) [(\N \B) (\B \C)]
(\C \B) [(\C \H) (\H \B)]})
flatten
(partition 2))
((\N \C) (\C \N) (\N \B) (\B \C) (\C \H) (\H \B))
That’s the bit of information that I couldn’t figure out myself. To be completely honest, even while writing it, I’m not sure if I understood the task correctly in the first place. The overlapping point suggests that I’m correct. On the other hand the same result can be constructed like this:
N N C B
^ ^ ^
  
C B H
We’re literally inserting new letters between existing letters, which is a totally different approach but it also works.
So in order to solve this task, we need to take a list of pairs, and transform each into two more pairs, as shown above. But instead of storing these pairs in a list, we can use a hashmap, that stores their counts. Additionally to that, we need a separate hashmap for counting inserted letters. On each step, we see how many instances of the given pair were there, and insert that many letters into the hash table. We convert a pair to two more pairs and insert as many of each into another hash table. This repeats until needed amount of iterations have passed:
day14> (defn solve [n {:keys [polymer recipes]}]
(loop [n n
letters (frequencies polymer)
pairs (frequencies (partition 2 1 polymer))]
(if (> n 0)
(let [[letters pairs]
(reduce (fn [[letters pairs]
[[a b :as pair] n]]
(let [letter (recipes pair)
add (fnil (partial + n) 0)]
[(update letters letter add)
(> pairs
(update [a letter] add)
(update [letter b] add))]))
[letters {}]
pairs)]
(recur (dec n) letters pairs))
[letters pairs])))
#'day14/solve
day14> (solve 1 {:polymer (seq "NNCB")
:recipes '{(\N \N) \C
(\N \C) \B
(\C \B) \H}})
[{\N 2, \C 2, \B 2, \H 1},
{[\N \C] 1, [\C \N] 1, [\N \B] 1, [\B \C] 1, [\C \H] 1, [\H \B] 1}]
Day 14 thoughts
I was a bit frustrated by this task, but it’s OK. I know that such tasks are my weakness, and it’s good that I’ve managed to finish them, even with a bit of help. A small ambiguity of the task was a bit problematic, but I’ve also failed to see the correct transformation.
Day 15  Chiton
We’ve almost reached the exit of the cave! But there’s another problem, the walls are getting closer together, and the walls are covered with chitons, and we need to find the safest way so we wouldn’t damage any. Our input is a map of risk values, and we need to reach the bottom right coordinate:
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
The highlighted numbers are the shortest path with the lowest risk level total of 40
.
Our task is to find such a path.
Well… Now I’m completely lost! I’ve never written a pathfinding algorithm before, and unfortunately the university where I studied completely skipped anything related to graphs. I’m not sure why, though, as I was studying to become a baremetal programmer, maybe they don’t need graphs, I don’t know. But we need some kind of algorithm to deal with this as a graph of points with weights. After a bit of searching, I’ve found that the Dijkstra’s algorithm is likely what I need.
Now, this algorithm works something like this (or at least how I understand it):
 We choose the first node with the lowest value and mark it as visited
 Next, we choose neighbor nodes and select the one which has a lower weight.
 If this node is the end node, we exit, if not we mark it as visited and freeze its weight to the sum of previous weights up to this node and node’s weight.
 We repeat the process, changing frozen weights if the new weight is smaller than the current one.
A better explanation can be found on the Wikipedia page I’ve linked, so if you’re interested, I suggest you read it there, as I could mess the explanation in some places. Let’s start by parsing the input:
day14> (ns day15 (:require [aoccommons :refer [parselong slurplines]]))
nil
day15> (defn readinput []
(>> "inputs/day15ex"
slurplines
(map seq)
(mapv #(mapv parselong %))))
#'day15/readinput
day15> (readinput)
[[1 1 6 3 7 5 1 7 4 2]
[1 3 8 1 3 7 3 6 7 2]
[2 1 3 6 5 1 1 3 2 8]
[3 6 9 4 9 3 1 5 6 9]
[7 4 6 3 4 1 7 1 1 1]
[1 3 1 9 1 2 8 1 3 7]
[1 3 5 9 9 1 2 4 2 1]
[3 1 2 5 4 2 1 6 3 9]
[1 2 9 3 1 3 8 5 2 1]
[2 3 1 1 9 4 4 5 8 1]]
Nice. Now, we need to implement the algorithm. The Wikipedia page has some pseudocode examples, and also mentions a priority queue. The algorithm actually computes the path, but we’re only interested in the total path weight, so we can potentially make it simpler:
day15> (defn dijkstra [world end]
(loop [points (sortedset [0 [0 0]]) ; our priority queue
visited #{}]
(let [[total [x y] :as point] (first points)]
(if (= [x y] end)
total ; total is the weight up to this point
(let [visited (conj visited [x y]) ; we only care about visited points,
points (reduce ; but not their weights
(fn [paths [newx newy]]
(iflet [risk (and (not (visited [newx newy]))
(getin world [newx newy]))]
(conj paths [(+ total risk) [newx newy]])
paths))
(disj points point)
[[(dec x) y] [(inc x) y]
[x (inc y)] [x (dec y)]])]
(recur points visited))))))
#'day15/dijkstra
day15> (dijkstra (readinput) [9 9])
40
Maybe not the best implementation, but it works! And it computes the correct value, so that’s good.
We use sortedset as our priority queue, as its semantics match our needs perfectly.
Elements are ordered, and getting first
element returns the smallest one.
We store points in the following format [weight [pointx pointy]]
, which can be easily sorted by the set implementation.
Plugging the real input also works out correctly, let’s see part two now.
Part two
Part two says that the cave is actually a lot bigger! But we need to compute the rest of the cave ourselves.
To do so, we need to take the current cave and repeat it five times to the right.
Each repetition has each value increased by 1
and values greater than 9
overlap back starting from 1
again.
For example, if we had a cave with a single [0 0]
coordinate with a weight 8
after repeating the first column five times we would get this:
89123
Now we need to repeat this row five times downwards to get the completed cave:
89123
91234
12345
23456
34567
We need to write such function and feed it our current input, then find the same path from top left to bottom right. First, let’s write a function that does the correct addition, overlapping values as described:
day15> (defn addtofield [field x]
(let [addtorow
(fn [row]
(mapv #(let [x (+ % x)]
(if (> x 9)
( x 9)
x))
row))]
(mapv addtorow field)))
#'day15/addtofield
day15> (addtofield [[4 5] [6 7]] 5)
[[9 1] [2 3]]
Next, we need to repeat the original world four times to the right, adding 1
, 2
, 3
, 4
to the original one on each repetition.
Then repeat this new world four times down, adding the same numbers:
day15> (defn extendfield [input]
(let [newworld (reduce (fn [world n]
(let [newworld (addtofield input n)]
(mapv #(into %1 %2) world newworld)))
input (range 1 5))]
(reduce (fn [world n]
(let [newworld (addtofield newworld n)]
(into world newworld)))
newworld (range 1 5))))
#'day15/extendfield
day15> (extendfield [[8]])
[[8 9 1 2 3]
[9 1 2 3 4]
[1 2 3 4 5]
[2 3 4 5 6]
[3 4 5 6 7]]
Exactly as in the example. Now, we can plug the real input, and see if it works:
day15> (let [world (extendfield (readinput))
endx (dec (count (first world)))
endy (dec (count world))]
(dijkstra world [endx endy]))
315
And indeed it does.
Day 15 thoughts
The first part was very interesting. I’m very new to this kind of stuff, and learning about Dijkstra’s algorithm surely was very useful. The second part was a bit too easy, as the only change was that we needed to compute the new field. But I suppose that perhaps someone tried to use some other pathfinding algorithm, which was checking all possible paths, so similarly to the previous day, it would have choked on the increased field. Luckily for us, our implementation performed well.
Day 16  Packet Decoder
We’ve finally left the caves! This is such a relief, no more walls full of Chitons, or volcanic activity. And since we’re out of the caves, we’re able to receive a transmission to our submarine!
The transmission is encoded with the Buoyancy Interchange Transmission System (BITS) and is represented in hexadecimal. It’s a continuous stream of the packets, and each packet has a fixed header format:
 First three bits encode the packet version
 Next three bits encode packet ID
Packets with an ID of 4
are value packets and can be processed by checking the 7th bit.
If the 7th bit is 1
we read four bits, and check the next bit.
If this bit is yet again equal to 1
, we read four more bits and check the fifth.
This repeats until the fifth bit is equal to 0
, meaning that this is the last portion of the packet, so we need to read only 4 more values.
Let’s write function to read a stream using the logic so far:
day15> (ns day16 (:require [clojure.string :as str]))
nil
day16> (def hextobinary
{\0 "0000", \1 "0001", \2 "0010", \3 "0011",
\4 "0100", \5 "0101", \6 "0110", \7 "0111",
\8 "1000", \9 "1001", \A "1010", \B "1011",
\C "1100", \D "1101", \E "1110", \F "1111"})
#'day16/hextobinary
day16> (defn parsebinary [b]
(Long/parseLong (str/join b) 2))
#'day16/parsebinary
day16> (defn readversionorid [packet]
(let [[verorid packet] (splitat 3 packet)]
[(parsebinary verorid) packet]))
#'day16/readversionorid
day16> (defn readvalue [packet]
(loop [[continue? a b c d & packet] packet
v ""]
(if (= \1 continue?)
(recur packet
(str v a b c d))
[(parsebinary (str v a b c d)) packet])))
#'day16/readvalue
Now, suppose we have the packet D2FE28
.
We convert it to the stream of bits first:
day16> (mapcat hextobinary "D2FE28")
(\1 \1 \0 \1 \0 \0 \1 \0 \1 \1 \1 \1 \1 \1 \1 \0 \0 \0 \1 \0 \1 \0 \0 \0)
Next, we can read it’s version and ID:
day16> (readversionorid *1)
[6 (\1 \0 \0 \1 \0 \1 \1 \1 \1 \1 \1 \1 \0 \0 \0 \1 \0 \1 \0 \0 \0)]
day16> (readversionorid (second *1))
[4 (\1 \0 \1 \1 \1 \1 \1 \1 \1 \0 \0 \0 \1 \0 \1 \0 \0 \0)]
As can be seen, each function returns the parsed value and the rest of the packet, so we can continue parsing it.
Now we can read the value, since this is the package with ID of 4
:
day16> (readvalue (second *1))
[2021 (\0 \0 \0)]
This returns the value of 2021
and the rest of the packet stream, which we do not care about right now.
There’s a second type of packet, which are operator packets.
They’re totally different beasts though.
Packets with IDs that are not equal to 4
, have the next bit after ID as length ID.
The length ID can be either 0
, meaning that we need to read the next N bits or 1
meaning that we need to process the next N packets.
Let’s implement the function that will read length ID and the length itself:
day16> (defn readlength [packet]
(let [[type & packet] packet
id (parsebinary (str type))
length (case id 0 15 1 11)
[length packet] (splitat length packet)]
[id (parsebinary length) packet]))
#'day16/readlength
day16> (mapcat hextobinary "38006F45291200")
(\0 \0 \1 \1 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \1 \1 \0 \1 \1 \1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)
day16> (readversionorid *1)
[1 (\1 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \1 \1 \0 \1 \1 \1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)]
day16> (readversionorid (second *1))
[6 (\0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \1 \1 \0 \1 \1 \1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)]
day16> (readlength (second *1))
[0 27 (\1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)]
Here it correctly reads the length and its type. Now we can implement the function that will process the stream of packets until it finishes. We need to store the packet versions in order to solve the first part:
day16> (defn processpacketstream [packets]
(let [[ver packets] (readversionorid packets)
[id packets] (readversionorid packets)]
(if (= id 4)
(let [[_ packets] (readvalue packets)]
[[ver] packets])
(let [[lengthid length packets] (readlength packets)
[vers packets]
(loop [length length
packets packets
innervers [ver]]
(if (> length 0)
(let [lenbefore (count packets)
[vers packets] (processpacketstream packets)]
(recur (case lengthid
0 ( length ( lenbefore (count packets)))
1 (dec length))
packets
(into innervers vers)))
[innervers packets]))]
[vers packets]))))
#'day16/processpacketstream
day16> (processpacketstream (mapcat hextobinary "A0016C880162017C3686B18A3D4780"))
[[5 1 3 7 6 5 2 2] (\0 \0 \0 \0 \0 \0 \0)]
Seems to work so far!
This function recursively calls itself when if finds an operator packet.
It determines the number of packages it needs to process recursively based on the lendthid
.
We get the list of versions as the first value of the returned vector.
Now we just need to reduce
it with addition, and we’ll get our answer.
This grants us the first gold star, let’s see what’s in part two!
Part two
So now, ununexpectedly we need to actually use values and operators stored in packets. Operators are determined by the packet ID, and are as follows:
0
 summation1
 product2
 minimum value3
 maximum value5
 greater than6
 smaller than7
 equal to
Applied to all the data in the packet. Seems easy to implement, as we just need to store values during recursion similarly to versions, and call some function based on ID when exiting the recursion step:
day16> (defn processpacketstream [packets]
(let [[ver packets] (readversionorid packets)
[id packets] (readversionorid packets)]
(if (= id 4)
(let [[val packets] (readvalue packets)]
[[ver] [val] packets])
(let [[lengthid length packets] (readlength packets)
[vers vals packets]
(loop [length length
packets packets
innervers [ver]
innervals []]
(if (> length 0)
(let [lenbefore (count packets)
[vers vals packets] (processpacketstream packets)]
(recur (case lengthid
0 ( length ( lenbefore (count packets)))
1 (dec length))
packets
(into innervers vers)
(into innervals vals)))
[innervers innervals packets]))]
(case id
0 [vers [(reduce + vals)] packets]
1 [vers [(reduce * vals)] packets]
2 [vers [(apply min vals)] packets]
3 [vers [(apply max vals)] packets]
5 [vers [(if (apply > vals) 1 0)] packets]
6 [vers [(if (apply < vals) 1 0)] packets]
7 [vers [(if (apply = vals) 1 0)] packets])))))
#'day16/processpacketstream
day16> (processpacketstream (mapcat hextobinary "A0016C880162017C3686B18A3D4780"))
[[5 1 3 7 6 5 2 2] [54] (\0 \0 \0 \0 \0 \0 \0)]
Checking the second return value grants us the second gold star.
Day 16 thoughts
Today’s task was pretty simple, but the description was very convoluted. I think I’ve spent most of the time figuring out what bits are responsive to what kind of information and so on. So I really have a question. I mean, yes, English is not my first language, but I think I’m pretty decent, as I can write, read and talk freely (albeit with some accent, and grammar issues). But I’ve spent good 20 minutes only to understand the task fully, but the leader board for this day shows people completing both parts in under 10 minutes! I understand, that there are people who compete with others and take it pretty seriously, but how do you read so fast?! I mean, yesterday’s task with pathfinding algorithm and terrain generation was completed in under 4 minutes. Four minutes! This is some serious speed programming.
I’ll try to search for the recording, but I’m generally interested in the thought process of people who’re able to solve these tasks so fast. The tasks are not too complicated, but the speed still amazes me. If you know some of the videos like this feel free to send me a link, I’ll be interested.
Day 17  Trick Shot
Today we need to send the probe into the ocean trench. To do that we need to fire the probe with certain x and y velocities, which are integers. For the first part, we need to find such velocity that the probe reaches maximum y position while still reaching the trench.
For example, for given trench coordinates:
target area: x=20..30, y=10..5
Shooting the probe with 6,3
velocities, we end up in the trench:
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 … 29 30
+
5 . . . . . . . . . . . . . . . # . . # . . . . … . .
4 . . . . . . . . . . . # . . . . . . . . # . . … . .
3 . . . . . . . . . . . . . . . . . . . . . . . … . .
2 . . . . . . # . . . . . . . . . . . . . . # . … . .
2 . . . . . . . . . . . . . . . . . . . . . . . … . .
1 . . . . . . . . . . . . . . . . . . . . . . . … . .
0 S . . . . . . . . . . . . . . . . . . . . # . … . .
1 . . . . . . . . . . . . . . . . . . . . . . . … . .
2 . . . . . . . . . . . . . . . . . . . . . . . … . .
3 . . . . . . . . . . . . . . . . . . . . . . . … . .
4 . . . . . . . . . . . . . . . . . . . . . # . … . .
5 . . . . . . . . . . . . . . . . . . . . T T T … T T
6 . . . . . . . . . . . . . . . . . . . . T T T … T T
7 . . . . . . . . . . . . . . . . . . . . T T T … T T
8 . . . . . . . . . . . . . . . . . . . . T T T … T T
9 . . . . . . . . . . . . . . . . . . . . T # T … T T
10 . . . . . . . . . . . . . . . . . . . . T T T … T T
Here we reach the highest y coordinate of 5
, and our probe crosses the trench in [9,21]
However, if the probe was fired at a different speed it might go through the trench, but never probe it, so we must ensure, that the probe touches the trench at least once.
To actually find the highest y
coordinate, we only need the minimum y value of the trench, which in this case is 10
, and take the triangular number from it:
( 10) * (1 + ( 10)) / 2 = 45
Which equals to 45
.
This also works for the real input, and it works because the bottom coordinate of the trench is the last one we’re able to hit, therefore we need to iterate it accordingly to how the velocity changes.
And the velocity changes by one, which means that ascending from position 10 + 1
will be (9)+(8)+...+(1)
.
The x
coordinate doesn’t matter here, as in ballistics x
and y
motions are independent from each other:
So it doesn’t matter what x
velocity the probe has, as long as we only care for maximum height.
Part two
Now we need to find all unique velocities, that will make the probe end up in the trench.
To do so we need to test all velocities for a range of velocities.
For x
it would be [0,max_x]
, and for y
it is [abs(min_y),abs(min_y))
.
So we need to implement the function, that determines if the given velocity vector will end up in the trench, based on how velocity changes over time.
The y
velocity simply decreases over time without a cap, so we will just use dec
function.
For x
velocity value we move towards zero from both positive and negative values:
day16> (ns day17)
nil
day17> (defn updatexvel [vel]
(cond (< vel 0) (inc vel)
(> vel 0) (dec vel)
:else 0))
#'day17/updatexvel
day17> (updatexvel 0)
0
day17> (updatexvel 2)
1
day17> (updatexvel 2)
1
Now we can write the movement function:
day17> (defn solve
([xvel yvel minx maxx miny maxy]
(when (solve 0 xvel 0 yvel minx maxx miny maxy)
[xvel yvel]))
([x xvel y yvel minx maxx miny maxy]
(cond (and (<= minx x maxx) (<= miny y maxy))
true
(or (and (< y miny) (< yvel 0))
(> x maxx)
(and (< x minx) (= xvel 0)))
nil
:else
(recur (+ x xvel) (updatexvel xvel)
(+ y yvel) (dec yvel)
minx maxx
miny maxy))))
#'day17/solve
This function is quite simple, it checks if current x
and y
coordinates are within the trench.
If they are we return the velocity vector.
If not, we move one more step.
But we stop completely when we overshoot the trench by x
or y
, or when we could not reach it by y
or x
when the respective velocity is not enough.
Let’s try it:
day17> (solve 6 3 20 30 10 5)
[6 3]
So it works for the example input, where we knew such velocity. Now we need to find all such velocities. For that we need to check the ranges, I’ve talked about earlier:
day17> (defn solveall [[minx maxx miny maxy]]
(>> (for [xv (range (inc maxx))
yv (range ( (Math/abs miny)) (Math/abs miny))]
(solve xv yv minx maxx miny maxy))
(filter some?)
distinct))
#'day17/solveall
day17> (solveall [20 30 10 5])
([6 0] [6 1] [6 2] [6 3] [6 4] [6 5] [6 6] [6 7] [6 8] [6 9] [7 1] [7 0]
[7 1] [7 2] [7 3] [7 4] [7 5] [7 6] [7 7] [7 8] [7 9] [8 2] [8 1] [8 0]
[8 1] [9 2] [9 1] [9 0] [10 2] [10 1] [11 4] [11 3] [11 2] [11 1]
[12 4] [12 3] [12 2] [13 4] [13 3] [13 2] [14 4] [14 3] [14 2]
[15 4] [15 3] [15 2] [20 10] [20 9] [20 8] [20 7] [20 6] [20 5]
[21 10] [21 9] [21 8] [21 7] [21 6] [21 5] [22 10] [22 9] [22 8]
[22 7] [22 6] [22 5] [23 10] [23 9] [23 8] [23 7] [23 6] [23 5]
[24 10] [24 9] [24 8] [24 7] [24 6] [24 5] [25 10] [25 9] [25 8]
[25 7] [25 6] [25 5] [26 10] [26 9] [26 8] [26 7] [26 6] [26 5]
[27 10] [27 9] [27 8] [27 7] [27 6] [27 5] [28 10] [28 9] [28 8]
[28 7] [28 6] [28 5] [29 10] [29 9] [29 8] [29 7] [29 6] [29 5]
[30 10] [30 9] [30 8] [30 7] [30 6] [30 5])
day17> (count *1)
112
We only need to check values in between those because others will overshoot. Plugging the real input results in the correct answer, and we get the second gold star.
Day 17 thoughts
It was an interesting discovery that we can just calculate a triangular number for the first part, and I’m a bit upset that I had to compute the second one by using almost a brute force solution. But it works, and it’s not slow, so it’s not a big deal. I wasn’t able to solve this task fast though, as I wasn’t sure how to properly approach it, and how to determine all velocities that needed to be checked. So I guess, people from the top of the table are pretty smart, as they’ve solved this task in 4.5 minutes. I mean, it’s possible to solve the first part quite fast, as it doesn’t require any coding at all, just to do the math, which isn’t really hard. But I’ve needed to figure this out first, and then write code for the second part.
Day 18
This weekend is quite different from the last one! Tasks are much harder this time, and I’m also out of the town without my laptop. So I’m writing this on my phone!^{5} I’m doing it in Emacs, installed inside Termux, which thankfully has a lot of packages, that allow me to continue working even without a laptop. And the craziest thing, that I was solving the eighteenth task on my phone too! JDK17 was recently added as a package to the main Termux repository, and this means that Clojure now can be installed directly on my phone too. This means, that I have Clojure, Emacs, and CIDER everywhere I go!
Sure, typing on the phone’s keyboard is not as pleasant as on a physical one, but I’m pretty decent at it. I was developing things on my phone for years now  almost half of the commits on my GitHub profile before the pandemic were made from the phone. So solving the AoC puzzle on the phone should not be too hard to do, especially since I can use fullblown Clojure IDE!
So let’s jump right into it!
Snailfish
Our journey to finding the sleigh keys may finally be over! Some snailfish says that they’ve seen the sleigh keys, but they won’t tell us where. Unless we’ll help them with their math homework. I guess we can, we really need every bit of information about these keys, and math should not be too complicated, given how deep we’re are already. But it turns out that snailfish numbers aren’t like our numbers at all. Each number is represented as a pair:
[1,2]
[[1,2],3]
[1,[2,3]]
[[1,2] [3,4]]
And so on. These numbers nest arbitrarily, but there are exactly two numbers in a pair.
Now, this looks like trees! Such tree can be represented by using an open square bracket as a node marker, and numbers or other square brackets will be leafs:
[
/ \
1 [
/ \
2 3
This is great because Clojure has a library for navigating treelike structures, called zippers! I’ve always wanted to look at zippers, but unfortunately, there were no tasks that required tree traversal.
Now, back to the numbers.
The addition of two numbers is simple enough.
To add two numbers [1,1]+[2,2]
we just wrap them into another set pf square brackets: [[1,1],[2,2]]
.
However, it’s not all.
Numbers need to be reduced when some conditions apply.
A number must be reduced if it has any pair nested at fourth level: [[[[[1,2],3],4],5],6]
.
In the case of this number, the [1,2]
pair is deep enough to “explode”.
An explosion of a pair is the first reduction step that we need to perform.
To do so we must add the left number from the pair with the first left number outside the pair if any.
The same is done to the right one.
Then the pair itself is replaced with a single 0
.
So for this number [[[[[1,2],3],4],5],6]
the steps are:
[1,2]
needs to explode.1
has no number on the left, so nothing happens with it. The number so far:[[[[[1,2],3],4],5],6]
.2
has3
on the right side, so we replace3
with5
. The number so far:[[[[[1,2],5],4],5],6]
 Addition was completed, and now the
[1,2]
is replaced with0
. Resulting number:[[[[0,5],4],5],6]
.
The same happens if there are only numbers from the left side, but no addition is done for the right number. And if there are numbers on both sides, they both are replaced by the sum, and the pair itself is replaced with zero.
The second reduction step happens when any number is greater than 9
.
Such a number splits into its own pair.
The left part is computed by dividing the number by 2
and rounding it down.
For the right part, the process is the same but rounded up.
So a number like [10,3]
becomes [[5,5],3]
, and a number like [11,3]
becomes [[5,6],3]
.
There’s one more thing for the reduction process. There are only two steps, but we must repeat the first one until there’s nothing left to explode. Then, if there are any numbers that can be split, we split the leftmost one. Then we go to the previous step. If the number remains unchanged in both steps, it means we’ve reached the end of the reduction process.
Phew, snailfish numbers are surely complicated. But since we, hopefully, understood the reduction process, we can begin by reading the input:
day17> (ns day18
(:require [clojure.zip :as z]
[clojure.string :as str]))
nil
day18> (defn readinput []
(> "inputs/day18"
slurp
(str/join "[]")
readstring))
#'day18/readinput
Wait, that’s cheating!
You might say that, but thankfully, Clojure can read snailfish numbers directly, as these are valid syntax!
Commas are ignored by the reader (thanks, Rich!) and square brackets represent vectors.
So to read the list of numbers into a list of vectors, we only need to join
the "[]"
string with a string of numbers as a separator!
This is a neat trick:
day18> (str/join "," "abcd") ; comma is a separator
"a,b,c,d"
day18> (str/join "abcd" "[]") ; "abcd" is a separator now
"[abcd]"
Now we can begin the homework.
The first thing we need to do is to find the leftmost pair that needs to explode. To do that, we can use zippers, and track how deep we’ve descended into the tree with a simple loop:
day18> (defn explodingnode [root]
(loop [level 0
loc (z/vectorzip root)]
(cond (and (= level 4) (z/branch? loc))
loc
(z/branch? loc)
(recur (inc level) (z/down loc))
(z/right loc) (recur level (z/right loc))
:else
(let [[level loc]
(loop [level (dec level)
loc (z/up loc)]
(cond (and (= level 0) (not (z/right loc)))
[level nil]
(not (z/right loc))
(recur (dec level) (z/up loc))
:else
[level (z/right loc)]))]
(when loc
(recur level loc))))))
#'day18/explodingnode
This function accepts a number and uses the vectorzip
function on it.
Then we traverse the tree, tracking when we go down
and up
.
Once we’ve found the needed node, we return it’s location as a zipper:
day18> (explodingnode [[[[[1,2],3],4],5],6])
[[1 2]
{:l [],
:pnodes
[[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4] [[1 2] 3]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5]],
:ppath
{:l [], :pnodes [[[[[[1 2] 3] 4] 5] 6]], :ppath nil, :r (6)},
:r (5)},
:r (4)},
:r (3)}]
Now, we need a way of finding numbers to the left and to the right of this pair.
Since there’s no number to the left right now, let’s write the findright
function first:
day18> (defn findright [loc]
(whennot (= (z/root loc) (z/node loc))
(iflet [right (z/right loc)]
(if (z/branch? right)
(loop [loc right]
(if (z/branch? loc)
(recur (z/next loc))
loc))
right)
(recur (z/up loc)))))
#'day18/findright
This function accepts a location in the tree and starts from it.
We only do the search for nodes that are not the root ones, as the root has no numbers outside of it.
First, we check if there’s a number to the right of the current location.
If not we simply ascend.
If there is a number, it means that we never need to ascend again, so we check whether it is a branch?
, meaning that we’re looking at another pair.
If not, we’ve found our number, so we return it.
If it is a branch we loop
moving to the next
element until we find one that is not a branch.
Let’s try it:
day18> (findright (explodingnode [[[[[1,2],3],4],5],6]))
[3
{:l [[1 2]],
:pnodes
[[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4] [[1 2] 3]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5]],
:ppath
{:l [], :pnodes [[[[[[1 2] 3] 4] 5] 6]], :ppath nil, :r (6)},
:r (5)},
:r (4)},
:r nil}]
The return value is another location in the tree.
Now, let’s do the same for the left number.
It’s a bit trickier, as we need to find the right number on the left side.
E.g. for this number [[7,6],[[[[5,4],3],2],1]]
the exploding pair is [5,4]
, and the left number is 6
:
day18> (defn findleft [loc]
(whennot (= (z/root loc) (z/node loc))
(iflet [left (z/left loc)]
(if (z/branch? left)
(loop [loc (z/next left)]
(let [loc (z/rightmost loc)]
(if (z/branch? loc)
(recur (z/next loc))
loc)))
left)
(recur (z/up loc)))))
#'day18/findleft
day18> (z/node (explodingnode [[7,6],[[[[5,4],3],2],1]]))
[5 4]
day18> (z/node (findleft (explodingnode [[7,6],[[[[5,4],3],2],1]])))
6
This function also ascends until there’s something on the left side, but then it descends to the rightmost element of each level.
It returns the location of the left number, which we render with the node
function, to keep the output short.
Now we can find the required numbers:
day18> (let [loc (explodingnode [[7,6],[[[[5,4],3],2],1]])
left (findleft loc)
right (findright loc)]
(println (format "exploding pair: %s\nleft: %s\nright: %s"
(z/node loc)
(z/node left)
(z/node right))))
exploding pair: [5 4]
left: 6
right: 3
nil
Good!
Now let’s implement the explosion step of the reduction process.
To do that, we need to change the tree.
Thankfully, zippers, while being immutable, support tree editing.
To change the tree, we need to find a location that is ready to be exploded and side numbers.
The structure of the numbers tells us that there will always be at least one number to the side.
So we can check which one is there, replace it with the sum, and then replace the location itself with 0
:
day18> (defn explode [root]
(iflet [loc (explodingnode root)]
(let [[a b] (z/node loc)
left (findleft loc)
right (findright loc)]
(> (cond (not left) (z/edit right + b)
(not right) (z/edit left + a)
:else (> left
(z/edit + a)
z/root
explodingnode
findright
(z/edit + b)))
z/root
explodingnode
(z/replace 0)
z/root))
root))
#'day18/explode
day18> (explode [[7,6],[[[[5,4],3],2],1]])
[[7 11] [[[0 7] 2] 1]]
In case where both numbers are available we have to do additional searches.
Unfortunately zippers are new to me, so maybe there’s a more optimal way of doing this, but I wasn’t able to find it.
My guess was to use the path
function, but it seems that there’s no way to navigate to a certain location in the changed zipper, but to search it from the root again.
Maybe I could write such function, but the semantics of the task allow me to just find the same exploding node from the root again.
This number explodes correctly, and we now have a number that can be split.
Let’s write a function, that finds the leftmost number that is greater than 9
:
day18> (defn splittablenode [root]
(loop [loc (z/vectorzip root)]
(whennot (z/end? loc)
(cond (z/branch? loc)
(recur (z/next loc))
(> (z/node loc) 9)
loc
:else
(recur (z/next loc))))))
#'day18/splittablenode
day18> (z/node (splittablenode *2))
11
Seems correct. Now let’s write another function, that splits the given location:
day18> (defn split [root]
(iflet [loc (splittablenode root)]
(> loc
(z/edit (juxt #(int (Math/floor (/ % 2)))
#(int (Math/ceil (/ % 2)))))
z/root)
root))
#'day18/split
day18> (split [[7 11] [[[0 7] 2] 1]])
[[7 [5 6]] [[[0 7] 2] 1]]
It’s always so pleasant when you can use the juxt
function.
Now we only need to implement addition with all necessary reduction steps:
day18> (defn sum [a b]
(loop [x [a b]]
(let [x' (explode x)]
(if (= x' x)
(let [x' (split x')]
(if (= x x')
x'
(recur x')))
(recur x')))))
#'day18/sum
day18> (sum [7,6] [[[[5,4],3],2],1])
[[7 [5 6]] [[[0 7] 2] 1]]
This loop will explode
the number until the number remains the same as before the explosion.
Then it will split a single number, and repeat.
If the number is unchanged after a split, means we’ve finished.
To actually compute the answer, we need to implement another function that calculates the magnitude. To do that we need to multiply the left part of the pair by 3 and the right pair by 2, then add them:
day18> (defn magnitude' [loc]
(cond (z/end? loc)
(z/root loc)
(z/branch? loc)
(let [loc (z/next loc)
left (magnitude' loc)
right (magnitude' (z/right loc))]
(z/replace loc (+ (* 3 (z/node left)) (* 2 (z/node right)))))
:else
loc))
#'day18/magnitude'
day18> (defn magnitude [root]
(z/node (magnitude' (z/vectorzip root))))
#'day18/magnitude
Finally, given that we have a list of numbers we need to add together, we can use reduce
on it with our sum
function, and then compute the magnitude for the final answer:
day18> (defn part1 [input]
(>> input
(reduce sum)
magnitude))
#'day18/part1
day18> (part1 (readinput))
3763
This grants us the first gold star!
Part two
For the second part, we need to find the largest magnitude across all numbers.
The catch is that snailfish addition is not commutative, which means that a+b
is not necessarily equal to b+a
, so we need to check all variants.
It’s quite simple in Clojure, thanks to for
:
day18> (defn part2 [input]
(>> (for [a input
b input]
(whennot (= a b)
(magnitude (sum a b))))
(filter some?)
(apply max)))
#'day18/part2
day18> (part2 (readinput))
4664
Here checking if the numbers are the same to avoid adding them.
This introduces elements that are nil
in our final list, so we filter
them out.
Then we just find the max value, and get the second gold star!
Day 18 thoughts
Phew, this was challenging! Writhing all of this on the phone, while simultaneously learning about zippers, is definitively something. The task itself wasn’t as hard, but there were some tricky parts with finding the correct number, which was extremely hard to debug, especially on the phone’s screen:
Day 19
Unfortunately, I wasn’t able to solve this task. I seriously couldn’t understand what I even need to do with all these coordinates. Maybe I’ll solve it later, though I highly doubt that I’ll come back to any missed day or previous events for that matter.
Well, a continuous 18 days streak for this year’s AoC seems good to me. The previous year ended at day 15, which I had not completed, and couldn’t find any willpower to continue.
Maybe tomorrow’s task will be more understandable, and so I’ll just skip a single day. We’ll see how it goes.
Day 20  Trench Map
With the scanners fully deployed (totallyDay 19][totally]]), we now can compute the map of the trench. But when we get the image from the scanners, it looks like a random noise (I wonder why, perhaps because of the extremely convoluted positioning in the previous task?). So we need to enhance the image with a certain algorithm.
The algorithm consists of the string, that specifies how to enhance a particular image pixel. The example input consists of such string and an image:
..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
#..#.
#....
##..#
..#..
..###
To determine the value of the pixel we need to look at all pixels around this pixel and construct a binary number.
For simplicity let’s replace #
with 1
and .
with 0
, and mark pixels that surround the middle one:
1 0 0 1 0
1 [0 0 0] 0
1 [1 0 0] 1
0 [0 1 0] 0
0 0 1 1 1
This forms a binary number 000100010
, which is 34
in decimal.
So, to enhance the current pixel, we need to take value from the enhancement string at this position, which happens to be #
or 1
.
We then repeat this for each pixel on the image.
However, the image is actually infinite, and we need to process it as a whole.
This task looks like a cellular automaton once again, as the image basically grows between iterations, as some previously dark pixels will become light or dark, depending on the surroundings. Let’s start by reading the input. First, I’d like to transform the image itself to a table of coordinates as keys, and brightness as values:
user> (ns day20
(:require [clojure.string :as str]))
nil
day20> (defn img>coords [img]
(reducekv (fn [img y line]
(reducekv (fn [img x c]
(assoc img [x y] (if (= c \#) 1 0)))
img (vec line)))
(sortedmap)
(str/split img #"\n")))
#'day20/img>coords
day20> (img>coords "#..\n.#.\n..#")
{[0 0] 1,
[0 1] 0,
[0 2] 0,
[1 0] 0,
[1 1] 1,
[1 2] 0,
[2 0] 0,
[2 1] 0,
[2 2] 1}
We’ll also parse the enhancement string as a vector of zeroes and ones:
day20> (defn readinput []
(let [[enh img] (> "inputs/day20"
slurp
(str/split #"\n\n"))]
{:enhance (mapv #(if (= % \#) 1 0) enh)
:image (img>coords img)}))
#'day20/readinput
Now, when we have our image and enhancement string parsed, we can write a function that will enhance a given image. First, we need to write a function, that reads the pixel’s value and values of all surrounding pixels. It then computing an index in the enhancement string, and gets the enhancement value from that string:
day20> (defn enhancement [{:keys [image enhance]} [x y] default]
(nth enhance
(> (for [y [(dec y) y (inc y)]
x [(dec x) x (inc x)]]
(get image [x y] default))
str/join
(Long/parseLong 2))))
#'day20/enhancement
Note that I’m using an explicit default value, but let’s forget about it for now.
Our image is infinite, and we only have a portion of it, so we need to extend the image somehow.
To do that we’ll just decrease the minimum image coordinate by 1
and increase the maximum by 1
.
We’ll do it during the enhancement process, so the new image will become larger automatically:
day20> (defn enhance [{:keys [enhance image] :as img} step]
(let [points (keys image)
[minx miny] (first points)
[maxx maxy] (last points)
default (cond (zero? step) 0
(even? step) (peek enhance)
:else (first enhance))]
{:image (into
(sortedmap)
(for [x (range (dec minx) (+ maxx 2))
y (range (dec miny) (+ maxy 2))]
[[x y] (enhancement img [x y] default)]))
:enhance enhance}))
#'day20/enhance
This default
value is the bane of my existence.
I’ve spent hours trying to understand why it is needed, and why at the first step it must be 0
.
So I assume, that it is zero (or .
in case of the task) on the first step is because we start with an empty image.
Then we need to check what step we’re on and enhance using the first or the last value in the string.
This is because when we expand the image new pixels are always zeroes, and thus will be converted to ones.
The final thing needed to do is to find all light pixels and count them  easy:
day20> (defn solve [n input]
(>> (reduce #(enhance %1 %2) input (range n))
:image
vals
(reduce +)))
#'day20/solve
day20> (solve 2 (readinput))
5619
Now, the craziest thing is that this solution will work the real input even without the (zero? step)
case, but will not work for example one!
Here:
day20> (defn enhance [{:keys [enhance image] :as img} step]
(let [points (keys image)
[minx miny] (first points)
[maxx maxy] (last points)
default (cond #_#_(zero? step) 0
(even? step) (peek enhance)
:else (first enhance))]
{:image (into
(sortedmap)
(for [x (range (dec minx) (+ maxx 2))
y (range (dec miny) (+ maxy 2))]
[[x y] (enhancement img [x y] default)]))
:enhance enhance}))
#'day20/enhance
day20> (solve 2 (readinput))
5619
day20> (defn readinput []
(let [[enh img] (> "inputs/day20example"
slurp
(str/split #"\n\n"))]
{:enhance (mapv #(if (= % \#) 1 0) enh)
:image (img>coords img)}))
#'day20/readinput
day20> (def exampleinput (readinput))
#'day20/exampleinput
day20> (solve 2 exampleinput)
34
It yields 34
instead of expected 35
but works for real input regardless.
Part two is just the same as part one, just with 50
steps instead of two:
day20> (solve 50 exampleinput)
5209
day20> (solve 50 (readinput)) ; using the original function
20122
Keep in mind that this is without the (zero? step)
, so 5209
is the wrong answer for example input.
But 20122
is the correct value for the real input.
Consider the same but with original enhance
function:
day20> (solve 2 exampleinput)
35
day20> (solve 50 exampleinput)
3351
day20> (solve 50 (readinput))
20122
And I’ve tested this on several inputs  it works, and I don’t understand why, honestly.
Day 20 thoughts
While working on this puzzle on the first development iteration I wrote an algorithm that always used zeroes as extended values. It worked on the example input, and on the real input but only for part one! And when I’ve tested it on different inputs it didn’t work, so I mean, this task is extremely finicky. Especially since I got the right answer for part one with the wrong code on one input nonexample, but it didn’t work for another.
Day 21  Dirac Dice
As it seems, when there are neither any problems to solve outside of the submarine nor inside of it, the computer still wants to give us some trouble! This time, though it is just a mere desire to play a game with us.
The game is simple, we have a circular board with 10 spaces. We throw dice three times and move our pawn amount of rolls added together. The score is initially zero, and each time we step on a certain space, we add this space to the score.
As a practice game, a computer offers us deterministic dice, which always roll in increasing order from 1 to 100.
And each player rolls three times, which means that the first one will roll 1
, 2
, and 3
, moving forward by 6
places.
The second player will roll 4
, 5
, and 6
, and move forward by 15
places.
The game ends when the first player reaches 1000
or more points.
Let’s start by parsing an input:
day20> (ns day21
(:require [clojure.string :as str]
[aoccommons :refer [parselong]]))
nil
day21> (defn readinput []
(reduce #(let [[_ player pos] (refind #".*(\d+).*(\d+)" %2)
player (parselong player)
pos (parselong pos)]
(assoc %1 player
{:pos pos
:score 0}))
(sortedmap)
(>> "inputs/day21"
slurp
str/splitlines)))
#'day21/readinput
day21> (readinput)
{1 {:pos 3, :score 0}, 2 {:pos 4, :score 0}}
I’m kinda lazy right now, so this code, while ugly, works for me. It returns a sorted map of players, which we will iterate. I’m using a map as it is easier to update than a vector, and the order is deterministic. Now we can jump into solving part one.
First thing we need to do is to form the infinite sequence of rolls:
day21> (set! *printlength* 10)
10
day21> (map (partial apply +) (partition 3 (cycle (range 1 101))))
(6 15 24 33 42 51 60 69 78 87 ...)
I’m generating a sequence of numbers from 1 to 100 and then using the cycle
function, to make this sequence repeat infinitely.
Next, we partition it into groups of three, and add each one, effectively changing the game so there’s only one roll per player.
Now we can just reduce this sequence, by switching players.
day21> (defn step [[throws players turns] [i player]]
(let [pos (inc (mod (+ (:pos player) (dec (first turns))) 10))
score (+ (:score player) pos)]
((if (>= score 1000)
reduced
identity)
[(+ throws 3)
(update players i
assoc
:pos pos
:score score)
(rest turns)])))
#'day21/step
This is a reducing function, that accepts the current amount of throws, players map, and sequence of turns as its first argument.
As the second argument, it accepts a player.
We simply calculate a new position, and score, and check if the score is greater than 1000
.
If it is we use reduced
to terminate the reduce
, and return the final result.
Now we only need to loop
until any player wins:
day21> (defn part1 [input]
(loop [throws 0
rolls (map (partial apply +) (partition 3 (cycle (range 1 101))))
players input]
(let [[throws players turns] (reduce step [throws players rolls] players)]
(if (some #(>= (:score (second %)) 1000) players)
(* throws (apply min (map (comp :score second) players)))
(recur throws
turns
players)))))
#'day21/part1
day21> (part1 (readinput))
995904
This was easy, but I suspect that the next part will be about something like computing the most optimal winning sequence of rolls or computing all possible games. So such a plain approach probably will not work.
Part two
Part two puts a twist on the game by changing the dice to Dirac dice.
This dice, when rolled, splits the universe to all possible outcomes of a single roll.
Since this dice has three sides it means that on each roll there are three new universes, in each of which the result is 1
, 2
, and 3
respectively.
The game still plays by rolling three times per player, which means on each turn the universe splits into 27 universes.
The task mentions that player one wins in 444356092776315
universes, so there’s no way we’ll be able to calculate all of that by brute force.
On the other hand, we can. If you know what the Fibonacci sequence is, you may also know that there are two ways of doing it  by using iteration and with recursion. Recursive approach is quite simple:
day21> (defn fib [n]
(if (or (= n 0) (= n 1))
1
(+' (fib ( n 1)) (fib ( n 2)))))
#'day21/fib
day21> (fib 4)
5
day21> (map fib (range 10))
(1 1 2 3 5 8 13 21 34 55)
day21> (time (fib 42))
"Elapsed time: 7221.764838 msecs"
433494437
The problem with this approach is that it splits into two branches on each number, and each branch recomputes the result over and over again:
. fib 5 .
/ \
. fib 4 . . fib 3 .
/ \ / \
. fib 3 . fib 2 fib 2 fib 1
/ \ / \ / \ 
fib 2 fib 1 fib 1 fib 0 fib 1 fib 0 1
/ \     
fib1 fib 0 1 1 1 1 1
 
1 1
As can be seen, fib 2
is computed 3
times, fib 1
is computed 1
times, and so on.
For bigger numbers, this tree becomes very wide.
But there’s an easy fix for that  we can memoize function calls, and cut this tree to a single branch:
fib 5
/ \
fib 4 memo
/ \
fib 3 memo
/ \
fib 2 memo
/ \
fib1 fib 0
 
1 1
Now, all duplicate branches are computed from memoized values. Sure, this uses more memory, but makes this variant very efficient:
day21> (def fib
(memoize
(fn [n]
(if (or (= n 0) (= n 1))
1
(+' (fib ( n 1)) (fib ( n 2)))))))
#'day21/fib
day21> (time (fib 42))
"Elapsed time: 1.176521 msecs"
433494437
day21> (time (fib 200))
"Elapsed time: 1.449005 msecs"
453973694165307953197296969697410619233826N
This will be our strategy for the second part. We’ll write the task as if we really were to play all games, but we’ll just memoize already played ones and cut the tree.
day21> (def play
(memoize
(fn [players turn]
(loop [[roll & rolls] (for [a [1 2 3] b [1 2 3] c [1 2 3]] [a b c])
wins {}]
(if roll
(let [roll (apply + roll)
p (players turn)
pos (inc (mod (+ (:pos p) (dec roll)) 10))
score (+ (:score p) pos)]
(if (> score 20)
(recur rolls (update wins turn (fnil inc 0)))
(let [players (update players turn assoc :pos pos :score score)
wins' (play players
(inc (mod turn (count players))))]
(recur rolls (mergewith + wins wins')))))
wins)))))
#'day21/play
I use for
to compute a sequence of rolls for each of 27 universes.
And wins are stored in the wins
table, where each player has their own score.
If the game is won we just return new wins
state, and go into the next game.
If the game isn’t won we go into parallel universes, and that’s where memoization comes into play.
Since we memoize players with their states, and a turn, we know for sure if we’ve played some game, as the game’s result is memoized.
The turns are cycled between players, meaning on each call of play
we increase the player’s number until there are no more players, e.g. 1
, 2
, 1
, 2
.
This will work with more players, even though there are no more players in the task.
Now we only need to determine who wins more:
day21> (defn part2 [input]
(apply max (vals (play input 1))))
#'day21/part2
day21> (part2 (readinput))
193753136998081
Phew, that’s a lot of games!
Day 21 thoughts
This was interesting indeed. I don’t know from where exactly I remember the memoization trick for the Fibonacci sequence, but this knowledge surely helped me to understand the problem. Other than that, this was pretty straightforward to solve.
Day 22  Reactor Reboot
Today we need to reboot the reactor.
Unfortunately, the reactor is made out of cuboids that can intersect in 3D space.
First part requires us to figure out which cubes are on
or off
, but only for the range of 50
to 50
for each coordinate.
This is a grand total of 1030301
cubes, so we can solve this by brute force approach, which I’m absolutely sure will not work for the second part, but I did it anyway.
The second part simply wants us to process a whole range of cubes, and I’ve thought about it for a bit and decided not to waste any more time on this. Honestly, the tasks lately are becoming really tedious and boring while not being really challenging. Seriously, there already were three tasks that are like “hey here’s an exponential growth, try it on a small sample, then do it on a whole one”. This one is no different.
I mean, the second part is essentially about keeping all ranges and subtracting overlapping ranges that are off from all currently existing ranges. The only challenge here is to properly write the detection and subtracting code. Then the remaining ranges need to be computed into the total amount of cubes. I just don’t want to waste time on this, I’ve seen such type of task three (or more) times already during this event only.
To be completely fair, I really wanted to complete this event, but as it seems I will not do it. I’m losing steam and don’t feel invested enough with the quite low variety of tasks this year.
Day 23  Amphipod
And they did it again. Today’s task is yet again “try this easy part, that can be solved by brute force. Yes, correct… now suffer from all this extra data you need to process” type of task. Our task is to move every Amphipod into their room:
############# #############
#...........# #...........#
###B#C#B#D### > ###A#B#C#D###
#A#D#C#A# #A#B#C#D#
######### #########
Each Amphipod is marked as a letter, and we can only place letters above #
symbols.
Furthermore, letters can only go into their own room, and only if there are no letters from other rooms.
In other words, these cases are invalid:
############# #############
#..B........# #.....C.....#
###.#C#B#D### ###.#B#B#D###
#A#D#C#A# #A#D#C#A#
######### #########
B stands over B entered a room that still contains D
the room's exit which don't belong to that room
We have a hallway with two pockets on each side, each of which can contain two letters at most, and we also have three more positions between rooms.
Letters can’t go over each other, so we need to avoid deadlocks.
The other catch is that each letter has a different move cost.
A
costs 1
point, B
costs 10
, C
costs 100
, and D
costs 1000
.
This means that we should try to never move D
more than once, and we can probably do some extra moves of A
and B
, but not too much.
Overall this looks like a Hanoi Tower type of task, but instead of moving sorted pillars of disks from one pole to another pole, we need to sort discs between poles. In the case of the following example, there aren’t too many ways we can solve it, because of deadlocks and move costs. But I’m not in the coding mood today, so let’s use a neural network instead, and let it solve the task for us without any line of code. By neural network, I mean my own brain ofc.
So I’ve tried it 4 times, and figured that the following sequence of moves leads to the most optimal result:
############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# #############
#...........# #..........A# #.........CA# #.........CA# #.A.......CA# #.A.B.....CA# #.A.B......A# #.A.B......A# #.A........A# #.A........A# #.A........A# #..........A# #...........#
###B#B#D#A### ###B#B#D#.### ###B#B#D#.### ###B#B#.#.### ###B#B#.#.### ###B#.#.#.### ###B#.#.#.### ###B#.#C#.### ###B#.#C#.### ###.#B#C#.### ###.#B#C#D### ###.#B#C#D### ###A#B#C#D###
#D#C#A#C# #D#C#A#C# #D#C#A#.# #D#C#A#D# #D#C#.#D# #D#C#.#D# #D#C#C#D# #D#.#C#D# #D#B#C#D# #D#B#C#D# #.#B#C#D# #A#B#C#D# #A#B#C#D#
######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### #########
0 3 300 5000 7 20 50 50 30 40 9000 3 9
Adding these together we get the correct result 14512
.
But the second part will not be that easy, because it adds two more rows to the rooms, with the preset pattern:
#############
#...........#
###B#B#D#A###
#D#C#B#A# < these
#D#B#A#C# < ones
#D#C#A#C#
#########
Now there a lot more moves to consider.
Well, given that the first column contains all three D
letters, we can safely assume that we will have at very least three moves 11000
worth of points.
Two C
letters in the last room are likely to be moved after we already fully empty the second room, so that’s another 1400
points.
Then we move A
letters to the packets, finish C
room, and then D
room, finishing with A
room.
Well, that’s just a guess based on the whole situation, so let’s try this:
############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# #############
#...........# #..........D# #B.........D# #BA........D# #BA.......AD# #BA.B.....AD# #BA.B.....AD# #BA.B...B.AD# #BA.B...B.AD# #BA.....B.AD# #BA.......AD# #BA.......AD# #B....A...AD# #.....A...AD# #A........AD# #AA.......AD# #AA...A...AD# #AA...A...AD# #AA...A...AD# #AA...A.A..D# #AA...A.A...# #AA...A....A# #AA.......AA# #AA.......AA# #AA.......AA# #AA.......AA# #A........AA# #.........AA# #..........A# #...........#
###B#B#D#A### ###B#B#.#A### ###B#B#.#A### ###B#B#.#A### ###B#B#.#A### ###B#.#.#A### ###B#.#.#A### ###B#.#.#A### ###B#.#.#A### ###B#.#.#A### ###B#.#.#A### ###.#.#.#A### ###.#.#.#A### ###.#B#.#A### ###.#B#.#A### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#D### ###.#B#C#D### ###.#B#C#D### ###.#B#C#D### ###A#B#C#D###
#D#C#B#A# #D#C#B#A# #D#C#.#A# #D#C#.#A# #D#C#.#A# #D#C#.#A# #D#.#.#A# #D#.#.#A# #D#.#.#A# #D#.#.#A# #D#.#.#A# #D#B#.#A# #D#B#.#A# #D#B#.#A# #D#B#.#A# #D#B#.#A# #D#B#.#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #.#B#C#.# #.#B#C#D# #.#B#C#D# #.#B#C#D# #.#B#C#D# #A#B#C#D# #A#B#C#D#
#D#B#A#C# #D#B#A#C# #D#B#A#C# #D#B#.#C# #D#B#.#C# #D#B#.#C# #D#B#.#C# #D#.#.#C# #D#.#C#C# #D#.#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#D# #.#B#C#D# #.#B#C#D# #.#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D#
#D#C#A#C# #D#C#A#C# #D#C#A#C# #D#C#A#C# #D#C#.#C# #D#C#.#C# #D#C#C#C# #D#C#C#C# #D#.#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#.# #D#B#C#.# #D#B#C#D# #D#B#C#D# #D#B#C#D# #D#B#C#D# #D#B#C#D# #.#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D#
######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### #########
0 5000 80 8 7 20 800 60 900 50 60 50 4 50 5 8 5 700 700 2 6000 3 4 11000 11000 11000 5 5 9 9
This gives us the total of 47544
points:
However, this is not the correct answer.
I’ve noticed that instead of moving B
to the left pocket, which I’ve assumed would be the most optimal move, I can instead move it to the right pocket.
This will add up later, but we can solve this in a bit fewer moves of A
letters:
############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# #############
#...........# #..........D# #.........BD# #A........BD# #AA.......BD# #AA.....B.BD# #AA.....B.BD# #AA.B...B.BD# #AA.B...B.BD# #AA.....B.BD# #AA.....B.BD# #AA.......BD# #AA.......AD# #AA...A...AD# #AA...A...AD# #AA...A...AD# #AA...A.A..D# #AA...A.A...# #AA...A....A# #AA.......AA# #AA.......AA# #AA.......AA# #AA.......AA# #A........AA# #.........AA# #..........A# #...........#
###B#B#D#A### ###B#B#.#A### ###B#B#.#A### ###B#B#.#A### ###B#B#.#A### ###B#.#.#A### ###B#.#.#A### ###B#.#.#A### ###B#.#.#A### ###B#.#.#A### ###.#.#.#A### ###.#.#.#A### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#.### ###.#B#C#D### ###.#B#C#D### ###.#B#C#D### ###.#B#C#D### ###A#B#C#D###
#D#C#B#A# #D#C#B#A# #D#C#.#A# #D#C#.#A# #D#C#.#A# #D#C#.#A# #D#.#.#A# #D#.#.#A# #D#.#.#A# #D#.#.#A# #D#.#.#A# #D#B#.#A# #D#B#.#A# #D#B#.#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #.#B#C#.# #.#B#C#D# #.#B#C#D# #.#B#C#D# #.#B#C#D# #A#B#C#D# #A#B#C#D#
#D#B#A#C# #D#B#A#C# #D#B#A#C# #D#B#.#C# #D#B#.#C# #D#B#.#C# #D#B#.#C# #D#.#.#C# #D#.#C#C# #D#.#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#.# #D#B#C#D# #.#B#C#D# #.#B#C#D# #.#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D#
#D#C#A#C# #D#C#A#C# #D#C#A#C# #D#C#A#C# #D#C#.#C# #D#C#.#C# #D#C#C#C# #D#C#C#C# #D#.#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#C# #D#B#C#.# #D#B#C#.# #D#B#C#D# #D#B#C#D# #D#B#C#D# #D#B#C#D# #D#B#C#D# #.#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D#
######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### #########
0 5000 50 9 9 40 800 40 900 50 60 50 60 5 700 700 2 6000 3 4 11000 11000 11000 5 5 9 9
This gives us 47510
points, which is less than our previous result, but still not correct.
The problem is, I don’t know if this answer is too low or too high, as the page stopped giving hints at some point, to avoid bisecting, I guess.
So I can’t verify if I’m doing it completely wrong in case this answer is too low, or I’m not doing it optimal enough if it is too high.
However, since I’m not going to write code for this task, I’ve decided to cheat. I went to the leaderboard and found the solution for this task. Funnily enough, I’ve noticed that I’m not the only one who decided to solve this task by hand, and some of these people are as high as 14th rank. Pretty impressive, as this task is not an easy one to do manually, given all possible variants.
But I’m here for the answers, and the code says that the correct answer is… 52358
!
I’m not going to submit it just because someone else computed it for me, I just wanted to see if I’m not doing it optimally or not.
But wait, my solution is much more optimal than that, what the hell?
Have I made a wrong move somehow or have I misinterpreted the rules?
While doing this I’ve checked that I basically:
 never step into the tiles that are directly above the room.
 never went into the other’s letter’s room.
 never jumped over another letter.
The rule about not standing above the room is a bit vague. It explicitly says that it refers to four open places above each room, so naturally, I think it’s safe to assume that we can never stand on those. But then it also mentions: “this refers to the four open spaces in the hallway that are directly above an amphipod starting position”. So this means that we can stand on this tile when we’re not moving out of the room or what?
############# #############
#........A..# #......A....#
###B#B#D#.### ###B#B#D#.###
#D#C#B#A# #D#C#B#A#
#D#B#A#C# #D#B#A#C#
#D#C#A#C# #D#C#A#C#
######### #########
forbidden. allowed???
I guess it’s not allowed, as the rule says that “never stop on the space immediately outside any room”. I’m not sure why they decided to mention the “above an amphipod starting position” part at all. So from now on, I’ll assume that both cases are forbidden. But I never used such moves in my solution, so what exactly have I done wrong?
Turns out, I’ve forgotten about one critical rule.
You can’t move in the hallway once you’ve stopped there.
From the hallway, you can only move into the room.
And In my solution, I’m moving letter A
back and forth through the hall to make room for maneuvers.
Now, this surely complicates the task.
However, it also cuts down a lot of possible moves.
So our strategy should be basically about finding optimal starting moves that occupy hallway ends and provide enough room for other letter moves. I’ve thought that it should not be that bad, but it turns out it was pretty hard. (who would have guessed?) Anyway, after about 18 tries (I’ve lost count) that ended in a deadlock one way or another, I’ve managed to do it like this:
############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# ############# #############
#...........# #B..........# #B.........D# #B........DD# #BD.......DD# #BD.......DD# #BD.C.....DD# #BD.C.C...DD# #BD.C.C...DD# #BD.C.C....D# #BD.C.C.....# #BD.C.C....B# #BD.C.C.A.AB# #BD.C...A.AB# #BD.....A.AB# #BD.......AB# #BD........B# #B.........B# #BB........B# #BB........B# #BB.B......B# #BB.B......B# #BB........B# #B.........B# #..........B# #...........#
###B#B#D#A### ###.#B#D#A### ###.#B#D#A### ###.#B#D#A### ###.#B#D#A### ###.#B#D#.### ###.#B#D#.### ###.#B#D#.### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###.#B#.#.### ###A#B#.#.### ###A#B#.#D### ###A#.#.#D### ###A#.#.#D### ###A#.#.#D### ###A#.#C#D### ###A#.#C#D### ###A#.#C#D### ###A#.#C#D### ###A#B#C#D###
#D#C#B#A# #D#C#B#A# #.#C#B#A# #.#C#B#A# #.#C#B#A# #.#C#B#A# #.#C#B#.# #.#C#B#.# #.#C#B#.# #.#C#B#.# #.#C#B#D# #.#C#.#D# #.#C#.#D# #.#C#.#D# #.#C#.#D# #A#C#.#D# #A#C#.#D# #A#C#.#D# #A#C#.#D# #A#.#C#D# #A#.#C#D# #A#.#C#D# #A#.#C#D# #A#.#C#D# #A#B#C#D# #A#B#C#D#
#D#B#A#C# #D#B#A#C# #D#B#A#C# #.#B#A#C# #.#B#A#C# #.#B#A#C# #A#B#A#.# #A#B#A#.# #A#B#A#.# #A#B#A#D# #A#B#A#D# #A#B#A#D# #A#B#.#D# #A#B#.#D# #A#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D# #A#.#C#D# #A#.#C#D# #A#.#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D#
#D#C#A#C# #D#C#A#C# #D#C#A#C# #D#C#A#C# #.#C#A#C# #A#C#A#C# #A#C#A#C# #A#C#A#.# #A#C#A#D# #A#C#A#D# #A#C#A#D# #A#C#A#D# #A#C#.#D# #A#C#C#D# #A#C#C#D# #A#C#C#D# #A#C#C#D# #A#C#C#D# #A#C#C#D# #A#C#C#D# #A#C#C#D# #A#.#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D# #A#B#C#D#
######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### ######### #########
0 30 10000 10000 5000 11 800 700 7000 4000 4000 60 5 500 600 7 8 8000 40 600 40 700 50 60 60 70
Which indeed computes to 52358
, so the code I’ve tried was correct.
I’m not sure if there is actually more than one solution to this problem.
With all rules listed in the task, it looks like that there can be only one solution.
So the code can probably just recursively try all games and cut branches that end in a deadlock.
Anyway, we got through, and there are only two days left. I’m unsure if I’ll be able to solve the 25th day in time, as I’ll be out yet again this weekend.
Day 24
Unfortunately, I’ve decided not to solve this task. It does require reverseengineering the given code, and I’m just not motivated enough to do that. So yet another task that needs to be done by hand is just too much for me. Sure today’s task is interesting, I’m just too exhausted to do it.
After the event ends, I’ll be removing all individual posts and will publish a single post, containing all days I’ve managed to solve. Let’s see what waits for us tomorrow and finish this.
Day 25  Sea Cucumber
This is it. The last puzzle of the event. We’ve almost made it through. The only thing that stands between us, and the sleigh keys are two herds of sea cucumbers.
Cucumbers are constantly in the move, and our task is to simulate their behavior.
There are two herds, one that always moves east, and another one that always moves south.
They’re represented with >
and v
respectively:
....v.....
.>v....v..
.......>..
....v....>
On each step, first, the south herd moves one step forward, then the south herd moves one step downward.
Cucumbers can only go into the empty place, marked with a dot .
, and will wait if there’s no room.
For the example above, the south herd moves first:
....v.....
.>v....v..
........>.
>...v.....
As can be seen the leftmost >
couldn’t move, because there’s v
standing in its way.
The second and third >
cucumbers moved freely.
The third one actually crossed the gap of the field and moved to the other side, almost as if we’re in a cylindrical world.
Then the south herd moves:
..........
.>..v.....
..v....v>.
>...v.....
All three topmost v
cucumbers were able to move.
However, because the moves are executed simultaneously, the bottom v
could not move, as the other cucumber was still in the starting position, from its perspective.
So we basically need to implement these rules and run the simulation. I hope the second part won’t require us to run the simulation one million times on a much bigger field, otherwise, I will be very disappointed. Looking at the leaderboard, it seems that the second part took approximately six seconds to solve, so it’s either some very little derivation in the algorithm, or the requirements for the task are just bigger, but the code is so optimal that it can handle it in no time.
Ok, we actually need to write the code today, so let’s do it quickly:
user> (ns day25 (:require [aoccommons :refer [slurplines transpose]]))
nil
day25> (defn readinput []
(>> "inputs/day25"
slurplines
(mapv vec)))
#'day25/readinput
Since there are no diagonal moves, we can restrict the problem to a single row at a time.
As we need to move a cell in the row, I think reducekv
can do:
day25> (defn move [kind row]
(let [len (count row)]
(reducekv
(fn [row' i c]
(if (= c kind)
(let [pos (mod (inc i) len)]
(if (= (nth row pos) \.)
(assoc row' i \. pos kind)
row'))
row'))
row row)))
#'day25/move
day25> (move \> [\. \> \> \. \>])
[\> \> \. \> \.]
This function accepts kind
of cucumber we’re moving, so we can reuse it for vertical movement as well.
And for vertical movement we will just transpose
our world, and repeat the process:
day25> (defn step [world]
(>> world
(mapv (partial move \>))
transpose
(mapv (partial move \v))
transpose))
#'day25/step
The only thing left is to write a function, that will run our simulation until the world stops changing:
day25> (defn part1 [input]
(reduce (fn [world i]
(let [world' (step world)]
(if (= world' world)
(reduced i)
world')))
input (drop 1 (range))))
#'day25/part1
day25> (part1 (readinput))
367
And part one is done. It was quite easy, compared to the two previous puzzles. Let’s see what awaits us in part two? I guess not.
Day 25 and event ending thoughts
Unfortunately, by the time I’ve finished the first part, I only had 44 stars. And part two unlocks only if you have 49 stars. So perhaps the last star isn’t a variation of the first part at all, but some kind of congratulations or something like that. However, I will not see what’s there unless I’ll go back and solve day 19, part two of day 22, and day 24. I’m not sure if I will, though.
The puzzle for day 25 was a joke. I’ve thought, that since this is a weekend, the task will be brutal, as was on both previous weekends. I guess it’s a holiday, and the task is not hard, so everyone could hang out with their families, friends, and so on. Well, I couldn’t  I was on a train solving and writing this on a phone yet again. It’s a bit sad that there was no part two, but I guess it’s my own fault. I couldn’t keep up with the difficulty spikes, and lost motivation over the last few days, because the variety of tasks was (IMHO) very low. Looking back at it, there definitively were interesting tasks.
As I said, my problem with this year’s event is that the variety wasn’t very big. There were three tasks with exponential growth^{6}, that required finding a way to tame this by grouping the data in some way. Six tasks about 2D data structures^{7}, not including two cellular automatonlike tasks^{8}, which also were 2D. Two tasks about binary data processing^{9}. One task for navigating trees^{10}, and two for navigating graphs^{11}. Two tasks could have been solved without any code fully on paper^{12}. The rest are hard to categorize.
Probably, my favorite ones were on days 8, 11, 13, 15, 17, 18, and 20.
I really like cellular automaton type of puzzles, as they allow you to run the simulation, and even visualize it. I’ve done this the last year, and this year was no different. However, I think there were just too many tasks of this type. The fun ones were on days 11 and 20.
I really liked day 8 because it was a neat task to figure out what wire corresponds to what  kind of reverse engineering, which required you to also write a program that will unmangle the input. Unlike day 24 which was also about reverse engineering, but required no code to solve, as was shown by a lot of people in the community.
I’ve liked days 15 and 18 because they’ve taught me new things  I’ve learned the pathfinding algorithm, and a library for navigating trees that I’ve long wanted to try out.
Days 13 and 17 were cool 2D tasks, which I’ve simply liked.
The tasks that I’ve really despised were tasks on days 6, 14, 19, 22, 23, and 24. I simply do not find these types of tasks fun. The challenge is also questionable, especially for the last 4 of these. They were more tedious than hard IMO.
Other than that, the event went mostly smoothly. I had some bad days where events in my life combined with the increased difficulty of tasks made me really angry (and you should never be angry about something like puzzles). Overall, if I was asked to explain my thoughts about this event in a single word, this word would be “meh”. I wanted to try to solve as many puzzles from the event as I can, and also write a post in my blog for every one of them. Maybe this was a mistake, as both solving, and writing in a single day is more exhausting than only solving a puzzle itself. I don’t think I’ll repeat this kind of format the next year if I will even participate. But if I will, I’ll probably do small writeups about days that I’ve really enjoyed instead.
I hope you’ve had fun during this event, and thank you for reading. Merry Christmas and until next year!

A funny coincidence: I’ve started on December 14 and completed 14 days, ending by December 28, with 28 stars. ↩︎

Sadly there’s no Wikipedia page for Lotto in English so, given that this game comes from Italy, I’ve linked the Italian one. The main difference from Bingo is that the winner has to mark all the numbers on the board, and the board is not a square. There’s a chance that only a single row will be fully covered, and usually, such players get a consolation prize. ↩︎

I’ve reordered the map items, as well as set items to match the ordering of letters, but the letters itselves weren’t changed. ↩︎

Obviously, I’m overreacting here  it was kinda obvious after seeing how points formed a rectangle. ↩︎

I’ve edited the post on PC once I came back in town, that’s why I wasn’t able to publish it on the same day as the task. ↩︎

days 7, 14 and 21 ↩︎

days 4, 5, 9, 13, 15, and 25 ↩︎

days 11 and 20 (25th was also kinda) ↩︎

days 3 and 16 ↩︎

day 18 ↩︎

days 12 and 15 (8th was also kinda) ↩︎

days 23 and 24 ↩︎