Advent of code 2021: Day 6- 3 minutes read - 514 words
On the next day of Advent of Code 2021 there were two approaches to solving the problem. Brute force and ignorance, and stopping to think about it. After finding out that Haskell often forces me to having a think first on Day 4 and Day 5, I was looking forward to
This puzzle was all about lanternfish population - yes there was a submarine theme to this year!
- The input consists of a list of lanternfish and their age
- When a lanternfish is 6 days old, an offspring hatches
- An offspring takes 8 days to reproduce on the first cycle, every 6 days from thereon in
- The solution is the total population after 80 days
More on the problem here
My first thought on this problem was that this wasn’t something to solve using brute force. The puzzle text mentions “exponential”, so there was a fair chance that even if part 1 could be brute forced, part 2 was going to take a fair while using “ignorance”.
Looking at the beginning of the puzzle input
I quickly determined that there would be a lot of repetition. If I was going to calculate how many fish were 1,2,3,… days old, rather than calculating it for each and every fish, it would be a lot more efficient. Thankfully, the previous puzzle on Day 5 already taught me how to do a frequency list.
Note, this only works if there are no gaps in the list - but as it happens, the input is complete and leaves no gaps, so I didn’t worry about it.
Once I had my array, I made a function to “advance a day”:
Note, this only works if the array is at least 9 elements long (but I wrote a function to ensure that the array is always of length 9).
This then allowed me to recursively grow the lanternfish:
One gotcha I had was, that because I started my list at index 0, I didn’t have to do “grow” for the first generation. So when I calculated the solution for part 1:
and because the complexity was
O(n) - doing part 2 - where 256 days of growth were to be calculated, it only took a
Rest of the solution on GitHub
I’m really starting to enjoy trying to abstract away the problem and think the expressiveness in Haskell is helping me here and guiding me to a simpler solution.Tags functional haskell advent-of-code
If you'd like to find more of my writing, why not follow me on Twitter or Mastodon?