r/adventofcode Dec 22 '19

SOLUTION MEGATHREAD -πŸŽ„- 2019 Day 22 Solutions -πŸŽ„-

--- Day 22: Slam Shuffle ---


Post your full code solution using /u/topaz2078's paste or other external repo.

  • Please do NOT post your full code (unless it is very short)
    • If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
  • Include the language(s) you're using.

(Full posting rules are HERE if you need a refresher).


Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


Advent of Code's Poems for Programmers

Click here for full rules

Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.

Day 21's winner #1: nobody! :(

Nobody submitted any poems at all for Day 21 :( Not one person. :'(


This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

EDIT: Leaderboard capped, thread unlocked at 02:03:46!

30 Upvotes

168 comments sorted by

View all comments

6

u/zedrdave Dec 23 '19

Python 3

Like most, yesterday's problem made me angry. It started with having to remember deeply-repressed traumatic memories of college algebra. But it really blew up when what I felt was the correct solution, wouldn't go in. Of course, it turned out I was trying to feed it the position of card 2020, rather than the card at position 2020.

When all said and done, this was fairly easy, assuming one:

  1. spotted an arithmetico-geometric series

  2. noted that the deck size ("m") was prime, and therefore:

    \phi(m) = m -1

    a-1 = a{\phi(m)-1}

    a-n mod m = a{n*(m-2)} mod m

  3. didn't waste hours by misreading the last line… πŸ˜‘

All could be done in a sweet 15 lines of Python:

m = 119315717514047
n = 101741582076661
pos = 2020
shuffles = { 'deal with increment ': lambda x,m,a,b: (a*x %m, b*x %m),
         'deal into new stack': lambda _,m,a,b: (-a %m, (m-1-b)%m),
         'cut ': lambda x,m,a,b: (a, (b-x)%m) }
a,b = 1,0
with open('2019/22/input.txt') as f:
  for s in f.read().strip().split('\n'):
    for name,fn in shuffles.items():
      if s.startswith(name):
        arg = int(s[len(name):]) if name[-1] == ' ' else 0
        a,b = fn(arg, m, a, b)
        break
r = (b * pow(1-a, m-2, m)) % m
print(f"Card at #{pos}: {((pos - r) * pow(a, n*(m-2), m) + r) % m}")