## Wednesday, January 13, 2016

### 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")))

(cond ([null? pile] #t)
((not [card-match? (car pile) card])
(else #f)))

(define (grow-pile pile size deck)
(cond ([= size 0] pile)
([null? deck] #f)
(else
(let ([card (car deck)])
(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)
```