In an attempt to bolster my geek-fu and partially just out of curiosity, I’ve been learning the Microsoft functional programming language F#. It has been simultaneously frustrating and fun, as I struggle to bend my mind around functional concepts that are alien in the imperative world from which I hail.
As a fun project, I decided to implement a guessing strategy for the popular board game Clue, as proposed by Wired magazine in a recent article about teen “mathletes”:
The Task: Dr. Black has been murdered. Detective Jill must determine the murderer, crime scene, and weapon. There are six possible murderers (numbered 1 through 6, Professor Plum to Mrs. Peacock), 10 locations (1 through 10, ballroom to cellar), and six weapons (1 through 6, lead pipe to spanner). Detective Jill tries to guess the correct combination (there are 360 possibilities). Each guess is a theory. She asks her assistant, Jack, to confirm or refute each theory. When Jack refutes a theory, he reports that one of the guesses—murderer, location, or weapon—is wrong. The contestants are tasked with implementing a procedure that plays the role of Detective Jill. A brute-force program that tests all 360 theories earns a mere 50 points. An efficient program that tests no more than 20 theories earns an additional 50.
While I’m sure that my program is far from efficient, it was a good exercise for assembling the things I’ve been learning from the trivial examples in books and on the web.
It isn’t the shortest solution, but it would have earned the bonus 50 points because for any given theory, the program will only need to guess a maximum of ten times. The way I limit guesses is by walking through each combination of guesses in the form:
- guess1: suspect1, weapon1, room1
- guess2: suspect2, weapon2, room2 (we’ve identified the suspect)
- guess3: suspect2, weapon3, room3 (we’ve identified the weapon)
- guess4: suspect2, weapon3, room4
When the suspect, weapon, or room equals the suspect, weapon, or room of the theory, they “stick” and are used in each subsequent guess (see lines 38 and 25). Since there are more rooms (10) than suspects (6) or weapons (6), the number of rooms becomes the limiting factor on possible guesses.
If you’re a functional programmer, I’d love to hear your comments, suggestions, and criticisms, or maybe an implementation example in your language of choice.
EDIT: Just for clarity, in the code below “theory” represents the actual correct answer (I misread the instructions), while “guess” represents the current combination the program is testing. So when guess = theory, the program stops testing guesses.
module Clue open System //http://en.wikipedia.org/wiki/Cluedo let guess theory = let suspects = [| "Miss Scarlett"; "Colonel Mustard"; "Mrs. White"; "The Reverend Green"; "Mrs. Peacock"; "Professor Plum" |] let weapons = [| "Dagger"; "Candlestick"; "Revolver"; "Rope"; "Lead Pipe"; "Spanner" |] let rooms = [| "Kitchen"; "Ballroom"; "Conservatory"; "Dining Room"; "Cellar"; "Billiard Room"; "Library"; "Lounge"; "Hall"; "Study" |] let indexOf anArray anElement = Array.findIndex (fun e -> e = anElement) anArray let indicesOf aTheory = let (s, w, r) = aTheory ((indexOf suspects s), (indexOf weapons w), (indexOf rooms r)) let next g t = if g <> t then g + 1 else t let show guess = let s, w, r = guess printfn "%s with the %s in the %s" suspects.[s] weapons.[w] rooms.[r] let rec test guess theory = show guess if guess = theory then printfn "correct" else let (gs, gw, gr) = guess let (ts, tw, tr) = theory let newGuess = ((next gs ts), (next gw tw), (next gr tr)) test newGuess theory test (0, 0, 0) (indicesOf theory) //end guess let main = printfn "--------------------" let theory1 = ("Mrs. White", "Rope", "Kitchen") guess theory1 printfn "--------------------" let theory2 = ("Professor Plum", "Candlestick", "Lounge"); guess theory2 printfn "--------------------" let theory3 = ("The Reverend Green", "Spanner", "Ballroom"); guess theory3 printfn "--------------------" Console.ReadKey(true) |> ignore //end main main