# Advent of Code Day 22¶

In [1]:
def readfile(input_name):
with open(input_name) as input_file:

In [2]:
input22 = readfile("AoC/input22.txt")

In [3]:
testinput = """deal into new stack
cut -2
deal with increment 7
cut 8
cut -4
deal with increment 7
cut 3
deal with increment 9
deal with increment 3
cut -1"""

In [4]:
def deal_incr(incr, stack):
nextstack = stack[:]
l = len(stack)
for i in range(len(stack)):
nextstack[(incr * i) % l] = stack[i]
return nextstack

def deal_new(stack):
return stack[::-1]

def cut(n, stack):
return stack[n:] + stack[:n]

def deal(size, inp):
stack = list(range(size))

for line in inp.split("\n"):
# print(stack)
# print(line)

if line.startswith("deal with increment"):
stack = deal_incr(int(line.split(" ")[-1]), stack)
elif line.startswith("cut"):
stack = cut(int(line.split(" ")[-1]), stack)
elif line.startswith("deal into new stack"):
stack = deal_new(stack)
return stack

# res = deal(10007, input22)
# print(res[2020])
# print("result")
# for i, val in enumerate(res):
#     if val == 2019:
#         print(i)
# res[2020]

In [5]:
easy = """deal with increment 7
deal with increment 9
cut -2"""

In [6]:
# easy = """deal with increment 3"""

def move_incr(incr, size, posn):
k = 0
act = (size * k + posn) / incr
while act < size:
act = (size * k + posn) / incr
integer = (size * k + posn) // incr
if act == integer:
return integer

k += 1

def deal2(size, posn, inp):
orig_posn = posn

inp = inp.split("\n")
inp.reverse()

result = 0
expected_result = None

i = 0
while i == 0 or orig_posn != 2020:
for line in inp:
if line.startswith("deal with increment"):
x = int(line.split(" ")[-1])
orig_posn = move_incr(x, size, orig_posn)
elif line.startswith("cut"):
x = int(line.split(" ")[-1])
orig_posn = (orig_posn + x) % size
elif line.startswith("deal into new stack"):
orig_posn = size - orig_posn - 1
pass

i += 1

return orig_posn, i

def deal3(size, posn, inp, reps):
orig_posn = posn

inp = inp.split("\n")
inp.reverse()

result = 0
expected_result = None

i = 0
while i < reps:
print(orig_posn)

for line in inp:
if line.startswith("deal with increment"):
x = int(line.split(" ")[-1])
orig_posn = move_incr(x, size, orig_posn)
elif line.startswith("cut"):
x = int(line.split(" ")[-1])
orig_posn = (orig_posn + x) % size
elif line.startswith("deal into new stack"):
orig_posn = size - orig_posn - 1
pass

i += 1

return orig_posn

# deal2(119315717514047, 2020, input22)
# deal3(119315717514047, 2020, input22, 100) # 101741582076661)
# deal3(10007, 3, input22, 100) # 101741582076661)

In [7]:
def symbolic(size, inp):
inp = inp.split("\n")
val = (1, 0) # x + 0

for line in inp:
if line.startswith("deal with increment"):
x = int(line.split(" ")[-1])
val = (val[0] * x, val[1] * x)
elif line.startswith("cut"):
x = int(line.split(" ")[-1])
val = (val[0], val[1] - x)
elif line.startswith("deal into new stack"):
val = (-val[0], size - 1 - val[1])
pass

return val[0] % size, val[1] % size

def apply(res, x, size):
return (res[0] * x + res[1]) % size

def point(size, inp, posn):
res = symbolic(size, inp)
print(f"({res[0]}x + ({res[1]})) % {size}")
return (res[0] * posn + res[1]) % size

easy = """deal with increment 7
deal with increment 9
cut -2"""
med = """deal into new stack
cut -2
deal with increment 7
cut 8
cut -4
deal with increment 7
cut 3
deal with increment 9
deal with increment 3
cut -1"""

neweasy = "deal into new stack"

size = 10007
eqn = symbolic(size, input22)
print(eqn)
res = deal(size, input22)
for i in range(10):
pt = apply(eqn, i, size)
print(pt, i, res[pt], i == res[pt])

(6377, 7785)
7785 0 0 True
4155 1 1 True
525 2 2 True
6902 3 3 True
3272 4 4 True
9649 5 5 True
6019 6 6 True
2389 7 7 True
8766 8 8 True
5136 9 9 True

In [9]:
def invert(eqn, posn, size):
k = 0
while k < size:
num = (posn + k * size - eqn[1])
den = eqn[0]
if num // den == num / den:
return num // den

k += 1

assert False

size2 = 119315717514047
eqn = symbolic(size2, input22)
print(eqn)
i = 100
pos = 2020
# while i >= 0:
print(pos)

# pos = invert(eqn, pos, size2)
print(pos)

(2220204964869, 51399895659261)
2020
2020

In [60]:
times2 = 101741582076661
size2 = 119315717514047
eqn = symbolic(size2, input22)

def gcde(a, b):
if a == 0:
return 0, 1, b
x1, y1, gcd = gcde(b % a, a)
return y1 - (b // a) * x1, x1, gcd

def inverse(b, m):
x, y, g =  gcde(b, m)
assert g == 1
return x

def ntheqn(eqn, n, size):
xcoeff = pow(eqn[0], n, size) % size
ycoeff = eqn[1]
ycoeff *= (pow(eqn[0], n, size) - 1) * inverse(eqn[0] - 1, size)
ycoeff %= size
return (xcoeff, ycoeff)

print(eqn)
neqn = ntheqn(eqn, times2, size2)
print(neqn)

(2220204964869, 51399895659261)
(118927380295524, 9290856136457)

In [66]:
inverse(neqn[0], size2) * (2020 - neqn[1]) % size2

Out[66]:
55574110161534
In [ ]: