advent-of-code-2021-day-7.md

Day 7

https://adventofcode.com/2021/day/7

Part 1

This is two steps. First we have to find the final position of all crabs. Then get the sum of steps each crab had to take.

Find the final position of all crabs.

My first intuition was that it would be the closest to the average position. I did the math in my head on the sample problem. The answer would have been 4, which is wrong. We were looking for 2.

So then I thought, maybe it's the geometric mean. IIRC it got the right answer for the sample problem. But that was a coincidence. The answer I got for the real problem was 1, which is clearly not right.

For the sake of curiosity, here's how I calculated the average (aka mean) and geometric mean:

function sum(a, b) {
  return a + b;
}

const xs = input.split(",").map((x) => parseInt(x));
const mean = xs.reduce((a, b) => a * b, 1) ** (1 / xs.length);
const squares = xs.map((x = x * x);
const sumOfSquares = squares.reduce(sum, 0);
const geometricMean = sumOfSquares ** (1 / squares.length);

Still my intuition tells me it's some kind of average. What else could it be? The mode (i.e. the most common number)? Not that's clearly not right. If there are 500 1s, 499 10s, and 1 9, the mode is 1 but we want 9.

I only know of one other kind of "average" and that's the median, i.e. the position that starts off with an equal number of crabs on the left and the right. (Spoiler: the median worked. It feels right, but at this point I'm not sure I can explain why it worked.)

To find the median, we first need to sort the crabs.

xs.sort((a, b) => a - b);

Then it's a matter of grabbing the one in the middle.

const middle = xs[xs.length / 2];

Technically that ends up being the crab at index 500, whereas the middle is really the average of the two middle crabs (499 and 500). If we had an odd number, we'd want the one at index length / 2. Since half of an odd number is not a whole number and our array is zero-indexed, we would need to round down: Math.floor(length / 2).

// Github Copilot wrote this code for me. Cool!
function median(xs) {
  xs.sort((a, b) => a - b);
  const length = xs.length;
  if (length % 2 === 0) {
    return (xs[length / 2] + xs[length / 2 - 1]) / 2;
  } else {
    return xs[Math.floor(length / 2)];
  }
}

Anyway, my naive solution to find the median worked.

Get the sum of steps each crab had to take

This is pretty simple. We know where each crab ends up. Now all we need to do is find out how far each crab is from the target (the absolute value of startPosition - targetPosition). Then take the sum of those values.

const answer = xs.map((x) => Math.abs(x - middle)).reduce(sum, 0);

Part 2

Ugh, this just got 100 times harder. There's probably a more efficient solution but I think I'm just going to calculate the expense of each position and then find the minimum. First we need a function to calculate the new fuel usage. I wonder if I can calculate that without using a loop. The first numbers in a sequence are:

1, 2, 3,  4,  5,  6,  7,  8,  9, 10, ...
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

I'm going to cheat and look that up on OEIS. Oh yeah, those are triangle numbers. I definitely did not remember the formula off the top of my head but it's pretty simple.

// again, I typed the function name and Copilot finished it for me.
function triangleNumber(n) {
  return (n * (n + 1)) / 2;
}

Okay, so now we need a function that calculates the total fuel usage for a given position.

function fuelUsage(position) {
  return xs.map((x) => triangleNumber(Math.abs(x - position))).reduce(sum, 0);
}

And map that over all positions from 0 to 999.

// an array of numbers from 0 to 999. It's weird because JavaScript.
const allPositions = new Array(1000).fill(null).map((_, i) => i);

const fuelUsages = allPositions.map(fuelUsage);

And then find the minimum.

const minimumFuelUsage = Math.min(...fuelUsages);