# Slam Shuffle

2019-12-22

# Day 22: Slam Shuffle

**Description:**

--- Day 22: Slam Shuffle ---

There isn't much to do while you wait for the droids to repair your ship. At least you're drifting in the right direction. You decide to practice a new card shuffle you've been working on.

Digging through the ship's storage, you find a deck of space cards! Just like any deck of space cards, there are 10007 cards in the deck numbered 0 through 10006. The deck must be new - they're still in factory order, with 0 on the top, then 1, then 2, and so on, all the way through to 10006 on the bottom.

You've been practicing three different techniques that you use while shuffling. Suppose you have a deck of only 10 cards (numbered 0 through 9):

To deal into new stack, create a new stack of cards by dealing the top card of the deck onto the top of the new stack repeatedly until you run out of cards:

Top Bottom

0 1 2 3 4 5 6 7 8 9 Your deck

New stack

1 2 3 4 5 6 7 8 9 Your deck

0 New stack

2 3 4 5 6 7 8 9 Your deck

1 0 New stack

3 4 5 6 7 8 9 Your deck

2 1 0 New stack

Several steps later...

9 Your deck

8 7 6 5 4 3 2 1 0 New stack

Your deck

9 8 7 6 5 4 3 2 1 0 New stack

Finally, pick up the new stack you've just created and use it as the deck for the next technique.

To cut N cards, take the top N cards off the top of the deck and move them as a single unit to the bottom of the deck, retaining their order. For example, to cut 3:

Top Bottom

0 1 2 3 4 5 6 7 8 9 Your deck

3 4 5 6 7 8 9 Your deck

0 1 2 Cut cards

3 4 5 6 7 8 9 Your deck

0 1 2 Cut cards

3 4 5 6 7 8 9 0 1 2 Your deck

You've also been getting pretty good at a version of this technique where N is negative! In that case, cut (the absolute value of) N cards from the bottom of the deck onto the top. For example, to cut -4:

Top Bottom

0 1 2 3 4 5 6 7 8 9 Your deck

0 1 2 3 4 5 Your deck

6 7 8 9 Cut cards

0 1 2 3 4 5 Your deck

6 7 8 9 Cut cards

6 7 8 9 0 1 2 3 4 5 Your deck

To deal with increment N, start by clearing enough space on your table to lay out all of the cards individually in a long line. Deal the top card into the leftmost position. Then, move N positions to the right and deal the next card there. If you would move into a position past the end of the space on your table, wrap around and keep counting from the leftmost card again. Continue this process until you run out of cards.

For example, to deal with increment 3:

0 1 2 3 4 5 6 7 8 9 Your deck

. . . . . . . . . . Space on table

^ Current position

Deal the top card to the current position:

1 2 3 4 5 6 7 8 9 Your deck

0 . . . . . . . . . Space on table

^ Current position

Move the current position right 3:

1 2 3 4 5 6 7 8 9 Your deck

0 . . . . . . . . . Space on table

^ Current position

Deal the top card:

2 3 4 5 6 7 8 9 Your deck

0 . . 1 . . . . . . Space on table

^ Current position

Move right 3 and deal:

3 4 5 6 7 8 9 Your deck

0 . . 1 . . 2 . . . Space on table

^ Current position

Move right 3 and deal:

4 5 6 7 8 9 Your deck

0 . . 1 . . 2 . . 3 Space on table

^ Current position

Move right 3, wrapping around, and deal:

5 6 7 8 9 Your deck

0 . 4 1 . . 2 . . 3 Space on table

^ Current position

And so on:

0 7 4 1 8 5 2 9 6 3 Space on table

Positions on the table which already contain cards are still counted; they're not skipped. Of course, this technique is carefully designed so it will never put two cards in the same position or leave a position empty.

Finally, collect the cards on the table so that the leftmost card ends up at the top of your deck, the card to its right ends up just below the top card, and so on, until the rightmost card ends up at the bottom of the deck.

The complete shuffle process (your puzzle input) consists of applying many of these techniques. Here are some examples that combine techniques; they all start with a factory order deck of 10 cards:

deal with increment 7

deal into new stack

deal into new stack

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

cut 6

deal with increment 7

deal into new stack

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

deal with increment 7

deal with increment 9

cut -2

Result: 6 3 0 7 4 1 8 5 2 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

Positions within the deck count from 0 at the top, then 1 for the card immediately below the top card, and so on to the bottom. (That is, cards start in the position matching their number.)

After shuffling your factory order deck of 10007 cards, what is the position of card 2019?

--- Part Two ---

After a while, you realize your shuffling skill won't improve much more with merely a single deck of cards. You ask every 3D printer on the ship to make you some more cards while you check on the ship repairs. While reviewing the work the droids have finished so far, you think you see Halley's Comet fly past!

When you get back, you discover that the 3D printers have combined their power to create for you a single, giant, brand new, factory order deck of 119315717514047 space cards.

Finally, a deck of cards worthy of shuffling!

You decide to apply your complete shuffle process (your puzzle input) to the deck 101741582076661 times in a row.

You'll need to be careful, though - one wrong move with this many cards and you might overflow your entire ship!

After shuffling your new, giant, factory order deck that many times, what number is on the card that ends up in position 2020?

There isn't much to do while you wait for the droids to repair your ship. At least you're drifting in the right direction. You decide to practice a new card shuffle you've been working on.

Digging through the ship's storage, you find a deck of space cards! Just like any deck of space cards, there are 10007 cards in the deck numbered 0 through 10006. The deck must be new - they're still in factory order, with 0 on the top, then 1, then 2, and so on, all the way through to 10006 on the bottom.

You've been practicing three different techniques that you use while shuffling. Suppose you have a deck of only 10 cards (numbered 0 through 9):

To deal into new stack, create a new stack of cards by dealing the top card of the deck onto the top of the new stack repeatedly until you run out of cards:

Top Bottom

0 1 2 3 4 5 6 7 8 9 Your deck

New stack

1 2 3 4 5 6 7 8 9 Your deck

0 New stack

2 3 4 5 6 7 8 9 Your deck

1 0 New stack

3 4 5 6 7 8 9 Your deck

2 1 0 New stack

Several steps later...

9 Your deck

8 7 6 5 4 3 2 1 0 New stack

Your deck

9 8 7 6 5 4 3 2 1 0 New stack

Finally, pick up the new stack you've just created and use it as the deck for the next technique.

To cut N cards, take the top N cards off the top of the deck and move them as a single unit to the bottom of the deck, retaining their order. For example, to cut 3:

Top Bottom

0 1 2 3 4 5 6 7 8 9 Your deck

3 4 5 6 7 8 9 Your deck

0 1 2 Cut cards

3 4 5 6 7 8 9 Your deck

0 1 2 Cut cards

3 4 5 6 7 8 9 0 1 2 Your deck

You've also been getting pretty good at a version of this technique where N is negative! In that case, cut (the absolute value of) N cards from the bottom of the deck onto the top. For example, to cut -4:

Top Bottom

0 1 2 3 4 5 6 7 8 9 Your deck

0 1 2 3 4 5 Your deck

6 7 8 9 Cut cards

0 1 2 3 4 5 Your deck

6 7 8 9 Cut cards

6 7 8 9 0 1 2 3 4 5 Your deck

To deal with increment N, start by clearing enough space on your table to lay out all of the cards individually in a long line. Deal the top card into the leftmost position. Then, move N positions to the right and deal the next card there. If you would move into a position past the end of the space on your table, wrap around and keep counting from the leftmost card again. Continue this process until you run out of cards.

For example, to deal with increment 3:

0 1 2 3 4 5 6 7 8 9 Your deck

. . . . . . . . . . Space on table

^ Current position

Deal the top card to the current position:

1 2 3 4 5 6 7 8 9 Your deck

0 . . . . . . . . . Space on table

^ Current position

Move the current position right 3:

1 2 3 4 5 6 7 8 9 Your deck

0 . . . . . . . . . Space on table

^ Current position

Deal the top card:

2 3 4 5 6 7 8 9 Your deck

0 . . 1 . . . . . . Space on table

^ Current position

Move right 3 and deal:

3 4 5 6 7 8 9 Your deck

0 . . 1 . . 2 . . . Space on table

^ Current position

Move right 3 and deal:

4 5 6 7 8 9 Your deck

0 . . 1 . . 2 . . 3 Space on table

^ Current position

Move right 3, wrapping around, and deal:

5 6 7 8 9 Your deck

0 . 4 1 . . 2 . . 3 Space on table

^ Current position

And so on:

0 7 4 1 8 5 2 9 6 3 Space on table

Positions on the table which already contain cards are still counted; they're not skipped. Of course, this technique is carefully designed so it will never put two cards in the same position or leave a position empty.

Finally, collect the cards on the table so that the leftmost card ends up at the top of your deck, the card to its right ends up just below the top card, and so on, until the rightmost card ends up at the bottom of the deck.

The complete shuffle process (your puzzle input) consists of applying many of these techniques. Here are some examples that combine techniques; they all start with a factory order deck of 10 cards:

deal with increment 7

deal into new stack

deal into new stack

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

cut 6

deal with increment 7

deal into new stack

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

deal with increment 7

deal with increment 9

cut -2

Result: 6 3 0 7 4 1 8 5 2 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

Positions within the deck count from 0 at the top, then 1 for the card immediately below the top card, and so on to the bottom. (That is, cards start in the position matching their number.)

After shuffling your factory order deck of 10007 cards, what is the position of card 2019?

--- Part Two ---

After a while, you realize your shuffling skill won't improve much more with merely a single deck of cards. You ask every 3D printer on the ship to make you some more cards while you check on the ship repairs. While reviewing the work the droids have finished so far, you think you see Halley's Comet fly past!

When you get back, you discover that the 3D printers have combined their power to create for you a single, giant, brand new, factory order deck of 119315717514047 space cards.

Finally, a deck of cards worthy of shuffling!

You decide to apply your complete shuffle process (your puzzle input) to the deck 101741582076661 times in a row.

You'll need to be careful, though - one wrong move with this many cards and you might overflow your entire ship!

After shuffling your new, giant, factory order deck that many times, what number is on the card that ends up in position 2020?

**Input:**

cut -4258

deal with increment 71

cut -6593

deal into new stack

deal with increment 54

cut -5397

deal into new stack

cut 1327

deal with increment 20

deal into new stack

deal with increment 45

cut -9986

deal into new stack

deal with increment 47

cut -3318

deal with increment 75

cut 542

deal with increment 48

cut 8670

deal with increment 13

deal into new stack

deal with increment 5

cut -8813

deal with increment 36

cut 3228

deal with increment 21

cut 5143

deal with increment 13

cut 7329

deal with increment 74

deal into new stack

deal with increment 4

cut 4178

deal with increment 29

cut -7664

deal with increment 17

cut 8216

deal with increment 22

cut -7497

deal with increment 10

cut -2813

deal into new stack

cut 8416

deal with increment 16

cut -4124

deal with increment 13

cut -8531

deal with increment 74

cut -9397

deal with increment 57

cut -1832

deal with increment 34

cut -2538

deal into new stack

cut 7837

deal with increment 57

cut 5257

deal with increment 2

cut -8241

deal with increment 26

deal into new stack

deal with increment 39

cut -659

deal with increment 58

cut 34

deal into new stack

deal with increment 46

cut 9168

deal with increment 35

cut 8530

deal into new stack

cut 297

deal into new stack

cut 1116

deal with increment 69

cut 5440

deal with increment 6

deal into new stack

cut 3811

deal with increment 7

deal into new stack

cut -8657

deal with increment 29

cut 8933

deal with increment 4

cut -6643

deal with increment 37

cut 1688

deal with increment 32

cut -554

deal with increment 69

deal into new stack

deal with increment 64

cut 4395

deal with increment 71

cut -9180

deal with increment 60

cut 6480

deal with increment 73

cut -7146

deal with increment 71

cut -6593

deal into new stack

deal with increment 54

cut -5397

deal into new stack

cut 1327

deal with increment 20

deal into new stack

deal with increment 45

cut -9986

deal into new stack

deal with increment 47

cut -3318

deal with increment 75

cut 542

deal with increment 48

cut 8670

deal with increment 13

deal into new stack

deal with increment 5

cut -8813

deal with increment 36

cut 3228

deal with increment 21

cut 5143

deal with increment 13

cut 7329

deal with increment 74

deal into new stack

deal with increment 4

cut 4178

deal with increment 29

cut -7664

deal with increment 17

cut 8216

deal with increment 22

cut -7497

deal with increment 10

cut -2813

deal into new stack

cut 8416

deal with increment 16

cut -4124

deal with increment 13

cut -8531

deal with increment 74

cut -9397

deal with increment 57

cut -1832

deal with increment 34

cut -2538

deal into new stack

cut 7837

deal with increment 57

cut 5257

deal with increment 2

cut -8241

deal with increment 26

deal into new stack

deal with increment 39

cut -659

deal with increment 58

cut 34

deal into new stack

deal with increment 46

cut 9168

deal with increment 35

cut 8530

deal into new stack

cut 297

deal into new stack

cut 1116

deal with increment 69

cut 5440

deal with increment 6

deal into new stack

cut 3811

deal with increment 7

deal into new stack

cut -8657

deal with increment 29

cut 8933

deal with increment 4

cut -6643

deal with increment 37

cut 1688

deal with increment 32

cut -554

deal with increment 69

deal into new stack

deal with increment 64

cut 4395

deal with increment 71

cut -9180

deal with increment 60

cut 6480

deal with increment 73

cut -7146

**Part 1:**

```
namespace AdventOfCode2019_22_1
{
const DAY = 22;
const PROBLEM = 1;
export async function run()
{
let input = await AdventOfCode.getInput(DAY);
if (input == null) return;
const cmds = input
.split(new RegExp('\r?\n'))
.filter(p => p.trim().length > 0)
.map(p => parseLine(p))
AdventOfCode.setIntermedOutputSize("0.275vw");
let data = [...Array(10007).keys()];
for (const cmd of cmds)
{
if (cmd.type === CmdType.CUT && cmd.param >= 0)
{
data = [...data.slice(cmd.param), ...data.slice(0, cmd.param)];
}
else if (cmd.type === CmdType.CUT && cmd.param < 0)
{
data = [...data.slice(data.length + cmd.param), ...data.slice(0, data.length + cmd.param)];
}
else if (cmd.type === CmdType.DEAL)
{
let d2 = Array(data.length);
for(let i=0; i<data.length;i++) d2[(i*cmd.param) % data.length] = data[i];
data = (cmd.param === 1) ? d2.reverse() : d2;
}
else throw cmd;
let str = "";
let len = 50;
for (let i=0; i<(data.length / len)+1; i++)
{
str += data.slice(i*len, (i+1)*len).map(p => p.toString().padStart(5, ' ')).join(" ") + "\n";
}
await AdventOfCode.outputIntermed(str);
AdventOfCode.outputConsole(data.map(p => p.toString()).join(" "));
}
AdventOfCode.output(DAY, PROBLEM, data.indexOf(2019).toString());
}
function parseLine(str: string): Cmd
{
const m0 = str.match(new RegExp('^cut (-?[0-9]+)$'));
if (m0 != null) return new Cmd(CmdType.CUT, parseInt(m0![1]));
const m1 = str.match(new RegExp('^deal into new stack$'));
if (m1 != null) return new Cmd(CmdType.DEAL, 1);
const m2 = str.match(new RegExp('^deal with increment ([0-9]+)$'));
if (m2 != null) return new Cmd(CmdType.DEAL, parseInt(m2![1]));
throw str;
}
enum CmdType { CUT, DEAL }
class Cmd
{
type: CmdType;
param: number;
constructor(t:CmdType, n: number) { this.type=t; this.param=n; }
}
}
```

**Result:**1252

**Part 2:**

```
namespace AdventOfCode2019_22_2
{
const DAY = 22;
const PROBLEM = 2;
export async function run()
{
const CARDS = 119315717514047n;
const SHUFFLES = 101741582076661n;
/*
NOTES
lcg skipping
https://www.nayuki.io/page/fast-skipping-in-a-linear-congruential-generator
cracking lcg
https://tailcall.net/blog/cracking-randomness-lcgs/
*/
let input = await AdventOfCode.getInput(DAY);
if (input == null) return;
const cmds = input
.split(new RegExp('\r?\n'))
.filter(p => p.trim().length > 0)
.map(p => parseLine(p));
let states = [];
let card_index = 0n;
for (let i=0; i<10; i++)
{
states.push(card_index)
card_index = getSourceIndex(card_index, cmds, CARDS)
}
AdventOfCode.outputConsole("[states]: " + states.join(" ; "));
const [modulus, multiplier, increment] = lcg_crack(states, CARDS);
AdventOfCode.outputConsole("[modulus]: " + modulus);
AdventOfCode.outputConsole("[multiplier]: " + multiplier);
AdventOfCode.outputConsole("[increment]: " + increment);
let r = lcg_skip(multiplier, increment, modulus, 2020n, SHUFFLES);
AdventOfCode.output(DAY, PROBLEM, r.toString());
}
function lcg_skip(a: bigint, b: bigint, m: bigint, x:bigint, skip: bigint): bigint
{
//let ainv = reciprocal_mod(a, m);
let a1 = a - 1n;
let ma = a1 * m;
let y = (modpow(a, skip, ma) - 1n) / a1 * b
let z = modpow(a, skip, m) * x
x = (y + z) % m
return x;
}
function modpow(base: bigint, exp: bigint, mod: bigint): bigint {
base = base % mod;
let r = 1n;
while (exp > 0n) {
if (base === 0n) return 0n;
if (exp % 2n === 1n) r = (r * base) % mod;
exp /= 2n;
base = (base * base) % mod;
}
return r;
}
function reciprocal_mod(x: bigint, mod: bigint): bigint
{
let y = x;
x = mod;
let [a, b] = [0n, 1n];
while (y !== 0n)
{
let _a = b;
let _b = (a-x) / (y * b);
a=_a; b=_b;
let _x = y;
let _y = x%y;
x=_x;y=_y;
}
if (x === 1n)
return a % mod
else
throw ("Reciprocal does not exist")
}
function getSourceIndex(idxDest: bigint, cmds: Cmd[], decklength: bigint)
{
let idx = idxDest;
for (let cmd of cmds.slice().reverse())
{
//AdventOfCode.outputConsole("[idx]: " + idx);
if (cmd.type === CmdType.CUT)
{
idx = (idx + cmd.param + decklength) % decklength;
}
else if (cmd.type === CmdType.DEAL && cmd.param > 1n)
{
let f = false;
for(let i=0n; i<cmd.param; i++)
{
if (((i * decklength + idx) % cmd.param) === 0n)
{
idx = (i * decklength + idx) / cmd.param;
f = true;
break;
}
}
if (!f) throw "--";
}
else if (cmd.type === CmdType.DEAL && cmd.param === 1n)
{
idx = decklength - idx - 1n;
}
else throw cmd;
}
return idx;
}
function lcg_crack(states: bigint[], modulus: bigint): [bigint, bigint, bigint]
{
const multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)
}
function crack_unknown_increment(states: bigint[], modulus: bigint, multiplier: bigint): [bigint, bigint, bigint]
{
const increment = (states[1] - states[0]*multiplier) % modulus;
return [modulus, multiplier, increment];
}
function egcd(a: bigint, b: bigint): [bigint, bigint, bigint]
{
if (a === 0n) return [b, 0n, 1n];
const [g, x, y] = egcd(b % a, a);
return [g, y - (b / a) * x, x];
}
function modinv(b: bigint, n: bigint): bigint
{
const [g, x, _] = egcd(b, n)
if (g === 1n) return x % n;
throw "rec";
}
function parseLine(str: string): Cmd
{BigInt
const m0 = str.match(new RegExp('^cut (-?[0-9]+)$'));
if (m0 != null) return new Cmd(CmdType.CUT, parseInt(m0![1]));
const m1 = str.match(new RegExp('^deal into new stack$'));
if (m1 != null) return new Cmd(CmdType.DEAL, 1);
const m2 = str.match(new RegExp('^deal with increment ([0-9]+)$'));
if (m2 != null) return new Cmd(CmdType.DEAL, parseInt(m2![1]));
throw str;
}
enum CmdType { CUT, DEAL }
class Cmd
{
type: CmdType;
param: bigint;
constructor(t:CmdType, n: number) { this.type=t; this.param=BigInt(n); }
}
}
```

**Result:**46116012647793