Advent of Code 2021, Day 7

What trickery is this? I’m doing the day 7 puzzle on day 7?

Well, as cute as the idea of crabs in tiny submarines coming to my rescue is, part 1 of the puzzle itself seems almost comically simple.

The submarines all have a numeric position, and they need to move to a common position with the least fuel expenditure possible. It immediately strikes me that, given that fuel expenditure is equal simply to the the distance to the target point, the most efficient point to reach must be the median. It’s right there in the name - the median’s the middle.

From there, it’s just a matter of taking the absolute value of each sub’s position minus the median, all summed together.

public String part1() {
    int midpoint = median(points);
    int sum = Arrays.stream(points).map(n -> Math.abs(n - midpoint)).sum();
    return String.valueOf(sum);
}

Part 2 adds a wrinkle in that the fuel cost now increases with every step taken. That’d make the fuel use after n steps the nth triangle number, which of course can be found by (n(n+1))/2.

But where to find the midpoint of these? It’s not nearly as obvious, but still simple if you know how: when dealing with triangle numbers like this, the midpoint is pretty close to the mean of the initial positions. By “pretty close”, I mean you either round up or down. There’s a formula that I don’t currently recall for figuring out which, but for this, I just find both answers and pick the best one.

So, take that midpoint, add the triangle calculation as an extra step in the fuel consumption, sum it all up, done.

public String part2() {
    int midpoint = mean(points);
    // The midpoint is the mean rounded either up or down; check both and pick the best
    int sumA = Arrays.stream(points).map(n -> Math.abs(n - midpoint)).map(n -> (n*(n+1))/2).sum();
    int sumB = Arrays.stream(points).map(n -> Math.abs(n - midpoint - 1)).map(n -> (n*(n+1))/2).sum();
    return String.valueOf(Math.min(sumA, sumB));
}

That didn’t take long at all!

• Advent of Code