DEV Community is a community of 852,088 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Eric Burden

Posted on • Originally published at ericburden.work on

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
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}()
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)]
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.

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!