My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1"""
2Credit to /u/mcpower_ for explaining the number theory involved in Part 2:
3https://www.reddit.com/r/adventofcode/comments/ee0rqi/2019_day_22_solutions/fbnkaju/
4"""
5
6import fileinput
7
8
9def solve_part_1(actions):
10 CARDS = 10007
11 POS = 2019
12
13 for action, n in actions:
14 if action == 'deal':
15 if n is None:
16 POS = (CARDS - 1) - POS
17 else:
18 POS = (n * POS) % CARDS
19 else:
20 if POS >= n:
21 POS -= n
22 else:
23 POS = (CARDS - (n - POS))
24
25 return POS
26
27
28def solve_part_2(actions):
29 CARDS = 119315717514047
30 SHUFFLES = 101741582076661
31
32 def modinv(n, p):
33 """Returns the inverse of n mod p, assuming p is prime."""
34 return pow(n, p - 2, p)
35
36 def get_card(offset, increment, i):
37 """Returns the ith card in the sequence given its offset and increment."""
38 return (offset + i * increment) % CARDS
39
40 def get_sequence(iterations, increment_mul, offset_diff):
41 """Returns the final increment and offset after the given number of iterations."""
42 increment = pow(increment_mul, iterations, CARDS)
43 offset = (offset_diff * (1 - increment) * modinv(1 - increment_mul, CARDS)) % CARDS
44 return increment, offset
45
46 # `increment` is the difference between two adajcent numbers
47 increment = 1
48
49 # `offset` is the first number in the sequence
50 offset = 0
51
52 for action, n in actions:
53 if action == 'deal':
54 # deal into new stack
55 if n is None:
56 # The sequence gets reversed...
57 increment = (increment * -1) % CARDS
58
59 # ...and shifted one to the left
60 offset = (offset + increment) % CARDS
61
62 # deal with increment n
63 else:
64 increment = (increment * modinv(n, CARDS)) % CARDS
65
66 # cut n
67 else:
68 offset = (offset + (n * increment)) % CARDS
69
70
71 inc, off = get_sequence(SHUFFLES, increment, offset)
72 return get_card(off, inc, 2020)
73
74
75actions = []
76
77for line in fileinput.input():
78 line = line.strip()
79 inst = line.split()
80 verb = inst[0]
81 if verb == 'cut':
82 actions.append(('cut', int(inst[1])))
83
84 else:
85 if inst[1] == 'into':
86 actions.append(('deal', None))
87 else:
88 actions.append(('deal', int(inst[-1])))
89
90
91print "Position of card 2019:", solve_part_1(actions)
92print "Card ending up in position 2020:", solve_part_2(actions)