TL;DR

On with Advent of Code puzzle 7 from 2021: discovering a property of the median.

This day’s puzzle can be solved with a brute force method. This is where I golfed a bit to:

#!/usr/bin/env raku
use v6;

sub MAIN ($filename = $?FILE.subst(/\.raku$/, '.tmp')) {
   my $x = $filename.IO.lines.comb(/\d+/)».Int;
   .put for
      ($x.min .. $x.max).map( { ($x «-» $_)».abs.sum }).min,
      ($x.min .. $x.max)
         .map( { ($x «-» $_)».abs.map({($_ + 1) * $_ / 2}).sum }).min;
}

Let’s unpack a bit.

It’s somehow intuitive that the solution must lie between the minimum and maximum value among all positions. In fact, the value beyond the maximum value (say 1 position over) would surely be greater than that for the maximum value, because it’s basically calculated from the value at the max position plus the number of crabs. Similar considerations can be done for candidates below the minimum, because we’re considering absolute distances here.

This accounts for why we restrict our search in the range(s) ($x.min .. $x.max). These are our candidate positions for a solution.

To iterate over them and calculate our target value we use map. As we eventually need to output the minimum value of the feature we are calculating, it’s just convenient to put a .min immediately after for both calculations (part 1 and part 2).

Inside each map we calculate the cost of each candidate, whose value is available in $_. In the first case, we subtract this candidate from each value in the input array using the hyperoperation «-», which “does the right thing” by repeating $_ the required amount of times to subtract it from each element of $x. This leaves us with a sequence of displacement values that might be positive or negative, so we first make sure to turn all of them positive (using hyperoperation ».abs) and then take their sum, which is the overall cost for this candidate.

In the second case we have to do a bit more calculations over the absolute values. In particular, we have to consider each absolute displacement to calculate the corresponding Triangular number:

Then, again, the sum to calculate the overall cost across all crabs.

One funny thing about these puzzles is the paralysis by analysis state that they can induce on me. I knew there had to be a quicker way to solve the first part than just brute-forcing it, but somehow it did not came to mind quickly. So I spent a good 20 minutes before surrendering to the brute force attack; in hindsight, considering the limited size of the inputs, it would have been better to just start with brute forcing and investigate optimizations later. Whatever.

Thanks to this solution by cetttbycettt, though, I discovered about a property of the median that basically solves the first part of the puzzle in the way I was looking for. This is what fellow Raku participant 0rac1e did in this solution, also making me discover the neat Stats module:

# code by 0rac1e
# https://www.reddit.com/r/adventofcode/comments/rar7ty/comment/hnkbauz/

use Stats;

my @c = 'input'.IO.split(',')».Int;

put [+] (@c «−» median(@c))».abs;
put [+] (1 «..» (@c «−» mean(@c)».floor)».abs)».sum;

TIL a lot!