The Treachery of Whales
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-02-12 18:39:42

## [Advent of Code 2021 Day 7](https://adventofcode.com/2021/day/7)

### [Try the simulator!](https://aocthetreacheryofwhales.rmion.repl.co/)
![Interactive crab migration tool](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7v7sj6zhnitpmmu97ag3.gif)

## 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 1 algorithm visualization](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lgp19wvpznib69rrrbz0.gif)

### 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.

```js
// 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](https://aocthetreacheryofwhales.rmion.repl.co/):
![Interactive crab migration tool](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7v7sj6zhnitpmmu97ag3.gif)