Day seven of AoC 2021 (available at https://adventofcode.com/2021/day/7) puts us in mortal peril: a giant whale is chasing our submarine! Fortunately, a swarm of crabs in tiny "crabmarines" arrives to help. They'll blast a hole in the ocean floor — but first they need to align horizontally.
The input is a list of horizontal positions for each crab submarine.
Parsing the Input
Simple comma-separated integers:
const processInput = async (day: number) => {
const input = await readInput(day);
return input.split(",").map(n => parseInt(n, 10));
};
Part One: Linear Fuel Cost
Each step costs 1 fuel. Find the position where aligning all crabs costs the least total fuel.
Brute force: try every position from minimum to maximum, calculate total fuel for each:
const partOne = (input: number[], debug: boolean) => {
const min = Math.min(...input);
const max = Math.max(...input);
let minValue = Number.MAX_SAFE_INTEGER;
for (let position = min; position <= max; position++) {
const pvalue = input
.map(value => Math.abs(value - position))
.reduce((acc, value) => acc + value, 0);
if (pvalue < minValue) {
minValue = pvalue;
}
}
return minValue;
};
This is O(n × range) — for ~1000 crabs across ~2000 positions, that's ~2 million operations. Fast enough.
Math note: The optimal position for part one is actually the median of the input. Moving away from the median always increases total distance. But brute force works fine here.
Part Two: Triangular Fuel Cost
Now each step costs more than the last: moving 1 step costs 1, moving 2 steps costs 1+2=3, moving 3 steps costs 1+2+3=6, and so on.
The cost to move n steps is the sum of integers from 1 to n. This is where Gauss comes in.
Legend has it that young Gauss was asked to sum the numbers 1 to 100. Instead of adding laboriously, he noticed: 1+100=101, 2+99=101, 3+98=101... There are 50 such pairs, so the answer is 50×101=5050.
The general formula: sum(1 to n) = n × (n+1) / 2
const partTwo = (input: number[], debug: boolean) => {
const min = Math.min(...input);
const max = Math.max(...input);
let minValue = Number.MAX_SAFE_INTEGER;
for (let position = min; position <= max; position++) {
const pvalue = input
.map(value => Math.abs(value - position))
.map(value => value * (value + 1) / 2) // Gauss's formula inline
.reduce((acc, value) => acc + value, 0);
if (pvalue < minValue) {
minValue = pvalue;
}
}
return minValue;
};
Same brute force structure, different cost function.
Math note: For part two, the optimal position is close to the mean (average) of the input — though rounding can be tricky. Some inputs need floor, others need ceiling. Brute force avoids this ambiguity entirely.
Why Brute Force Works
With ~1000 crabs and ~2000 positions:
- Part 1: 2 million additions
- Part 2: 2 million multiplications and additions
Both complete in milliseconds. Sometimes the naive approach is good enough.
I always consider: is the brute force O(n²) or worse? Is n small enough that it doesn't matter? Here, n×range is around 2 million — modern computers eat that for breakfast.
The Gauss Formula in Practice
This formula appears constantly in programming:
- Summing consecutive integers
- Calculating triangular numbers
- Handshake problems (how many handshakes in a room of n people?)
- Counting pairs
It's worth committing to memory: n × (n+1) / 2
You could also compute it iteratively with a loop or Array.from({length: n}, (_, i) => i + 1).reduce((a,b) => a+b), but the formula is O(1) versus O(n). For small n it doesn't matter; for large n it's essential.
Performance
Both parts run in under 100 milliseconds. The input processing is trivial, and the double loop is fast despite being quadratic in theory.
No optimization needed. Ship it.
Takeaways
Brute force first: If the search space is small (thousands, not billions), just try everything. It's simple, correct, and often fast enough.
Know your classic formulas: Gauss's sum formula turns O(n) summation into O(1) arithmetic. These tricks compound over a programming career.
Median vs mean: Part one's optimal is the median (minimizes absolute deviations). Part two's optimal is near the mean (minimizes squared-ish deviations). Different cost functions, different optima.
Don't optimize prematurely: The brute force solution runs in milliseconds. Implementing a clever median/mean solution would save... milliseconds. Not worth the debugging risk.
Crabs move sideways: Just like in real life. 🦀
The full solution is available in the repository.