DEV Community

Cover image for The Treachery of Whales
Robert Mion
Robert Mion

Posted on

The Treachery of Whales

Advent of Code 2021 Day 7

Try the simulator!

Interactive crab migration tool

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
Enter fullscreen mode Exit fullscreen mode

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

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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:
Interactive crab migration tool

Top comments (1)

Collapse
 
sraaphorst profile image
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]
Enter fullscreen mode Exit fullscreen mode

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