Advent of Code 2021 Day 6
Try the simulator!
The task at hand
Solve for X where
X = number of lanternfish after N days
- 80
- 256
Input is
- A long string of comma-separated numbers
1-5
It represents
- The number of days before each lanternfish creates a new one
My literal, foolish and unscalable solution to Part 1
Split the input at each ',' into an array
Coerce each string to a number
Counting down from 80:
Create a new array to store fish in
For each fish from the previous iteration (or the parsed input on the first pass):
If the days is 0:
Change the day to 6
Insert an 8 at the end of the new array
Else:
Decrement the day by 1
Return the day
If the new array has any fish:
Append the contents of the new array to that of the array from the previous iteration
Return the length of the copied, mutated array of numbers
See the problem?
- My algorithm re-generates an exponentially-larger array with each iteration
Luckily, it was small enough to finish running 80 iterations.
Expectedly, I would have been waiting days for it to finish running 256.
I found a far more eloquent, scalable algorithm
- JavaScript solver Totto16 wrote a simple solution to this puzzle
- Even better, it made sense to me immediately!
Setup:
Create an array, tracker, with 9 values, each being 0
For each number in the parsed input:
Increment the value by 1 at the index corresponding to the parsed input's number
Main loop:
Counting down from N days:
Store a reference to the value at the first location in tracker
Remove the first item from tracker, thus shortening the array to 8 values
Insert an item with value 0 at the end of tracker
Update the value at location 6 to equal the sum of its current value and the stored value
Update the value at location 8 to equal the sum of its current value and the stored value
Return the sum of all numerical values in tracker
Here is a visual description of how Totto16's algorithm works:
Making the simulator for this puzzle felt easy
- I pulled the majority of the code from the simulator for Dumbo Octopus: the HTML, CSS and JS, including the slider for playback speed
- Since this algorithm was so much simpler, there was a lot of deleting, thankfully
- Lastly, just a few lines of array mapping and reducing to generate the displays for the individual fish tallies and the total count
Thanks to Totto16's algorithm, I discovered the most logical, performant, and scalable way to solve this challenge:
- Represent consistently changing counts of items as unchanging quantities of items - each with incrementing tallies - in an array.
I sense that this puzzle-solving tactic will come in handy for a few other puzzles in this series.
Top comments (0)