Day 6/2021 - Lanternfish

Day six of AoC 2021 (available at https://adventofcode.com/2021/day/6) introduces us to lanternfish — bioluminescent creatures down by the water that reproduce exponentially. Each fish has an internal timer. When it hits zero, it resets to 6 and spawns a new fish with timer 8.

The input is a list of initial timer values: 3,4,3,1,2.

Part One: Naive Simulation

For 80 days, simulation works fine. Track each fish, decrement timers, spawn new fish:

const partOne = (input: number[], debug: boolean) => {
    const fishes = [...input].sort((a, b) => a - b);
    
    for (let day = 0; day < 80; day++) {
        let newFish = 0;
        let fishIndex = 0;
        
        // Process fish at zero (they're sorted, so zeros are first)
        while (fishes[fishIndex] === 0) {
            fishes[fishIndex] = 6; // Reset timer
            newFish++;
            fishIndex++;
        }
        
        // Decrement all other fish
        while (fishIndex < fishes.length) {
            fishes[fishIndex]--;
            fishIndex++;
        }
        
        // Add new fish
        for (let i = 0; i < newFish; i++) {
            fishes.push(8);
        }
    }
    
    return fishes.length;
};

After 80 days: 5934 fish for the example. My real input: some large but manageable number. Runs in ~300ms.

Part Two: The Wall

Part two asks for 256 days instead of 80. "Just change the constant," I thought.

The simulation slows down around day 140. By day 150, it's crawling. I watched the array grow: 9 million fish... 10 million... 13 million...

This is the nature of exponential growth. The population roughly doubles every 7-8 days. At that rate:

• 80 days: ~thousands of fish
• 256 days: ~trillions of fish

No computer can store trillions of individual fish in an array. The naive approach is mathematically impossible.

The Insight: Fish Are Fungible

Here's the key realization: individual fish don't matter. A fish with timer 3 is identical to every other fish with timer 3. We don't need to track them separately.

There are only 9 possible states (timers 0-8). Instead of an array of millions of fish, use an array of 9 counts:

function calculateFishes(fishes: number[], days: number) {
    const fishCycle = 6;
    const newFishCycle = 8;
    let dayIndex = 0;

    let state = new Array(newFishCycle).fill(0);
    for (const fish of fishes) {
        state[fish] += 1;
    }

    while (dayIndex < days) {
        const newState = new Array(newFishCycle + 1).fill(0);
        for (let i = 1; i < state.length; i++) {
            newState[i - 1] = state[i];
        }
        newState[newFishCycle] = state[0];  // New fish start at 8
        newState[fishCycle] += state[0];     // Parents reset to 6

        state = newState;
        dayIndex += 1;
    }
    return state.reduce((a, b) => a + b, 0);
}

Each day:

1. Shift all counts left (timer 5 fish become timer 4 fish, etc.)
2. Fish at timer 0 spawn new fish at timer 8
3. Fish at timer 0 reset to timer 6 (add to existing count)

That's it. Nine numbers, updated 256 times. Runs in 3 milliseconds.

The Numbers

The result for 256 days is an 11-digit number. JavaScript handles integers safely up to about 16 digits (Number.MAX_SAFE_INTEGER ≈ 9×10¹⁵), so we're fine. If the answer were larger, we'd need BigInt.

Always check your result against MAX_SAFE_INTEGER when dealing with exponential growth. An off-by-one error in the last digit means a wrong answer.

Performance Comparison

Approach	80 days	256 days
Simulation	~300ms	∞ (impossible)
State counting	~1ms	~3ms

The state-counting approach is O(days × states) = O(256 × 9) = O(2304). The simulation is O(days × fish_count), where fish_count grows exponentially.

Takeaways

1. Recognize when simulation won't scale: If the problem involves exponential growth and a large number of iterations, simulation is probably not the answer.

2. Look for equivalence classes: When individuals are interchangeable, count them instead of tracking them. This is a fundamental technique in combinatorics.

3. The constants are chosen deliberately: Eric (the puzzle creator) picked 256 days specifically because it's just beyond what brute force can handle. Part one's 80 days is a trap to make you think simulation works.

4. Check integer limits: JavaScript's safe integer range is large but not infinite. Know when you might overflow.

5. Refactor after solving: Once both parts work, extract the common logic. The final solution uses the same function for both parts, just with different day counts.

The full solution is available in the repository.