Lanternfish

Advent of Code 2021 Day 6

Try the simulator!

The task at hand

Solve for X where

X = number of lanternfish after N days

1. 80
2. 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.