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 aBitMatrix.
# 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 theiterate 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!
Top comments (0)