73 lines
1.6 KiB
Python
73 lines
1.6 KiB
Python
#!/usr/bin/env python3
|
|
|
|
from functools import reduce
|
|
|
|
deal = lambda: (-1, -1)
|
|
dealN = lambda n: (n, 0)
|
|
cutN = lambda n: (1, -n)
|
|
id = (1, 0)
|
|
|
|
instructions = {"deal into new stack" : deal,
|
|
"deal with increment" : dealN,
|
|
"cut" : cutN
|
|
}
|
|
|
|
def egcd(a, b):
|
|
if a == 0:
|
|
return (b, 0, 1)
|
|
else:
|
|
g, y, x = egcd(b % a, a)
|
|
return (g, x - (b // a) * y, y)
|
|
|
|
def modinv(a, m):
|
|
g, x, y = egcd(a, m)
|
|
if g != 1:
|
|
raise Exception('modular inverse does not exist')
|
|
else:
|
|
return x % m
|
|
|
|
def comp(ab, cd, mod):
|
|
a, b = ab
|
|
c, d = cd
|
|
return ((a*c) % mod, (a*d + b) % mod)
|
|
|
|
def apply(ab, x, mod):
|
|
a, b = ab
|
|
return (a*x + b) % mod
|
|
|
|
def inverse(ab, mod):
|
|
a, b = ab
|
|
x = modinv(a, mod)
|
|
return (x, (-b * x) % mod)
|
|
|
|
def powcomp(ab, pw, mod):
|
|
a, b = ab
|
|
return (pow(a, pw, mod), ((pow(a, pw, mod) - 1) * modinv(a-1, mod) * b) % mod)
|
|
|
|
def parse(line):
|
|
for inst in instructions.keys():
|
|
if line[:len(inst)] == inst:
|
|
return instructions[inst](*map(int, line[len(inst):].split()))
|
|
return NotImplemented
|
|
|
|
def compile(program, deck):
|
|
return reduce(lambda f1, f2: comp(f2, f1, deck), program, id)
|
|
|
|
|
|
def preproc(puzzle_input):
|
|
return list(map(parse, puzzle_input.split('\n')))
|
|
|
|
def partI(program):
|
|
deck = 10007
|
|
shuffle = compile(program, deck)
|
|
return apply(shuffle, 2019, deck)
|
|
|
|
def partII(program):
|
|
deck = 119315717514047
|
|
pw = 101741582076661
|
|
shuffle = compile(program, deck)
|
|
invshuffle = inverse(shuffle, deck)
|
|
|
|
repeated = powcomp(invshuffle, pw, deck)
|
|
return apply(repeated, 2020, deck)
|