# AoC 2021 Day 7: Brachyura Aligner

### Source: The Treachery of Whales

#### Part 1: Given a list of numbers, find the minimum integer I such the sum difference of each number and I is minimized.

There is probably a fancy number theory way of doing it to solve directly for I, but it’s a really quick problem to brute force:

def part1(file: typer.FileText):

positions = [
int(value)
for line in file
for value in line.split(',')
]

fuel, target = min(
(
sum(abs(position - target) for position in positions),
target
)
for target in range(min(positions), max(positions)+1)
)

print(f'{target=}, {fuel=}')


Load in the numbers, calculate every possible target from minimum to maximum and the sum distance for that value of I, then return just the minimum such value.

python3 brachyura-aligner.py part1 input.txt target=323, fuel=336040  Quick. #### Part 2: Instead of using the distance function |I-n|, instead use d(1)=1, d(2)=3, d(3)=6, etc (the triangular numbers). It actually originally said: Instead, each change of 1 step in horizontal position costs 1 more unit of fuel than the last: the first step costs 1, the second step costs 2, the third step costs 3, and so on. That ends up turning into 1, 3, 6, 10, ... which I recognized as the Triangular numbers. And it turns out there isa direct formula for calculating the nth Triangular number: t(n) = \frac{n(n-1)}{2} def part2(file: typer.FileText): def t(n): return n * (n + 1) // 2 positions = [ int(value) for line in file for value in line.split(',') ] fuel, target = min( ( sum(t(abs(position - target)) for position in positions), target ) for target in range(min(positions), max(positions)+1) ) print(f'{target=}, {fuel=}')  And off we go:  python3 brachyura-aligner.py part2 input.txt
target=463, fuel=94813675


It is interesting how that changes the answer, but I expect that’s because distance scale much more quickly, so extremes matter more than in part 1.

#### Optimization

One optimization that you can notice is that either of these functions still results in a function with a single local minimum (the solution). Let’s show that:

last_score = 0

for target in range(min(positions), max(positions)+1):
score = sum(t(abs(position - target)) for position in positions)

if last_score:
print('=' if score == last_score else ('^' if score > last_score else 'v'), end='')

last_score = score


For each score, we’re going to print ^ if the score is currently rising and v if it’s falling.

vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


Swaps right at 463 (as expected). So one optimization would be to start at the low end and wait until it swaps. Another would be to do a binary search, looking for that inversion point. In either case though…

--- Day 7: The Treachery of Whales ---

python3 brachyura-aligner.py part1 input.txt target=323, fuel=336040 # time 140666042ns / 0.14s python3 brachyura-aligner.py part2 input.txt
target=463, fuel=94813675
# time 284611417ns / 0.28s


It doesn’t seem necessary. It’s the slowest problem so far, but by no means slow. After all:

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

– Donald Knuth, The Art of Computer Programming

😄