def readfile(input_name):
with open(input_name) as input_file:
return input_file.read().rstrip("\n")
input22 = readfile("AoC/input22.txt")
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"""
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]
easy = """deal with increment 7
deal with increment 9
cut -2"""
# 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)
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])
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)
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)
inverse(neqn[0], size2) * (2020 - neqn[1]) % size2