2019-12-22 - Slam Shuffle
(original .ipynb)
Day 22 puzzle input is an set of instructions on how to shuffle a set of cards (mine is here). Part 1 involves performing the shuffle according to these instructions and finding the card at index 2019. Part 2 involved performing this shuffle for an insanely huge deck, many times over. This involved something I had never seen before, so I ended up consulting the reddit and to be honest I still don't properly get it.
def new_deck(size):
return [ c for c in range(size) ]
def deal_new_stack(deck):
deck = [ c for c in reversed(deck) ]
return deck
def cut(deck, n):
cut_cards = []
return deck[n:] + deck[:n]
def deal_with_increment(deck, increment):
new_deck = [ None for d in deck ]
position = 0
while deck:
card = deck.pop(0)
new_deck[position] = card
position = (position + increment) % len(new_deck)
return new_deck
def parse_deal_instruction(instruction_str):
deal_increment_instr = "deal with increment "
cut_instr = "cut "
deal_new_stack_instr = "deal into new stack"
if instruction_str.startswith(deal_increment_instr):
increment = int(instruction_str[len(deal_increment_instr):])
return lambda deck: deal_with_increment(deck, increment)
elif instruction_str.startswith(cut_instr):
cut_index = int(instruction_str[len(cut_instr):])
return lambda deck: cut(deck, cut_index)
elif instruction_str.startswith(deal_new_stack_instr):
return lambda deck: deal_new_stack(deck)
else:
raise Exception(f"couldn't parse instruction {instruction_str}")
# part 1
puzzle_input = open("puzzle_input/day22.txt", "r").read()
stack = new_deck(10007)
for instruction_str in puzzle_input.split("\n"):
instruction = parse_deal_instruction(instruction_str)
# print(instruction_str)
stack = instruction(stack)
print(stack.index(2019))
6526
# part 2 - what is in position 2020 after doing this for 119315717514047 cards
# a total of 101741582076661 times.
#
# So obviously we cannot model this directly - we'd need to do 100 transforms of
# about ~100 trillion numbers 101741582076661 times which would be ridiculous.
#
# I thought this might also be possible to implement using generators which are all
# chained together, starting with range(), then next()-ing 2020 times. I don't think
# this is possible though - "deal with increment" interleaves the cards which I think
# complicates all of this.
#
# After hammering on this problem it turns out this requires "modular arithmatic"
# which I never learned :-/ I read a couple of articles (https://codeforces.com/blog/entry/72593
# and https://work.njae.me.uk/2020/01/12/advent-of-code-2019-day-22) but mostly
# followed along someone else's solution. I don't know this mathematics and I honestly
# probably won't :(
def deal_with_increment_modular(deck_size, a, b, increment):
z = pow(increment, deck_size - 2, deck_size)
a = a * z % deck_size
b = b * z % deck_size
return (a, b)
def cut_modular(deck_size, a, b, cut_index):
b = (b + cut_index) % deck_size
return (a, b)
def deal_new_stack_modular(deck_size, a, b):
a = -a
b = deck_size - b - 1
return (a, b)
def parse_deal_instruction_modular(deck_size, instruction_str):
deal_increment_instr = "deal with increment "
cut_instr = "cut "
deal_new_stack_instr = "deal into new stack"
if instruction_str.startswith(deal_increment_instr):
increment = int(instruction_str[len(deal_increment_instr):])
return lambda a, b: deal_with_increment_modular(deck_size, a, b, increment)
elif instruction_str.startswith(cut_instr):
cut_index = int(instruction_str[len(cut_instr):])
return lambda a, b: cut_modular(deck_size, a, b, cut_index)
elif instruction_str.startswith(deal_new_stack_instr):
return lambda a, b: deal_new_stack_modular(deck_size, a, b)
else:
raise Exception(f"couldn't parse instruction {instruction_str}")
def polypow(a, b, m, n):
if m == 0:
return 1,0
if m % 2 == 0:
return polypow(a * a % n, (a * b + b) % n, m // 2, n)
else:
c, d = polypow(a, b, m - 1, n)
return (a * c % n, (a * d + b) % n)
deck_size = 119315717514047
shuffle_count = 101741582076661
a = 1
b = 0
deal_actions = [ parse_deal_instruction_modular(deck_size, instruction_str) for instruction_str in puzzle_input.split("\n") ]
for deal_action in reversed(deal_actions):
a, b = deal_action(a, b)
a, b = polypow(a, b, shuffle_count, deck_size)
print((2020 * a + b) % deck_size)
79855812422607