Advent of Code 2021 - Day 22

By Eric Burden | January 1, 2022

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 22 - Reactor Reboot

Find the problem description HERE.

The Input - Cubic Impressions

The input for today’s puzzle isn’t super complicated, consisting of lines that start with the word ‘on’ or ‘off’, followed by a string in the format of “x=..,y=..,z=..”, where the values are positive or negative numbers that represent the bounds of a cube. So, with a function that can parse one line, we can parse all the lines.

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

# We'll represent each of the cubes of lights as a set of x, y, and z-ranges
# that encompass all the points of the cube
struct Cube

# Constructor that ensures that the first number in the x, y, or z-range is 
# the smaller number.
function Cube(x1, x2, y1, y2, z1, z2) 
    if x1 > x2; (x1, x2) = (x2, x1); end
    if y1 > y2; (y1, y2) = (y2, y1); end
    if z1 > z2; (z1, z2) = (z2, z1); end
    Cube(x1:x2, y1:y2, z1:z2)

# Constructor that takes a line from the input and produces a `Cube`
function Cube(s::AbstractString)
    re = r".*x=(-?\d+)\.\.(-?\d+),y=(-?\d+)\.\.(-?\d+),z=(-?\d+)\.\.(-?\d+)"
    bounds = parse.(Int, match(re, s).captures)
    return Cube(bounds...)

# An `Instruction` encompasses a `Cube` and whether the instruction is to turn
# 'on' all the lights in that cube (state == True) or to turn the lights 'off'
struct Instruction

# Constructor that takes a line from the input and returns an `Instruction`
function Instruction(s::AbstractString)
    re = r"^(on|off) (.*)$"
    (statestr, cubestr) = match(re, s).captures
    state = statestr == "on"
    cube = Cube(cubestr)
    return Instruction(state, cube)

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

# Parse the input file into a list of `Instruction`s
function ingest(path)
    return open(path) do f
        [Instruction(l) for l in readlines(f)]

We’ll keep the parsing simple by representing each cube as a set of ranges bounded by the values in the input. Based on how large some of the values in the input are, we won’t be able to keep track of every point.

Part One - Minicube

Time to reboot the submarine! As we all know, most every technological problem is solved with a reboot. In fact, if we can figure this one out, we should be good for Days 23-25 as well! And, as it turns out, we were overly pessimistic when parsing the input. We actually only care about the portions of the instruction cubes in the range from -50 -> 50, so we can just keep track of which lights are on in a 3D Array. This will be easier than we thought!

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

# It is often convenient to get the upper and lower bounds of the 
# x, y, and z-ranges that comprise a `Cube`
function bounds(cube::Cube)
    (x1, x2) = (cube.x.start, cube.x.stop)
    (y1, y2) = (cube.y.start, cube.y.stop)
    (z1, z2) = (cube.z.start, cube.z.stop)
    return (x1, x2, y1, y2, z1, z2)

# Check whether a `Cube` overlaps the region being considered for the 
# initialization sequence.
function overlap(lights::BitArray, cube::Cube)
    (x1, x2, y1, y2, z1, z2) = bounds(cube)
    (lightx, lighty, lightz) = size(lights)
    return (x1 <= lightx && x2 >= 1
            && y1 <= lighty && y2 >= 1
            && z1 <= lightz && z2 >= 1)

# Shift a cube so that all its dimensions are positive and have at least a
# a value of 1, so that the coordinates map cleanly to an `Array`.
function displace(cube::Cube, offset::Int64)
    cubebounds = map(c -> c + offset, bounds(cube))
    return Cube(cubebounds...)

# Apply an instruction (turning lights on or off) to the lighted region. Just
# sets positions in `lignts` bounded by the coordinates of the instruction's
# `Cube` to either 1 or 0, depending on the type of instruction. Displaces
# the `Cube` before making this change.
function apply!(lights::BitArray, instruction::Instruction, offset = 51)
    (lightx, lighty, lightz) = size(lights)
    cube = displace(instruction.cube, offset)
    overlap(lights, cube) || return
    xrange = intersect(1:lightx, cube.x)
    yrange = intersect(1:lighty, cube.y)
    zrange = intersect(1:lightz, cube.z)
    lights[xrange, yrange, zrange] .= instruction.state

# Solve Part One ---------------------------------------------------------------

# Simple, straightforward; represent the target region as a 3D `BitArray` and 
# turn on/off the lights according to the instructions, in order. We use 
# `displace()` to adjust the coordinates of each `Cube` so that its bounds fall
# within the bounds of `lignts`.
function part1(input)
    lights = falses(101, 101, 101)
    foreach(cube -> apply!(lights, cube), input)
    return count(lights)

On second thought, yesterday’s puzzle has me a bit paranoid. Is it possible that this part was too easy…

Part Two - Rubik’s Wonderland

sigh Of course it was too good to be true. I did try to create a 3D Array large enough to accommodate the entire range, but it wouldn’t fit into my laptop’s memory. I also tried processing the instructions in chunks, which would probably work, but it was going to take forever (approximately). So, it was back to the drawing board for some shudder geometry. I ended up drawing a diagram for myself to help work out the ‘shattering’ rules (see the code below).

Diagram of a cube and the cubic zones surrounding it
# Helper Functions -------------------------------------------------------------

# Check whether two cubes overlap
function overlap(a::Cube, b::Cube)
    (ax1, ax2, ay1, ay2, az1, az2) = bounds(a)
    (bx1, bx2, by1, by2, bz1, bz2) = bounds(b)
    return (   ax1 <= bx2 && ax2 >= bx1
            && ay1 <= by2 && ay2 >= by1
            && az1 <= bz2 && az2 >= bz1)

# Check whether the `Cube`s from two `Instruction`s overlap
overlap(a::Instruction, b::Instruction) = overlap(a.cube, b.cube)

# Mostly just used for sanity checking while developing the `shatter()` function
# below, but it's interesting enought to keep around. Returns a `Cube` 
# representing the portions of `a` and `b` that overlap.
function Base.intersect(a::Cube, b::Cube)
    overlap(a, b) || return Cube(0:0, 0:0, 0:0)
    (ax1, ax2, ay1, ay2, az1, az2) = bounds(a)
    (bx1, bx2, by1, by2, bz1, bz2) = bounds(b)
    x = max(ax1, bx1):min(ax2, bx2)
    y = max(ay1, by1):min(ay2, by2)
    z = max(az1, bz1):min(az2, bz2)
    return Cube(x, y, z)

# Volume of a cube. Tricky, right? Yeah, well, *I* mistakenly corrected for 
# Julia's 1-indexing by adding one to each of these lengths and spent _way_
# too long debugging the wrong thing before I realized what I'd done...
function volume(cube::Cube)
    xlen = length(cube.x)
    ylen = length(cube.y)
    zlen = length(cube.z)
    return xlen * ylen * zlen

# The next set of functions are related to functionality to break apart one
# `Cube` around another `Cube`. This depends on creating new `Cubes` for each
# "zone" around the smaller `Cube`, 8 zones that align with the corners of the
# smaller `Cube`, 6 zones that align with the faces of the smaller `Cube`, and
# 12 zones that align with the edges of the smaller `Cube`. This way, if an 
# 'off' `Instruction` has a cube that overlaps a `Cube` of lignts already on,
# we can 'cut out' the `Cube` that gets turned off from the `Cube` that's 
# already on, replacing the remaining portions of the 'on' `Cube` with smaller
# `Cube`s and removing the overlapping section.

# For "face" and "edge" zones, for each dimension, there are four possible
# ranges that can be taken based on the relative coordinates of the `target`
# and `template`. Arguments are the min/max coordinates of `target` and 
# `template` (from `shatter()`) in a single dimension. I find it easier to
# imagine these values as line endpoints on a number line, if one line
# stretches from D1>D2 and the other from d1>d2.
function middlerange(D1, D2, d1, d2)
    D1 <= d1 && D2 >= d2 && return d1:d2
    D1 > d1  && D2 >= d2 && return D1:d2
    D1 <= d1 && D2 < d2  && return d1:D2
    D1 > d1  && D2 < d2  && return D1:D2
    return nothing

# Break a `target` cube into up to 27 segments, based on the location of 
# template. I find it easiest to image that every corner of `template` that
# lies inside `target` emits a line in each direction, carving up `target`. 
# Returns all the pieces _except_ for the piece that intersects with the
# `template`.
function shatter(target::Cube, template::Cube)
    # I'm using capital letters for the `target`, and lowercase letters for
    # the `template` `Cube`.
    (X1, X2, Y1, Y2, Z1, Z2) = bounds(target)
    (x1, x2, y1, y2, z1, z2) = bounds(template)

    pieces = Vector{Cube}()

    # These checks are used to determine if any of the points of the `target`
    # cube stray into one of the 26 cubic 'zones' adjacent to the `template` 
    # cube. This includes 12 "edge" zones, 8 "corner" zones, and six "face"
    # zones.
    xoffsets = (X1 < x1, X1 <= x2 || x1 <= X2, x2 < X2)
    yoffsets = (Y1 < y1, Y1 <= y2 || y1 <= Y2, y2 < Y2)
    zoffsets = (Z1 < z1, Z1 <= z2 || z1 <= Z2, z2 < Z2)

    # The ranges to use to construct the pieces. For each axis: the range when 
    # the `target` extends past the `template` in the negative (xyz)-direction,
    # when the `target` occupies the same (xyz)-range as the `template`, and 
    # when the `target` extends past the `template` in the positive direction
    xranges = (X1:x1-1, middlerange(X1, X2, x1, x2), x2+1:X2)
    yranges = (Y1:y1-1, middlerange(Y1, Y2, y1, y2), y2+1:Y2)
    zranges = (Z1:z1-1, middlerange(Z1, Z2, z1, z2), z2+1:Z2)
    # Generate the pieces
    for (a, b, c) in Iterators.product(1:3, 1:3, 1:3)
        (a, b, c) == (2, 2, 2) && continue # Skip the `template` range
        if xoffsets[a] && yoffsets[b] && zoffsets[c]
            push!(pieces, Cube(xranges[a], yranges[b], zranges[c]))
    # Sanity check, ensures that the volume of the pieces returned + the volume
    # removed is equal to the volume of the `target` `Cube`. Not needed to run
    # the solution, but it was handy for debugging.
    # @assert sum(volume.(pieces)) + volume(intersect(template, target)) == volume(target)

    return pieces

# Convenience function to `shatter()` the cubes held by two `Instruction`s. 
# Returns a list of `Instruction`s containing each of the pieces.
function shatter(target::Instruction, template::Instruction)
    newcubes = shatter(target.cube, template.cube)
    return Instruction.(target.state, newcubes)

# Given an iterable containing `Instruction`s, add up the volume of all the
# `Instruction`s that turn lignts on.
function countlights(instructionset)
    lightson = 0
    for instruction in instructionset
        !instruction.state && continue
        lightson += volume(instruction.cube)
    return lightson

# Solve Part Two ---------------------------------------------------------------

# Add each instruction to a set of final instructions. As each instruction is
# added, have it `shatter()` any `Instruction` it overlaps with before adding
# it to the set of final instructions, thereby replacing the overlapping
# region with itself. This means that instructions to turn lights off will 
# "overwrite" regions that turn lights on, and instructions that turn lights on
# dont' get double-counted.
function part2(input)
    finalinstructions = Set{Instruction}()
    for instrin in input
        for instrout in finalinstructions
            overlap(instrin, instrout) || continue # No overlaps? No problem!

            newinstrs = shatter(instrout, instrin)
            delete!(finalinstructions, instrout)

            # `shatter()` will return an empty list if `target` fits completely
            # inside `template`, so there's no parts of `target` to add back
            # after shattering in that case.
            isempty(newinstrs) && continue
            push!(finalinstructions, newinstrs...)

        # Only need to store the 'on' `Instruction`s. 
        instrin.state && push!(finalinstructions, instrin)

    return countlights(finalinstructions)

Somehow, it’s always math, isn’t it? I’m pretty satisfied with this approach, though. There’s possibly a way to do this without needing to explicitly turn off cubes, if we worked from the end of the list backwards and only turned on the ones that were going to stay lit, but that seems complicated and I’m happy enough with this solution.

Wrap Up

Oh, AoC, when will I learn that I should never relax when part one seems pretty easy compared to previous days? This was a somewhat time-consuming puzzle, but I’m really happy with the way shatter() worked out. That moment when I realized I should be able to sum the volumes of all the pieces to get the original volume? Should have been obvious? Yes. Was it still a great feeling? Absolutely! Today leaned heavily on Julia’s destructuring functionality, and provided some great practice there, so I’m going to call today a win-win!

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

comments powered by Disqus