DEV Community

Joseph

Posted on • Updated on

Advent of Code day 22 - 2019

Using JavaScript to calculate the position of a card on a deck with a total of 119 315 717 514 047 cards after shuffling it 101 741 582 076 661 times.

The problem statement in length can be found here.

The problem

The input for the problem consists of a list of shuffling instructions, to be done on a card deck. The deck is defined by its length.

The cards are numbered from `0 to length - 1` and are initially ordered in ascending order.

There are three types of shuffles, NEW STACK, INCREMENTAL or CUT.

• NEW STACK takes no parameters, which is itself a type of parameter.
• INCREMENTAL and CUT take in a defining parameter

One could say that NEW STACK takes in an undefined parameter

Part 1 requires to you to find out the position of card 2019 after one shuffle on a deck of length `10007`.

Part 2 requires to you to find out which card is at position `2020` after a very large number of shuffles, on a very large deck.

Part 1

Easy enough, we can define a reducer, which goes over the list of shuffle instructions, pattern matching against them, collects the parameter of each instruction, and does the work on the deck.

The shuffle parameter is referred to as payload from now on.

``````const reducer = (deck, action) => {
const copy = [...deck];
switch (action.type) {
case NEW_STACK:
return copy.reduce((prev, curr) => [curr, ...prev], []);
case INCREMENT:
case CUT:
// cut from the bottom to the top
const offset = copy.length - cut;

return copy
.slice(offset)
.concat(copy.slice(0, offset))
.flat();
}

return copy
.slice(cut)
.concat(copy.slice(0, cut))
.flat();
}
};
``````

Where the deal with increment is defined as:

``````const dealWithIncrement = (deck, increment) => {
let newDeck = [];
let pointer = 0n;
let index = 0n;

while (index < BigInt(deck.length)) {
newDeck[pointer % deck.length] = deck[index];

pointer = pointer + increment;
index = index + 1n;
}

return newDeck;
};
``````

Because part 2 deals with large integers, begin to use `BigInt` notation as early as possible.

Although verbose, it is easy to follow. We just need to create a deck array of length `10007`, parse the shuffling instructions.

``````const newDeck = actions.reduce((prev, curr) => reducer(prev, curr), [...deck]);
``````

Where the actions array is the result of matching all instructions in the problem input. Notice that this step parses the payload into `BigInt`.

``````const NEW_STACK = "deal into new stack";
const INCREMENT = "deal with increment";
const CUT = "cut";

const instructions = data.split("\n");

const actions = instructions.map(instruction => {
if (instruction.includes(NEW_STACK)) {
return { type: NEW_STACK, payload: null };
}
if (instruction.includes(INCREMENT)) {
const [increment] = instruction.split(" ").slice(-1);
return { type: INCREMENT, payload: BigInt(increment) };
}
if (instruction.includes(CUT)) {
const [cut] = instruction.split(" ").slice(-1);
return { type: CUT, payload: BigInt(cut) };
}
});

``````

After running this code, we just need to read the index `2019` in the `newDeck`. In my case that's `7860`.

This solution is very slow. Part 2 uses a deck with length `119_315_717_514_047n`. This approach won't cut it!

Using the index

We do not need a representation of the whole deck after a shuffle, we just need to be able to calculate the output index, given an input index.

Let's start naively with the following `indexReducer`, which still yields `7860` for `2019`, for the same actions.

``````const indexReducer = length => (index, action) => {
switch (action.type) {
case NEW_STACK:
const middle = length % 2n === 0n ? (length - 1n) / 2n : length / 2n;
if (index !== middle) {
return middle + (middle - index);
}
return index;
case INCREMENT:
return (index * increment) % length;
case CUT:
if (cut < 0n) {
if (index < cut) {
return index - cut;
}
return index - length - cut;
} else {
if (index < cut) {
return index + length - cut;
}
return index - cut;
}
}
};
``````

The INCREMENT case is the most straight forward. We can definitely improve the NEW STACK and CUT cases.

In the NEW STACK, we notice that the new index is always the `length - 1 - index` , for odd lengths, which is true for both part 1 and part 2.

Finally the CUT case seems to depend on the sign of the payload. However, when one inspects the branches realizes that the result is always of form `index - cut ยฑ length`.

``````const indexReducer = length => (index, action) => {
switch (action.type) {
case NEW_STACK:
return length - 1n - index;
case INCREMENT:
return (index * increment) % length;
case CUT:
if (cut < 0n) {
if (index < cut) {
return index - cut;
}
return index - length - cut;
} else {
if (index < cut) {
return index + length - cut;
}
return index - cut;
}
}
};

``````

One should observe that the indexes are always in the range between `0` and `length - 1`.

Indexes higher that `L` are not possible...

In practice, this means that the results of `indexReducer` should always be transformed to the said range.

Proof of this is that the INCREMENT case always calculates the remainder of `index * increment` over the `length`.

Can a card index be greater than or equal to the number of cards? Pro-tip: It can't be.

We should do this for every case in the reducer. The NEW STACK operation should never yield more than `length`, so we can leave it as is.

We move on to the CUT case, and see that after applying remainder operation the possible outputs given by `index - cut ยฑ length` transform to `index - cut`.

The new reducer then looks like this:

``````const indexReducer = length => (index, action) => {
switch (action.type) {
case NEW_STACK:
return length - 1n - index;
case INCREMENT:
return (index * increment) % length;
case CUT:
return index - cut;
}
};
``````

By this point we've gained a lot of speed when running the shuffling once, regardless of the deck's `length`.

The remainder `%` operations is also known as modulo.

There's one caveat. We've implied that `(x - L) % L` returns a valid index when doing the CUT case. In JavaScript, this does not hold for negative numbers.

``````> (-4 - 5) % 5
-4
``````

Meanwhile, Python does the type of modulo we need:

``````>>> (-4 - 5) % 5
1
``````

To overcome this, define the modulo operation like this:

``````const mod = length => val => {
if (val < 0n) {
return length - mod(length)(-val);
}
return val % length;
};
``````

Perhaps the greatest piece of insight, is that, on each case, the `indexReducer` modifies its input index by a factor, and then adds or subtracts from it.

One can represent this initial condition as `index = card`, and then every case will modify this, for example, NEW STACK produces `index = -card + length - 1`.

Next, passing this through INCREMENT give us `index = increment * (-card + length - 1) % length`, which simplifies to, `index = -increment * card % length + length - 1`, making sure that we simplify `-1` to `length - 1` (modulo of `-1` over `length`).

Finally if we apply the CUT case `index = (-increment * card % length + length - 1) - cut) % length`, one must not forget to take modulo for all the results, which simplifies the expression to, `index = -increment * card % length + (length - 1 - cut) % length`.

These are all linear transformations!

The order in which these are done, doesn't matter. We'll never have index squared, and we can always simplify to a `y = mx + b` shape! Fantastic! That means that given the initial mapping where `n` sits at index `n`, represented by the identity functions, written as `y = 1 * x + 0`, we can calculate `m` and `b` after a shuffle!

We need to find how `m,b` change after a shuffle. In the `indexReducer` we replace index by `mx` and the constant terms are by `b`.

``````const linearEqReducer = length => ([m, b], action) => {
// index = m * x + b
// with inputs [m,b];
switch (action.type) {
case NEW_STACK:
// - index * length - 1n
// - (m * x + b) + length - 1n
// - m * x + length - 1n + b
return [-m % length, (length - 1n + b) % length]; // always take % length
case INCREMENT:
// (index * increment) % length;
// ((m * x + b) * increment) % length;
// (m * increment * x) % length + (b * increment) % length;
return [(m * increment) % lenght, (b * increment) % length]; // always take % length
case CUT:
// m * x + b - cut;
// (m * x) % length + (b - cut) % length
return [m % length, (b - cut) % length]; // always take % length
}
};
``````

Math to the rescue

Treating the shuffle as a black box, call it `f`, which takes in `m,b` as inputs, and returns `m',b'`:

If we represent the inputs as a vector `v`:

If the transformations are linear, it must be true that, there's a matrix `A`, such that:

Next, to calculate 2 shuffles, looks like this:

Or better yet:

And in general, for `n` shuffles:

Then one can easily calculate the matrix `A` to the power of `n`, using the binary exponentiation technique.

To pull this off, write the binary representation of your target number, for instance 13 is `1101`. Move from right to left, starting with `1` and then multiplying by `A` at every step.

Then filter out the products which were created under a zero digit.

Finally, we multiply all of the leftover products.

Enough Math for now. A JavaScript implementation looks like this:

``````const binaryExp = length => (
number,
seed,
prod = (x, y) => (x * y) % length,
identity = 1n
) => {
const binary = number
.toString(2)
.split("")
.reverse();

return binary
.reduce(
prev => {
const [last] = prev.slice(-1);
return [...prev, prod(last, last)];
},
[seed]
)
.filter((_, i) => binary[i] === "1")
.reduce((prev, curr) => prod(prev, curr), identity);
};
``````

This function takes `length`, to handle modulo operations as matrices are multiplied. It returns a function with closure over the `length`.

This function, in turn, optionally takes product function, as well as, an identity to be used. When using matrices products the identity should be the identity matrix. If no `prod` is passed, then this function calculates binary exponentiation for numbers, and the identity defaults to `1`.

The `binExp` function returns a function which, multiplies `seed` as many times as binary digits exist in number, and then collects a product that is `seed ^ number`, in a very fast and efficient way, `O(log n)`.

We can now shuffle a large number of times, with `log n` complexity, as long as we can find the `A` matrix. Here I initially made a mistake. I assumed `A` to be `2x2` matrix.

Looking back, this should have been easily spotted, because the `indexReducer` and `linearEqReducer` clearly show that the variations of `m` and `b` are independent of each other. A matrix of `2x2` implies the opposite!

This is wrong. A better way is to say `A` is the matrix that applies to `m`, and `D` the matrix that applies to `b`. The sub vector `m` now equal to `M0` and sub vector `b` equal to `B0`.

From the `linearEqReducer`, we see that `m` is always a multiplication `p*m`. With this we simplify `A`. Also, every new `b` value, depends only on `b` and not `d`, so `j` must be `0`.

Apply `m=1` and `b=0` to the `linearEqReducer`, and to obtain `p` and `h*d`:

``````const [p, hd] = actions.reduce(
(prev, action) => linearEqReducer(length)(prev, action),
[1n, 0n]
); // h * d
``````

And, then, apply`m=0` and `b=1`, this time the first value can be ignored.

``````const [, gh] = actions.reduce(
(prev, action) => linearEqReducer(length)(prev, action),
[0n, 1n]
); // gh is g * b + h * d
``````

Calculate `g * b` by doing `gh - hd = g * b + h * d - h * d = g * b`. Knowing that `b` equals `1`, we now have `g`.

Moreover, when we shuffle for `1 * x + 0` we take the initial deck and shuffle it once into `m * x + b` so `hd` is the next `b`. If we want `d` to be constant, then `k * d = d` then `k = 1`.

We notice that the `d` value is arbitrary, and different than `0`, as long as we can simplify `hd = h * d` to `h = hd / d`. The easiest is for `d=1`. The value `c` is also arbitrary, and given the shape of `A`, we can just set it to `0`.

Where `g = gh - hd` and `h = hd` derived from:

``````const [p, hd] = actions.reduce(
(prev, action) => linearEqReducer(length)(prev, action),
[1n, 0n]
);

const [, gh] = actions.reduce(
(prev, action) => linearEqReducer(length)(prev, action),
[0n, 1n]
);
``````

Replacing all matrices, the `M,B` vectors after a shuffle follow this equation.

Part 2

Finally! We run:

``````const large = 119_315_717_514_047n;
const [p, hd] = actions.reduce(
(prev, action) => linearEqReducer(large)(prev, action),
[1n, 0n]
);
const [, gh] = actions.reduce(
(prev, action) => linearEqReducer(large)(prev, action),
[0n, 1n]
);

const h = hd;
const g = gh - hd;
``````

``````const AD = [
[p, 0n, 0n, 0n],
[0n, 0n, 0n, 0n],
[0n, 0n, g, h],
[0n, 0n, 0n, 1n]
];
``````

Do binary exponentiation for `101_741_582_076_661n`:

``````const dotProduct = length => (left, right) => {
let result = [];
for (let i = 0; i < left.length; i++) {
result[i] = [];
for (let j = 0; j < right[0].length; j++) {
let sum = 0n;
for (let k = 0; k < left[0].length; k++) {
sum += (left[i][k] * right[k][j]) % length;
}
result[i][j] = sum % length;
}
}
return result;
};

const matrixMult = dotProduct(large);

const I = [
[1n, 0n, 0n, 0n],
[0n, 1n, 0n, 0n],
[0n, 0n, 1n, 0n],
[0n, 0n, 0n, 1n]
];

const total = 101_741_582_076_661n;
const matrix = binaryExp(large)(total, AD, matrixMult, I);
``````

In the above, we define a `matrixMult` which does the dot product of two matrices, while taking modulo of `large` on every multiplication and sum performed.

``````const [[M_], , [B_]] = matrixMult(matrix, initial);
const largeNormalizer = mod(large);
const M = largeNormalizer(M_);
const B = largeNormalizer(B_);
``````

And now have a formula to calculate the `index = card * M + B` after `101_741_582_076_661n` shuffles on a deck with `119_315_717_514_047n` cards.

There's just one issue. The problem requires to know which card ends up at index `2020`.

That is, we need to solve for x in: `y - b = m * x`, or `(index - B) % length = M * card`, and solve for the card.

"Problems worthy of attack prove their worth by fighting back." โ Piet Hein

One can just start to increase card until the expression `(M * card) % length = (index - B) % length` holds true, but that will take any time between `0` and `length`.

Up to this point the fact that `10007n` and `119_315_717_514_047n` are primes has not been used. We want to solve, with `L=length`:

Since `r` is less than `L`, we can rewrite like this:

If `M` is less than the prime `L` then all possible values of `n % L` contains `M`. Also, all natural numbers less than `L` are part of the set of `n % L`.

Although the syntax might be confusing, this just means that all possible results of `M%L` are contained in the set `N`.

If we limit `M` to `M < L`, so that we can eliminate `0` from `N`. Then we can multiply any `n` of `N` by a number less than prime `L`, call it `Q`, and take modulo of the result.

This will generate the same set `N`, albeit, in a different order, `N'`. Remember that `Q` would also be part of `N`.

We can be sure that `N` and `N'` are the same set, but with different order, because:

• `Q` and `n` are both greater than `0`, but less than prime `L`, so their product can never divide `L`, so none of `N'` elements is zero.
• Any `n * Q`, for example `2 * Q` exists only once, and therefore each modulo is unique. This implies the same number of elements in both sets.

In turn this means that multiplying members of both groups and taking modulo of each product, should be equal.

Again, since each factor of factorial `L-1` is less than `L`, we can simplify the factorial on both sides.

This is called Fermat's Little Theorem. Replacing `Q` for `M` and expanding:

We have found the inverse modulo of `M` modulo `L`. This means, that `x'` is `M ^ (L-2)`.

Replacing back in the original formula:

Calculate `M^(L-2)` using the binary exponentiation once again.

``````const fastModInv = length => m => {
return binaryExp(length)(length - 2n, m);
};

const large = 119_315_717_514_047n
const modInverter = fastModInv(large);
const x_inv_mod = modInverter(M_large);
const r = 2020n - B_large;
const largeNormalizer = mod(large);
const card = largeNormalizer(x_inv_mod * r);
``````

And it is done! Full code here.

Summary

• Model a shuffle as a black box that takes an index and outputs a new index.
• Realize that the black box is a linear transformation on an input equation.
• Use a Matrix to model the linear transformation.
• Use binary exponentiation to calculate the Matrix that represents a large number of shuffles.
• Calculate the linear equation resulting of multiplying the identity linear equation with the Matrix.
• Use Fermat's little theorem and binary exponentiation to calculate the inverse modulo.

I solved this problem at around midnight on my local time zone. It was super challenging for me, but I pushed through.

Happy hacking!