# Advent of Code 2021: Day 6

·

This blog post is sixth in the Advent of Code 2021 series and shows a JavaScript-based solution to the problem described in Day 6. The challenge was creating and optimizing an algorithm for calculating the lanternfish population after a number of days.

All solutions are in this GitHub repository.

## Solving Part One

We have an initial set of fish with given internal times until they multiply. According to the problem, after creating a new fish, each fish resets their internal time to 6 days since they need a week to make a new fish. A new fish starts with an internal time of 9 days until multiplying the first time. The challenge is to calculate the amount of fish after 80 days.

We can solve the problem with the following steps:

• update the state of each fish after a day
• repeat for 80 days and count fish

The input contains comma-separated numbers, which represent the state of each fish. We can use an array to store each fish as a number.

``````let fish = data.split(',').map((n) => Number(n))
``````

### Update the state of each fish after a day

Without considering new fish for now, after a day, each fish's internal time decreases by one until it reaches 0, at which point it resets to 6.

``````const newFishPopulation = fish.map((f) =>
{
if (f === 0) {
return 6
}
return f - 1
})
``````

We can count the amount of fish that reset to 6 and add that amount to the list of new fish population.

``````const getNewFishPopulation = (fish) => {
let newFishCount = 0
const newFishPopulation = fish.map((f) => {
if (f === 0) {
newFishCount++
return 6
}
return f - 1
})
newFishPopulation.push(...Array(newFishCount).fill(8))
return newFishPopulation
}
``````

### Repeat for 80 days and count fish

The challenge is to find the amount of fish after 80 days, so we can write a for loop which would update the fish array every day.

`````` for (let day = 1; day <= 80; day++) {
fish = getNewFishPopulation(fish)
}
return fish.length
``````

You can see the final solution for part one on my GitHub repository.

## Solving Part Two

Part two is about optimizing the algorithm to calculate the fish population after 256 days. The solution from part one is not efficient in terms of memory. It exceeds the maximum number of elements allowed in an array, thus throwing the following range error.

``````fish.push(...Array(newFishCount).fill(8))
^
RangeError: Maximum call stack size exceeded
``````

While thinking about this problem, it occurred to me that fish with the same state produces the same amount of ancestors. For example, two fishes left with three days until reproduction create the same amount of ancestors after 80 or any amount of days. Thus, it would be enough to keep track of the amount of fish in a given state each day. So I opted for an occurrence array with nine elements, where each index represents the state of days until reproduction and stores the amount of fish with that corresponding state.

We can break the problem like this:

• initialize occurrence array from input
• shift occurrence array one position
• add fish corresponding to state 6
• repeat for 256 days and count fish
``````import { URL, fileURLToPath } from 'url'

const sumFish = (occurenceArray) => {
return occurenceArray.reduce((sum, fishCount) => sum + fishCount, 0)
}

const solve = (data) => {
const fish = data.split(',').map((n) => Number(n))
const fishOccurence = Array(9).fill(0)

fish.forEach((f) => fishOccurence[f]++)

for (let day = 1; day <= 256; day++) {
const newFishCount = fishOccurence.shift()
fishOccurence[6] += newFishCount
fishOccurence.push(newFishCount)
}
return sumFish(fishOccurence)
}

const inputPath = fileURLToPath(new URL('./input.txt', import.meta.url))