×

[–] 6 points7 points  (5 children)

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

[–] 2 points3 points  (2 children)

Would you mind explaining this a little more? Let's say I have a list of adapters shown in the example: [16 10 15 5 1 11 7 19 6 12 4]. Sorted, and with the appropriate beginning and ending: [0, 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, 22].

So I start with 0 jolts, and the number of ways of getting [0,-1,-2] jolts is: [1,0,0]. The gap to the next adapter is 1, so, the update is [1,1,0] for getting to [1,0,-1] jolts?

The next gap is 3, so the update to get to [4,3,2] jolts is [4,0,0] (Edit: this should be [1,0,0] I believe)? I'm sure I'm butchering this, but I'm hoping to get a better understanding of this idea. Thanks! Also, cheers to using Julia for this; I'm using AoC to learn Julia.

Edit: more questions. What are the 3x3 matrices that are being used to produce the updated vector? Are they some kind of localized adjacency matrix?

[–] 1 point2 points  (0 children)

Yea you basically have the idea right. Let me be more explicit in my explanation.

Let W[j] denote the number of ways to get to Joltage j. The first DP solution you could use is simply to set W[0]=1, W[j]=0 for j<0, and then use W[j]=W[j-1]+W[j-2]+W[j-3] to iterate up and compute the entire vector W. But what I was pointing out is that you only actually need the last three elements of this vector to update it. Specifically, we only need to store [W[J]; W[J-1]; W[J-2]], where J is the Joltage of the last adapter considered. To see how this works, start by considering the 3 possible gaps

Gap 1: W[J+1]=W[J]+W[J-1]+W[J-2]
Gap 2: W[J+1]=W[J]+W[J-1], W[J+1]=0
Gap 3: W[J+1]=W[J], W[J+2]=W[J+1]=0

So in terms of the leading three entries of W, this means we go from [W[J]; W[J-1]; W[J-2]] to...

Gap 1: [W[J]+W[J-1]+W[J-2]; W[J]; W[J-1]]
Gap 2: [W[J]+W[J-1]; 0; W[J]]
Gap 3: [W[J]; 0; 0]

Nicely all three of these are linear, so they can be represented by matrix multiplication by

Gap 1: [1 1 1; 1 0 0; 0 1 0]
Gap 2: [1 1 0; 0 0 0; 1 0 0]
Gap 3: [1 0 0; 0 0 0; 0 0 0]

When running in serial this representation is perhaps overkill, but one advantage is that the entire problem is a string of n matrix multiplications, which allows for the problem to be heavily parallelised, running in time O(log n) on O(n) processors. And yea, you can these matrices as the local adjacency matrices between the old top 3 Joltages and the new top 3 Joltages.

Ah, a fellow Julian, nice to see a man of culture :p If you have any questions about Julia or anything feel free to send me a message. Been working professionally with Julia for a few years and still keep finding little tricks to speed things up constantly, I find it a very fun language.

[–] 0 points1 point  (0 children)

You can express the number of ways to output a given joltage as a linear recurrence in terms of the previous 3 joltages. You can only output joltage n if you have an adapter with given rating and if you have the adapter you have as many ways as the sum of ways of n, n-1, n -2.

    a = 1 if 1 in data else 0
b = a + 1 if 2 in data else 0
c = a + b + 1 if 3 in data else 0
for i in range(4, max(data) + 1):
a, b, c = b, c, a + b + c if i in data else 0
return c


which is just multipling by [1 1 1; 1 0 0; 0 1 0]

Now if you are iterating through differences, you have 3 different cases. From joltage n if the next adapter is n + 1 the relation is above. If the next adapter is n + 2 you have 0 + n + n -1 way of expressing expressing n + 2 no way of n + 1 and you can carry n which is multiplying by [1 1 0; 0 0 0; 1 0 0] and if you go to n + 3 you have no way of expressing n + 1, and n + 2 and as many of expressing n + 3 as n

You can express any linear recurrence as a matrix multiplication and a closed form solution by finding its eigenvalues but I don't know how you can do that with branching other than inserting a relation for each possible number which will give us an n x n matrix. which has practically O(n3) complexity or sub-cubic with Coppersmith-Winograd

[–] 1 point2 points  (1 child)

I've been looking for someone else who did this! This is definitely the best way, or it would be if the inputs were more challenging.

• You can trivially parallelize it with a divide-and-conquer evaluation scheme (as you noted), but it's also a good strategy for serial execution if there were thousands of chargers, because you can use fast integer multiplication to get better than quadratic bit complexity.
• Fun fact: you can express part 1 as a matrix product too. It's worse than solving it the obvious way, but it's sort of nice that you can unify the two parts.

[–] 1 point2 points  (0 children)

Ah nice, I hadn't thought about the bit complexity point, but right you are. Much of my work is shoehorning problems into linear algebra, so I've become pretty good at doing so, even when it isn't so productive haha. Thankfully these Fibonacci-like problems are one where it is sorta useful in some cases, which is nice.

[–] 6 points7 points  (5 children)

algorithm for 1 milisecond execution time

• sort ascending (plus leading zero):
0,1,2,3,4,7,8,9,10,11,14,17,20,21,22,23,24,27,28...
• calculate diff of each two consecutive adapters:
1,1,1,1,3,1,1,1,1,3,3, 3,1,1,1,1,3,1,1,1...
• make groups of adjacent 1's and sum each separately:
4,4,4,4,2,4,3,2,4,2,4,3,2,2,2,4,4...
• calculate ways to arrange each group with f(n)=1+(n*(n-1)/2):
7,7,7,7,2,7,4,2,7,2,7,4,2,2,2,7,7...
• multiply all together: 323965.....

[–] 2 points3 points  (0 children)

Went through and checked all of the adapters for how many other adapters they could reach.Found that you would get one of three patterns (at least for my input). These each had a number of set combinations (multiplier). I would then ignore all other 1s.

3,3,2,1 = 7 combos

3,2,1 = 4 combos

2,1 = 2 combos

Count the number of times each pattern occurs and calculate: 7^x * 4^y * 2^z

[–] 2 points3 points  (0 children)

Just a remark, had there been groups of 5 or larger, your f(n) doesn't work. Next step of the actual sequence is 13.

[–] 0 points1 point  (0 children)

Did pretty much that (except I used the Tribonacci sequence explicitly) and it is indeed a ~0.1 ms solution…

[–] 0 points1 point  (0 children)

How do you get the row with 4s from the row with 1s?

[–] 0 points1 point  (0 children)

f(n)=1+(n*(n-1)/2)

How do you end up with the formula? Is that a hand created formula or is there a proof?

[–][deleted] 3 points4 points  (1 child)

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
• This means the only removable adapters are those with a gap of 1 on both sides
• There were no more than three removable adapters in a row (sequence of 5 consecutive values)

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.

[–][S] 1 point2 points  (0 children)

Hey, that's pretty neat :) You could even do more than 3 in a row by using the Tribbonacci Sequence I think!

https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Tribonacci_numbers

[–][deleted] 1 point2 points  (7 children)

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

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

[–] 0 points1 point  (4 children)

By using some abstract nonsense we can argue that analytically derived identities in one variable also apply to matrices, e. g. the given sum equals inv(1-X).

[–] 1 point2 points  (3 children)

That's not true. This identity only works for matrices with all eigenvalues less than 1. "Abstract nonsense" is generally not very useful in maths.

[–] 0 points1 point  (2 children)

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.

[–] 0 points1 point  (1 child)

Reference, for anyone interested.

[–] 0 points1 point  (0 children)

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

[–] 1 point2 points  (3 children)

So didnt anyone else think of binomial coefficients?

[–] 0 points1 point  (1 child)

thank god, someone else did i was going crazy with these overengineered solutions.

[–] 0 points1 point  (0 children)

Haha, indeed. All these involved answers:p none of the answers posted have them, as far as I could find with a short search.

[–] 0 points1 point  (0 children)

Would you mind explaining how this works in regards to this problem?

[–] 0 points1 point  (1 child)

Graphs processing as matrix operations has always been really cool to me.

This would probably be slower than DP, but more parallelize-able?

[–] 0 points1 point  (0 children)

Pretty sure that inverse can be calculated in O(log2 n) with a sufficient number of parallel processors. Then again, with a probably somewhat larger don't quote me on this though number of processors, the von Neumann series should also be directly evaluatable in O(log^2 n) here.

[–] 0 points1 point  (3 children)

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.

[–][S] 0 points1 point  (0 children)

Ah yes thanks, I actually dropped a zero row! D:

[–][S] 0 points1 point  (1 child)

I also believe this should always work, because the series we're summing here is finite -- A^n will be zero for n > the number of items in the list. So the series will always be finite in theory.

Additionally, the eigenvalues of the matrix are all zero in every case, because of how paths can't go back to themselves.

[–] 1 point2 points  (0 children)

I believe I see it now - a short sketch:

A^n != 0, A^(n+1) = 0 // By construction, for some n
B = I + A^1 + ... + A^n
(I - A)B = (I - A)(I + A^1 + ... + A^n) // (I - A) is automorph
(I - A)B = I + A^1 + ... + A^n - (A^1 + ... + A^(n+1))
(I - A)B = I - A^(n+1) => B = (I - A)^-1


Typically, we need A \in B_1(0) for that A^(n+1) term to converge to zero, here it is trivially satified. Sweet!

[–][deleted] 0 points1 point  (1 child)

I’ve been thinking about doing next year in Fortran, it’s be great if more problems could be solved with linear algebra!

[–][S] 1 point2 points  (0 children)

You might enjoy my write-up on 2018 Day 10 :D

https://blog.jle.im/entry/shifting-the-stars.html

[–] 0 points1 point  (2 children)

then A^2_ij contains the number of ways to reach j from i in two steps

Sorry if this is a stupid question, but it isn't obvious to me why this is the case. Could you elaborate, please?

[–] 2 points3 points  (1 child)

I'm not a math wiz by any means – especially when it comes to linear algebra, but think of it this way:

An adjacency matrix, by itself, tells you if two values in a graph are connected (i.e., if the row value and column value have a 1 where they cross, those values are directly connected in the graph). Connectedness is another way of saying that you can get between the two values in one step.

But, if you apply the adjacency matrix to itself (which, in linalg-ese, is done by multiplying), you get an adjacency matrix of the adjacency matrix, i.e., which pairs of values in the first matrix, not in the graph, are connected. You can think of this as the two values being connected by one step as before, but, since we're looking at an adjacency matrix (which, by definition, itself indicates which values are one step away), this squared matrix shows us which values are two steps away. And so on, and so on...

This is a known feature of adjacency matrices. I couldn't tell you exactly how it works, but if you know how to multiply matrices (or, at the very least, know a programming language that can!) then you can see for yourself.

[–] 0 points1 point  (0 children)

if you apply the adjacency matrix to itself (which, in linalg-ese, is done by multiplying), you get an adjacency matrix of the adjacency matrix

I know how matrix multiplication works but my linear algebra isn't strong enough that I understand a quarter of the magical things that it does, but this does sound like something reasonable that it would do.

Thanks so much!

[–] 0 points1 point  (0 children)

I came up with 1,2,4,7,14,28,... 7*2^(n-4) for the number of permutations.

[–] 0 points1 point  (0 children)

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 :)
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.reddit.com/r/adventofcode/comments/kabi91/2020_day_10_closedform_mathematical_solution/", "fetch_time": 1680260657000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-14/segments/1679296949598.87/warc/CC-MAIN-20230331082653-20230331112653-00662.warc.gz", "warc_record_offset": 1075908560, "warc_record_length": 30287, "token_count": 4404, "char_count": 15536, "score": 3.59375, "int_score": 4, "crawl": "CC-MAIN-2023-14", "snapshot_type": "latest", "language": "en", "language_score": 0.9140380620956421, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00021-of-00064.parquet"}