By: Julia on Eric Burden

Re-posted from: https://ericburden.work/blog/2021/12/07/advent-of-code-2021-day-7/

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 7 – The Treachery of Whales

Find the problem description HERE.

The Input – Nothing to See Here

Seriously. Today’s input is a comma-separated list of numbers. So…

function ingest(path)
    return open(path) do f
        readsplit(x) = split(readchomp(x), ",")
        [parse(Int, s) for s in readsplit(f)]
    end
end

See? Told you.

Part One – Crabwalk

For today’s puzzle, our job is to help a bunch of crabs in submarines (?) line
up while expending as little energy as crabbily possible. Thankfully, since
they’re crabs, they can only move sideways, so we only have one dimension to
work with. Given our list of numbers, our job is to find a number such that the
crabs, in aggregate, can line up on that number while moving as little as
possible. Something about not having a lot of fuel in their little submarines,
which you’d imagine would be a good thing to think about before you took
it down to the ocean floor, but what do I know?

using Statistics

# The position that will be optimally close to each crab is
# the median of all the crab positions.
function part1(input)
    position = convert(Int, median(input))
    crabdistance = abs.(position .- input)  # Broadcasting!
    return sum(crabdistance)
end

This was less a programming challenge than a math/logic challenge. If it’s not
clear why the median of the array of crab positions is the right value for them
to line up on, consider the following sequence (our example) in order:

0, 1, 1, 2, 2, 2, 4, 7, 14, 16
              ^
            median

It makes intuitive sense that the optimal position should be somewhere near the
middle, and there’s nowhere more “middle” than the median. A mean, or average,
can be influence by large outlier values, but not the median. With this intuition
in hand, try to come up with an example where the median wouldn’t be the right
answer. I couldn’t, but maybe you’re more creative than I am.

Part Two – Give it the Gauss

Turns out, crab submarines burn fuel at an ever-increasing rate the longer they
move. I mean, it’s good for us that the crabs are down here, but I don’t think
they ever stood a chance of getting back to the surface. This part is more
interesting, from a coding perspective:

using Base.Iterators
using Statistics 

# Overloading arbitrary operators is fun!
±(a, b) = (a + b, a - b)

# Use the Gaussian method for summing sequences of numbers to quickly calculate
# the total distance of all crabs to a given position.
function gaussdistance(position::Int, crabs::Vector{Int})::Int
    # So much broadcasting!
    n = abs.(crabs .- position) .+ 1
    distances = (n .* (n .- 1)) .÷ 2
    return sum(distances)
end

# Makes a reasonable guess about where the optimal crab position is, then
# searches to the left or right to find the real optimal position.
function part2(input)
    # Start at a reasonable place, the average value of the crab positions
    startingat = trunc(Int, mean(input))
    crabdistance(x) = gaussdistance(x, input)
    currentmin = crabdistance(startingat)

    # Now we need to decide if we should search for a position to the left
    # or right of our starting position. Check to the left and right of the
    # starting position. We'll move in whichever direction has a lower
    # aggregate crab distance. If somehow our guess was spot on, we'll 
    # end up skipping the for loop below and just returning the total distance
    # to the starting position.
    (left, right) = startingat ± 1
    (leftdist, rightdist) = map(crabdistance, (left, right))
    
    (position, nextdist, step) = (
        leftdist < rightdist 
        ? (left, leftdist, -1) 
        : (right, rightdist, 1)
    )

    # Now just iterate in the direction we decided on above, until we find
    # the total distance starts to increase. At that point, we can return 
    # the minimum value found.
    while nextdist < currentmin
        currentmin = nextdist
        position += step
        nextdist = crabdistance(position)
    end

    # NOTE: For my input, the above loop never runs because the actual position
    # turned out to be one to the right of my starting position. Your mileage 
    # may vary.
    return currentmin
end

We can quickly calculate the amount of fuel a crab needs to move a given distance
using the Gaussian Method.
With that in place, we pick a spot on the number line to start our search for
the optimal position. Since we know that somewhere on the number line there is
a value that will yield the minimum crab fuel cost (and we can surmise that
crab fuel costs rise to either side of that value), we can check to the left and
right of our starting guess. Whichever side has a value lower than our initial
guess is the direction we should go to find the minimum aggregate fuel cost. From
there, it’s just a matter of trying values down the number line until the
fuel cost starts to go back up again, then we’ll know we’ve found our ideal
position.

Wrap Up

Today was all about broadcasting! And a bit of math. But mostly broadcasting! If
you’re not familiar, broadcasting is the term used in Julia to describe the syntax
for vectorizing functions and operations, named after the broadcast() function.
That’s what all the dots before operators and after function names are about.
Once you understand that 5 .+ [5, 10, 15] is [10, 15, 20], then the vectorized
operations and functions can make your code a lot more readable. Using broadcasting
eliminated a number of for loops in today’s code.

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