## DEV Community is a community of 847,300 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 13

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 = []
(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+)"
m = match(foldre, foldstring)
axis = m == "x" ? XAxis() : YAxis()
index = parse(Int, m) + 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
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
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
# 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 `1`s and `0`s 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!