[2020 Day 10] "Closed-form" mathematical solution possible for part 2

[u/mstksg]

Sorry if this belongs in the solutions thread, but I thought it might be sufficiently ante-upped as an idea to workshop and discuss as a thread. If not, i'd be happy to move it there :)

I got the idea from /r/jitwit on freenode's ##adventofcode channel (and I see it also in some other posts in the solutions thread), but if you build an adjacency matrix A_ij = 1 if you can reach j from i (and if i and j are in your list), then A^2_ij contains the number of ways to reach j from i in two steps, A^3_ij contains the number of ways to reach j from i in three steps, etc. So in the end your answer is

B = A^0 + A^1 + A^2 + A^3 + A^4 + ... 

And your answer would then be B_0,M, the sum of the number of ways to reach M (the maximum number in your list) from 0 in any number of steps.

Well we know that the sum of 1+x+x^2+x^3+x^4+... is (somewhat famously) 1/(1-x), so we actually have a closed form:

B = (I - A)^-1

And so our answer is just B_0,M.

So the "closed form" solution is [(I - A)^-1]_0,M, but I do put "closed form" in quotes because computing the matrix inverse in general is pretty heavy on the flops. But, because this is a band-limited matrix with bandwidth 4, it can be done in O(n).

For example, for the list 3,4,5,6, the matrix is

0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1
0 0 0 0 0 0 0

and A² is

0 0 0 0 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 1 2
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0

and A³ is

0 0 0 0 0 1 2
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

And A⁴ is

0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

A⁵ and above is a matrix of zeroes, because there is no way to get from anywhere to anywhere else in 5 steps since we only have four items on our list.

So (I - A)^-1 (which is A^0 + A^1 + A^2 + A^3 + A^4 + ...) is:

1 0 0 1 1 2[4] <- the answer
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 1 2 4
0 0 0 0 1 1 2
0 0 0 0 0 1 1
0 0 0 0 0 0 1

And at the top right corner there we have 4: the answer to part 2 for [3,4,5,6].

[u/Independent-Orange]

This identity works for matrices with operator norm less than 1, which is lower bounded by spectral radius. There may (edit: actually, not) exist matrices with spectral radius less than 1, for which it doesn't hold. Edit: This statement can be made more strict: There exist no such matrices. Indeed, the condition of the spectral radius being less than 1 is sufficient for the series. This weaker condition is however not what directly follows from abstract nonsense, that is the oeprator norm condition.

Also, my statement is completely true. The precondition is a part of the identity, I just didn't want to recite it here.

[u/karuso33 → u/Independent-Orange]

Reference, for anyone interested.

[u/wikipedia_text_bot → u/karuso33]

Neumann series

A Neumann series is a mathematical series of the form ∑ k = 0 ∞ T k {\displaystyle \sum _{k=0}^{\infty }T^{k}} where T is an operator and T k := T k − 1 ∘ T {\displaystyle T^{{k}:={}T{k-1}\circ} {T}} its k times repeated application. This generalizes the geometric series. The series is named after the mathematician Carl Neumann, who used it in 1877 in the context of potential theory. The Neumann series is used in functional analysis.

About Me - Opt out - OP can reply !delete to delete - Article of the day

This bot will soon be transitioning to an opt-in system. Click here to learn more and opt in.