AoC 2021 D6: Lanternfish

| Problem statement | Source code | Tags: Dynamic programming

← Previous Back to AoC Index Next →

The naïve solution is to simulate each fish individually:

fishes = fishes.flatMap((fish) => (fish === 0 ? [6, 8] : [fish - 1]));

However, the number of fish grows exponentially, so this doesn't work for part 2. The next observation is that all fish with the same internal timer behave identically. Therefore, we can put fish into 9 bins based on their internal timer (0 to 8). Each day, the fish in each bin move to the next lower bin, and the fish in bin 0 create new fish in bin 8 and also move to bin 6.

I'm labeling this "Dynamic programming" because we have a state and a state transition. But this is really just bin counting.

let counterToCount = Array.from({ length: 9 }, () => 0);
for (const fish of fishes) {
  counterToCount[fish]++;
}
for (let day = 1; day <= days; day++) {
  const newCounterToCount = Array.from({ length: 9 }, () => 0);
  for (let newCounter = 0; newCounter < 8; newCounter++) {
    newCounterToCount[newCounter] = counterToCount[newCounter + 1];
  }
  newCounterToCount[6] += counterToCount[0];
  newCounterToCount[8] = counterToCount[0];
  counterToCount = newCounterToCount;
}

← Previous Back to AoC Index Next →