Author Archives: Julia on Eric Burden

Advent of Code 2021 – Day 20

By: Julia on Eric Burden

Re-posted from: https://www.ericburden.work/blog/2021/12/30/advent-of-code-2021-day-20/

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 20 – Trench Map

Find the problem description HERE.

The Input – A Tale of Two Inputs

Day 20 was interesting in that we basically had two different inputs in a single file. Granted, we’ve seen files with “chunks” of inputs before, but either my memory is faulty (totally plausible) or this is the first time we’ve seen two totally different inputs. Which, really, isn’t much of a problem, as it turns out. The first input comes from the first line, which we’re going to treat as a BitVector since we only need to know if each character is in one of two possible states. For the second input, we’ll use a Dict where the key is the row/col coordinate of a character in the character grid, and the value is a Bool that indicates whether that character is ‘#’ (on) or ‘.’ (off).

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

const Point = NTuple{2,Int64}
const Image = Dict{Point,Bool}


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

function ingest(path)
    return open(path) do f
		# Parse the first line into a BitVector, with '#' => 1, '.' => 0
		algostr = readuntil(f, "\n\n")
		algo = collect(algostr) .== '#'

		# Parse the rest of the lines into a Dict of (row, col) => true/false, 
		# where the value is true if the corresponding row/col of the input
		# is a '#'
		image = Dict{Point,Bool}()
		imagestr = readchomp(f)
		for (row, line) in enumerate(split(imagestr))
			for (col, char) in enumerate(collect(line))
				image[(row,col)] = char == '#'
			end
		end

		(algo, image)
    end
end

The keyword “infinite” in the problem statement clues us in that using a Matrix or even a BitMatrix is going to be the wrong call for this puzzle.

Part One – Beneath a Sea of Light (Pixels)

Today’s puzzle is (thankfully) pretty straightforward. Given a low resolution image, we just keep enhancing it until it resolves into something useful. As Seen on TV! There’s no way this won’t work, plus, we may get to put on our sunglasses in a really cool way after we solve it. YYeeaaaahhh!! We’ll take the values in a 3×3 grid around any given pixel to determine its new value, and the only really tricky bit (‘bit’, get it?) is to know what value to use for pixels we aren’t actively keeping track of. You might think it would be ‘false’ or ‘0’ for all those, but that’s the tricky part!

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

# Used to get the coordinates of the nine pixels surrounding any given
# pixel in the image
const OFFSETS = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)]


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

# Get a list of the coordinates of the pixels surrounding a given point
offsets(p::Point) = [p .+ offset for offset in OFFSETS]

# Convert binary value to decimal
todecimal(x) = sum(D*2^(P-1) for (D, P) in zip(x, length(x):-1:1))

# Given a point in the image, calculate the value of the point from the
# 3x3 area centered on that point
function valueat(image::Image, point::Point, default=false)
    value = [get(image, p, default) for p in offsets(point)]
    return todecimal(value)
end

# Enhance the image! Creates a new image (expanded by one in all directions) 
# where each pixel is flipped according to its calculated value.
function enhance(image::Image, algo::BitVector, default=false)
    newimage = Dict{Point,Bool}()

    # Need to expand the enhancement area by 1 in all directions each pass
    (minpoint, maxpoint) = extrema(keys(image))
    rng = (minpoint[1]-1):(maxpoint[2]+1)

    # For each possible point in the new image, determine its value
    for point in Iterators.product(rng, rng)
        pointvalue = valueat(image, point, default)
        pixel = algo[pointvalue + 1]
        newimage[point] = pixel
    end

    return newimage
end

# Solve ------------------------------------------------------------------------

function solve(input, rounds; test = false)
    (algo, image) = input
    for round in 1:rounds
        # The 'real' algorithm (not the test) has a '#' in the first position 
        # and a '.' in the last position, which means that the 'empty' pixels
        # surrounding the image all flip from '.' to '#' on odd numbered rounds.
        # The 'test' input does not have this 'feature'.
        default = !test && round % 2 == 0
        image = enhance(image, algo, default)
    end
    return sum(values(image))
end

See, apparently Eric Wastl, creator and designer of Advent of Code, thought that after the last two days we were probably having it too easy and he needed to keep us on our toes… Well played! The ‘enhancing algorithm’ for the actual input (not the test input) had the amusing feature that, each round, it would ‘flip’ all the pixels in the infinite expanse of untracked pixels from on, to off, then back again. I feel like there should have been one of those “photosensitive viewers” warnings for this one. But, knowing that, we could just change the default value every other round to get to the final answer.

Part Two – De Nada

Same as Part One, just more times! We’ve seen this sort of escalation before, and since we’re already taking a rounds argument in our part one solve() function, getting the answer here just requires passing 50 instead of 2 as our rounds argument. No new code!

Wrap-Up

Man, I needed Day 20. Days 18 and 19 really stretched me, either leading me down paths that turned out to have some unsatisfactory conclusions (Day 18) or forcing me to learn math (Day 19), and knocked me off my pace of a solution and a blog post every day. With the holidays looming close, a pretty straightforward implementation for Day 20 with one weird trick thrown in to spice things up was exactly the sort of enjoyable, non-head-bashing sort of day I needed. I will say, that having gotten this far with Julia, I was delighted at how smoothly the code came out of my fingers and how well I was able to think in Julia, even for this relatively easier puzzle. Just in time, too!

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

Advent of Code 2021 – Day 19

By: Julia on Eric Burden

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!

Advent of Code 2021 – Day 19

By: Julia on Eric Burden

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!