# ETOOBUSY 🚀 minimal blogging for the impatient

# AoC 2021/7 - Median crabs

**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:

\[T(n) = \frac{(n + 1) n}{2}\]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!