I’ve left my blog untouched lately, a combination of being abroad and sheer lazyness. Anyway, I want to (briefly) wrap up my discussion of how I went about writing this mastermind-style guessing game. Last time I discussed in depth how I wrote the functions to compare a guess and an answer.
What I want to demonstrate is how we utilise those methods to create a computer player that will guess your hidden number. The algorithm is fairly simple: –
Human picks a four-digit number
Computer starts with a set of all 10,000 possibilities
Computer randomly guesses a number from the set of all remaining possibilities
Human tells Computer how many bulls and cows there were
If the answer is not correct, Computer compares all remaining possibilities against this response and reduces the set of possibilities accordingly.
If there is more than one possibility left, go back to step 3.
This routine is actually very simple. The only hard work really happens in step 5, yet we have already done the grunt work by writing our function previously to calculate bulls and cows from a given guess and answer, and we can reuse this e.g. let’s assume the secret number is 8100 and the computer guessed 3800. That gives us 2 bulls and 1 cow. Starting from the set of all possibilities, given a guess of 3800, how many numbers would give us 2 bulls and 1 cow
10,000 possibilities –> guess 3800 –> 2 bulls, 1 cow –> 80 possibilities –> etc. etc.
Again, this logic can be done using a simple filter i.e. for the set of all combinations, run the CompareGuess function against it using the supplied guess (3800) and see what the result is; if it matches it’s a possible answer, otherwise discard it.
This sort of approach will typically guess a 4-digit number in around 7 guesses.
This series of posts didn’t turn out quite how I intended… I wanted to illustrate how we can use F# to solve a problem using declarative code rather than imperative style for loops etc.; using stateless functions and recursion for Console runners etc. – but to be honest I would have had to spend much more time and posts going through it. But my blog is primarily a C# blog and I want to stick with that.
I hope though I showed that there is more than one way to think about problems like this – rather than thinking about everything as “go through each item in the list, do something to it, if its value is x then do something else” etc., you can see how simple functions like map (C# Select) etc. can be used to perform complex logic simply by chaining them up and using functions / lambda expressions.