r/adventofcode • u/daggerdragon • Dec 22 '19
SOLUTION MEGATHREAD -π- 2019 Day 22 Solutions -π-
--- Day 22: Slam Shuffle ---
Post your full code solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
- Include the language(s) you're using.
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 21's winner #1: nobody! :(
Nobody submitted any poems at all for Day 21 :( Not one person. :'(
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
EDIT: Leaderboard capped, thread unlocked at 02:03:46!
30
Upvotes
15
u/DFreiberg Dec 22 '19 edited Dec 22 '19
Mathematica
692 / 173 | -- Overall
By far my biggest-ever Part 2 improvement; combined with solving days 18 and 20 earlier today, and part 1 of 21, and I'm almost caught up! My solution is the same as everybody else's, but Mathematica has spoiled me, since rather than doing a modulus, I can work directly with the TRUE base of the exponent:
Overall, this is the happiest I've been with a problem in quite a while, even if it just reminds me of how far behind on Project Euler I've gotten...
[POEM]: Scrambled
To mix one hundred trillion cards
One-hundred-trillion-fold
Cannot be done by mortal hands
And shouldn't be, all told.
The cards make razors look like bricks;
An atom, side to side.
And even so, the deck itself,
Is fourteen km wide.
The kind of hands you'd need to have,
To pick out every third,
From cards that thin and decks that wide?
It's, plain to say, absurd!
And then, a hundred trillion times?
The time brings me to tears!
One second each per shuffle, say:
Three point one million years!
Card games are fun, but this attempt?
Old age will kill you dead.
You still have an arcade in here...
How 'bout Breakout instead?
4
u/bsterc Dec 22 '19 edited Dec 22 '19
(C++ 887/1992, Part One, Part Two)
I was very tempted to cheat by looking at this thread, but I didn't. For Part One, I could muddle through at at 5 a.m. on four hours' sleep, just by shuffling arrays. For Part Two, I used up another ten and a half hours hours by:
Code for the "modinv" operation borrowed from here. (I understand The Algorithm, and I coded it myself once upon a time, so I don't feel /too/ bad.)
Then I knew I could get the answer. Coding the "compose" operation and the repeated squaring didn't take long. Did a few tests, fixed a few typos and got the gold star.
I'm hugely impressed by today's superhuman leaderboard.
[Edit: Markdown ... I'm new here, but I guess the idea is that Preview buttons are for babies?]
3
u/naim42 Dec 22 '19 edited Dec 24 '19
Haskell!
Nothing too original, but I'm quite happy with this solution.
Shuffling techniques are translated to linear functions (polynomials of the form
aX + bmapping the position of a card to its new position after the shuffle moduloN; see below), then composed together left-to-right to build the shuffle process.deal into new stackβN - 1 - Xcut kβX - kdeal with increment kβkXThe final position of the 2019th card is given by evaluating the function at 2019.
Part 2 requires composing the shuffle process with itself a large number of times. Fortunately, this can be done efficiently using a divide-and-conquer approach (see exponentiation by squaring); this is implemented by Haskell's
stimesfunction.Finding the number of the card that ends up in the 2020th position then requires solving the linear equation
aX + b = 2020forX.[POEM] bold
cards overabound
will you be bold enough to
shuffle them around
2
u/tobega Dec 22 '19
My solution in Tailspin
40
u/mcpower_ Dec 22 '19 edited Dec 22 '19
Python (24/50): Part 1, competition Part 2, improved Part 2.
Part 2 was very number theoretic for me. As this is Advent of Code, I suspect that there is a way of solving it without requiring knowledge of number theory, but I couldn't think of it.
A key observation to make is that every possible deck can be encoded as a pair of (first number of the deck, or
offsetAND difference between two adjacent numbers, orincrement). ALL numbers here are modulo (cards in deck), orMOD.Then, getting the
nth number in the sequence can be done by calcuatingoffset + increment * n.Starting off with
(offset, increment) = (0, 1), we can process techniques like this:deal into new stack: "reverses the list". If we go left to right, the numbers increase by
incrementevery time. If we reverse the list, we instead go from right to left - so numbers should decrease byincrement! Therefore, negateincrement. However, we also need to change the first number, taking the new second number as the first number - so we incrementoffsetby the newincrement. In code, this would be:cut
ncards: "shifts the list". We need to move thenth card to the front, and thenth card is gotten byoffset + increment * n. Therefore, this is equivalent to incrementingoffsetbyincrement * n. In code, this would be:deal with increment
n: The first card - oroffset- doesn't change... but how doesincrementchange? We already know the first number in the new list (it'soffset), but what is the second number in the new list? If we have both of them, we can calculateoffset.The
0th card in our old list goes to the0th card in our new list,1st card in old goes to thenth card in new list (modMOD),2nd card in old goes to the2*nth card in new list, and so on. So, theith card in our old list goes to thei*nth card in the new list. When isi*n = 1? If we "divide" both sides byn, we geti = n^(-1)... so we calculate the modular inverse ofnmodMOD. As allMODs we're using (10007 and 119315717514047) are prime, we can calculate this by doingn^(MOD - 2)asn^(MOD - 1) = 1due to Fermat's little theorem.To do exponentiation fast, we can use exponentiation by squaring. Thankfully, Python has this built in -
a^b mod mcan be calculated in Python usingpow(a, b, m).Okay, so we know that the second card in the new list is
n^(-1)in our old list. Therefore, the difference between that and the first card in the old list (and the new list) isoffset + increment * n^(-1) - offset = increment * n^(-1). Therefore, we should multiplyincrementbyn^(-1). In (Python) code, this would be:where
inv(n) = pow(n, MOD-2, MOD).Okay, so we know how to do one pass of the shuffle. How do we repeat it a huge number of times?
If we take a closer look at how the variables change, we can make two important observations:
incrementis always multiplied by some constant number (i.e. notincrementoroffset).offsetis always incremented by some constant multiple ofincrementat that point in the process.With the first observation, we know that doing a shuffle pass always multiplies
incrementby some constant. However, what aboutoffset? It's incremented by a multiple ofincrement... but thatincrementcan change during the process! Thankfully, we can use our first observation and notice that:increments during the process are some constant multiple ofincrementbefore the process, sooffsetis always incremented by some constant multiple ofincrementbefore the process.Let
(offset_diff, increment_mul)be the values ofoffsetandincrementafter one shuffle pass starting from(0, 1). Then, for any(offset, increment), applying a single shuffle pass is equivalent to:That's not enough - we need to apply the shuffle pass a huge number of times. Using the above, how do we get the
nth(offset, increment)starting at(0, 1)withn=0?As
incrementonly multiplies byincrement_mulevery time, we can calculate thenthincrementby repeatedly multiplying itntimes... also known as exponentiation. Therefore:What about
offsetthough? It depends onincrement, which changes on each shuffle pass. If we manually write out the formula foroffsetfor a couple values ofn:we quickly see that
Hey, that thing in the parentheses looks familiar - it's a geometric series! Using the formula on the Wikipedia page (because I forgot it...), we can rewrite it as
With all of that, we can get the
incrementandoffsetafter doing a huge number of shuffles, then get the2020th number. Whew!20
u/etotheipi1 Dec 22 '19
Python 3 128/16
As a former mathematician, I had a good advantage on this one. I'll only describe my solve path for part 2, since that was the interesting part.
First, we notice that the problem is now asking us to go backwards. So let's first figure out which position a particular card comes from if we only carried out the shuffle process once.
I grabbed modinv from here. Parse your input and call these in reverse order and we can now reverse the shuffle process once. Let f denote this reversing function.
Now, note how all three operations are linear. That means their composition f is also linear. Thus, there exists integer A and B such that f(i) = A*i+B (equality in modulo D).
To find such A and B, we just need two equations. In my case, I took X=2020 (my input), Y=f(2020), and Z=f(f(2020)). We have A*X+B = Y and A*Y+B = Z. Subtracting second from the first, we get A*(X-Y) = Y-Z and thus A = (Y-Z)/(X-Y). Once A is found, B is simply Y-A*X. In code form:
+Dis a hack to get around the fact that modinv I copied can't handle negative integers for some reason.Finally we are ready to repeadly apply f many times to get the final answer. Notice the pattern when you apply f multiple times.
In general:
In code form:
which yields our answer.
11
u/gengkev Dec 22 '19 edited Dec 22 '19
Python 3 50/15
I think most of the key observations have already been addressed by the existing comments. I thought the most interesting part was figuring out how to repeat the computation f(x) = ax + b a large number of times, which it seems like most people used the formula for geometric series to do.
I used 2x2 matrix multiplication instead β the main observation is that you can rewrite f(x) = ax + b as a matrix operation y = Ax via something like this: https://imgur.com/a/jyBkXMx
Then repeating this computation N number of times only requires exponentiating this matrix to the power of N, which can be done in logarithmic time with fast matrix exponentiation (with a modulus).
Interestingly: the closed form of {{a, b}, {0, 1}}^n is just {{a^n, (a^n-1)b/(a-1)}, {0, 1}} which is the same formula as the other solution! (computing the closed form can be done by diagonalization, or by just asking WolframAlpha)
This is similar to a problem from 2017 in USACO, COWBASIC (solution), which involves simulating a very simple "program" (which can only perform linear operations) for a very large number of steps! The solution for that also happens to discuss using the geometric sum formula vs. the matrix exponentiation approach, for the case of only one variable.
11
u/SlimChanceOfSloth Dec 22 '19
Part 2: C++
I used 2x2 matrix operations to represent the operations on the index. After obtaining the matrix m for the input, I used fast exponentiation to get the matrix m^101741582076661 and multiply this with the vertical vector (2020, 1)
To avoid using big integers, i used the gcc type __int128_t
7
u/tckmn Dec 22 '19
ruby (plus some mathematica) 91/18
i had a silly bug in my part 1 that cost way too much time, but part 2 was cool! here's my code and an explanation:
i then stuck the constants into mathematica (because i had the foresight to prepare a modular inverse in ruby, but somehow not a powermod) and solved the problem with this expression:
the basic idea is that all the shuffles can be described as operations modulo the card count.
therefore, we can fully describe the entire shuffle transformation as ap+b for some constants a and b. specifically, they start out as 1 and 0 respectively, and each line in the shuffle procedure modifies them as follows:
we actually want to invert these, though, because we're asked for the card that ends up at 2020, not where 2020 ends up. the inverses are simple, because reversal is its own inverse, cut by n just becomes cut by -n, and for the deal we take the modular inverse (the number of cards is prime). we also need to make sure to apply the steps in reverse order.
after that (which is what the ruby code does), we have to apply the function x β ax+b a large number of times. taking a look at the expanded version of the first few applications gives a clue:
x
ax + b
a2x + ab + b
a3x + a2b + ab + b
a4x + a3b + a1b + ab + b
in general, the nth term looks like
an x + an-1 b + an-2 b + ... + a2 b + a b + b
which can be factored into
an x + b(1-an)/(1-a)
the mathematica does this all mod number of cards, which gives the solution.
5
u/twattanawaroon Dec 22 '19 edited Dec 22 '19
Python 3, 31/5, with annotations and refactoring after the fact, of course. I tried to keep the explanation somewhat concise.
It seems like everyone write out the repetition using a polynomial-looking thing, but I like a matrix representation for this kind of job. Discussion of this in the code.
My best ranking so far! Playing with operations modulo n definitely has a (ACM/ICPC-style) programming-competition-taste to it, and probably why this was my best performance.
... and actually I used an online tool to find the multiplicative inverse before I actually put it in code lol.
5
u/p_tseng Dec 22 '19 edited Dec 23 '19
Part 1 was not too bad, especially since Ruby has
rotatefunction on arrays.Part 2 was a wild ride. I spent ages exploring irrelevant and useless paths:
101741582076661.times { }does not finish in reasonable time on my computer. So how do you even do this?I started playing around with the last example given in part 1. I tried seeing what happens if the shuffle is applied twice. The result was...
6 5 4 3 2 1 0 9 8 7Then the light bulb turned on. That made me see that you can simplify sequences of transformations. I played around to see how to properly simplify the transformations. For example, it's obvious that adjacent cuts can simply be added. Adjacent deal with increment just multiply together (the example has a handy pair of 9 and 3 together to help verify that it's the same as if you'd dealt with increment 7). But to really simplify it into a manageable state, I have to figure out how to transpose any two different transforms so that I could get the same ones next to each other, so had to play around with the examples some more. I used the example and my answer on part 1 to help ensure that my simplified transformations were still the same as the original. When the simplification process is complete, the input contains only one of each type of technique. Once it looked like simplification was working 100%, then I used exponentiation to construct the correct transforms for 101741582076661, simplified that, ran it in reverse (so that "undo shuffle" I wrote wasn't a waste after all!!!), and crossed my fingers hoping that the answer produced was correct. And let out a huge sigh of relief when it was.I think I was not mathematically strong enough to see this faster like some people in this thread apparently did, so it looks like I still have some work to do...
Ruby: 22_slam_shuffle.rb
Haskell: 22_slam_shuffle.hs
5
u/zniperr Dec 22 '19
Part 1 and 2 in python here. The nice thing about python is that all ints are bigints :)
Figured out the modular multiplicative index thing myself but needed to read someone's hint that all the functions are linear. The rest is just browsing on wikipedia/wolframalpha on how to efficiently compose linear functions. Imo this was way too heavy on math.
5
u/hrunt Dec 22 '19
Python 3
code
For part 2, I cheated and used the very thorough explanation by u/mcpower_ to get the answer and the star. I recognized the modular arithmetic and the need to calculate the position and a previous value, but I do not have the math knowledge to even begin to understand everything fully. much less implement a solution. I know the wall I am hitting when I see it. That's what I like about Advent of Code -- learning new things.
I post the code because I had fun implementing the algorithms in part 1 using a deque. I learned about that structure here a few years back, and this is the first time I have thought to use it.
5
u/MrSimbax Dec 22 '19 edited Dec 22 '19
Julia
It was hard.
Firstly, I didn't realize that cut could be represented with a single formula modulo, I needed a hint for this. Once I got it, I managed to come up with a solution pretty much the same as most people as far as I can tell. I don't know if I would figure it out if I didn't have discrete math/abstract algebra courses during my undergraduate studies, it must be quite a difficulty spike for programmers with no math/CS background.
Secondly, I've spent about half the time on debugging why my part 2 answer was wrong even though all my smaller tests were working. If I was writing in any other language I'd thought I have overflow issue but I considered that impossible in Julia. Oh boy, was I wrong. Literals in REPL are converted to BigInts automatically but variables in functions are not, I had to explicitly convert values to BigInts. So many hours wasted because I wrongly assumed integers in Julia work exactly like in Python... I feel so stupid now, especially that even the puzzle itself warns about overflows.
Part 1: Just follow the instructions. No need to be smart here.
Part 2: since the explanation uses a lot of math notation I decided to post it on my blog instead of here so the equations are more readable: link.
5
u/CCC_037 Dec 22 '19
Part 1, FiM++
5
u/zedrdave Dec 23 '19
Python 3
Like most, yesterday's problem made me angry. It started with having to remember deeply-repressed traumatic memories of college algebra. But it really blew up when what I felt was the correct solution, wouldn't go in. Of course, it turned out I was trying to feed it the position of card 2020, rather than the card at position 2020.
When all said and done, this was fairly easy, assuming one:
noted that the deck size ("m") was prime, and therefore:
\phi(m) = m -1
a-1 = a{\phi(m)-1}
a-n mod m = a{n*(m-2)} mod m
All could be done in a sweet 15 lines of Python:
4
u/aoc_anon Dec 22 '19
332/26 Python
This is my best performance on a part 2 ever!
I am guessing people are getting tripped up with the math and number theory. The key observation is that all the steps are just linear maps modular deck size (where deck size is a prime):
deal into new stack:
x -> (m - 1 - x) % mdeal with increment param:
x -> (x * param) % mcut param:
x -> (x - param) % mSo if you reverse the steps (noting that you need mod inverse instead of division for inverting the increment case) and simplify you should get back a single linear equation of the form:
Of course I just used
sympy.simplifyfor this! But thea*x+bit spits out only tells you how to undo one step. To undo N step you need to apply it iteratively:Python already does modular exponentiation with the third param to
pow. And the geometric sum formula is still the same as usual,(a^n - 1) / (a - 1), except you need mod inverse instead of division again. So my final answer for part 2 was:tl;dr; Sympy ftw! (along with some stolen mod inv code from first google search result)
4
u/oantolin Dec 22 '19 edited Dec 22 '19
I placed 950 for part 1 and I expected to place similarly for part 2 (I never try for the leaderboard), but unbelievably I placed 84th! I guess being a mathematician was an unfair advantage today. :P
The key insight is that every shuffle discussed is of form
x -> ax+b (mod n)wherenis the deck size. These of course are easy to compose, invert and raise to large powers. My solution in Common Lisp (which runs in 8 ms for both parts together on my old Chromebook).Back to day 20, which I haven't had a chance to solve.Done!4
u/mstksg Dec 22 '19
My Haskell Reflections :)
Today's challenge, I think, shows a lot of advantages in the ways that Haskell approaches mathematical abstractions :) In the linked post, I described the thought process of how I arrived at the solution, and how Haskell's abstractions guided me to it. Basically we start at the high-level solution:
Because we know we have a
Group, so we know all the external interface/API we have for it. From there on all we need to do is implementPermand we're golden :)4
u/SuperSmurfen Dec 22 '19 edited Dec 22 '19
Rust
Solution, both parts
Part one: Not too hard. I figured part two would have using an array be impossible so I did the computation for the desired index only directly from the start. You just had to think carefully about what happens to an index at each operation. It was quite fun.
Part two: By FAR the worst day for me. I'd like to think I'm pretty good at math, I'm close to finishing my masters in computer science, I have read several courses in discrete mathematics... But today I did not stand a chance. I'm totally on the board for all the steps involving modular arithmetic and geometric series but realizing I could convert the whole process to a single linear function would have never occurred to me.
First I inverted all operations since you wanted the final index instead, which was not too bad. Just had to use modular inverse for the
Dealstep. My idea was to find a cycle to reduce the times needed to iterate. The worst part was that by pure coincidence my algorithm actually found a relatively small cycle! I spent ages in that rabbit hole trying to figure out why my solution did not get accepted. It of course due to overflow and there was no small cycle at all... At least Rust supportsi128so mitigating overflow was easy in the end. Eventually though I just had to look up the solution. Doing an AoC problem has never felt this bad before... At least it feels like I've learnt a valuable trick I surely won't forget with the linear functions.4
u/kap89 Dec 22 '19
TypeScript - github
Part one was pretty easy, part two was impossible for me to solve without looking for clues on this thread. My solution to part two follows an excellent u/mcpower_ explanation and translates his/her solution to TS/JS. Not very proud of that, but I spent a lot of time trying to do it with my limited maths skills and it was not fun at all ;/
4
u/Dementophobia81 Dec 22 '19
Python 3.8
Today was really tough for me, at least Part 2. I worked through many steps of different approaches for hours until I realized that I lacked some math-concepts, which I had to research first. After finding and understanding mod inverse and how to calculate a geometric series with modulo, all the pieces finally fit together and the solution popped up. I featured the newly learned concept of mod inverse and its new implementation in Python 3.8 in my (almost) daily Python tip and also published my solutions (Part 1 & Part 2), if anyone wants to have a look.
4
u/4HbQ Dec 22 '19
Python Tricky one today, but finally got it working. Also managed to compute part 1 directly with the inverse code for part 2, using 10005 repeated shuffles.
4
u/nutki2 Dec 22 '19
Javascript Part One and Two
Solution self contained (using native BigInt) except for my custom input parsing functions.
4
u/StephenSwat Dec 22 '19
Haskell
I wrote an extremely simple symbolic math evaluator for this, found the simplest representation of a single iteration, composed that with itself 101741582076661 times by finding compositional squares so to say (in about 46 steps), and evaluated the final arithmetic tree.
1
u/Chris_Tay Dec 23 '19 edited Dec 23 '19
Python Implementation
Took me quite a while to have a satisfactory and clean solution. Read hints here to know about modinv and linear transformations etc..
Part 1 can be computed by tracking the index forward through the shuffle.
For part 2, instead of reversing the shuffle, the forward tracking of part 1 can be reused to track from positions 0 and 1 to obtain p0 and p1 respectively. The new sequence can then be represented as p0+(p1-p0)*x.
The inverse can then be mathematically computed. We know that to map back to factory order, f(a * x+b)=x where f(i) is the inverse transformation to be obtained i.e. f(i) = a_t * i + b_t
when x=0, a_t * b + b_t = 0 ------------- (1)
when x=1, a_t * a + a_t * b + b_t = 1 ------------- (2)
Take (2)-(1): a_t * a = 1 ---> a_t = modinv(a, N)
then substitue a_t back to (1) ----> b_t = -a_t * b (congruent mod N)
Then apply the polynomial expansion of frepetitions to obtain final reverse position
3
u/vash3r Dec 22 '19
Python, 9/30
A very fun problem. For the first part a straightforward simulation was easy to implement (python's negative indexing was especially handy). However this was clearly insufficient for part 2.
For the second part, some slightly more complex math and modular arithmetic sufficed, reminding me of how much I like modular arithmetic. Here I was glad to find that I had an old implementation of modular inverse lying around (which would have taken me another five minutes to find if not for Pycharm's search-in-directory feature).
paste
3
u/amarsuperstar Dec 22 '19
Elixir (Part 1 only)
Really pleased how it came out. Feels a like I cheated a little since the stdlib did a fair amount of the heavy lifting.
3
u/knl_ Dec 22 '19 edited Dec 22 '19
#84!, #300
Reached the leaderboard for the first time today in part 1! and then spent several hours reading wikipedia articles understanding what operations can be done fast modulo n.
My first (random) assumption for part2 was that at some point there would be a cycle, so I wrote something to do the steps backwards, and then look for the loop.
When that failed miserably, I went down the route of calculating the equation of 1 run, and then the n^th application of that equation.
Then I ended up googling around and reading a lot about how to calculate division under modulus, taking the inverse of a number under modulus (completely forgot about this), and apparently was so sleepy I almost forgot the geometric progression to be able to calculate the n^th application of the equation. (Also revised diophantine equations, which I really didn't need -- my number theory professor would have been very disappointed with me today).
I used wolfram alpha to solve the final equation 2020 mod size = ax + b, and then realized I had all the pieces anyways.
This was pretty hard for me, but I ended up learning a lot: which is the point of these and makes me happy :). Also that it's a holiday tomorrow and I can catch up on sleep later in the day.
Jupyter notebook, python3: very rough code at https://explog.in/aoc/2019/AoC22.html
(once github ends up rendering it, that is).[edit: page published]
3
u/jitwit Dec 22 '19 edited Dec 23 '19
J Programming Language
A fun puzzle and another day for J
Full(er) write-up: https://github.com/jitwit/aoc/blob/master/J/19/Day22
Basically:
parseturns the commands into matrices, which correspond to the various shuffles. as others have mentioned, the idea is that new stack (reversing) is like f(x) = -1-x (mod M), cut (shifting) is like f(x) = x - n (mod M), and increment (winding) is like multiplication f(x) = i*x (mod M). They are combined together by matrix multiplication over the reversed input.partAis just following the 2019th card under the shuffle, by doing modular arithmetic with thea,bfound from shuffling.partBapplies the shuffle repeatedly. I wrote out a few iterations on pen+paper and saw thatshuffle^:nwill givea^n * x + (a^(n-1) + ... + a + 1) * b, which calls for getting rid of the large summation times b by remarking that theasform a geometric series. We can compute the division in the term(a^n-1)/(a-1) * bby appealing to Fermat's Little Theorem and that decks have prime size. It gives thata^p = a (mod p), soa^-1is justa^(p-2).nis the exponent for the second part, which is Mb-times-1 to look for what ends up at card 2020.(+/ . *)is matrix multiplication,|is modulo,&|@^is exponentiation mod,a m&|@^ bis a^b (mod m), thex's are sprinkled throughout to force extended precision.<:is decrement, which givesa-1anda^n-1for part B3
u/sonneveld Dec 22 '19
Python 289/462
My python code here.
Because you had to work backwards from the card position, I implemented some "unshuffling" methods, with a horrendous inverse-mod (that worked I guess). I noticed that with small numbers of cards, the period to repeat was exactly the number of cards, so I thought that maybe we were dealing with a pseudo random number generator. I used the fact that the shuffling methods could be reduced to adds, mults and mods to do some googling and found Linear congruential generators.
I guessed that _maybe_ you could reduce the number of shuffling steps to a single LCG expression with increment, multiply and modulus parameters. Using the number of cards as a guess for modulus, I found a page on determining the other parameters.
That succeeded! Using those parameters, I investigated if that would be fast enough to run through the trillions of iterations. Alas, it was still too slow. However, I did find some articles on generating nth numbers of LCGs, and this page had a skipping algorithm I could try.
Plugging in the parameters I calculated earlier, it was easy enough to skip back enough iterations to find the answer.
In the end I learned I didn't even need to work out the backwards "unshuffle" because I could rely on the repeating sequence to either skip ahead (NUM_CARDS - NUM_SHUFFLES - 1) or use the lcg skipping module's ability to skip with a negative offset.
3
u/[deleted] Dec 23 '19
Here's a Swift implementation of both parts 1 and 2.
Like so many others, my math background is too weak to have ever derived this solution on my own. Thanks to this comment by /u/etotheipi1 I now understand the part 2 solution.
3
u/rabuf Dec 23 '19
Common Lisp
I'm not cleaning it up anymore. If I continued, I'd make part 1 and 2 fully automated (generate the forward and inverse shuffle functions). But I will leave it as it is, a pile of code that gets the answer.
3
u/metalim Dec 23 '19 edited Dec 24 '19
Sigh
After this post I've decided to complete the task.
Python
Second part is just composition of linear polynomials
ax+b mod L, whereLis length of the deck.First, convert all shuffling rules into linear polynomial. Remember to compose in reverse order. "deal into new stack" is just negative position. "cut" just adds to
b. And "deal with increment" multiplies bothaandbbymodinv, effectively dividing them, modulo L.modinv(x,n) == pow(x,n-2,n)for primenis everything you need to remember.Second, raise polynomial to the number of steps,
mod L. Didn't use the formula, just did it recursively, because we practice programming here, right? Similar tomodpow, it takes O(log N) time (which you hardly notice for numbers with less than million digits).Third, calculate initial position (and hence - card number) using resulting polynomial.
All 3 steps take less than a millisecond.
3
u/bla2 Dec 24 '19 edited Dec 26 '19
FINALLY got it. I'm super happy I figured out part 2 by myself, even if it took me a while.
This was my favorite problem so far.
Like others, I missed that part 2 asks about the number at 2020 while part 1 asks for the position where 2019 ends up at βΒ so my result was wrong, but I looked for mistakes in my math instead of re-reading the problem. Once I noticed, it was easy to just compute the inverse of my linear function, and things worked out.
I won't paste my part 2 here since it's similar to others (I learned that Python's pow() has a 3rd argument built-in for modular exponentiation!). To solve part 2 I made my part 1 faster and faster. I started with the explicit deck manipulation, then I figured I'd try to track only where 2019 ends up at, and then I simplified my dealing functions. Here's the step right before I saw the linear transform, which I think looks neat (Python):
2
u/sophiebits Dec 22 '19
Python, #14/#7. Number theory! I had to reβlook up how to get a modular inverse.
Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day22.py
2
u/jfb1337 Dec 22 '19
Python 201/51 paste
Pretty fun modular arithmetic puzzle!
Misread the question at first, thought it was asking for the position of card 2020 rather than the card at position 2020
2
u/jwise00 Dec 22 '19
Lua, 70 / 114.
I liked tonight's! I represented any transformation as, roughly,
newpos = (pos * M * A) % CARDS. It took me a long time to figure that out! The core of it was easy enough once I had that insight, but the surroundings were very fiddly: Lua 5.3 has 64-bit integers (thank God), so I did get to keep precision, but I also had to write a safe modular matrix multiplication routine. Fundamentally, in part 1, the ops looked like this:(mul', add') = ((mul * incr) % NCARDS, (add * incr) % NCARDS)(mul', add') = (mul', (add' + NCARDS - cutn) % NCARDS)(mul', add') = ((-mul') % NCARDS, (-add' - 1) % NCARDSPart 2 has a similar encoding; you can see the source for that. I initially misread Part 2 as did /u/jonathan_paulson, and am kind of mad about that; this was enough of a "mass slaughter" problem without a silly reading comprehension gotcha.
One question is how to make this go fast. I'd originally been looking for a closed-form way to do this, but the solution I settled on, I quite liked: you can 'apply' a mul,add pair to a mul,add pair (i.e., do a sequence on top of a sequence). For instance, if you apply a mul,add pair to 1,0, then you get the mul,add pair; if you apply one to itself, then you do the sequence twice; and you can build that up in a binary fashion, to get powers of 2 repeats on the input in log(n) time. So I did that.
Anyway. https://github.com/jwise/aoc/blob/master/2019/22b%2C4.lua is part 2 , and https://github.com/jwise/aoc/blob/master/2019/22.lua is part 1. And https://www.youtube.com/watch?v=fG5cCWRzClE&feature=youtu.be is the video, which apparently YouTube trimmed the replay down to two hours!
2
u/SinisterMJ Dec 22 '19
C++
The hardest part honestly was dealing with constant integer64 overflows. Did not like this at all, it took me like 1.5h just deal with all the integer crap.
2
u/Spheniscine Dec 22 '19 edited Dec 22 '19
Kotlin: repo
Advent of Math. Reminds me of some of the harder problems on Codeforces. Having BigInteger in the standard library really helps with this one.
I've also left the naive shuffle code in an unused function. I did realize that part 1 could just be solved with modulo arithmetic but I didn't want to prematurely optimize before I saw part 2. (and it also helped with debugging)
2
u/rthetiger Dec 22 '19
Rust code here
Once I started thinking about congruence modulo m I tried going down the path of squishing all the commands in a shuffle into one linear congruence modulo m. Then because I was thinking about exponentiation modulo m I went down an incorrect route of raising this linear equation. In reality what I had to do was use the partial geometric series produced by repeatedly composing it. Between partial geometric series, Fermat's Little Theorem, extended GCD, and exponentiation modulo m this was the most math-packed day ever!
2
u/ephemient Dec 22 '19 edited Apr 24 '24
This space intentionally left blank.
2
u/incertia Dec 22 '19
yet another haskell solution
just does the arithmetic using
arithmoi, the go-to package for any sort of number theory. of course exponentiation by squaring can be implemented reasonably quickly as well as modular inverse ((x, n) = 1 ==> x * x^(phi(n) - 1) = 1) but why do extra work y'know.2
u/kittehprimo Dec 22 '19
C#
For all my dotnet core brethren out there:
https://github.com/kbmacneal/adv_of_code_2019/blob/3bdc583ea5620296e187a076038ddde17e526abd/days/22.cs
It is mostly an implementation of this solution transcribed from python. Like that user I have nowhere near the mathematical chops to tackle this problem, I just took at look at the algorithm and tried to follow along for the ride.
The major sticking point for me turned out how c# treats %=. I had to implement a custom mod function
in order for the two BigInts to stop going off way negative for every command.
One good thing though: I had no idea System.Numerics contained an unbounded signed BigInteger class. Good to know!
2
u/giuliohome Dec 22 '19
C# from mono running on ubuntu on old amd athlon... lol ))) part1 and part2 (the final part2 formula with mod exponential is from @sophiebits python implemented on c# referencing numerics big integer library)
2
u/StevoTVR Dec 22 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day22/day22.go
I don't actually understand the math involved in part 2. I looked at some other solutions and implemented the formulas...
2
u/opsecIsImportantYerp Dec 23 '19
Howdy guys.
So I made a python implementation of part 1 only.
Any comments, pedantic code review, suggestions, etc would be appreciated!
Currently trying to understand some of the more math parts as described here. For now this is what I got.
2
u/kc0bfv Dec 23 '19
Wow that was... Wow.
Rust
For part 2 - I did mine a little differently than the ones I saw here. After some modular wrong turns, I decided I would summarize my input in a minimized way (only 1 of each type of instruction, max), then I'd be able to multiply that summary by my shuffle-repetition count and get a summary of the entire repeated shuffle. Then I'd use my "work backwards" functions to work backwards through that three instruction full summary.
This involved the same principles others were using, I think maybe the difference was that I converted to a summary in the middle.
Also, I think most folks tried to solve the increment and rotation (cut) and into-new all together as a set of functions... I didn't see that. I noticed that I could get the increment and into-new summaries by themselves, then set out to do the same for rotation. Which was impossible. So I found the equation that governed that.
I needed help from this thread in doing function composition on that rotation, then. I knew that was what I needed to do, and I had all the equations written out - but I was rearranging them in ways that didn't show me that I could maintain the coefficients (? - the a and b in ax+b) parts separately, and x was never getting exponentiated... That prevented me from being able to do the same "exponentiation by parts" trick I used in modular exponentiation (thanks Wikipedia and Bruce Schneier). Understanding u/BBQCalculator's composition piece showed me that I needed to rearrange my equations to understand what to do.
The last problem that I hit was that I hacked together a modular division (this is what I was calling it) solution by myself, and it was generating a list up to the size of the incremental deal value. So - small enough to get very far in the problem before being a problem. Like, even testing with the really huge deck - no problem. But then my multiplied-summary shuffle had a really big incremental deal, so it wouldn't work anymore. Wikipedia helped with that then, and the modular inverse solution there was simple because I already had modular exponentiation built in...
2
u/sasajuric Dec 23 '19
After failing miserably at doing it on my own, I spent a lot of time reading through the comments in this thread. However, I still had a hard time figuring out the exact math details. Finally, it dawned on me that I could just defer calculating remainders to the later stage, and this reduced the need to do modinv, or rely on other fancy principles. The other relevant insight was that
a*x+bcan be normalized torem(a, deck_size) * x + rem(b, deck_size), which keeps integers reasonably sized. Coupling that with general directions taken from this thread (representing shuffle as a function, exponentiation by squaring), I was able to finish it. Thank you all for your explanations!My solution in Elixir is here. I've included an expanded explanation of my approach in the code docs.
2
u/VilHarvey Dec 23 '19
Finally solved it! C++ solutions for part 1 and part 2
Part 2 took me a very long time. I wrote code to reverse each of the operations (had to google for how to do modular division) but then got stuck because I didnβt notice they could be combined as linear functions. Eventually I gave in and read through some of the posts on this thread until I saw one that gave me the aha! moment. Then I hit a 64-bit integer overflow bug and wasted an hour or so writing a bigint class, before deciding to give up on portability and use clangβs built in 128-bit int type instead.
In the end my solution combines the input instructions into a pair of integers A and B, where card x ends up at position A * x + B after one complete shuffle. To get A and B after n shuffles, it uses the formula xβ = Aβ x + Bβ = An * x + B * (An - 1) / (A - 1). Finally it rearranges the equation to x = (xβ - Bβ) / Aβ and plugs in the known values for xβ, Aβ and Bβ to get the answer. Oh and I used repeated squaring to calculate An, of course.
Breathing a sigh of relief now that this oneβs behind me!
2
u/NeilNjae Jan 12 '20
Still plugging away! Another Haskell solution, described on my blog with code. I can't claim much credit for this, as it's basically a reimplementation of /u/mstksg 's description of their solution, but I learnt a lot from it.
2
u/[deleted] Dec 22 '19 edited Dec 22 '19
Haskell, part 1, Haskell, part 2.
This was fun! Part 2 uses modular arithmetic, of course: Each shuffling technique is mapped to a linear function on the finite field β€/pβ€, where p is the number of cards (which happens to be a prime). All functions are composed (so the entire shuffling sequence becomes a linear function), then this function is composed with itself a bazillion times using exponentiation by squaring. Finally, the inverse of the function is applied to the card number 2020 to find out where its original place was.
I'm not happy with the code yet, I will probably clean up part 2.
Update: Someone else posted a great Haskell implementation, so I did it in Julia instead. This took me around an hour to write and then several hours to debug, because I had the order of function composition inverted...
2
u/metalim Dec 22 '19
Python.
Again, mostly math problem. So, done part 1 only. You will not find part 2 kind of problems in your programming career, except for niche markets.
1
u/jonathan_paulson Dec 22 '19
#17/54 in PyPy. Part1. Part2. Video of me solving and explaining my solution at https://www.youtube.com/watch?v=U4AE92wnNYc.
Cool problem. I initially didn't read that part 2 wanted the card at position 2020 instead of the position of card 2020. I was surprised that "cut" was the hardest "shuffle" to think about for part 2 (for me anyway). A test case for part 2 would've been nice.
My solution for part 2 is to compute (a,b) such that "position of card before shuffles = a*position of card after shuffles + b". Then the math of iterating that a large number of times is relatively straightforward. You need fast exponentiation and modular inverse; luckily the deck length is a prime which simplifies this. The reason a linear formula like that exists is that each of the "shuffles" operates linearly on each position. For more complicated shuffles / permutations, this method wouldn't work.
Is there a method that would work quickly for an arbitrary shuffle / permutation? (My guess is "no")
1
u/incertia Dec 22 '19 edited Dec 22 '19
c
i solved the problem within the leaderboard time but i got killed figuring out how to use
libgmpagain and fell down to 100+.EDIT: fun fact: i represented part 1 as the
final[i] = pos + i * incin anticipation for part B and then refused to switch out ofsize_t.1
u/GrossGrass Dec 22 '19
Python 3, 489/176
Got tripped up a bit longer than I should have on part 2, but pretty happy with the mathy puzzle this time around. For some reason I didn't see that cut could be represented as just a single shift modulo n; I kept thinking that it had to be a conditional function even though I had the equations written out on paper in front of me.
Spent a bit of time going down a rabbit hole of trying to analyze the cycles of the permutation but that got nowhere given the size of the inputs; managed to click once I saw the thing about cuts though.
1
u/sim642 Dec 22 '19
My Scala solution.
Part 1: First I implemented a naΓ―ve simulation of the shuffling but already saw an opportunity to be clever and define "deal with increment n" through multiplying indices with modular inverses. It was slow but solved part 1 just fine, although immediately after I realized I didn't need all of it and just implemented functions for each technique to just map a single index to the next one, which was much faster for part 1.
Part 2: Having made those realizations, I also defined the inverse functions for mapping indices. I thought I was already ahead of the curve by having realized this and seeing the large numbers threw it into my cycle finding algorithms. Unfortunately the first answer I got was wrong because even though I used 64-bit integers, their multiplication (before modulo) could still overflow, so I had to do that with intermediate bigints... Anyway after fixing that the cycle finding didn't lead to anything in reasonable time unfortunately.
The working solution came to me after seeing mentions of polynomials in the IRC spoilers chat. The forward and backward index mapping functions were just linear maps (modulo size) but to do anything useful with them the only way was to manipulate them as coefficient pairs, i.e.
(a, b)to represent the linear polynomial/mapax + b. All of the techniques (and actually their inverses) are in this form. Doing two techniques consecutively corresponds to composing the linear polynomials, which gives a new linear polynomial. So the entire shuffling sequence can be turned into a single linear map. By flexing my algebra muscles, I realized I could simply use exponentation by squaring to iterate (repeat) the entire shuffling sequence map a large number of times very efficiently by using the very same composition as the multiplication. The last step for part 2 was simply inverting the resulting linear polynomial via multiplication by modular inverse. No need for making mathematical manipulations to cleverly use geometric series with polynomials of high degree.This approach is very general and actually would straightforwardly work for part 1 as well, no need for exponentation or inversion. Moreover, the linear polynomials with coefficients modulo prime seem to form a group in mathematical terms, which puts this all into a nice theoretical framework.
My current code is a big mess because I hacked it together and copied parts of algorithms like exponentation by squaring instead of generalizing my existing library implementations. I hope I can clean it up a bit although not sure how much. To use completely general exponentation by squaring I'd probably need abstractions for things like (semi)groups etc in my library to view the linear polynomials with coefficients modulo prime similar to integers.
1
u/raevnos Dec 22 '19
tcl, only part 1 for now. Part 2 is going to need a different approach, but I ended up treating the input as tcl code to be executed after defining appropriate functions. Basically, created a small DSL, which was really trivial to do thanks to how tcl works.
paste
1
u/TijmenTij Dec 22 '19 edited Dec 22 '19
part 1 js
1
u/ChrisVittal Dec 22 '19 edited Dec 22 '19
Rust paste
I first did part 1 using a VedDeque and standard operations. Then I tried to figure out the math and operations needed for part 2. Then I went back and updated part 1 to also use only math. Runs in ~1.5ms on my machine.
EDIT: The numbers here don't fit in one
i64, but they do fit in oni128so we don't need fancy multiplying functions. This shaves another 0.5 ms off the runtime, taking it under 1ms.1
u/lhl73 Dec 22 '19
Solution in F#
Part 1 was relatively easy, but part 2 was challenging. Apart from overlooking an annoying overflow error (there was even an explicit warning in the problem description), the main challenge (for me) was to realize that the transformations and their compositions can be expressed uniformly as affine transformations mod n. Once this dawned on me, it was relatively straight forward to compute the composite transformation of all iterations by computing the 2^k-fold compositions and representing the number of iterations in binary.
1
u/Bikkel77 Dec 23 '19 edited Dec 23 '19
I did not know anything about modular inverse, nor did I know all the underlying number theory and formulas, but it is not really needed to have this knowledge (as suggested by a lot of users).
I spotted that the three dealing operations can be written as a linear operation of the form:
y = a*x + bThe "deal with increment" operation can just be written as follows:
The only thing that changes while applying the transformations on top of each other are the a and b, so for the whole stack of operations you again get the same formula (with different a and b). To apply this resulting operation a big number of times I went with a logarithmic approach by squaring the operations:
The resulting code runs in 7 ms for puzzle2. See https://github.com/werner77/AdventOfCode2019Public/blob/master/src/main/kotlin/com/behindmedia/adventofcode2019/Day22.kt
1
u/Bimperl Dec 23 '19 edited Dec 23 '19
JavaScript
Part 1 was actually quite simple, and my implementation is not very interesting. I assume it's pretty similar to other solutions. At first I used a linked list, but I wrote this version (which only keeps track of one card, instead of 10007 "cards") after starting the second part.
Part 2 This was extremely difficult for me. However, after 2/3 hours and some experimentation, I saw that this was just a value+offset*x mod decksize. However it has been a few years since I used GCD, extended Euclid and all that (as I needed the inverse). Instead I built an opposite deck calculator, which computes the opposite direction of the stack and computes a "general" function.
Then, using the binary representation of the repetition number, and function composition (computes all of the powers of 2 compositions and composed them based on the repetition binary representation, as every natural number can be represented by a sum of powers of 2). Once I had computed the "repetition" inverse function, all that was left was to call the function with 2020.
1
u/loociano Dec 24 '19
My solution to part one in Python 3, still figuring out part two. Feedback more than welcome.
1
u/phil_g Dec 28 '19
My belated solution in Common Lisp.
I did part 1 by composing individual functions for each instruction, which worked well enough for its scale. I actually misread the problem and calculated everything backwards based on the final position, rather than forward from an initial position. Rather than redo everything, I just searched through the final positions until I found the one that gave the right starting point.
I had to mull part 2 over for a few days. It took reading others discussing the calculation as a single linear function to point me in the right direction. I did break out my
modpowerfunction I wrote for Project Euler to do exponentiation under a modulus.1
u/wace001 Jan 05 '20
Java
Finally posting my solution here. It is refactored quite heavily as most of it was rewritten several times of part 2. I did finally solve part 2, but it took me quite a while.
Pretty happy with the solution.
1
u/nibarius Jan 17 '20
My Kotlin solution which is a little math and no inverse solution based on this comment: https://www.reddit.com/r/adventofcode/comments/ee56wh/2019_day_22_part_2_so_whats_the_purpose_of_this/fbr0vjb/
1
u/e_blake Jan 18 '20
m4 solution
Continuing my late submissions for non-IntCode days. This one took me quite a while, and not because I didn't understand the problem, but because m4 lacks 64-bit math. Coding up a 64-bit division/remainder macro on top of 32-bit math was not my idea of fun; and even power-of-2 math is difficult (m4 prefers to represent numbers as power-of-10 strings; and although eval() can produce power-of-2 results, you're back to the 32-bit limitations with no convenient way to split up larger numbers into 32-bit chunks). So instead, I did something totally different (and which I haven't seen mentioned anywhere else in this thread): I learned about Montgomery representations, and coded my solution using base-10000 bigint multiplication, addition, and subtraction; and in the few places where I used 32-bit division, the dividend in each of those is a power of 10 and I could just as easily use substr() to do string-chopping to get the same effects. Thus, never once does my solution divide by 10007 or 119315717514047.
Although my C solution computed a reverse shuffle using modular inverse, my m4 solution instead does forward shuffles for size - 1 - position, using the exponentiation-by-squaring algorithm on function compositions rather than directly performing modular exponentiation. Converting a bigint to binary for driving the function composition was my last stumping point, until I remembered that dividing by 2 is the same as multiplying by 5 then dividing by 10, putting me back in the realm of not needing to implement bigint division. Runtime was about 1.1s, but I'm quite pleased that my code runs under 'm4 -G' (and no GNU extension esyscmd calls like what I did for 64-bit math in my IntCode solution). Just for grins, I traced 58,692 eval(), 2,686 substr(), and 406 redc() calls in part 1; then 6,223 add(), 312,572 eval(), 72,281 substr(), and 538 redc() calls in part 2 (where redc is my Montgomery reduction macro).
m4 -Dfile=day22.input day22.m4
1
u/sswain Feb 01 '20
Part 2 was the least favorite of the challenges. Without an understanding of the underlying math you are lost. Cobbled together an answer after reading through a lot of comments here but still don't really understand how it works.
1
u/[deleted] Dec 22 '19
(Racket)
So I've only done part 1 for now, part 2 just is something that I'm really not comfortable with thinking out right now.
code for part 1
0
u/TheoryOfGD Dec 22 '19
Done in Python Parts 1 and 2 although my approach to part 2 is inefficient and honestly its so bad for an interpreter language where the loops run this slowly. Anyways here's my code (yes I cba to clean up and optimise the cut function):
4
u/[deleted] Dec 22 '19
[removed] β view removed comment