Day 6 was the first of the puzzles where the challenge was dealing with large numbers. It even says in the puzzle description that it's modelling exponential growth, with a doubling time of around 8 days.

## Part 1

For 80 days, its enough to model the population directly as a list of the fish ages. That's the same data structure as the input.

At each generation, two things happen. All the fish age, dropping their age by 1 (unless their age is 0, when it becomes 6 again). All the fish of age 0 produce a new fish of age 8. The new generation is formed by combing these two processes.

```
generation shoal = (age shoal) ++ (birth shoal)
age = map ageFish
ageFish 0 = 6
ageFish n = n - 1
birth = map (const 8) . filter (== 0)
```

I `iterate`

the `generation`

function to produce an infinite list of fish populations, then take the 80th day and count the fish.

```
part1 fish = length $ (iterate generation fish)!!80
```

## Part 2

Part 1 generates about 10⁵ fish, so that explicit approach is fine. Part 2 ends up generating about 10¹² fish, so we need another approach.

Rather than tracking each fish individually, I track groups of fish. The example in the puzzle description (after 18 days) can be described as in this table.

Age | Number of fish |
---|---|

0 | 3 |

1 | 5 |

2 | 3 |

3 | 2 |

4 | 2 |

5 | 1 |

6 | 5 |

7 | 1 |

8 | 4 |

Importantly, this table will only have at most 8 entries, as there are only 8 possible ages of fish. Generating a new generation is just creating a new 8-entry table.

I call this sort of table a `Shoal`

, and use the convenient `IntMap`

to store it. I build a shoal from a list of fish by sorting the list, grouping like elements, then converting them into the assoc list for `M.fromList`

.

Ageing a shoal has a wrinke, as both fish of age 0 and age 7 become fish of age 6. Birthing new fish is just finding the number of existing age 0 fish.

```
generation :: Shoal -> Shoal
generation shoal = M.union (age shoal) (birth shoal)
age :: Shoal -> Shoal
age shoal = M.insert 6 (was0 + was7) shoal'
where shoal' = M.mapKeys ageFish shoal
was0 = M.findWithDefault 0 0 shoal
was7 = M.findWithDefault 0 7 shoal
birth :: Shoal -> Shoal
birth shoal = M.singleton 8 parents
where parents = M.findWithDefault 0 0 shoal
mkShoal :: [Int] -> Shoal
mkShoal = M.fromList
. map (\g -> (head g, fromIntegral $ length g))
. group
. sort
```

Finding the population at a given generation is the same as before: `iterate`

to find all generations, `!!`

to pick out the one we want.

## Code

You can get the code from my locally-hosed Git repo, or from Gitlab.