Re-posted from: https://www.ericburden.work/blog/2021/12/29/advent-of-code-2021-day-19/
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 19 – Beacon Scanner
Find the problem description HERE.
The Input – Deceptively Simple
Input parsing was not the hard part of today’s puzzle. Here, we’re just converting each “chunk” of the input into a key/value pair in a Dict, where each key is the scanner’s ID number and its value is a Set of beacon coordinates.
# Data Structures --------------------------------------------------------------
# We'll store each `Beacon` as a Tuple of (x, y, z) coordinates, each `Scanner`
# as a Set of `Beacon`s, and maintain a collection of `Scanner`s as a Dict where
# each key is the scanner ID and value is the set of beacons associated with
# that scanner.
const Beacon = NTuple{3,Int}
const Scanner = Set{Beacon}
const Scanners = Dict{Int,Scanner}
# Helper Functions -------------------------------------------------------------
# Functions to help parse a chunk of the input into an (<ID>, `Scanner`) pair
# Parse a line starting a scanner chunk into the scanner ID
scannerid(s) = parse(Int, match(r"--- scanner (\d+) ---", s)[1])
# Parse a line containing beacon coordinates into a `Beacon`
parsebeacon(s) = NTuple{3,Int}(parse(Int,n) for n in split(s, ","))
# Parse a "scanner chunk" (from the "--- scanner ## ---" line to the next blank
# line) into an (<ID>, `Scanner`) pair, for conversion into a Dict entry.
function parsescanner(f)
id = readline(f) |> scannerid
beacons = Set(parsebeacon(s) for s in split(readuntil(f, "\n\n")))
return (id, beacons)
end
# Ingest the Data -------------------------------------------------------------
# Parse scanner chunks until the file is empty!
function ingest(path)
return open(path) do f
entries = []
while !eof(f); push!(entries, parsescanner(f)); end
Scanners(entries)
end
end
No sweat. Once again, the stream and data parsing functions built into Julia’s Base package makes this pretty painless.
Part One – Where Are We?
According to our puzzle input, our expertly launched probe has seeded the area with scanners and beacons that can be used to map out our current location. Unfortunately, the scanners don’t have any way to know about each other, or their own orientation. They can, somehow, ensure that they are aligned exactly to one of three axes, though, which is a bit suspicious, but let’s let that pass since it makes the coding somewhat easier (and cuts down on the potential runtime tremendously). Today’s puzzle requires (as far as I can tell) a pretty brute-force approach, wherein we apply up to 24 transformations on however many beacons each scanner has, for each pair of scanners…
# Some Useful Data Structures --------------------------------------------------
# The cosines for each 90° rotation: 0° => 1, 90° => 0, 180° => -1, 270° => 0
const COS = Dict{Int,Int}([(0,1), (90,0), (180,-1), (270, 0)])
# The sines for each 90° rotation: 0° => 0, 90° => 1, 180° => 0, 270° => -1
const SIN = Dict{Int,Int}([(0,0), (90,1), (180, 0), (270,-1)])
# These are all the rotations that can place a scanner into any of the 24
# orientations described in the puzzle input, starting with no rotation.
const ROTATIONS = [
(0, 0, 0), (90, 0, 0), (180, 0, 0), (270, 0, 0),
(0, 90, 0), (90, 90, 0), (180, 90, 0), (270, 90, 0),
(0, 180, 0), (90, 180, 0), (180, 180, 0), (270, 180, 0),
(0, 270, 0), (90, 270, 0), (180, 270, 0), (270, 270, 0),
(0, 0, 90), (90, 0, 90), (180, 0, 90), (270, 0, 90),
(0, 0, 270), (90, 0, 270), (180, 0, 270), (270, 0, 270)
]
# Describes the unit vector for a 3D system
const Basis = NTuple{3, NTuple{3,Int}}
# Helper Functions -------------------------------------------------------------
# The formula to rotate a vector about the x axis in 3 dimensions:
# - x′ = x
# - y′ = y × cos(θ) - z × sin(θ)
# - z′ = y × sin(θ) + z × cos(θ)
rotabout_x(x, y, z, θ) = (x, y*COS[θ] - z*SIN[θ], y*SIN[θ] + z*COS[θ])
# The formula to rotate a vector about the y axis in 3 dimensions:
# - x′ = x × cos(θ) + z × sin(θ)
# - y′ = y
# - z′ = z × cos(θ) - x × sin(θ)
rotabout_y(x, y, z, θ) = (x*COS[θ] + z*SIN[θ], y, z*COS[θ] - x*SIN[θ])
# The formula to rotate a vector about the z axis in 3 dimensions:
# - x′ = x × cos(θ) - y × sin(θ)
# - y′ = x × sin(θ) + y × cos(θ)
# - z′ = z
rotabout_z(x, y, z, θ) = (x*COS[θ] - y*SIN[θ], x*SIN[θ] + y*COS[θ], z)
# Rotate a vector about the x, y, and z axes in sequence
function rotabout_xyz(x, y, z, xθ, yθ, zθ)
(x, y, z) = rotabout_x(x, y, z, xθ)
(x, y, z) = rotabout_y(x, y, z, yθ)
return rotabout_z(x, y, z, zθ)
end
# Pre-calculate the rotation matrices for each of the 24 possible Scanner
# facings. The unit vector for 'no rotation' is `standard` below. Each rotation
# matrix can be used to translate points from one scanner facing to another
# scanner facing.
const BASES = begin
standard = ((1,0,0), (0,1,0), (0,0,1))
(sx, sy, sz) = standard
unitvectors = []
for rotation in ROTATIONS
unitvector = (
rotabout_xyz(sx..., rotation...),
rotabout_xyz(sy..., rotation...),
rotabout_xyz(sz..., rotation...),
)
push!(unitvectors, unitvector)
end
unitvectors
end
# Translate the location of a given beacon using another basis vector. This is
# basically just a matrix right multiply:
# https://cseweb.ucsd.edu/classes/wi18/cse167-a/lec3.pdf
function translate(beacon::Beacon, basis::Basis)
(bx1, by1, bz1) = basis[1]
(bx2, by2, bz2) = basis[2]
(bx3, by3, bz3) = basis[3]
(x, y, z) = beacon
newx = x*bx1 + y*by1 + z*bz1
newy = x*bx2 + y*by2 + z*bz2
newz = x*bx3 + y*by3 + z*bz3
return (newx, newy, newz)
end
# Translate all the beacon locations for one scanner to what their locations
# would be if the scanner had a different facing.
function translate(scanner::Scanner, basis::Basis)
return Set(translate(beacon, basis) for beacon in scanner)
end
# Identify the beacons detected in common between two scanners. This is a pretty
# intensive process:
# - For each possible scanner facing...
# - Translate all the `Beacon`s for Scanner `b` to the given facing
# - For each combination of a `Beacon` detected by Scanner `a` and a `Beacon`
# detected by Scanner `b`...
# - Calculate the distance between the `Beacon` from `a` and the `Beacon`
# from `b`, called `offset`
# - Add the `offset` to all the `Beacon` locations from Scanner `b`
# - Check how many of the offset Beacons from Scanner `b` are matched by a
# Beacon detected by Scanner `a`
# - If 12 or more beacon locations match, then we have determined the
# relative location of Scanner `b` from Scanner `a`
function incommon(a::Scanner, b::Scanner)
for basis in BASES
translated_b = translate(b, basis)
for (a_beacon, b_beacon) in Iterators.product(a, translated_b)
offset = a_beacon .- b_beacon
shifted_b = Set(beacon .+ offset for beacon in translated_b)
length(a ∩ shifted_b) >= 12 && return (shifted_b, offset)
end
end
return Iterators.repeated(nothing)
end
# To map all the Scanners, we check each Scanner against every other Scanner,
# adding scanners to `mapped` when we identify (and apply) the appropriate
# offset of between the two scanners.
function mapscanners(scanners)
mapped = Dict(0 => scanners[0])
offsets = [(0,0,0)]
searched = Set()
while length(setdiff(keys(scanners), keys(mapped))) > 0
for id1 in keys(scanners)
(id1 ∈ searched || id1 ∉ keys(mapped)) && continue
for (id2, scanner2) in scanners
(id2 ∈ keys(mapped) || id1 == id2) && continue
(common, offset) = incommon(mapped[id1], scanner2)
if !isnothing(common)
mapped[id2] = common
push!(offsets, offset)
end
end
push!(searched, id1)
end
end
return (mapped, offsets)
end
# Solve Part One ---------------------------------------------------------------
# Given the mapping of scanners from `mapscanners()`, count the total number of
# beacons. Since they've all been translated and offset relative to the initial
# scanner, this just means union-reducing the sets of beacons.
function part1(mapped)
allbeacons = reduce(∪, values(mapped))
return length(allbeacons)
end
Aw, man, it was math again. The fact that I’m not sure whether this qualifies as geometry or linear algebra probably means that I don’t know enough math to be doing this. Oh well, it works. Of course, this probably also means that there is a better, more math-y way to solve this puzzle too…
Part Two – It’s A Small World, After All
Now that we know where each scanner is relative to the others, it’s time to figure out just how widely these scanners have spread. Part 2 tasks us with identifying the largest distance (Manhattan-style) between any two scanners. Good thing we kept those offsets from before, huh?
# Solve Part Two ---------------------------------------------------------------
# Calculate the manhattan distance between two beacons
distance(a::Beacon, b::Beacon) = mapreduce(abs, +, a .- b)
# Given the offsets from `mapbeacons()`, calculate the manhattan distance between
# all pairs of offsets and return the largest value.
function part2(offsets)
maxdistance = 0
for (offset1, offset2) in Iterators.product(offsets, offsets)
distance = mapreduce(abs, +, offset1 .- offset2)
maxdistance = max(maxdistance, distance)
end
return maxdistance
end
Given that these are all relative distances, it’s just a matter of calculating the distance between all the pairs and taking the largest. No sweat!
Wrap-Up
This was the other very time-consuming day for me, in part because I just knew there had to be some clever way to identify where the scanners were relative to one another without checking every single beacon against every single other beacon (multiple times, probably). It shows in the run time for this solution, where running the mapscanners() function takes ~15s for my input. Then there was the small matter of figuring out the rotations for the 24 different facings, and researching how to translate the beacon locations for each of the 24 scanner facings. Extremely luckily for me, it wasn’t that long ago that I was watching a video for 3Blue1Brown that mentioned unit vectors and talked a bit about translating points to different unit vectors, which at least helped me know what I needed to Google. This was a tough day, but I’m glad to have accomplished it.
If you found a different solution (or spotted a mistake in one of mine), please drop me a line!