Well… it’s my third F# application really. The first was hello world, and the second was Roy Osherove’s TDD String Calculator Kata (I find that TDD for a known problem is a great way to slowly learn something bit by bit).
Anyway – I decided to try to write a fairly simple application in F# to help reinforce my understanding of F# – an implementation of Bulls and Cows. I actually did this in my first year of university in good old Modula2 many years ago, and figured it would be interesting to do it again all this time later in F#.
Disclaimer: The sum total of my F# knowledge is a Tomas Petriks’ excellent book, a two-day Skills Matter course, and a few days fumbling around in Visual Studio 2010. There are almost certainly better ways of doing what I’ve done below (and I’d be grateful for any suggestions 🙂
Speccing it out
Simply put, the objective of Bulls and Cows is for one player to think of a a 4-digit number and for the opponent to guess it. After every guess, the player has to tell the opponent how many numbers in the guess were in the correct position (bulls) and how many were in the wrong position. e.g. if the answer was 1234 and the guess was 1499, there would be one bull (the 1) and one cow (the 4).
The system should also be able to handle things like duplicate numbers on both sides e.g. if the answer was 1111 and the guess was 1999, there should only be one cow (not four); similarly if the answer was 1999 and the guess was 1111, there should still only be one cow.
What I wanted was for the computer to act as both player and opponent – when acting as the opponent, it should be able to intelligently guess the correct number.
I created a VS solution that ended up with four projects, although to be honest I did not create the last two until after I had 99% written the Core; F# interactive and my unit tests were enough to guide me to design and write the majority of the API.
Core – Contained the API to expose to the main runners (e.g. WPF / Silverlight / Console etc.), written in F#
Tests – Unit tests, written in C#
CSharpConsole – Console runner in C#
FSharpConsole – Console runner in F#
Breaking things into functions
Given the above requirements, I set about solving it in good old divide-and-conquer fashion, writing some unit tests as I went, although I ended up using F# Interactive for a lot of it. I can’t know for certain how much it helped, but I do know that using the REPL let me get through the development of the functions much quicker than both a test rig or unit tests alone would have done.
I broke it into a few main functions that I knew would be required, and then filled in the fluff around to make my API: –
Calculate the number of bulls given a guess and an answer
Calculate the number of cows given a guess and an answer
I know that that’s not really the TDD way of doing things (which prescribes top-down testing and development of your public API), but I wanted to get into the heart of the problem-solving side of things, and F#’s REPL makes it easy to do that; these two methods above are the core to doing anything, and all the public-facing functions delegate to these two.
So if we take the simpler scenario i.e. Computer thinks of an answer and the human guesses it, this is what the public facing API looks like: –
GenerateAnswer simply creates a random number between 0000 and 9999, stored as an array of integers e.g. .
CompareGuess is more interesting. It takes in two arrays of <T>, compares them, and returns an object which contains two properties i.e. the number of Bulls and Cows (aka exact & partial matches).
Notice that CompareGuess is generic i.e. it compares two arrays of <T> – in our application these are integers, but they could just as easily be string characters, and this code would work just fine. That’s because, when you think about it, all we’re really doing is comparing equality of two arrays of “things” – in our real console application they are numbers, of course. But because in F# by default everything is generic unless it’s clear that the argument must be e.g. an integer, we get the method as generic. That makes you think differently about the problem – it’s really just an array comparer.
Given those two methods, our console application can simply generate an answer, prompt the user to guess, and then repeatedly feed both that and the generated answer into the CompareGuess method until the user guesses the right answer. I’m not going to spend too much time talking about the console app at the moment – I’m much more interested in the routine which compares our hidden number with our guess and returns back the bulls and cows score.
Calculating the number of bulls
This method is fairly small, and looks as follows: –
It takes in two arguments, guess and answer. At the moment we don’t specify the type of them. We then do the following: –
Create an array from 0 to 3.
Apply a function over that array which returns a tuple of that number (index), plus the Boolean result of the isMatch function, which takes the two arguments and given positions e.g. guess versus answer, and returns a Boolean based on their equality.
We then filter out any that didn’t match.
We then return the indexes of those that did match.
So imagine we compare  against : –
1 against 1, isMatch = true
2 against 9, isMatch = false
3 against 3, isMatch = true
4 against 2, isMatch = false
We’d therefore return 1 and 3. Just in case you’re curious, isMatch is a simple function as follows: –
You’ll notice that I’ve had to tell the compiler that we’re dealing with arrays (hence the ), plus that T has to provide equality functionality so that we can do =. Aside for the comparison, it does one other very useful thing: It actually helps to put this as a function rather than inline inside getBulls, because of the awesome type inference of F# – once it sees that first and second are arrays of T, getBulls now knows that guess and answer must also be arrays of T etc. etc., hence why I do not specify the types in the getBulls function signature.
That’s enough for this post. Next time I want to cover the larger, and more difficult getCows method, and then how we compose them together to create the result object that our API returns.