This morning I played around with the end-game solution for Shut the Box. Part of the issue I had was the way I determined the end game in other languages was iterative. It would iterate through the list of tiles, subtract the current tile it was using, and then recurse through the list to find combinations that worked. eg: If the tiles [1 2 3 5 9] were present and I wanted to find out if the sum 6 could still be shut then it would check 9 (which is too big). It would then check 5 (which wasn't larger than 6) and then subtract 5 from the sum (to get 1) and then find the tiles that were equal to 1 (which is 1). So there was one solution in there, so it would exit upon finding the one solution).
Unfortunately in Racket this algorithm was a bit of a pain to generate. You can look at yesterday's end-game to see how well I did (hint: not great).
So I needed a different way to figure out if there was a solution. I happened upon the "Count the Coins" solution, which seemed to work. Unfortunately it assumes replacement so a list of tiles [1 2 3] would generate combinations for 6 that weren't correct ([2 2 2] and [1 1 1 1 1 1] for instance).
Back to the drawing board I went, and I happened upon this solution:
#lang racket
(define tiles '(1 2 3 4 ))
(filter (lambda (x) (eq? (apply + x) 6)) (cdr ( combinations tiles)))
What this does is creates combinations of the tiles (combinations tiles) and removes the first combination (which is '(), or the empty set. So (cdr (combinations tiles)) contain a list of the non-empty combinations.) it then filters out the combinations that sum up to the number we're looking for (6 in this case). That leaves us with the following output:
'((1 2 3) (2 4))
which are the combination of tiles that will get us to 6.
With that in mind the code now looks like this:
#lang racket
#| Init Block |#
(define tiles '())
(define die1 0)
(define die2 0)
(define turn-number 1)
(define took-turn #f)
(define end-of-game #f)
(define (start-game)
(set! tiles '(1 2 3 4 5 6 7 8 9)))
(define (dice)
(+ 1 (random 6)))
(define (dice-roll)
(set! die1 (dice))
(set! die2 (dice)))
(define (sum-of-dice)
(+ die1 die2))
(define (sum-of-tiles tilelist)
(apply + tilelist))
(define (list-check l1 l2)
(andmap (lambda (x) (not (boolean? (memq x l2)))) l1))
(define (shut-tiles tilelist)
(if (not took-turn)
(if (list-check tilelist tiles)
(for ([i tilelist])
(if (index-of tiles i)
(begin
(set! tiles (remove i tiles))
(set! took-turn #t))
(error "Tile already shut")))
(println "Tile not available to be shut"))
(println "Already took your turn")))
(define (check-roll dice-sum tile-sum)
(= dice-sum tile-sum))
(define (player-turn tilelist)
(if (check-roll (sum-of-dice) (sum-of-tiles tilelist))
(shut-tiles tilelist)
(println "Roll does not equal shut tiles. Try again.")))
(define (my-read-line)
(let ([contents (read-line)])
(if (string=? contents "")
(read-line)
contents)))
(define (input)
(map string->number (string-split (my-read-line))))
(define (next-turn)
(set! turn-number (+ 1 turn-number))
(set! took-turn #f)
(dice-roll)
(show-turn))
(define (show-turn)
(printf "Turn: ")
(println turn-number)
(println tiles)
(printf "Dice roll ~v ~v = ~v\n" die1 die2 (sum-of-dice) ))
(define (tile-combinations sum)
(filter (lambda (x) (eq? (apply + x) sum)) (cdr ( combinations tiles))))
(define (end-of-game-test sum)
(let ((combinations (tile-combinations sum)))
(println combinations)
(empty? combinations)
))
#| Main Loop |#
(start-game)
(dice-roll)
(let loop()
(show-turn)
(define tilelist (input))
(player-turn tilelist)
(next-turn)
(when (not (end-of-game-test (sum-of-dice))) (loop)))
I need to clean up the game loop some, but it actually plays a game of "Shut the Box" to completion. Better still, I could instrument the "tile-combinations" to provide a hint functionality so you can see which tile sets can be shut for a particular roll.
Ever onward!