DEV Community

Cover image for Lanternfish
Robert Mion
Robert Mion

Posted on

Lanternfish

Advent of Code 2021 Day 6

Try the simulator!

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

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

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

Here is a visual description of how Totto16's algorithm works:
Totto16's algorithm visualization

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 Lanternfish reproduction simulator

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)