In yesterday's Advent of code puzzle (https://adventofcode.com/2021/day/6), we are asked to model a population of fish, and the model works like this (see link for more infos):
- Each fish is represented by a number
- The number decreases each day
- Once it reaches 0, on the next day, two things will happen: the fish number is reset to 6 (this means it will cycle every 7 days), and a new fish with a value of 8 is created. This means the first time a fish is born, it will take 9 days to generate a new fish.
Basically, a fish has a child every 7 days, and the new fish need 2 more days the first time they have a child.
I've managed to solve it programmatically, but I have yet to find a mathematical formula to solve this problem. To simplify the problem, I'm considering a single fish at the start, with a value of 0, and I'm trying to find a formula that gives the fish population every day, up to 256 days.
For reference, a fish starting at 0 on day 0 will produce a population of 1421 on day 80, and 6 703 087 164 on day 256.
Can anyone help creating this formula ?
EDIT: After Mike's answer, I've implemented the solution in R, if anyone is interested the code is below.
library(expm) # Exponents on matrices
options(scipen = 50) # Show all digits in final result
inp <- scan('aoc2021/day6.csv',0L,sep=',',quiet=T) # Read data
V0 <- c(0,table(inp), 0, 0, 0) # Compute frequencies of fish as first state and pad with 0
A <- matrix(0L, nrow = 9, ncol = 9) # Create empty matrix
diag(A[,2:9]) <- A[7,1] <- A[9,1] <- 1L # Fill 1 in matrix
sum((A %^% 256) %*% V0) # Sum of all fish after 256 days
The new solution is much faster than the old one (both are really fast).
Time to compute the number of fish after 256 days:
expression median
matrices 7.34µs
programming 99.62µs
(Expanding on Joppy's comment).
For each $t\in \mathbb N$ and $i\in \{0,\dots,8\}$, let $v_{t,i}$ be the number of fish with level $i$ at time $t$, and let $v_t=(v_{0,t},v_{1,t},\dots,v_{8,t})$. You can show that $v_{t+1}$ is determined from $v_t$ via matrix multiplication. Specifically, $$ v_{t+1}=Av_t,\qquad A=\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} $$ It follows by induction that that $$ v_t = A^t v_0, $$ giving a simple formula for the fish distribution at time $t$. If you like, this implies the number of fish at time $t$ is given by the formula ${\bf 1}^{\top}Av_t$, where ${\bf 1}$ is the column vector with nine ones.
If you further like, you could put this matrix in Jordon form, which should give a formula for the number of fish at time $t$ in the form $\sum_i p_i(t) (\lambda_i)^t$, where $\{\lambda_i\}_{i\in I}$ is the set of eigenvalues of $A$, and $p_i(t)$ are certain polynomials in $t$. However, in this case the eigenvalues are irrational, so this form is not well suited for exact integer computation. The previous formula is excellent for computation, since you can compute $A^t$ with only $O(\log t)$ matrix multiplications using exponentiation by squaring.