## Advent of Code 2021 Day 7

### Try the simulator!

## The task at hand

### Solve for X where

`X = a tallied cost of moving to a shared location`

### Input is

- A string of comma-separated integers

### It represents

- Locations of crab submarines

## Studying someone's code: wait, my code?!

- I solved both parts of this puzzle on the day it was released
- I recall not feeling too intimidated by it
- Returning to my code, I am delighted by how concise and readable it is

### Part 1: where each move costs one fuel

```
Split the input into an array of integers
Identify the smallest and largest integers in the list
Setup a variable mapping fuel costs and end locations
For all integers as i from min to max positions of the list
For each position
Increment an accumulating integer - starting from 0 - by the absolute value of the result of subtracting i from the current position
Create a key in the variable matching the accumulated value
Store in that key the integer of the current iteration
Return the smallest value from a list of all of the fuel mapping's keys
```

Here's a visualization of this algorithm's first three iterations

### Part 2: where each move costs one additional fuel

```
Split the input into an array of integers
Identify the smallest and largest integers in the list
Setup a variable mapping fuel costs and end locations
For all integers as i from min to max positions of the list
For each position
Increment an accumulating integer - starting from 0 - by the result of the following operations:
Store the absolute value of the result of subtracting i from the position
Calculate the result of the following equation to amass a value equal to the sum of all numbers between 1 and the position:
Multiply the stored absolute value by the sum of itself and 1
Divide that product by 2
(e.g. 5+4+3+2+1 = 5(5+1)/2 = 15)
Create a key in the variable matching the accumulated value
Store in that key the integer of the current iteration
Return the smallest value from a list of all of the fuel mapping's keys
```

The difference is subtle. Even more subtle in the code. Because it is one edit to one line of code.

```
// Part 1
For i from min to max:
Math.abs(position - i)
// Part 2
For i from min to max:
Math.abs(position - i) * (Math.abs(position - i) + 1) / 2
```

## A brief puzzle with a bonus lesson

- When I solved this the first time, I was proud to do so quickly
- I was proud of incorporating memoization and recursion - popular techniques used in dynamic programming
- But after returning to this puzzle, I realized I was overthinking the problem: I didn't need either of those techniques.
- I was using them to generate the sum of all numbers between some number N and 1.
- There's an easy formula for that: N(N+1)/2

It was also fun and rewarding practice to build this puzzle's simulator:

## Top comments (1)

I'm pretty sure that the solution to part (1) of this problem is always the median position of the crabs, i.e.

If

`positions.size`

is odd, you'd likely have to try the floor and the ceil, but in both the test data and my personal data, the median was the correct position. I don't think it would be hard to provide a mathematical proof.I'm wondering if there's something similar for the second part, but nothing glaringly obviously jumps out at me and I brute forced it as it seems all the other solutions did.

(I'm doing it late this year... December was a rough month.)