Day 22: Slam Shuffle - Code
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 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?
The card at index x is y where
y = mx + b mod s,
s = size of deck
Initially, when the cards are 0, 1, 2, ..., 9, the cards can be defined by y = 1x + 0 mod 10. The first card (x = 0) is y = 0. Second position (x = 1) has y = 1, and so on.
Each technique takes the current formula y = mx + b and transforms it in some way.
If y = 1x + 0 mod 10 represents 0, 1, 2, 3, ...., and if the new stack technique makes 0, 1, 2, 3... to 9, 8, 7, ..., what happened to y = 1x + 0? It became y = -x - 1 mod 10. Remember that -1 mod 10 = 9, not -1. Read modular arithmetic intro below for more details.
What if there some other other card at the end? Say it was y = 3x + 7 mod 10, which returns 7, 0, 3, 6, 9, 2, 5, 8, 1, 4. Reversing y = 3x + 7 to y = -3x + 7 - 1 = -3x + 6 returns 6, 3, 0, ..., which is close but not correct. When x = 0, we want the last element to be first. I.e., at x = 0, we want y to be y(-1). The transformation can better be represented as
If y0 = mx + b, then
NewStack(y0) =
y1 = -mx + y0(-1)
= -mx + (-m + b)
= -mx + b - m
So for the y = 3x + 7 (7, 0, 3, 6, 9, 2, 5, 8, 1, 4) example, our equation y1 = -mx + b - m gives us y = -3x + 7 - 3 = -3x + 4, which returns 4, 1, 8, .... As desired!
export const newStack = (constant: bigint, slope: bigint, mod: bigint): [bigint, bigint] =>
[(constant - slope) % mod, -1n * slope]; // [b, m]This one is straightforward. Slope doesn't change, everything just gets shifted. We now want y(N) to be the first element, so we replace b in y = mx + b with y = mx + y(N) and work from there:
If y0 = mx + b, then
Cut(N)(y0) =
y1 = mx + y0(N)
= mx + (mN + b)
= mx + mN + b
Code:
export const cut = (n: number) => (constant: bigint, slope: bigint, mod: bigint): [bigint, bigint] =>
[(constant + BigInt(n) * slope) % mod, slope]; // [b, m]This also works for negative Ns.
Whatever the increment in, say inc = 3, you need to first figure out the form of y = mx + b. E.g.,
if 0 1 2 3 4 5 6 7 8 9, and inc = 3, then the set becomes
0 7 4 1 8 5 2 9 6 3
if you notice, slope = m = 7. That's because we know that if a number it at index i, it'll get moved to
i * inc % size = newIndex --> 3i % 10 = newIndex
E.g.,
i = 0 -> newIndex = 0
i = 1 -> newIndex = 3
i = 2 -> newIndex = 6
i = 3 -> newIndex = 9
i = 4 -> newIndex = 2
We want to know the CHANGE, the slope, and to do that, we need to solve what the old index was to get newIndex = 1. I.e., 3i % 10 = 1. What's i to get newIndex = 1?
We can split this up modularly:
3i % 10 = 1
3i % 10 = 1 % 10
3i ≡ 1 (mod 10)
We can figure out i using modular multplicative inverse (described in the appendix below).
We learn that 3i ≡ 1 (mod 10) returns i = 7. For the initial deck y = 1x + 0, this makes our deck y = 7x + 0 % 10.
What if there was already an existing slope? Say it was y = 7x + 0 to begin with, and we do another inc 3:
0 7 4 1 8 5 2 9 6 3
^ we increment that by 3 again to get
0 9 8 7 6 5 4 3 2 1
By observation, we can see that the slope = m = 9 now, which we can get by solving 3i ≡ 1 (mod 10) -> i = 7, and multiplying previous slope (7) with new slope (7) to get 49 % 10 = 9.
export const increment = (n: number) => (constant: bigint, slope: bigint, mod: bigint): [bigint, bigint] =>
[constant, (slope * solveLinCongruence(n, 1, mod)) % mod]; // [b, m]Straightforward. Parse and appply each technique, compounding the constant (b) and slope (m):
const toTechnique = (s: string) => {
if (s.indexOf('stack') >= 0)
return newStack;
if (s.indexOf('increment') >= 0)
return increment(Number(first(s.match(/-?\d+/g) ?? [])));
if (s.indexOf('cut') >= 0)
return cut(Number(first(s.match(/-?\d+/g) ?? [])));
throw new Error('Technique not found');
};
export const getSimulations = () => getRunsFromIniFile(input).map(ini => {
const header = ini.name.split(',');
const size = Number(header[1]);
const times = Number(header[2]);
const indicesOfInterest = header[3] === 'ALL' ?
Array.from({length: size}, (_, i) => i) :
header.slice(3).map(Number);
return {
name: header[0],
size,
times,
indicesOfInterest,
techniques: ini.content.split('\n').filter(s => s.trim() !== '').map(toTechnique)
};
});
export const applyTechniques =
(
// array of technique functions, where each returns [constant, slope]
techniques: ((constant: bigint, slope: bigint, mod: bigint) => [bigint, bigint])[],
size: number | bigint
) =>
(initConstant = 0n, initSlope = 1n) =>
{
let constant = initConstant;
let slope = initSlope;
const sizeN = BigInt(size);
for (let i = 0; i < techniques.length; i++) {
[constant, slope] = techniques[i](constant, slope, sizeN);
}
return { slope, constant };
};When we shuffle for the first time, we go from y0(x) = 1x + 0 to y1(x) = mx + b. Makes sense because
y0(0) = 0, y0(1) = 1, etc. The cards start off in order.
After we shuffle once, the card @ index = 0 is y1(0) = b, index = 1 is y1(1) = m + b, y1(2) = 2m + b, etc.
Now we're going to start at x = b (instead of x = 0 like we do for y0) to get y2, i.e., after shuffling twice
y2(0) = m * y1(0) + b = mb + b // card at index 0 after shuffling twice
y2(1) = m * y1(1) + b = m * (m + b) + b = m^2 + (mb + b)
y2(2) = m * y1(2) + b = m * (2m + b) + b = 2m^2 + (mb + b)
...
y2(x) = xm^2 + (mb + b)
What happens after we shuffle 3 times? Again, shuffle 3 will start off where shuffle 2 ended, so y2(0) is where y3 will start
y3(0) = m * y2(0) + b = m * (mb + b) + b = m^2*b + mb + b
y3(1) = m * y2(1) + b = m * (m^2 + mb + b) + b = m^3 + (m^2*b + mb + b)
y3(2) = m * y2(2) + b = m * (2m^2 + mb + b) + b = 2m^3 + (m^2*b + mb + b)
...
y3(x) = xm^3 + (m^2*b + mb + b)
Can be generalized for 
as follows:
Again, everything is mod'ed (%)
The new constant is a geometric series, which has a closed-form equation:
How do you ago about solving this? By using linear congruence again.
- First solve
- Solve for
xinAx ≡ B (mod m)using linear congruence like such:
Then, x will equal our new constant, and we got newSlope in step 1 above.
export const repeatShuffle =
(size: number) =>
(constant: bigint, slope: bigint, times: number) =>
(indexOfInterest: number) =>
{
const sizeN = BigInt(size);
const indexOfInterestN = BigInt(indexOfInterest);
const timesN = BigInt(times);
const slopePowerN = modExp(slope, timesN, sizeN);
const newConstant = solveLinCongruence(1n - slope, constant * (1n - slopePowerN), sizeN);
const inRange = (newConstant + indexOfInterestN * slopePowerN) % sizeN;
return Number((sizeN + inRange) % sizeN);
};const { constant, slope } = applyTechniques(s.techniques, s.size)();
const finalIndex = repeatShuffle(s.size)(constant, slope, s.times)(2020);
console.log(finalIndex);Topics include:
- Modular arithmetic introduction
- Extended Euclidean algorithm
Topics included:
- Terminology
- Modulo operator identities
- Fermat's Little Theorem
- Exponentiation by squaring
If you're new to the world of competitive programming, you may have noticed that some questions, typically combinatorial and probability questions, have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo 
". Like, it's not enough that they ask you to calculate a number they know will overflow basic integer data types, but now you need to apply the modulo operation after that? Even worse are those that say you need to calculate a fraction 
and ask you to output 
where 
... not only do you have to calculate a fraction with huge numbers, how in the world are you going to find x?
(for itnegers n and m) to always produce an integer between 0 and m-1 inclusively. This may or may not correspond to the expression n % m (In Javascript, it does not correspond!) % in Javascript is more like the remainder operator.
If your programming langauge returns -8 % 7 == 6, you're set. If it returns -1, you need to adjust it by adding m to any negative results. You can fix this in Javascript by doing
Number.prototype.mod = function(n) {
return ((this % n) + n) % n;
};Now you can replace all the x % y references with x.mod(y).
The mod operator has the lowest precedence (lower than addition and subtraction), but Javascript does not. Thus,
Again, this doesn't correspond with the precedence of the % operator.
This is a congruent statement. When you see 
, it reads that expr1 is congruent to expr2 in modulo m. I.e., it's a shortcut for:
But what about division and fractions? That's slightly more complicated, and requires a concept called the modular multiplicative inverse. The modular multiplicative inverse of a number a is the number 
such that 
. You may notice that this is similar to the concept of a reciprocal, but here we don't want a fraction; we want an integer, specifically an integer between 0 and m−1 inclusive.
How do you find such a number? Two fast ways to calculate the inverse:
- The extended Euclidean algorithm, and
- Fermat's Little Theorem
Though the extended Euclidean algorithm is more versatile and sometimes slightly faster, the Fermat's little theorem method is more popular.
The purpose of FLT is to find the multiplicative inverse of a in mod m. I.e., find the value of x such that
This allows us to solve equations like 
by doing
Or if you have to solve something like this:
FLT says that as long as the modulus m is a prime number, then
If 
results in 
, then 
must result in 1! Right? Because
must be true for FLT to hold.
Since now we know that 
, and we need that mod equation in the form 
, we just do
Thus, the mulplicative inverse of a in mod m is
This brings us to our next topic: how to quickly exponentiate a number in mod m.
The code below has plenty of comments describing how it works. It pretty much commutes 
:
// x^9 =
// a = x^4
// b = x^2
// c = x -> return x
// -> return c * c (equiv to x * x)
// -> return b * b (equiv to x^2 * x^2)
// -> return a * a * x (equiv to x^4 * x^4 * x = x^9)
// Another way to look at it:
// x^9 = x^4 * x^4 * x
// x^4 is calculated the same way: x^2 * x^2
const modExp = (base: bigint, power: bigint, mod: bigint): bigint => {
if (power === 0n)
return 1n;
if (power === 1n)
return base % mod;
let result = modExp(base, power >> 1n, mod); // power = Math.floor(power / 2)
result = (result * result) % mod;
// if power is odd, multiply it with base. E.g., 5^3 = 5^2 x 5^1.
// 5^2 is taken care of from the recursion
if ((power & 1n) === 1n)
result = (result * base) % mod;
return result;
};An iterative solution would be as follows:
const modExp = (base: bigint, power: bigint, mod: bigint) => {
let ans = 1n;
while (power > 0n) {
// if odd
if ((power & 1n) === 1n)
ans = (ans * base) % mod;
power = power >> 1n; // Math.floor(power / 2)
base = (base * base) % mod;
}
// even if power is like 4, power will eventually become 1, in which case
// ans = (1 * base^4) % mod, and that'll get returned
return ans;
};We now have the modulo field! I.e., 
field.
- The
stands for all positive and negative integers (
is all real numbers, 
is all rational numbers, and 
is all natural numbers (1,2,...,inf). - A field is just a fancy term from abstract algebra theory for a set with the four basic operators (addition, subtraction, multiplication, division) defined in a way that works just like you've learned in high-school for the rational and real numbers (however division by zero is still undefined).
- Thus,
is a fancy term meaning the set of integers from 0top-1treated as residues modulop.
This also means algebra works much like the way you learned in highschool. How do you solve 
? Pretend x is a real number to get 
The extended Euclidean is a more versatile method of determining the modulo multiplicative inverse than Fermats' Little Theorem (FLT), because FLT requires the mod to be a prime, whereas extended Euclidean only requires the a and mod to be relatively prime (or co-prime), i.e., gcd(a, m) = 1 must be true.
E.g., in ax ≡ 1 (mod m), if a = 7 and m = 10, FLT will fail in finding the inverse of a, but GCD extended will work because gcd(7, 10) = 1.
The basic Euclidean algorithm allows us to solve gcd(a, m), but the extended Euclidean algorithm allows us to solve for x and y such that
Basically, not only tell me the GCD of a = 30 and m = 20, but also tell me what do I need to multiply a = 30 with and m = 20 with to get the the GCD.
Since we've already verified that gcd(a, m) = 1, we can simplify our equation to
The value 
will always be equal to zero because we're multiplying the mod with some integer constant y, which gives us
As we know from grade school, when we divide one integer by another (nonzero) integer we get an integer quotient (the "answer") plus a remainder. For instance,
13/5 = 2 ("the quotient") * 5 + 3 ("the remainder")
More formally stated,
If a and b are positive integers, there exist integers unique non-negative integers q and r so that
a = qb + r, where 0 <= r < b
q is called the quotient and r the remainder.
The gcd of two integers can be found by repeated application of the division algorithm, this is known as the Euclidean Algorithm. You repeatedly divide the divisor by the remainder until the remainder is 0. The gcd is the last non-zero remainder in this algorithm. The following example shows the algorithm.
Finding the gcd of 81 and 57 by the Euclidean Algorithm:
- 81 = 1(
57)+24- 57 = 2(
24)+9- 24 = 2(
9)+6- 9 = 1(
6)+3- 6 = 2(
3)+0
It is known that if gcd(a, b) = r, then there exists integers p and s such that
By reversing the steps in the Euclidean Algorithm, it is possible to find these integers p and s. We shall do this with the above example. Starting with the next to last line, we have:
- 3 = 9 - 1(
6)- 3 = 9 - 1(24 - 2(
9))
= 3(9) - 1(24)- 3 = 3(57 - 2(
24)) - 1(24)
= 3(57) - 7(24)- 3 = 3(57) - 7(81 - 1(57))
= 10(57) - 7(81)
Thus, p = -7 and s = 10
The process of finding p and s is extended Euclidean algorithm. The whole idea is to start with the GCD and recursively work our way backwards. This can be done by treating the numbers as variables until we end up with an expression that is a linear combination of our initial numbers. We shall do this with the example we used above.