Advent of Code: 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 '[aoc-commons :refer [parse-long]]
'[clojure.string :as str])
nil
day11> (def example-input "
11111
19991
19191
19991
11111")
#'day11/example-input
day11> (defn read-input []
(->> example-input
str/trim
str/split-lines
(mapv (partial mapv parse-long))))
#'day11/read-input
day11> (read-input)
[[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 parse-long 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 (read-input))
[[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 find-flashing-cells [rows]
(->> rows
(keep-indexed
(fn [i row]
(keep-indexed
(fn [j oct]
(when (> oct 9)
[i j]))
row)))
flatten
(partition 2)
(keep seq)))
#'day11/find-flashing-cells
day11> (find-flashing-cells (tick (read-input)))
((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 to-single-level.
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 safe-update [rows point f]
(if (get-in rows point)
(update-in rows point f)
rows))
#'day11/safe-update
day11> (safe-update [0 1 2] [10] inc)
[0 1 2]
day11> (safe-update [0 1 2] [1] inc)
[0 2 2]
Here, for a one-dimensional 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 two-dimensional 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
(safe-update [(inc x) y] inc)
(safe-update [(dec x) y] inc)
(safe-update [x (inc y)] inc)
(safe-update [x (dec y)] inc)
(safe-update [(inc x) (inc y)] inc)
(safe-update [(dec x) (inc y)] inc)
(safe-update [(inc x) (dec y)] inc)
(safe-update [(dec x) (dec y)] inc))
(conj flashed [x y])]
[rows flashed]))
[rows flashed] (find-flashing-cells 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 to-zero [rows]
(reduce (fn [rows [x y]] (assoc-in rows [x y] 0))
rows (find-flashing-cells rows)))
#'day11/to-zero
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))
[(to-zero 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 part-1 [input]
(second (reduce (fn [[rows flashed] _]
(let [[rows flashed*] (step rows)]
[rows (+ flashed flashed*)]))
[input 0] (range 100))))
#'day11/part-1
day11> (part-1 (read-input))
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 part-2 [input]
(reduce (fn [[rows flashed] i]
(let [[rows flashed] (step rows)]
(if (= 100 flashed)
(reduced i)
[rows 0])))
[input 0] (rest (range))))
#'day11/part-2
day11> (part-2 (read-input))
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. But it’s not a problem in itself, today’s task was pretty fun!