1. 10
  1. 2

    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

    1. 2

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

      1. 2

        Thanks a lot for measuring!

    2. 1

      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

      A = [
      [0 0 0 0 0 0 1 0 1]
      [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 0]
      [0 0 0 0 0 0 1 0 0]
      [0 0 0 0 0 0 0 1 0]
      ]
      

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

      1. 4

        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 :)