Robert Mion

Posted on

# Slam Shuffle

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

### 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
``````

• 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.

## 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.