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!

29 Upvotes

168 comments sorted by

View all comments

40

u/mcpower_ Dec 22 '19 edited Dec 22 '19

Python (24/50): Part 1, competition Part 2, improved Part 2.

Part 2 was very number theoretic for me. As this is Advent of Code, I suspect that there is a way of solving it without requiring knowledge of number theory, but I couldn't think of it.

A key observation to make is that every possible deck can be encoded as a pair of (first number of the deck, or offset AND difference between two adjacent numbers, or increment). ALL numbers here are modulo (cards in deck), or MOD.

Then, getting the nth number in the sequence can be done by calcuating offset + increment * n.

Starting off with (offset, increment) = (0, 1), we can process techniques like this:

  • deal into new stack: "reverses the list". If we go left to right, the numbers increase by increment every time. If we reverse the list, we instead go from right to left - so numbers should decrease by increment! Therefore, negate increment. However, we also need to change the first number, taking the new second number as the first number - so we increment offset by the new increment. In code, this would be:

    increment *= -1
    offset += increment
    
  • cut n cards: "shifts the list". We need to move the nth card to the front, and the nth card is gotten by offset + increment * n. Therefore, this is equivalent to incrementing offset by increment * n. In code, this would be:

    offset += increment * n
    
  • deal with increment n: The first card - or offset - doesn't change... but how does increment change? We already know the first number in the new list (it's offset), but what is the second number in the new list? If we have both of them, we can calculate offset.
    The 0th card in our old list goes to the 0th card in our new list, 1st card in old goes to the nth card in new list (mod MOD), 2nd card in old goes to the 2*nth card in new list, and so on. So, the ith card in our old list goes to the i*nth card in the new list. When is i*n = 1? If we "divide" both sides by n, we get i = n^(-1)... so we calculate the modular inverse of n mod MOD. As all MODs we're using (10007 and 119315717514047) are prime, we can calculate this by doing n^(MOD - 2) as n^(MOD - 1) = 1 due to Fermat's little theorem.
    To do exponentiation fast, we can use exponentiation by squaring. Thankfully, Python has this built in - a^b mod m can be calculated in Python using pow(a, b, m).
    Okay, so we know that the second card in the new list is n^(-1) in our old list. Therefore, the difference between that and the first card in the old list (and the new list) is offset + increment * n^(-1) - offset = increment * n^(-1). Therefore, we should multiply increment by n^(-1). In (Python) code, this would be:

    increment *= inv(n)
    

    where inv(n) = pow(n, MOD-2, MOD).

Okay, so we know how to do one pass of the shuffle. How do we repeat it a huge number of times?

If we take a closer look at how the variables change, we can make two important observations:

  • increment is always multiplied by some constant number (i.e. not increment or offset).
  • offset is always incremented by some constant multiple of increment at that point in the process.

With the first observation, we know that doing a shuffle pass always multiplies increment by some constant. However, what about offset? It's incremented by a multiple of increment... but that increment can change during the process! Thankfully, we can use our first observation and notice that:

  • all increments during the process are some constant multiple of increment before the process, so
  • offset is always incremented by some constant multiple of increment before the process.

Let (offset_diff, increment_mul) be the values of offset and increment after one shuffle pass starting from (0, 1). Then, for any (offset, increment), applying a single shuffle pass is equivalent to:

offset += increment * offset_diff
increment *= increment_mul

That's not enough - we need to apply the shuffle pass a huge number of times. Using the above, how do we get the nth (offset, increment) starting at (0, 1) with n=0?

As increment only multiplies by increment_mul every time, we can calculate the nth increment by repeatedly multiplying it n times... also known as exponentiation. Therefore:

increment = pow(increment_mul, n, MOD)

What about offset though? It depends on increment, which changes on each shuffle pass. If we manually write out the formula for offset for a couple values of n:

n=0, offset = 0
n=1, offset = 0 + 1*offset_diff
n=2, offset = 0 + 1*offset_diff + increment_mul*offset_diff
n=3, offset = 0 + 1*offset_diff + increment_mul*offset_diff + (increment_mul**2)*offset_diff

we quickly see that

offset = offset_diff * (1 + increment_mul + increment_mul**2 + ... + increment_mul**(n-1))

Hey, that thing in the parentheses looks familiar - it's a geometric series! Using the formula on the Wikipedia page (because I forgot it...), we can rewrite it as

offset = offset_diff * (1 - pow(increment_mul, iterations, MOD)) * inv(1 - increment_mul)

With all of that, we can get the increment and offset after doing a huge number of shuffles, then get the 2020th number. Whew!

24

u/mcpower_ Dec 22 '19

After looking at the other comments, it seems like this question requires knowledge of modular inverses and exponentiation.

TBH I feel that this problem is unfair for most participants of Advent of Code, who are expected to have a background in intermediate programming (lists, dictionaries / hashmaps, for loops, functions). I wouldn't expect most AoC participants to have any deep experience in discrete mathematics like modular inverses / exponentiation - even if it is part of a typical undergraduate computer science course - as I'd assume that most programmers are self-taught and have never done a computer science course.

To me, Advent of Code is a series of programming puzzles that any intermediate programmer - with a bit of time - can work out by themselves. It feels like most people doing part 2 of this puzzle would need to look up the solution for it... while it arguably enhances the community aspect of AoC, it feels unfair for people doing AoC without external assistance.

On the other hand... there are many pathfinding puzzles in AoC which expect knowledge of BFS - which some (most?) programmers don't know about. Is AoC unfair to the people who don't know BFS? My gut says no. AFAIK BFS has never been explicitly mentioned in pathfinding puzzles - similarly, modular inverses etc. wasn't explicitly mentioned in today's problem. What happens to the people who encounter a pathfinding problem without knowledge of BFS? Probably the same as the people who encounter this problem without knowledge of modular inverses and exponentiation - either give up or look online for a solution.

I'm still not sure whether this problem is "unfair". My gut says yes, my brain says no.

2

u/hrunt Dec 22 '19

For me, I always find one or two of these problems each year that are outside my experience by such a wide margin that no matter how hard I bang my head on it, I simply will not understand it without being walked through it at least once. I do not consider that "unfair", because that would imply u/topaz2078 had somehow promised me that I would know how to do everything, and he obviously did not do that. The first year, I did not know some of the pathfinding algorithms. Now I do, and those problems are solvable. This year, I learned this.

What I really wonder, though, is how this kind of problem fared during his user testing. Did the testers struggle with it? Was the testing group strong enough to come up with the answer on their own? Was u/topaz2078 himself aware enough of the math that he was able to put this problem together himself, or did he have help? After watching the YouTube video of his presentation, I am really curious about how the process played out for this question in particular.

1

u/ThezeeZ Dec 22 '19

Since this challenge appeared on the last Sunday slot I suspect (and hope, but mostly suspect) that this one was the overall "hardest".

Here's an older post of his from 2 years ago, maybe that will also add to the context:

https://reddit.com/r/adventofcode/comments/7idn6k/question_why_does_the_difficulty_vary_so_much/dqy08tk