yknow i find it pretty cool

when i first did this problem as a high school freshman

i malded so hard it wasn't even funny

had to read like 3 explanations and even then i was copying code without having any idea what it was doing

and now i'm like, "yeah, this is just how it is" and solve it without looking at anything

but anyways

brute force suffices for p1

but we're here for the much more interesting p2

it just makes your deck STUPID big and also makes you go through the shuffle sequence a STUPID
amount of times

how about let's try to come up with mathematical analogues for each of the shuffle operations? perhaps that'll let us simplify the shuffle sequence we're given here

in all of these ops, here, say we have a card at position \(x\) in a deck of size \(d\) we number our positions \(0\) to \(d-1\)

- when we `deal into new stack`, our new position is \(d-x-1\)
- to `cut N` cards, we make our new position \(x-N \ (\mathrm{mod}\ d)\). this works even when \(N\) is negative, don't worry
- and finally to `deal with increment N`, our position gets turned into \(N \cdot x \ (\mathrm{mod}\ d)\). also quick note that \(d\) and \(N\) have to be coprime, otherwise you'd have two cards in the same position! (at least i think so lol)

now, with these arithmetic operations, notice that all of them are just +/-/*

so we can compress our *ENTIRE SHUFFLE SEQUENCE* into the form \(ax-b\ (\mathrm{mod}\ d)\)

meaning that to get the position of a card initially at \(x\) after the shuffle, we just
do one multiplication, one subtraction, and one modulus and we're done!

but we also have to go through the shuffle sequence itself like a stupid amount of times as well

which amounts to applying \(f(x)=ax-b\ (\mathrm{mod}\ d)\) to \(x\) alot

let's try to find a pattern here, maybe that'll help (the mod is removed for brevity reasons)

in general, if we apply the shuffle sequence \(n\) times, a card at position \(x\) ends up at the position given by the following expression:

\[a^nx - b(a^{n-1}+a^{n-2} + \cdots + a)\]with the formula for the sum of a geometric series, we can then turn this into

\[x'=a^nx - b\frac{a^n-a}{a-1}\]where \(x'\) is the new position of x

then you might be thinking,
"my brother in christ it's not asking for where card `2020` went!
it's asking for the card *in* position `2020`!"

yeah. unfortunately we have to do a teensy bit more work,
which is modifying the equation to give \(x\), the initial position, in terms of \(x'\), the final position

doing that gives us this:

and that's our formula! note that since things are done mod \(d\), we have to compute some modular inverse, but that's an implementation detail python can do itself

look, i know this *is* hosted on my
aoc repo,
but might as well put it here too