p22.py

#!/usr/bin/env python3
# -*- coding: utf8 -*-

from aocd import data
from re import compile 
import sys

cut = compile("cut (-?\d+)")
deal_with_increment = compile("deal with increment (\d+)")
deal_into_new_stack = compile("deal into new stack")

instructions = []
for row in data.split('\n'):
    m = cut.match(row)
    if m is not None:
        instructions.append((0, int(m.groups()[0])))
    m = deal_with_increment.match(row)
    if m is not None:
        instructions.append((1, int(m.groups()[0])))
    m = deal_into_new_stack.match(row)
    if m is not None:
        instructions.append((2, 0))

def get_stack_information(stack_len, instructions, stack=(0,1)):
    for cmd, arg in instructions:
        start, diff = stack
        if cmd == 0:
            start += arg*diff % stack_len
        elif cmd == 2:
            start -= diff
            diff = -diff
        elif cmd == 1:
            # diff should increment by arg^(-1)
            # Fermat's Little theorem: a^(p - 1) is congruent with 1, modulo p.
            # Since we will take mod of the diff later, we may replace
            #  1     arg^(stack_len - 1)
            # --- = -------------------- = arg^(stack_len - 2)
            # arg           arg
            diff *= pow(arg, stack_len-2, stack_len) % stack_len
        stack = (start % stack_len, diff % stack_len)

    return stack

start, diff = get_stack_information(10007, instructions)
for i in range(10007):
    if (start + diff*i) % 10007 == 2019:
        print("Pt 1", i)

#  Using hints from https://www.reddit.com/r/adventofcode/comments/ee0rqi/2019_day_22_solutions/fbnkaju/
start0, diff0 = get_stack_information(119315717514047, instructions)

diff = pow(diff0, 101741582076661, 119315717514047)
start = start0 * (1 - pow(diff0, 101741582076661, 119315717514047))*pow(1-diff0, 119315717514047-2, 119315717514047)

print("Pt 2:", (start + diff*2020) % 119315717514047)