Mystery Solved: One Approach to Spot-It Game Card Generation

Spot-It is one of my go-to quick games for kids and adults alike. Many a wait at the pediatrician's office has been made that much more bearable thanks to this handy little game. While there are a few variations for playing it, they all involve the same basic strategy: the faster you can spot the match between any two Spot-It cards, the better. Which brings me to the cards:

The magic of the game is this: every card matches every other card exactly once. Take a moment and confirm this by looking at the cards above.

Every time I play Spot-It I think to myself: how the heck did that do that? And so after a rousing game a few weeks ago I decided I'd have to find out. And what better way to do so than to write some code to generate my own deck of cards?

And so began a multi-week saga in puzzling out a solution. I have to admit, the problem pretty much kicked my butt. If you look at the history of my code, you'll see all sorts of wrong headed attempts. From a random statistical solution, to mutating vectors full of vectors, I tried in vain to crack the problem. For the last few weeks our table has been covered in little scraps of paper, like so:

But I lived with the problem, and during last week's dentist cleaning, I had a bit of breakthrough. Luckily, I had to wait for Shira to finish up, and so that gave me some time in the waiting room to work on a solution. I can't imagine what the receptionist thought as I tore apart pages from my pocket notepad to create prototype cards. From there, I busted out my keyboard and coded up my new insights. Alas, that solution had flaws, but it took me in the right direction.

Finally, I realized I needed a solution that had a component of backtracking to it. Luckily, before I jumped in and implemented amb, and I discovered I could get this backtracking by using simple recursion. I finally figured out the the last iteration of a solution on a jog a few days ago, and then last night I typed it in. And voila!, I give you a generated set of Spot-It cards:

OK, the above uses numbers instead of funky symbols. But the core principle holds: each card (implemented as a list of numbers) matches each other card exactly once. The prettification of the output is left as an exercise to the reader.

I'm sure there's a much more elegant solution to this problem than mine. However, for now, I'm just enjoying that feeling that comes from living with, and ultimately conquering, a problem. Whoo!

And here's the code. The mystery to Spot-It card generation (or at least, one version) is revealed below:

;;
;; Not an actual programming praxis exercise, but it should be.
;; Implement the spot-it game card sequence
;;
;; Every card matches every other card in exactly one way
;;

#lang scheme

(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))

(define (make-symbol-generator)
  (let ([x 0])
    (lambda ()
      (set! x (inc x))
      x)))

(define (card-match? c1 c2)
  (cond ([null? c1] #f)
        ([null? c2] #f)
        ([member (car c1) c2] #t)
        (else (card-match? (cdr c1) c2))))

(define (make-deck n sym-gen)
  (if (exact? (sqrt n))
      (apply append
             (for/list ([i (sqrt n)])
               (let ([sym (sym-gen)])
                 (for/list ([j (sqrt n)])
                   (list sym)))))
      (error "Deck size must a perfect square")))
  
(define (can-add-to-pile? card pile)
  (cond ([null? pile] #t)
        ((not [card-match? (car pile) card])
         (can-add-to-pile? card (cdr pile)))
        (else #f)))

(define (grow-pile pile size deck)
  (cond ([= size 0] pile)
        ([null? deck] #f)
        (else
         (let ([card (car deck)])
           (if (and (can-add-to-pile? card pile)
                    (grow-pile (cons card pile) (dec size) (cdr deck)))
               (grow-pile (cons card pile) (dec size) (cdr deck))
               (grow-pile pile size (cdr deck)))))))


(define (remove-pile-from-deck pile deck)
  (filter (lambda (card)
            (not (memq card pile)))
          deck))

(define (match-pile pile sym-gen)
  (let ([sym (sym-gen)])
    (map (lambda (card)
           (cons sym card))
         pile)))

(define (done? deck)
  (let loop ([cards deck])
    (cond ([null? cards] #t)
          (else
           (if (andmap (lambda (c)
                         (card-match? c (car cards)))
                       deck)
               (loop (cdr cards))
               #f)))))

(define (tick deck sym-gen)
  (let ([psize (sqrt (length deck))])
    (let loop ([i 0] [deck deck] [piles '()])
      (cond ([= i psize]
             (apply append (map (lambda (p)
                                  (match-pile p sym-gen))
                                piles)))
            (else
             (let ([pile (grow-pile '() psize deck)])
               (loop (inc i)
                     (remove-pile-from-deck pile deck)
                     (cons pile piles))))))))

(define (go size)
  (let ([sym-gen (make-symbol-generator)])
    (let loop ([deck (make-deck size sym-gen)])
      (cond ([done? deck] deck)
            (else
             (loop
              (tick deck sym-gen)))))))
  

(go 9)
(go 16)