Advent of Code day 22 - 2019

Advent of Code Day 22

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:
      return dealWithIncrement(copy, action.payload);
    case CUT:
      const cut = Math.abs(action.payload);
      if (action.payload < 0) {
        // 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:
      const increment = action.payload;
      return (index * increment) % length;
    case CUT:
      const cut = action.payload;
      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:
      const increment = action.payload;
      return (index * increment) % length;
   case CUT:
      const cut = action.payload;
      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:
      const increment = action.payload;
      return (index * increment) % length;
    case CUT:
      const cut = action.payload;
      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:
      const increment = action.payload;
      // (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:
      const cut = action.payload;
      // 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, applym=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;

Calculate the AD matrix:

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!

Comments

[This Dot Media]

Thanks for sharing this with us 🙏😊