Advent of Code, in Erlang: Day 7

Oh good, this series has made it to Day 7, the day that I wasn't sure my code was "right", but did give the correct answer.

We're given a list of "crab positions", and we're supposed to move them all to the same position, using "as little energy" as possible. Parts 1 and 2 differ only in how the energy is calculated. In Part 1, each time any crab moves one space, we count one unit of energy. In Part 2, a crab moving N spaces costs sum(1..N) energy (=N*(N+1)/2, which hilariously just came up again in Day 17).

Before we get to the code, let's talk strategy. Intuitively, the point that is going to cost the least to get all the crabs to is "somewhere in the middle". Primary school math gives us two versions of "middle" to choose from: mean and median. Before doing any more research, I gave them a try, and … huh, the answers they give are the ones the website accepts. Hooray! But why do they work? And which one is which?

If you guessed that median works for Part 1, and mean for Part 2, you're correct. If you have a proof for why that is, please share (Twitter: @hobbyist). I went on intuition, and that went something like the following.

For the case where N spaces == N energy, it is better to move outliers toward the group that the group toward outliers. That's because moving the outlier costs only "a little" more energy to move it "a little" more space, but moving the group costs the size of the group multiplied by their move. Even if their move is small, if there's a lot of them, it's costly. Median chooses a point that puts half of the crabs to the left, and half to the right of the target point. It's not affected by the magnitude of the outlier (how far it is from the group), only whether the outlier is to the right or the left.

For the case where N spaces = sum(1..N) energy, it is better to move the group at least some of the way toward the outlier. A small amount of energy from their small amount of movement is a good tradeoff for what would be a large amount of additional movement for the outlier. Mean chooses a point in the weighted "middle" of the crabs' positions. That is, it is affected by the magnitude of the outlier.

The example input was 16,1,2,0,4,2,7,1,2,14. If we sort that, we get 0,1,1,2,2,2,4,7,14,16. Median will divide that in two: 0,1,1,2,2 on the left, 2,4,7,14,16 on the right. So, the median is two. That's the correct position for the example in Part 1.

cost_to_moveA(Position, Crabs) ->
    lists:sum([abs(Position-C) || C <- Crabs]).

This is my Part 1 energy calculator. The sum of the absolute values of the changes in position gives the expected value of 37. Let's just check - what does it give for the other positions?

[puzzle07:cost_to_moveA(P, Crabs) || P <- lists:seq(0, 16)].
[49,41,37,39,41,45,49,53,59,65,71,77,83,89,95,103,111]

There is no number in that list less than 37 at position 2. And, we can see that it's a global minimum, not a local one - the energy cost only climbs in both directions. This should remain the case even if we put an outlier *way* out - say 1000.

[puzzle07:cost_to_moveA(P, Crabs++[1000]) || P <- lists:seq(0, 16)].
% [1049,1040,1035,1036,1037,1040,1043,1046,1051,1056,1061,1066,1071,1076,1081,1088,1095]

Yep, it still makes sense to move that 1000 outlier all the way to position 2, instead of moving the three crabs at 2 *at all* toward 1000. It makes sense if you think about it this way: moving that crab that starts at 1000, from position 3 to position 2 takes one unit of energy, but moving all three crabs that start at position 2 just to position 3 costs 3 units of energy.

For Part 2, it makes more sense to plot the positions of the crabs. A crab histogram looks something like this:

        c
     c  c
  c  c  c     c        c                    c     c
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16

The mean (what some would call the "average") of these positions is 5, which is the correct position for this example input in Part 2.

cost_to_moveB(Position, Crabs) ->
    lists:sum([lists:sum(lists:seq(1, abs(Position-C))) || C <- Crabs]).

Oh look at that, I didn't think of the formula for sum(1..N) that day, and wrote it out as, literally, sum(1..N). Well either way it calculates the energy of moving all crabs to 5 as 168. That's the correct answer for the example in Part2. What does it give for the other positions?

[puzzle07:cost_to_moveB(P, Crabs) || P <- lists:seq(0, 16)].
% [290,242,206,183,170,168,176,194,223,262,311,370,439,518,607,707,817]

Same story! The energy required to move climbs straight away in both directions away from the 168 at position 5. Doing just a little bit of checking - moving the crab from position 16 just one more space, to 4 would cost 12 more units of energy. Moving the three crabs that start at position 2 from 4 to 5 costs 3 units of energy each - that's only 6 total, half the extra energy crab sixteen needed! Of course the tradeoff of each other crab matters as well, but the numbers above show the result: 2 more net energy units for every crab to reach position 4 instead of 5.

Whew, I think I've finally convinced myself that my code is giving the right answer for the right reason. Are any mathematicians reading? Is my intuition the right way to think about this? Is there a clearer, or more formal way to say it?

Categories: Development AdventOfCode