Slam Shuffle

Advent of Code 2019 Day 22

Task: Solve for X where...

Part 1

X = the position of card 2019 after shuffling the factory order deck of 10007 cards per the instructions

Part 2

X = the number on the card that ends up in position 2020 using an exponentially larger factory order deck and shuffling exponentially more times

Example input

deal into new stack
cut -2
deal with increment 7
cut 8
cut -4
deal with increment 7
cut 3
deal with increment 9
deal with increment 3
cut -1

It represents:

• Instructions for continually shuffling the same deck of cards

Part 1

1. Three shuffling techniques, algorithmatized!
2. Testing all these functions on the examples
3. Parsing the input into function calls
4. Wrong answer, then right answer

Three shuffling techniques, algorithmatized!

Deal into new stack

• This seems like a straight reversal of order

Before:
0 1 2 3 4 5 6 7 8 9

After:
9 8 7 6 5 4 3 2 1 0

As an algorithm:

Reverse the order of the elements in the array

Cut N cards

• Split the cards into two groups, divided at a specified location
• Swap the order of the groups

N = 3
Before:
0 1 2|3 4 5 6 7 8 9
     ^
After:
3 4 5 6 7 8 9 0 1 2

As an algorithm:

Join two sub-arrays in the appropriate order, depending on whether N is positive or negative:
  1. The original array, starting from the specified location thru to the end
  2. The original array, starting from the beginning up to and not including the specified location

Luckily, in JavaScript, the algorithm is the same for positive and negative N:

cards.slice(N).concat(RA.slice(0,N))

Deal with Increment N

• This will require a loop that runs as many times as there are cards, unfortunately
• And a list of the same size of cards, starting as empty
• And a number to track the proper location in the empty list needing populated

N = 3
Before:
0 1 2 3 4 5 6 7 8 9

0 3 6 9 2 5 8 1 4 7 <- New location

After:
0 7 4 1 8 5 2 9 6 3

As an algorithm:

Create a copy of the array
Set i as 0
For each card in the latest shuffled array
  Set the card at location i in the copy to the value of the card
  Set i to the remainder after dividing the sum of i and N by the length of the card array
Update the shuffled array to the newly-populated copy

Testing all these functions on the examples

I'll manually call my three functions for now.

Start with:
0 1 2 3 4 5 6 7 8 9

deal with increment 7
deal into new stack
deal into new stack
Result: 0 3 6 9 2 5 8 1 4 7

Success!

Start with:
0 1 2 3 4 5 6 7 8 9

cut 6
deal with increment 7
deal into new stack
Result: 3 0 7 4 1 8 5 2 9 6

Success!

Start with:
0 1 2 3 4 5 6 7 8 9

deal with increment 7
deal with increment 9
cut -2
Result: 6 3 0 7 4 1 8 5 2 9

Success!

Start with:
0 1 2 3 4 5 6 7 8 9

deal into new stack
cut -2
deal with increment 7
cut 8
cut -4
deal with increment 7
cut 3
deal with increment 9
deal with increment 3
cut -1
Result: 9 2 5 8 1 4 7 0 3 6

Success!

Parsing the input into function calls

I need to turn this:

deal into new stack
cut -2
deal with increment 7
cut 8
cut -4
deal with increment 7
cut 3
deal with increment 9
deal with increment 3
cut -1

Into this:

stack()
cut(-2)
increment(7)
cut(8)
cut(-4)
increment(7)
cut(3)
increment(9)
increment(3)
cut(-1)

I opted for a simple conditional-based sub-string look-up:

Split the input at each newline character into an array of strings

For each string
  If the string includes the sub-string, 'stack'
    Call stack()
  Else, if the string includes the sub-string 'cut'
    Call cut(), passing as argument the number-coerced second value in the array resulting from splitting the string at the space character
  Else, if the string includes the sub-string 'increment'
    Call cut(), passing as argument the number-coerced fourth value in the array resulting from splitting the string at the space character

Wrong answer, then right answer

• I made sure my program returned what I thought was the correct number: the card at location 2019
• That was wrong - too low
• I then re-read the instructions and noticed it was asking for the location of the card originally at location 2019
• So, I needed my program to return the index of 2019 in my shuffled array
• Sure enough, that was the correct answer!

Part 2

1. A performance test with hints of a shortcut
2. Ya, I never would have figured that out

A performance test with hints of a shortcut

• Use 100 trillion cards instead of 10 thousand, it says
• Run the shuffle instructions 100 trillion times instead of once, it says
• Well, an oddly specific number just north of 100 trillion
• An odd number so specific that there must be a pattern or trick involved
• Since performing that task computationally would take eons

I had a hunch the first part's relative ease would mean a drastically-scaled second part.

Ya, I never would have figured that out

• I quick trip down the sub-reddit's Solution Megathread for today reveals how mathematically-intense this part is
• There's mention of modular division and exponentiation! Woah!
• There's a link to one solver's careful analysis of patterns within the instructions

Celebrating my accomplishment

• I solved Part 1!

Bummer:

• My star count is quickly dwindling with each passing day nearing 25
• Although, that is to be expected with the increasing difficulty of the puzzles and my lacking computer science degree

I'm crossing my fingers that I can finish the year with at least 34 stars, like year 2021.

But if not, I am still happy I built the ASCII-capable Intcode computer that should be capable of solving Day 25...as I set out to do when I started this year's puzzles.

Onward, to Day 23...for what I presume is the penultimate Intcode computer puzzle.