Today's puzzle involved figuring out the fastest way to align a swarm of crab submarines. Being crab submarines, they can only move sideways and our puzzle input describes their current horizontal positions. The submarines use one unit of fuel each time they move to an adjacent position.

The way I chose to solve part one, was to iterate through every possible position and calculate the fuel cost of moving every submarine there. If the total cost was lower than the previous best, then use that as the new best cost.

proc part1(input: string): int =
result = high(int)
let positions = input.split(",").map(parseInt)
for target in min(positions) .. max(positions):
let cost = costOfMove(positions, target)
if cost < result: result = cost

Because we're working in one-dimensional space here, actually calculating the fuel costs was very straightforward.

proc costOfMove(positions: seq[int], target: int): int =
for position in positions:
result += abs(position - target)

I usually try to solve the problem with the solution I'm most likely to get correct. Most of the time this gives me the correct answer, which I use to write some assertions, so that I can refactor confidently. Today was a day where that strategy paid off, because part two was an identical problem, it just needed different logic for calculating the fuel costs.

This time, the first time a submarine moves, it uses one unit of fuel, the second time it moves it uses two, the third time three, and so on. In other terms, when the distance is n the fuel cost is given by the following formula.

1 + 2 + 3 + ... + n

I misidentified the pattern as factorial, but after a brief attempt with fac, I returned to Google find out the proper name for "factorial with addition". Turns out that it doesn't have a catchy name, but the sequence of numbers are called triangular numbers and that you can calculate the nth triangular number with the formula (n * (n + 1)) / 2.

With this formula it was straightforward to copy my part one solution and swap out the fuel cost function.

proc crabCostOfMove(positions: seq[int], target: int): int =
for position in positions:
let n = abs(position - target)
result += (n * (n + 1)) div 2

proc part2(input: string): int =
let positions = input.split(",").map(parseInt)
for target in min(positions) .. max(positions):
let cost = crabCostOfMove(positions, target)
if cost < result: result = cost

I haven't talked about it yet, but Nim's result variable is return keyword. It can look a bit magical and having a preinitialized variable (from the return type of the procedure) seems like it has the potential to cause confusion. That said, it's quite nice to avoid duplication from declaring a return type, then immediately initializing a variable that will eventually be used.

There's not much on GitHub that didn't make it into the blog today, but here's the code, nonetheless!

GitHub Day 7