Figuring out the Spot It! algorithm

Whenever I play Spot It!, I find myself wondering how each card manages to share exactly one symbol with every other card. There must be an algorithm behind it; figuring out how to distribute the symbols manually would be a nightmare. (There are 57 total symbols, 8 on each card). Well, the other day, after a few games with my son, I sat down with a pencil and paper to figure it out.

Head scratching

I started by listing out all of the cards you could create using three symbols per card (each letter is a symbol and each line is a card):

A B C
A D E
A F G
B D F
B E G
C D G
C E F

That’s interesting, but wasn’t quite enough to figure out a pattern. I tried again with four symbols per card:

A B C D
A E F G
A H I J
A K L M
B E H K
B F I L
B G J M
C E I M
C F J K
C G H L
D E J L
D F H M
D G I K

Writing out these four-symbol cards manually was tough. I had to erase previous cards several times and triple-check each new card to make sure it shared exactly one symbol with all the others. But by the time I was done, I was starting to see the method to the madness.

Relating symbols per card to total cards (and total symbols)

First I figured out a formula for how many cards you can create with n symbols per card: (n * n) - n + 1. Basically, each of the n symbols on the first card will be used n times (n * n). However, one of those n times will be when all n of them appear on that first card, so we must subtract n (for the duplicates, including the first card) and then add 1 back (for the first card).

(n * n) - n + 1 is also the total number of symbols needed. If you add more symbols, you could also create more cards with only n symbols per card, but all of the cards would have to share the same symbol. (Prove this fact to yourself by trying to use extra symbols to add more cards to the three- or four-symbol examples above.)

The inverse of this formula can be used to go the other direction: if you want to create x cards, you’ll need at least sqrt(x - 3/4) + 1/2 symbols on each card.

(Based on this math, the real Spot It! game could have (8 * 8) - 8 + 1 = 57 cards, but it only has 55. Why? Your guess is as good as mine.)

The algorithm explained

From there, I stared at and played with my list of four-symbol cards until I began to see a pattern. Creating the first four cards is fairly straightforward. Make the first symbol on each card an A (vertical arrow below). Then fill in all of the remaining symbols on each card by proceeding through the alphabet (horizontal arrows below, from top to bottom).

     ---->
|  A B C D
|    ---->
|  A E F G
|    ---->
|  A H I J
|    ---->
v  A K L M

The rest of the cards are trickier, but viewing the first four cards as a grid helps to make sense of them. We’ll omit the first row and column of the grid (you’ll see why below), leaving us with the following:

E F G
H I J
K L M

Recall from the formula above that each of the n symbols on the first card will be used n times. We’ve already used the first symbol (A) all n (four) times. We’ve also used each the other symbols once, so we need to use them all n - 1 (three) more times.

We can start by creating the rest of the cards that contain B. Each of these three B cards must contain exactly one symbol from each of the A cards we already created. Additionally, the new B cards must not share any symbols with each other aside from B. Sharing a symbol with the first A card is a given since these three cards will each start with B. Sharing a symbol with the other A cards is accomplished by moving down the grid we constructed above, grabbing one letter from each row. For these cards, we simply move straight down the grid.

[E]F G --> B E H K
[H]I J
[K]L M

E[F]G  --> B F I L
H[I]J
K[L]M

E F[G] --> B G J M
H I[J]
K L[M]

We can do the same thing for the cards that start with C, but instead of moving straight down the grid, we move over by one each time we go down, wrapping around as needed.

[E]F G  --> C E I M
 H[I]J
 K L[M]

 E[F]G  --> C F J K
 H I[J]
[K]L M

 E F[G] --> C G H L
[H]I J
 K[L]M

And then we do it one more time for the cards starting with D, but we move over by two each time we go down.

[E]F G  --> D E J L
 H I[J]
 K[L]M

 E[F]G  --> D F H M
[H]I J
 K L[M]

 E F[G] --> D G I K
 H[I]J
[K]L M

This same process works for any number of symbols per card. Create the first n cards by starting each with the first symbol and filling in the remaining symbols left-to-right, top-to-bottom. Then, for each other symbol on the first card, create n - 1 more cards. Each starts with the symbol from the first card and contains one symbol from each of the remaining first-symbol cards, obtained by moving down and over (first by zero, then by one, then by two, etc.) in the grid. Each time the starting symbol changes, the amount by which to move over increases by one.

A demo

Once I’d figured out the algorithm, I had to write some code to generate cards, of course. I’ll explain the code shortly, but first use the controls below to try it out.

The algorithm as code

Now let’s take a look at the code. I start by creating the first n (symbolsPerCard in the code) cards. Each card is simply an array of numbers. (Previously I’ve represented symbols as letters. In the code, they’re numbers, starting from 0.)

const cards = new Array(symbolsPerCard).fill().map((_, c) => (
  new Array(symbolsPerCard).fill().map((_, s) => (
    s === 0
      ? 0
      : c * (symbolsPerCard - 1) + s
  ))
))

With four symbols per card, cards would be created as follows:

[
  [0, 1, 2, 3],   // A B C D
  [0, 4, 5, 6],   // A E F G
  [0, 7, 8, 9],   // A H I J
  [0, 10, 11, 12] // A K L M
]

Next, I create a grid of symbols.

// a grid with n - 1 rows...
const grid = new Array(symbolsPerCard - 1).fill().map((_, row) => (
  // ...and n - 1 columns...
  new Array(symbolsPerCard - 1).fill().map((_, col) => (
    // ...filled with the symbols after the last symbol in the first card
    symbolsPerCard + row * (symbolsPerCard - 1) + col
  ))
))

This grid is the same as the grid explained above. So with four symbols per card, the grid would look like so:

[
  [4, 5, 6],   // E F G
  [7, 8, 9],   // H I J
  [10, 11, 12] // K L M
]

Finally, we use the grid to add the remaining cards according to the algorithm described above.

// for each symbol in the first card (except the first symbol)...
for (let first = 1; first < symbolsPerCard; first++) {
  // ...create n - 1 cards...
  for (let card = 0; card < symbolsPerCard - 1; card++) {
    // ...filled with n symbols
    cards.push(new Array(symbolsPerCard).fill().map((_, symbol) => (
      symbol === 0
        // the first symbol in the card is the symbol from the first card
        ? first

        // the remaining symbols come from the grid -- one from each row, moving
        // along the columns for each move down the rows
        : grid[symbol - 1][(card + (first - 1) * (symbol - 1)) % (symbolsPerCard - 1)]
    )))
  }
}

The indexing to move down and over in the grid is a bit complicated. Indexing into the grid with symbol - 1 takes care of moving down a row for each symbol in the card. Then we start in the column corresponding to the card we’re on (card), and move over by an amount based on which symbol from the first card we’re using (first - 1; e.g., 0 for B, 1 for C, etc.). Each time we move to the next symbol in the card, we move over again (* (symbol - 1)). And we take care to wrap around as needed (% (symbolsPerCard - 1)).

And that’s it! There’s some extra code to convert the number symbols into letter symbols, but I won’t get into that here.

Testing the code

I can’t be sure that the card generation code is working unless I test it. And testing manually is tedious. So I wrote a test function as well.

The first test is simple: make sure that each card has the correct number of symbols.

for (const c of cards) {
  assert(c.length === symbolsPerCard, `expected len ${symbolsPerCard}, got ${c.length}`)
}

Next, make sure that none of the cards contain duplicate symbols. Sorting the symbols within each card makes it possible to check each card in linear time (after the O(n * log(n)) sorting…).

const sortedCards = cards.map(c => [...c].sort((a, b) => a - b))
for (const c of sortedCards) {
  assert(c.every((s, i) => s !== c[i - 1]), `duplicate symbols in card ${c}`)
}

Finally, make sure that each card shares exactly one symbol with each other card. Using the sorted cards from the last test case plus a two-pointer method to compare each pair of cards speeds things up again.

(I’ve been doing technical software engineering interviews lately… of course I’m thinking about efficiency.)

for (let i = 0; i < cards.length; i++) {
  for (let j = i + 1; j < cards.length; j++) {
    const cardI = sortedCards[i]
    const cardJ = sortedCards[j]

    let n = 0;
    let m = 0;
    let matches = 0;

    while (n < cardI.length && m < cardJ.length) {
      if (cardI[n] < cardJ[m]) {
        n++
      } else if (cardI[n] > cardJ[m]) {
        m++
      } else {
        matches++
        n++
      }
    }

    assert(matches === 1, `expected 1 match, got ${matches}: ${cardI} ${cardJ}`)
  }
}

If you want to try out the test code, you can run generate(<symbols per card>) in the dev console to create some cards. Then call test(<cards>, <symbols per card>) on the return value to run the tests. (For example, test(generate(4), 4).) It should print out all tests passed! when it’s done.

Notes & links

• According to a bit of online research I did after figuring things out myself, there’s some math with points and lines that explains the Spot It! cards. I thought briefly about points and lines on my own but wound up with the grid-based solution above instead.

• There appear to be places where you can play Spot It! online, although one that I tried didn’t work and the others wanted me to create an account. (No thanks!) Maybe someday I’ll make my own…