I also used a stupidly simple solution for mine, and while I see how a matrix multiplication can “shift” and do the correct multiplication… all I think we need is the matrix

I think the post for some reason stops before it actually describes the matrix needed… and I think yours is, in fact, it. Your A is a permutation matrix (the permutation is a simple rotation) with one “1” added.

The thing that’s interesting about the post (although again it’s not really communicated clearly) is that given A you can compute A^80 or A^256 independent of the problem input, and you can accelerate that computation using exponentiation by squaring. Then you can do a single matrix multiplication to apply an 80-day evolution or a 256-day evolution to any given input condition.

In the case of this problem it doesn’t really buy anything, but it’s a technique that could be useful in some real-world scenario where you could precompute the matrix and reuse it on lots of inputs.

I went ahead and implemented the idea using your matrix (in Raku, as that’s my challenge for AoC this year; I already took a different approach yesterday), and it works: https://gist.github.com/arodland/9fb200941da85ddbc252d69e21c6ba39 given the input 3,4,3,1,2 prints 5934 and 26984457539.

It’s significantly slower than my previous solution, but that’s probably down to Math::Matrix not being optimized and not using the exponentiation trick. I’m not going to hand-roll my own just for this :)

I complete 256 iterations/days in 2.8μs without a matrix. I wonder if a matrix will make it faster for such a small iteration count.

https://github.com/timvisee/advent-of-code-2021/blob/master/day06b/src/main.rs

94 microseconds here using the matrix in rust. I think your way is faster for inputs in that range!

Thanks a lot for measuring!

I’m afraid I still don’t understand it.

I also used a stupidly simple solution for mine, and while I see how a matrix multiplication can “shift” and do the correct multiplication… all I think we need is the matrix

but I don’t see that here, and don’t understand how the described use of matrix math solves the problem.

I think the post for some reason stops before it actually describes the matrix needed… and I think yours is, in fact, it. Your A

isa permutation matrix (the permutation is a simple rotation) with one “1” added.The thing that’s interesting about the post (although again it’s not really communicated clearly) is that given A you can compute A^80 or A^256

independent of the problem input, and you can accelerate that computation using exponentiation by squaring. Then you can do asinglematrix multiplication to apply an 80-day evolution or a 256-day evolution to any given input condition.In the case of this problem it doesn’t really buy anything, but it’s a technique that could be useful in some real-world scenario where you could precompute the matrix and reuse it on lots of inputs.

I went ahead and implemented the idea using your matrix (in Raku, as that’s my challenge for AoC this year; I already took a different approach yesterday), and it works: https://gist.github.com/arodland/9fb200941da85ddbc252d69e21c6ba39 given the input

`3,4,3,1,2`

prints`5934`

and`26984457539`

.It’s significantly slower than my previous solution, but that’s probably down to Math::Matrix not being optimized and not using the exponentiation trick. I’m not going to hand-roll my own just for this :)