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

- Three shuffling techniques, algorithmatized!
- Testing all these functions on the examples
- Parsing the input into function calls
- 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

- A performance test with hints of a shortcut
- 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.

## Top comments (0)