## DEV Community # The Treachery of Whales

## Advent of Code 2021 Day 7

### Try the simulator! ### 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 I'm pretty sure that the solution to part (1) of this problem is always the median position of the crabs, i.e.

``````positions.sorted()[positions.size / 2]
``````

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

DEV Community