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\)
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
```py import enum import re P1_DECK, P1_CARD = 10007, 2019 P2_DECK, P2_POS, P2_LOOPS = 119315717514047, 2020, 101741582076661 class CardOp(enum.Enum): STACK = enum.auto() CUT = enum.auto() INC = enum.auto() def compress_ops(ops: list[tuple[CardOp, int]], deck: int) -> tuple[int, int]: mul = 1 sub = 0 for t, v in ops: if t == CardOp.STACK: mul, sub = -mul, -sub sub -= deck - 1 elif t == CardOp.CUT: sub += v elif t == CardOp.INC: mul *= v sub *= v mul %= deck sub %= deck return mul, sub def mod_inv(x: int, mod: int) -> int: """https://stackoverflow.com/a/9758173/12128483""" return pow(x, -1, mod) def card_pos( ops: list[tuple[CardOp, int]], card: int, deck: int ): mul, sub = compress_ops(ops, deck) return (card * mul - sub) % deck def pos_card( ops: list[tuple[CardOp, int]], pos: int, deck: int, loops: int ) -> int: # i really should explain what i'm doing here huh mul, sub = compress_ops(ops, deck) mul_pow = pow(mul, loops, deck) top = pos + sub * (mul_pow - 1) * mod_inv(mul - 1, deck) bot = mod_inv(mul_pow, deck) return top * bot % deck stack_fmt = "^deal into new stack$" cut_fmt = r"^cut (-?\d+)$" inc_fmt = r"^deal with increment (\d+)" ops = [] with open("input/day22.txt") as read: for i in read.readlines(): if re.findall(stack_fmt, i): ops.append((CardOp.STACK, 0)) # 2nd # isn't needed lol elif res := re.findall(cut_fmt, i): ops.append((CardOp.CUT, int(res[0]))) elif res := re.findall(inc_fmt, i): ops.append((CardOp.INC, int(res[0]))) print(f"pos of card {P1_CARD}: {card_pos(ops, P1_CARD, P1_DECK)}") print(f"card in pos {P2_POS}: {pos_card(ops, P2_POS, P2_DECK, P2_LOOPS)}") ```