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