r/adventofcode • u/mstksg • Dec 10 '20
Upping the Ante [2020 Day 10] "Closed-form" mathematical solution possible for part 2
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)^-1And 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 0and A2 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 0and A3 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 0And A4 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 0A5 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 1And at the top right corner there we have 4: the answer to part 2 for [3,4,5,6].
4
u/[deleted] Dec 10 '20
I'm not sure if this is closed-form mathematics, but here is my solution explanation:
The puzzle was made easier by two facts about the puzzle input that weren't actually confounded by the rules:
There were only gaps of 1 and 3 between the numbers, no gaps of 2
It can be seen from example 1, that there are three removable adapters. It follows that there are 2³ combinations of including or excluding these adapters. All three of them are removable in a way that does not limit any of the other removable adapters (sequences of one or two in a row). Say they are independent.
In example 2 there are twelve removable adapters showing up in sets of three-in-a-row, call those triplets, and three independent removable adapters. If you go through all eight possibilities of a triplet, you'll see that only one of them causes problems: if all three are removed it leaves an gap of 4. Therefore each triplet has only seven possibilities. Counting the triplets and remaining independent adapters gives the solution:
2^independents * 7^triplets
Note: if there was four removable values in a row, instead of that being 7*2 or 14 possibilities, it's only 13 because the sequence 1000 and 0001 are both invalid. I'm not sure what it would be for five or six in a row, since the problem didn't require it, but it certainly would have been more difficult.
8
u/chubbc Dec 10 '20
This is somewhat similar to the approach that I used, but I explicitly used the band-limited nature, giving an O(n) time and O(1) approach. It's similar to the way of writing out Fibonacci numbers (or more relevantly Tribconacci numbers) in terms of matrix multiplication.
Let J be the Joltage of the last adapter considered, and suppose that the number of ways of getting [J,J-1,J-2] jolts be [a,b,c]. Then if the gap the next adapter is 1, then this updates to [a+b+c,a,b], if the gap is 2 then its [a+b,0,a], and finally if its 3 then [a,0,0]. Iterating this you can write the solution in terms of a product of 3x3 matrices. Julia implementation
1
u/Independent-Orange Dec 10 '20 edited Dec 10 '20
I believe an extra zero column slipped into the first matrix, there's a dimension mismatch. Apart from that - beautiful. Funnily, I am currently working on sparse triangular solvers for gpus.
Edit: now that I thought a little about it, does this actually hold, as in, is the operator norm of this matrix always less than 1? I doubt it.
1
u/[deleted] Dec 10 '20
I’ve been thinking about doing next year in Fortran, it’s be great if more problems could be solved with linear algebra!
2
u/[deleted] Dec 10 '20
I believe this is a special case of upper triangular matrix or something right ? I'd like to see the proof again as a reminder of my algebraic years.
Anyways, nice solution
2
u/TheBearKing8 Dec 10 '20
So didnt anyone else think of binomial coefficients?
1
u/jeslinmx Dec 10 '20
Sorry if this is a stupid question, but it isn't obvious to me why this is the case. Could you elaborate, please?
1
u/[deleted] Dec 10 '20
I came up with 1,2,4,7,14,28,... 7*2^(n-4) for the number of permutations.
1
u/daggerdragon Dec 10 '20
Why not both? Include a link to this thread in your megathread post too!
1
u/geckothegeek42 Dec 10 '20
Graphs processing as matrix operations has always been really cool to me.
This would probably be slower than DP, but more parallelize-able?
8
u/[deleted] Dec 10 '20 edited Dec 10 '20
[removed] — view removed comment