Slam Shuffle
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-05-24 19:32:02

## [Advent of Code 2019 Day 22](https://adventofcode.com/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](https://www.reddit.com/r/adventofcode/comments/ee56wh/2019_day_22_part_2_so_whats_the_purpose_of_this/fbr0vjb/)

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