The Treachery of Whales

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:

Comments

[Sebastian Raaphorst]

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