DEV Community

Eric Burden
Eric Burden

Posted on • Originally published at ericburden.work on

Advent of Code 2021 - Day 11

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 11 - Dumbo Octopus

Find the problem description HERE.

The Input - (Re)Enter the Matrix

Exactly the same as Day 9, actually.

# Read in the input data file, parsing it into a matrix of numbers
function ingest(path)
    outvectors = open(path) do f
        [collect(line) for line in readlines(f)]
    end
    toint(x) = parse(Int8, x)

    # I transposed the matrix to make debugging easier, since 
    # otherwise it won't print in the same orientation as the input.
    (outmatrix
     = outvectors
     |> (x -> reduce(hcat, x))
     |> (x -> map(toint, x))
     |> transpose
     |> collect)
    return outmatrix
end

Enter fullscreen mode Exit fullscreen mode

Moving on.

Part One - Flash Mob

If you haven’t visited r/adventofcode yet, I’d recommend you do so for the visualizations of Day 9, for sure. In today’s puzzle, we have encountered a species of bioluminescing dumbo octopus who appear to enjoy arranging themselves into a two-dimensional grids but do not appreciate Christmas lights. A bit stuffy, aren’t they? Each octopus has a particular energy level, which is the number we’ll be keeping up with, and when it exceeds an energy level of 9, it “flashes” and resets to an energy level of 0. But wait, there’s more! Each time an octopus flashes, it increases the energy level of all the surrounding octopuses, who in turn might flash and continue the chain reaction. Luckily, an octopus can only flash once per cycle, otherwise we’d be at this forever, probably. There’s a good amount of code for this, but it’s pretty heavily commented:

# Helper Functions -------------------------------------------------------------

# Return a view of the matrix `M` centered on the index `idx` and encompassing
# the eight surrounding indices. Accounts for corners and edges.
function neighborhoodof(idx::CartesianIndex, M::AbstractMatrix)
    (rows, cols) = size(M)
    (row, col) = Tuple(idx)

    top = row > 1 ? row - 1 : row
    left = col > 1 ? col - 1 : col
    bottom = row < rows ? row + 1 : row
    right = col < cols ? col + 1 : col

    return view(M, top:bottom, left:right)
end

# Given a matrix representing our octopuses, advance the state of the 
# school of octopuses, mutating the input and returning the number of
# octopuses who flashed this round.
function advance!(octopuses::Matrix{Int8})::Int
    # Increase the value of all octopuses
    octopuses .+= 1

    # Identify the octopuses who have flashed
    flashed = justflashed = octopuses .> 9

    # Shorthand to fetch octopuses surrounding an index. There's no need to
    # exclude the central octopus, since they've already flashed.
    getneighborhood(idx) = neighborhoodof(idx, octopuses)

    # So long as any octopus just crossed the threshold...
    while any(justflashed)
        # Get all the neighborhoods of the octopuses who just flashed
        neighborhoods = map(getneighborhood, findall(justflashed))

        # For each neighborhood, increase the energy level of all
        # octopuses by 1
        foreach(N -> N .+= 1, neighborhoods)

        # Identify the octopuses who just crossed the threshold
        justflashed = (octopuses .> 9) .& .!flashed

        # Update the listing of all octopuses who have flashed this round
        flashed .|= justflashed
    end

    # Reset all the octopuses who have flashed and return the count
    octopuses[flashed] .= 0
    return count(flashed)
end

# Advance the school of octopuses 100 times, counting the number of octopuses
# who flash each round and returning the count of all octopuses flashing over
# 100 rounds
function part1(input)
    flashes = 0
    octopuses = deepcopy(input)
    for _ in 1:100
        flashes += advance!(octopuses)
    end
    return flashes
end

Enter fullscreen mode Exit fullscreen mode

Key insights here are that we don’t need to reset any of the energy levels until the end of each step, since we don’t really care about any differences between an octopus with energy level 10 and energy level 99, they’ve both already flashed and won’t flash again. I feel like there’s probably a more elegant way to differentiate justflashed and flashed, but this works. I’d normally be tempted to write an iterator for this, but I’ve been a bit slow getting this blog post out due to being extra busy with work, so this is as re-factored as the code is going to get (for now, at least).

Part Two - Synchronized Swimming

For part two, we need to keep going until all the octopuses sync up their flashing. This basically just means continuing our cycles from part one until we find one where every octopus gets reset, then reporting how many cycles it took. Thankfully, we wrote a bunch of code in part one that handles this:

# Now, we advance the octopuses until we reach a state where all octopuses
# have been reset at the same time, meaning they all flashed simultaneously.
function part2(input)
    octopuses = deepcopy(input)
    rounds = 0
    while any(octopuses .> 0)
        advance!(octopuses)
        rounds += 1
    end
    return rounds
end

Enter fullscreen mode Exit fullscreen mode

Yay for over-engineering the first part!

Wrap Up

I’m not 100% satisfied with my code for today. I didn’t feel like I did anything particularly interesting, apart from using a view of the octopuses matrix to identify neighbors instead of trying to calculate indices. This was a good opportunity to practice writing Julia code, though, which is like 80% of the point of doing AoC this year (the other 20% is a combination of joy and stubbornness).

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!

Discussion (0)