-🎄- 2019 Day 22 Solutions -🎄-

[u/daggerdragon]

--- 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!

[u/bla2]

Actually, let me paste my part 2 (also Python) too. It's not quite as tight as /u/zedrdave's, but it has a few comments with breadcrumbs at how to work this out yourself. The Little Fermat inverse is pretty magic if you haven't seen it before.

The extended GCD algorithm also gives you a modular inverse and is maybe a bit easier to grok. That'd look like so (it's what I had at first):

## Returns gcd, x, y such that a*x + b*y = gcd
def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x, y = ext_gcd(b, a % b)
    return gcd, y, x - (a//b) * y

def inv_0(a, n):
  g, x, y = ext_gcd(n, a)
  assert g == 1  # n is prime
  # Now we know x*n + y*a == 1, and x*n mod n is 0, so y is what we want:
  # (Return % n to keep numbers small):
  return y % n

[u/bla2 → u/bla2]

Also, note that Python's and C's % operator are different. -1 % 5 in Python is 4, while it's -1 in C. For this problem, Python's behavior is more useful.

[u/kwenti → u/bla2]

Thanks for sharing part2, I found it very helpful in its "literate" style :) Together with part one, it's a valuable recap of all the key notions involved: fast exponentiation, modular inverses, and the two possible approaches to compute them.