Advent of Code 2021 - Day 13

By Eric Burden | December 14, 2021

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 13 - Transparent Origami

Find the problem description HERE.

The Input - Making Paper

This puzzle is all about “folding” a sheet of virtual “paper” to find overlapping points. So, when ingesting the data, I’ve opted to model this problem with a Paper struct that contains a BitMatrix to indicate where the “dots” on the paper are, and a Vector{Fold} to indicate where we’ll need to fold the paper, in order. Each Fold indicates the axis the folder needs to be folded on (either the X-axis or Y-axis) and the position along the axis where the paper will be creased when folding.

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

# Basically just an enum for `Axis` types
abstract type Axis end
struct XAxis <: Axis end
struct YAxis <: Axis end

struct Fold
    axis::Axis
    index::Int
end

mutable struct Paper
    dots::BitMatrix
    folds::Vector{Fold}
end


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

function ingest(path)
    return open(path) do f

        # Start by reading all the lines from the top section of the input file
        # and parsing each one into a `CartesianIndex`.
        coordinateslist = []
        for coordinatestring in split(readuntil(f, "\n\n"))
            (col, row) = [parse(Int, s) for s in split(coordinatestring, ",")]
            push!(coordinateslist, CartesianIndex(row+1, col+1))
        end

        # Next read in the lines from the bottom section and parse each
        # one into a `Fold` struct.
        folds = []
        foldre = r"(x|y)=(\d+)"
        for foldstring in split(readchomp(f), "\n")
            m = match(foldre, foldstring)
            axis = m[1] == "x" ? XAxis() : YAxis()
            index = parse(Int, m[2]) + 1
            fold = Fold(axis, index)
            push!(folds, fold)
        end

        # Figure out how many rows/columns the `dots` Matrix should be. We
        # assume that it must be tall and wide enough to accommodate the
        # largest horizontal and vertical fold.
        rows = cols = 0
        for fold in folds
            if isa(fold.axis, XAxis)
                cols = max(cols, (fold.index * 2) - 1) 
            else
                rows = max(rows, (fold.index * 2) - 1) 
            end
        end

        # Make a large enough BitMatrix to accommodate all the 'dots' and
        # and set each coordinate found above to `true`.
        dots = falses(rows, cols)
        for coordinate in coordinateslist
            dots[coordinate] = true
        end

        Paper(dots, folds)
    end
end

The trickiest part was making sure the dots matrix would be the right size, which we calculated to be tall/wide enough to accommodate the largest fold along both the X and Y axes.

Part One - Flip It and Reverse It

Ah, nothing beats that new software smell! Oh wait, that’s cars… New software means entering activation codes. Boo. Honestly, though, the process we need for today’s puzzle seems comparable onerous to other software validation schemes I’ve experienced, which makes today one of the more plausible sequences in this year’s storyline.

For this part, we need to fold the paper a single time and count the visible dots. There’s most certainly some more abstract ways to approach this, but I’d rather fold some paper! Or, in this case, combine the two halves of a BitMatrix.

# Given a BitMatrix representing the current arrangement of dots on a page
# and a fold indicating where/how to fold that paper, fold the paper and
# return the result.
function foldit(dots::BitMatrix, fold::Fold)::BitMatrix
    (rows, cols) = size(dots)

    # Need to define two views into the `dots` BitMatrix, one for the 
    # half of the paper that will stay in place, and one for the half
    # of the paper to be 'folded over'. The 'folded' view will have
    # its rows/columns reversed as appropriate.
    toprows  = bottomrows = 1:rows
    leftcols = rightcols  = 1:cols
    if isa(fold.axis, XAxis)
        leftcols   = 1:(fold.index-1)
        rightcols = cols:-1:(fold.index+1)
    else
        toprows    = 1:(fold.index-1)
        bottomrows = rows:-1:(fold.index+1)
    end

    # Take the two views, overlay them, then return the result
    still  = view(dots, toprows,    leftcols) # Stationary!
    folded = view(dots, bottomrows, rightcols)
    return (still .| folded)
end

# Take the input, fold it once, then return the number of 'dots' from
# that single fold.
function part1(input)
    dots = input.dots
    fold = input.folds[1]
    folded = foldit(dots, fold)
    return count(folded)
end

This feels like a satisfying solution, mostly because the process actually models the described physical process pretty well. It may not be the most efficient approach, but it is very approachable, which is a win in my book.

Part Two - I Like to Fold It, Fold It

We all saw this coming from a mile away. Time to finish folding the paper all the way. What I didn’t see coming was how the input, once folded all the way, would actually spell out the solution when printed to the console. Nifty!

# Iteration for a `Paper` Struct ----------------------------------------------
struct PaperFoldState
    dots::BitMatrix
    lastfold::Int
end

# Initial iterator, returns the first fold
function Base.iterate(paper::Paper)
    fold = paper.folds[1]
    folded = foldit(paper.dots, fold)
    state = PaperFoldState(folded, 1)
    return (folded, state)
end

# Subsequent iterator, given the last state, return tne next state
function Base.iterate(paper::Paper, state::PaperFoldState)
    (dots, lastfold) = (state.dots, state.lastfold)
    lastfold >= length(paper.folds) && return nothing
    fold = paper.folds[lastfold + 1]
    folded = foldit(dots, fold)
    state = PaperFoldState(folded, lastfold + 1)
    return (folded, state)
end

# Needed to be able to get a specific fold state of the `Paper`
function Base.getindex(paper::Paper, i::Int)
    for (iteration, dots) in enumerate(paper)
        iteration > i && return dots
    end
    throw(BoundsError(paper, i))
end

# Some more necessary implementations so I can use the `paper[end]` syntax
# in our solution function.
Base.length(paper::Paper)    = length(paper.folds) - 1
Base.lastindex(paper::Paper) = lastindex(paper.folds) - 1
Base.eltype(::Type{Paper})   = BitMatrix

# Pretty prints a BitMatrix to make the solution to Part Two more
# readable, because reading the block characters from the default
# 1/0 display of the BitMatrix is difficult.
function prettyprint(matrix::BitMatrix)
    for line in eachrow(matrix)
        for bit in line
            if bit; print('█'); else; print(' '); end
        end
        println()
    end
end


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

# Fold the paper until all the folds are used up. The commented out print
# statement is there for solving the puzzle. The rest of it is there for 
# comparing in my test suite.
function part2(input)
    final_paper = input[end]
    # prettyprint(final_paper)
    rowsums = mapslices(sum, final_paper, dims = 2)
    colsums = mapslices(sum, final_paper, dims = 1)
    return (vec(rowsums), vec(colsums))
end

I decided to go with an iterator again, because that’s handy and I like being able to use the native iterator/indexing syntax to get answers. Plus, it’s good practice. The prettyprint() function is there purely to make the answer more readable, since trying to make out letters in a bunch of 1s and 0s printed to the console is a royal pain.

Wrap Up

Today’s puzzle was a lot of fun, particularly the way we got to the final answer. I even saw someone on Reddit using their folding phone to visualize this process, which was super neat! As far as the Julia went, implementing the iterate interface is fun, and I picked up a few new best practices since the last time I did that, so it was a good learning day, too.

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

comments powered by Disqus