shuffle

Back in 2012 or so, I stumbled upon this article from Mike Bostock. I loved how visually-interactive it was. As a nod to the article, here's another form of it.

If you were to ask me back then how I'd shuffle a deck of cards, I'd probably do the same mistake mentioned in the article above. Consider this code below:

inefficientShuffle

function inefficientShuffle() {
  const cards = getCards();
  const shuffled = [];
  const picked = [];

  while (shuffled.length < cards.length) {
    const idx = Math.floor(Math.random() * cards.length);
    picked.push(idx);
    if (!shuffled.includes(idx)) shuffled.push(idx);
  }

  return { shuffled, picked };
}

The very naive approach was indeed to have a list of cards, then pick a random one and inserts it into a shuffled list, if it's not already there. Here's how the code looks like, visualized:

If we inspect the shuffled and picked output above, picked would most likely be a bigger list than shuffled, due to the chances of picking the card that's already shuffled over and over, as seen in the visualization above.

The article suggests an obvious fix: shrink the cards after picking a random card.

splicedShuffle

function splicedShuffle() {
  const cards = getCards();
  const shuffled = [];

  while (cards.length) {
    const pick = Math.floor(Math.random() * cards.length);
    shuffled.push(cards[pick]);
    cards.splice(pick, 1);
  }

  return shuffled;
}

Makes sense. But! There's an even better way: the Fisher-Yates shuffle.

fisherYatesShuffle

function fisherYatesShuffle() {
  const cards = getCards();
  const swaps = [];
  let cursor = cards.length;

  while (cursor) {
    const pick = Math.floor(Math.random() * cursor--);
    swap(cards, pick, cursor);
    swaps.push([pick, cursor]);
  }

  return swaps;
}

function swap(cards, before, after) {
  [cards[before], cards[after]] = [cards[after], cards[before]];
}

function getSteps() {
  const swaps = fisherYatesShuffle();
  const steps = [];
  const cards = getCards();

  swaps.forEach(([pick, cursor]) => {
    const picked = cards[pick];
    const settled = cards[cursor];
    const pickedCard = lineCards[picked];
    const settledCard = lineCards[settled];

    steps.push(highlight(pickedCard));

    if (picked !== settled) {
      steps.push(
        Canvas.parallel(
          Canvas.moveTo(
            [pickedCard],
            { x: rowX(cursor) },
            { duration: SHUFFLE },
          ),
          Canvas.moveTo(
            [settledCard],
            { x: rowX(pick) },
            { duration: SHUFFLE },
          ),
          setPicked(pickedCard),
        ),
      );
    } else {
      steps.push(setPicked(pickedCard));
    }

    swap(cards, pick, cursor);
  });

  return steps;
}

render(getSteps());

Instead of shrinking the list of cards, swap the last unshuffled card with the one we just picked. The next shuffle would ignore that anyway, so in a way, the list of cards still shrinks all the same. But, more efficient. And in this case, cards itself is the output, due to the shuffling happened in-place.

shared helper

const CARDS_COUNT = 60;
const CARD_HEIGHT = 50;
const CARD_WIDTH = 2;
const SPACING = 6;
const Y_SHIFT = 100;
const COLOR = { r: 224, g: 122, b: 95 };
const COLOR_HIGHLIGHT = { r: 255, g: 25, b: 25 };
const COLOR_PICKED = { r: 229, g: 163, b: 163 };
const DECK_WIDTH = (CARDS_COUNT - 1) * (SPACING + CARD_WIDTH);
const START_X = (width - DECK_WIDTH) / 2;
const START_Y = (height - CARD_HEIGHT) / 2;
const SHUFFLE = 100;
const HOLD = 800;

function getCards() {
  return Array.from({ length: CARDS_COUNT }, (_, idx) => idx);
}

function rowX(i, count = CARDS_COUNT) {
  return (width - ((count - 1) * SPACING + CARD_WIDTH)) / 2 + i * SPACING;
}

function setPicked(lineCard) {
  return Canvas.tween(
    [lineCard],
    { color: COLOR_PICKED },
    { duration: SHUFFLE },
  );
}

function highlight(lineCard) {
  return Canvas.sequence(
    Canvas.tween([lineCard], { color: COLOR_HIGHLIGHT }, { duration: SHUFFLE }),
    Canvas.tween([lineCard], { color: COLOR }, { duration: SHUFFLE }),
  );
}

function render(shuffleSteps) {
  const layers = Canvas.layer(
    lineCards,
    Canvas.sequence(...shuffleSteps, Canvas.wait(HOLD)),
  );

  const scene = new Canvas.Scene({ canvas, layers });

  loop((t) => scene.render(t));
  scene.onFinish(() => reset());
}

const lineCards = getCards().map((idx) => {
  const xOffset = idx - CARDS_COUNT / 2;
  const height =
    Canvas.easeInOutSine(1 - Math.abs(xOffset / CARDS_COUNT)) * CARD_HEIGHT;

  const x0 = rowX(idx);
  const y0 = START_Y + CARD_HEIGHT - height;

  return Canvas.path({
    x0,
    x1: x0 - xOffset,
    y0,
    y1: y0 + height,
    color: COLOR,
    lineWidth: CARD_WIDTH,
  });
});

@briwa.dev/canvas@1.6.1

https://cdn.jsdelivr.net/npm/@briwa.dev/canvas@1.6.1/dist/index.iife.js