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)