Advent of Code 2021 - Day 20

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 20 - Trench Map

Find the problem description HERE.

The Input - A Tale of Two Inputs

Day 20 was interesting in that we basically had two different inputs in a single file. Granted, we’ve seen files with “chunks” of inputs before, but either my memory is faulty (totally plausible) or this is the first time we’ve seen two totally different inputs. Which, really, isn’t much of a problem, as it turns out. The first input comes from the first line, which we’re going to treat as a BitVector since we only need to know if each character is in one of two possible states. For the second input, we’ll use a Dict where the key is the row/col coordinate of a character in the character grid, and the value is a Bool that indicates whether that character is ‘#’ (on) or ‘.’ (off).

# Data Structures --------------------------------------------------------------

const Point = NTuple{2,Int64}
const Image = Dict{Point,Bool}

# Ingest the Data -------------------------------------------------------------

function ingest(path)
    return open(path) do f
        # Parse the first line into a BitVector, with '#' => 1, '.' => 0
        algostr = readuntil(f, "\n\n")
        algo = collect(algostr) .== '#'

        # Parse the rest of the lines into a Dict of (row, col) => true/false, 
        # where the value is true if the corresponding row/col of the input
        # is a '#'
        image = Dict{Point,Bool}()
        imagestr = readchomp(f)
        for (row, line) in enumerate(split(imagestr))
            for (col, char) in enumerate(collect(line))
                image[(row,col)] = char == '#'
            end
        end

        (algo, image)
    end
end

The keyword “infinite” in the problem statement clues us in that using a Matrix or even a BitMatrix is going to be the wrong call for this puzzle.

Part One - Beneath a Sea of Light (Pixels)

Today’s puzzle is (thankfully) pretty straightforward. Given a low resolution image, we just keep enhancing it until it resolves into something useful. As Seen on TV! There’s no way this won’t work, plus, we may get to put on our sunglasses in a really cool way after we solve it. YYeeaaaahhh!! We’ll take the values in a 3x3 grid around any given pixel to determine its new value, and the only really tricky bit (‘bit’, get it?) is to know what value to use for pixels we aren’t actively keeping track of. You might think it would be ‘false’ or ‘0’ for all those, but that’s the tricky part!

# Some Useful Data Structures --------------------------------------------------

# Used to get the coordinates of the nine pixels surrounding any given
# pixel in the image
const OFFSETS = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)]

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

# Get a list of the coordinates of the pixels surrounding a given point
offsets(p::Point) = [p .+ offset for offset in OFFSETS]

# Convert binary value to decimal
todecimal(x) = sum(D*2^(P-1) for (D, P) in zip(x, length(x):-1:1))

# Given a point in the image, calculate the value of the point from the
# 3x3 area centered on that point
function valueat(image::Image, point::Point, default=false)
    value = [get(image, p, default) for p in offsets(point)]
    return todecimal(value)
end

# Enhance the image! Creates a new image (expanded by one in all directions) 
# where each pixel is flipped according to its calculated value.
function enhance(image::Image, algo::BitVector, default=false)
    newimage = Dict{Point,Bool}()

    # Need to expand the enhancement area by 1 in all directions each pass
    (minpoint, maxpoint) = extrema(keys(image))
    rng = (minpoint[1]-1):(maxpoint[2]+1)

    # For each possible point in the new image, determine its value
    for point in Iterators.product(rng, rng)
        pointvalue = valueat(image, point, default)
        pixel = algo[pointvalue + 1]
        newimage[point] = pixel
    end

    return newimage
end

# Solve ------------------------------------------------------------------------

function solve(input, rounds; test = false)
    (algo, image) = input
    for round in 1:rounds
        # The 'real' algorithm (not the test) has a '#' in the first position 
        # and a '.' in the last position, which means that the 'empty' pixels
        # surrounding the image all flip from '.' to '#' on odd numbered rounds.
        # The 'test' input does not have this 'feature'.
        default = !test && round % 2 == 0
        image = enhance(image, algo, default)
    end
    return sum(values(image))
end

See, apparently Eric Wastl, creator and designer of Advent of Code, thought that after the last two days we were probably having it too easy and he needed to keep us on our toes… Well played! The ‘enhancing algorithm’ for the actual input (not the test input) had the amusing feature that, each round, it would ‘flip’ all the pixels in the infinite expanse of untracked pixels from off, to on, then back again. I feel like there should have been one of those “photosensitive viewers” warnings for this one. But, knowing that, we could just change the default value every other round to get to the final answer.

Part Two - De Nada

Same as Part One, just more times! We’ve seen this sort of escalation before, and since we’re already taking a rounds argument in our part one solve() function, getting the answer here just requires passing 50 instead of 2 as our rounds argument. No new code!

Wrap-Up

Man, I needed Day 20. Days 18 and 19 really stretched me, either leading me down paths that turned out to have some unsatisfactory conclusions (Day 18) or forcing me to learn math (Day 19), and knocked me off my pace of a solution and a blog post every day. With the holidays looming close, a pretty straightforward implementation for Day 20 with one weird trick thrown in to spice things up was exactly the sort of enjoyable, non-head-bashing sort of day I needed. I will say, that having gotten this far with Julia, I was delighted at how smoothly the code came out of my fingers and how well I was able to think in Julia, even for this relatively easier puzzle. Just in time, too!

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