Home
🐠

Day 6: Lanternfish

https://adventofcode.com/2021/day/6
Challenge
The sea floor is getting steeper. Maybe the sleigh keys got carried this way?
A massive school of glowing lanternfish swims past. They must spawn quickly to reach such large numbers - maybe exponentially quickly? You should model their growth rate to be sure.
Although you know nothing about this specific species of lanternfish, you make some guesses about their attributes. Surely, each lanternfish creates a new lanternfish once every 7 days.
However, this process isn't necessarily synchronized between every lanternfish - one lanternfish might have 2 days left until it creates another lanternfish, while another might have 4. So, you can model each fish as a single number that represents the number of days until it creates a new lanternfish.
Furthermore, you reason, a new lanternfish would surely need slightly longer before it's capable of producing more lanternfish: two more days for its first cycle.
So, suppose you have a lanternfish with an internal timer value of 3:
A lanternfish that creates a new fish resets its timer to 6, not 7(because 0 is included as a valid timer value). The new lanternfish starts with an internal timer of 8 and does not start counting down until the next day.
Realizing what you're trying to do, the submarine automatically produces a list of the ages of several hundred nearby lanternfish (your puzzle input). For example, suppose you were given the following list: 
3,4,3,1,2
This list means that the first fish has an internal timer of 3, the second fish has an internal timer of 4, and so on until the fifth fish, which has an internal timer of 2. Simulating these fish over several days would proceed as follows: 
Initial state: 3,4,3,1,2
After  1 day:  2,3,2,0,1
After  2 days: 1,2,1,6,0,8
After  3 days: 0,1,0,5,6,7,8
After  4 days: 6,0,6,4,5,6,7,8,8
After  5 days: 5,6,5,3,4,5,6,7,7,8
After  6 days: 4,5,4,2,3,4,5,6,6,7
After  7 days: 3,4,3,1,2,3,4,5,5,6
After  8 days: 2,3,2,0,1,2,3,4,4,5
After  9 days: 1,2,1,6,0,1,2,3,3,4,8
After 10 days: 0,1,0,5,6,0,1,2,2,3,7,8
After 11 days: 6,0,6,4,5,6,0,1,1,2,6,7,8,8,8
After 12 days: 5,6,5,3,4,5,6,0,0,1,5,6,7,7,7,8,8
After 13 days: 4,5,4,2,3,4,5,6,6,0,4,5,6,6,6,7,7,8,8
After 14 days: 3,4,3,1,2,3,4,5,5,6,3,4,5,5,5,6,6,7,7,8
After 15 days: 2,3,2,0,1,2,3,4,4,5,2,3,4,4,4,5,5,6,6,7
After 16 days: 1,2,1,6,0,1,2,3,3,4,1,2,3,3,3,4,4,5,5,6,8
After 17 days: 0,1,0,5,6,0,1,2,2,3,0,1,2,2,2,3,3,4,4,5,7,8
After 18 days: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8
Each day, a 0 becomes a 6 and adds a new 8 to the end of the list, while each other number decreases by 1 if it was present at the start of the day.
In this example, after 18 days, there are a total of 26 fish. After 80 days, there would be a total of 5934.
Find a way to simulate lanternfish. How many lanternfish would there be after 80 days?

🔗 Part Two

Suppose the lanternfish live forever and have unlimited food and space. Would they take over the entire ocean?
After 256 days in the example above, there would be a total of 26984457539 lanternfish!
How many lanternfish would there be after 256 days?

🔗 Part A

There is no need for us to be clever with this one (hint hint 👀). Start off by reading in the correspond lanternfish "timers" using stdin from our Utilities module. 
import { stdin } from "./util";

const lanternfish = stdin()
  .split(",")
  .map((n) => parseInt(n));
We can define a tick function which moves our lanternfish timers ahead one step. When a timer goes below 0, we set it back to 6 and additionally append a new lanternfish with a timer of 8. 
function tick(arr: number[]) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    arr[i] -= 1;
    if (arr[i] < 0) {
      arr.push(8);
      arr[i] = 6;
    }
  }
}
Then we tick 80 times and print the number of lanternfish. 
for (let i = 0; i < 80; i++) {
  tick(lanternfish);
}

console.log(lanternfish.length);

🔗 Part B

Suppose the lanternfish live forever and have unlimited food and space. Would they take over the entire ocean?

After 256 days in the example above, there would be a total of 26984457539 lanternfish!
How many lanternfish would there be after 256 days?
That's a lot of fish, and we're probably not going to be able to use a solution which appends to an array and computes its length. (Feel free to try it!) Instead we'll need to be a little clever.
My alarm bells went off immediately thinking this would have something to do with the Fibonacci sequence, based on the much-contrived Fibonacci rabbits puzzle.
A pair of rabbits produces a new pair each month, and that new pair needs a month before it can itself produce offspring.
A pair of rabbits produces a new pair each month, and that new pair needs a month before it can itself produce offspring.
After staring at my editor for a bit and trying various Fibonacci-looking sequences, I threw in the towel and realized I'll probably have to write something novel.
There's still a nugget of truth in there, however. Namely: Instead of tracking all the Rabbits and their "timers," we only track (a) how many rabbits are ready to produce offspring and (b) how many rabbits are maturing. We can do the same for our lanternfish.
Let's read in our input. 
import { stdin } from "./util";

// Timers 0 through 8
const lanternfish = [
  0, 0, 0, 0, 0, 0, 0, 0, 0,
];
stdin()
  .split(",")
  .map((n) => lanternfish[parseInt(n)]++);
Instead of tracking each lanternfish, we can track how many have a timer 0, how many have a timer 1, etc (all the way to 8). With the following rules to update each generation.
We'll do this for each of the 256 generations. 
for (let i = 0; i < 256; i++) {
  const prev = lanternfish.slice();

  for (let j = 0; j < 8; j++) {
    lanternfish[j] = prev[j + 1];
  }

  // ...
}
But we missed TWO important details!
So our for-loop becomes the following: 
for (let i = 0; i < 256; i++) {
  const prev = lanternfish.slice();

  for (let j = 0; j < 8; j++) {
    lanternfish[j] = prev[j + 1];
  }

  // 0's spawn 6's
  lanternfish[6] += prev[0];

  // 0's spawn 8's
  lanternfish[8] = prev[0];
}
After our loop runs we can total up the lanternfish to get our result. 
console.log(
  lanternfish.reduce((a, b) => a + b, 0)
);
There's likely a closed-form solution but this felt clever enough for me. Tough one, though!