Advent of Code 2021 - Day 9

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 9 - Smoke Basin

Find the problem description HERE.

The Input - Enter the Matrix

Not much to say about today’s input that isn’t covered in the code comments below.

# Today's input is essentially a big block of numbers (0-9).
# Ingest it by reading each line, breaking it into characters,
# storing all the character vectors in a big vector, then 
# converting the 2D vector into a Matrix{Int}
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

I feel like there’s probably got to be a way to produce a ‘properly’ rotatedMatrix directly, without needing to transpose(), but I haven’t hit upon it yet. If someone knows how, I’d really appreciate a comment letting me know what I’ve missed.

Part One - Shifty Business

Our job in part one is to identify each position in a Matrix of height values that is lower than all four of its neighbors, only considering directly adjacent neighbors and ignoring diagonals. Now, you could iterate over every position in the Matrix, check all its neighbors, and save off the indices that meet the criteria. Or, and hear me out, you could shift the entireMatrix up, down, left, and right and do some sort of map-reduce to do the same thing, just with more array operations. You know what, that second one sounds more interesting, let’s do that.

# Takes an integer matrix and adds a "ring" of `9`'s to the outside
# of it, essentially "padding" the matrix with the number `9`
function pad(M::Matrix{T}) where T <: Integer
    (rows, cols) = size(M)
    rowpadding = fill(9, (1, cols))
    colpadding = fill(9, (rows + 2, 1))

    (vcat(rowpadding, M, rowpadding)
     |> (x -> hcat(colpadding, x, colpadding)))
end

# Find the points in a numeric matrix where the value in that
# position is smaller than the values in the four cardinal 
# directions, if viewed as a map. 
function findlowpoints(heightmap::Matrix{T}) where T <: Integer
    # Create a copy of the heightmap padded with `9`'s
    (rows, cols) = size(heightmap)
    padded = pad(heightmap)

    # Take views of the heightmap that are the same size but
    # shifted either up, down, left, or right. The padding ensures
    # that the `upshift` has a bottom row of all `9`. This ensures
    # that values in the bottom row of `heightmap` will identify
    # as a 'lowest point' if the values above, to the left, and to
    # the right are also larger. This similarly holds true for values
    # on all four edges of `heightmap`.
    upshift = view(padded, 1:rows, 2:(cols+1))
    downshift = view(padded, 3:(rows+2), 2:(cols+1))
    leftshift = view(padded, 2:(rows+1), 3:(cols+2))
    rightshift = view(padded, 2:(rows+1), 1:cols)

    # Check `heightmap` against all four views. For any point where the
    # value at the corresponding position in all four `shifts` is greater
    # than the value at that point in `heightmap`, that position in the
    # returned BitMatrix will be `1`, otherwise it will be `0`.
    shifts = [rightshift, leftshift, upshift, downshift]
    return mapreduce(S -> S .> heightmap, .&, shifts)
end

# Identify each position in the input that represents a 'low point', 
# and return the sum of the values at those positions.
function part1(input)
    lowpoints = findlowpoints(input)
    return sum(input[lowpoints] .+ 1)
end

Consider this simple example, to help visualize what’s going on:

Original Matrix     Padded Matrix
   _____              _________
  | 3 4 |            | 9 9 9 9 |
  | 4 9 |            | 9 3 4 9 |
   -----             | 9 4 9 9 |
                     | 9 9 9 9 |
                      ---------

Shifted to the...
       _____            _____         _____           _____
Left: | 4 9 |   Right: | 9 3 |   Up: | 4 9 |   Down: | 9 9 |
      | 9 9 |          | 9 4 |       | 9 9 |         | 3 4 |
       -----            -----         -----           -----

         _____
Output: | 1 0 |
        | 0 0 |
         -----

If you look at the index at [1, 1], in the original matrix it has a value of3. In the ‘shifted’ matrices, index [1, 1] has the values 4, 9, 4, and9, in the order given above. Since these values are all greater than 3, the bit in the output BitMatrix will be 1.

Yes, this was an excuse to use a whole lot of Array/Matrix goodness built in to Julia. I’m not even sorry.

Part Two - Bottoms Up!

Next, we need to find the sizes of the three largest ‘basins’, or contiguous areas of our map that are less than the maximum height of 9. Theoretically, this tells us which areas to avoid, but I couldn’t help but notice that theBitMatrix generated in part one had a bunch of these ‘ridges’ consisting of lines throughout the map where the value was 9. Yes, these represent the boundaries of the ‘basins’, but I’d wager they also represent safe paths through the cave. Ah well, maybe we burn fuel at some weird rate just like those crabs from earlier. Let’s size up some basins!

# Given a matrix and an index, return the indices of the positions
# above, below, to the left, and to the right of the given index,
# accouting for edges.
function neighborindices(matrix::AbstractMatrix, idx::CartesianIndex)::Vector{CartesianIndex}
    out = []; sizehint!(out, 4)
    (rows, cols) = size(matrix)
    if idx[1] > 1; push!(out, idx - CartesianIndex(1, 0)); end
    if idx[1] < rows; push!(out, idx + CartesianIndex(1, 0)); end
    if idx[2] > 1; push!(out, idx - CartesianIndex(0, 1)); end
    if idx[2] < cols; push!(out, idx + CartesianIndex(0, 1)); end
    return out
end

# Given a BitMatrix were a `1` indicates a part of a basin and a `0` 
# indicates a part of a ridge and an index to start search from,
# perform a breadth-first search of `heightmap`, to find all adjacent
# 'basin' points that can be reached from the starting point.
function basinsizeat(heightmap::BitMatrix, idx::CartesianIndex)::Int
    queue = [idx] # Points to check
    visited = Set(queue) # Points we've already checked
    cells = 1 # Number of points that have been checked

    # As long as there are still more points to check...
    while !isempty(queue)
        # Take an index from the top of the queue 
        location = pop!(queue)

        # For all of that index's neighbors...
        for neighbor in neighborindices(heightmap, location)
            # If it's already been checked, skip it
            neighbor in visited && continue

            # Mark it as checked
            push!(visited, neighbor)

            # If that neighboring index is part of the basin, add that
            # index to the front of the queue and increment our count
            if heightmap[neighbor]
                pushfirst!(queue, neighbor)
                cells += 1
            end
        end
    end

    return cells
end

# Transform our input into a BitMatrix, where `1`'s indicate basins,
# positions where the value is less than 9. For each lowpoint, in
# the input, perform a breadth-first search for neighboring basin 
# cells and return the count. Once all the basins have been measured,
# get the sizes (by number of included indices) of the three largest
# and return the product of all three.
function part2(input)
    basins = input .< 9
    lowpoints = findlowpoints(input)
    basinsizes = []; sizehint!(basinsizes, sum(lowpoints))
    for index in findall(lowpoints)
        push!(basinsizes, basinsizeat(basins, index))
    end
    sort!(basinsizes, rev = true)
    return prod(basinsizes[1:3])
end

I used some Julia matrix magic in part one, but for part two it’s a pretty standard breadth-first search starting at each low point. Now, you could easily imagine a situation in which we’d need to remove low points from our search list for cases where a single large basin contained multiple low points, but my input didn’t include any areas like that. Your mileage may vary.

Wrap Up

This was a fun day. It was also the only day I stayed up to actually work on the puzzle when it unlocked at 11:00 PM CST, due in large part to the fact that I fell asleep putting my kid to bed and woke up with a truly egregious amount of energy for that time of night. I managed to finish, both parts in under an hour, which is pretty good for me since I tend to re-factor as I go (I’m a bit nit-picky). It seems like the challenge for these is starting to hit the upward slope, but it’s been a pretty friendly progression so far. It’s still fun, so I’m looking forward to the next one!

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