Codesignal Solution: FaroShuffles

Original Problem

A faro shuffle is a method of shuffling playing cards that is often used by gamblers and magicians to manipulate a deck of cards. It works by splitting the deck into equal halves of 26 cards that are then interwoven perfectly.

When 8 faro shuffles are performed consecutively, a deck of 52 cards is always brought back to its original order. Imagine splitting the face-down deck in half, 26cards in each hand, and slowly interleaving them one after the other in a shuffle, with the bottom card in your right hand hitting the table first and the top card in your left hand on top once the shuffle is complete. Performed 8 times, the deck will return to its original state. Amazingly, this phenomenon works for any even deck size above 8, such that the original order can be restored if enough faro shuffles are done.
For this challenge, you should return the number of faro shuffles required to bring the given deck size back to its original order.

Example
For n = 8, the output should be
faroShuffles(n) = 3.
You have a deck of 8 cards, all of which are face down. Let's call the cards "a", "b", "c", "d", "e", "f", "g", and "h". Take the top half in your left hand and the bottom half in your right. Shuffle such that the new order is: "a", "e", "b", "f", "c", "g", "d", "h". Repeat ("a", "c", "e", "g", "b", "d", "f", "h"), and shuffle a third time to return the deck to its original order.

• [time limit] 4000ms (js)

• [input] integer n

  The number of cards in the deck. This is always an even integer.

  Guaranteed constraints:
  8 ≤ n ≤ 10⁴.

• [output] integer

  The number of faro shuffles required to return the deck to its original order.

Solution

Writing a routine which generates the shuffles is pretty straighforward:

var L = [["a"], ["b"], ["c"], ["d"], ...];

for (var r = 0; r < 10; r++) {
  for (var i = 0; i < L.length / 2; i++) {
    L[i * 2 + 0].push(L[i][r])
    L[i * 2 + 1].push(L[i + L.length / 2][r])
  }
}

Using the code, we can generate a table to analyze the pattern:

The first observation is that the first and last row never changes. After that it took quite some time to observe a pattern. But when taking a character, it's subsequent position is always doubled. That's a pretty nice pattern that evolves!

When the double process overflows a column with height \(n\), it starts at the top again, ignoring the last line. That means that a letter in row \(i\) will appear in row \(2i\mod{(n-1)}\) (maybe in the following column). It follows that a character from the first column at index \(i\) will appear in row \(i \cdot 2^k \mod{(n-1)}\) for column \(k>0\). What we try to find is when the expression is again in the same residual class as \(i\) itself, that means

\[i \equiv i \cdot 2^k \pmod{n-1}\]

Dividing both sides by \(i\) yields

\[1 \equiv 2^k \pmod{n-1}\]

That means we need to double 2 as long as it's residuum under \(\mod{(n-1)}\) is not 1. That can be implemented quite easily in JavaScript:

function faroShuffles(n) {

  var i = 2;
  var k = 1;
  while (i !== 1) {
    k++;
    i = 2 * i % (n - 1);
  }
  return k;
}

The rest is typical obfuscation stuff to minimize the code size by defining the function recursively:

_ = faroShuffles = (n, i=2) =>
  i < 2 || 1 + _(n, 2 * i % ~-n)