My first F# application – part 2


In my previous F# post, I discussed the problem and first section of the solution to Bulls and Cows in F#. In this post, I want to discuss the algorithm to solving the function which retrieves the total number of cows (partial matches) when comparing a guess to an answer.

Function definition by tests

To my mind, there are a few test cases that we can use to validate the method: –

Case Answer Guess Partial matches
Single partial 1000 9991 1
Many partials 1200 9921 2
Duplicates 1000 0999 1
Exact match 1000 1199 0

Any items in green indicate a valid partial match. Those in yellow indicate false positives i.e. those that appear to be partial matches but aren’t.

Given those tests as a template, Let’s start by taking some example data: –

Guess: 1234

Answer: 1313

In this example, we have just 1 cow, which is the 3rd index of the guess (3) against the 2nd index of the answer. It should not match it again against the fourth index of the answer. Similarly, we should not match the first index of the guess (1) against the 3rd index of the answer as it already matches as a bull.

Building the comparison matrix

The first step I did was to build a set of guess / answer indexes that we should compare with one another. This is essentially a 4×4 matrix where we eliminate any indexes that are either:

  • The same index on both guess and answer (which would be a bull)
  • Comparing against an index which is already known to be a bull

This second point means that before we calculate the cows, we must have already calculated the bulls for this guess / answer pair. So taking the above example, we can assume that we know that index 0 is a bull. Our function getCowCount() should therefore should take in the guess, answer, and what I can the ignoreList of bull indexes. It should return a single number which is the total number of cows found.

The first stage is to write a function which, given the ignore list, should build up a sequence of index pairs (guess, answer) to use for comparisons based on the remainder of the 4×4 matrix e.g. for our scenario above: –

0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3
3,0 3,1 3,2 3,3
  • Items in red indicate exact matches (bulls) and should be ignored
  • Items in yellow indicate those which compare against a bull index (0) and should be ignored
  • Items in green indicate valid comparison indexes

This leaves us with just six indexes to compare against. So how do we construct this set in code?

image

buildCheckMap() takes in the ignoreList mentioned earlier – in our sample, a sequence with just the value 0 in it (i.e. index 0 of the guess is a bull, so we should ignore it from our calculations in this function).

We first construct a set of numbers [0;1;2;3] and take the difference from any numbers in the ignoreList, which in our example leaves us with [1;2;3] which is then bound to uncheckedPositions. Then we pipe this sequence into a series of functions.

The first maps the sequence against itself, except that we ignore elements where the guess and answer index are the same i.e. a bull. So we end up with a sequence something like: –

  • 1, ([2;3])
  • 2, ([1;3])
  • 3, ([1;2])

Notice that the each element of the result is actually a tuple containing two parts – a single index e.g. 1, plus an array of indexes to compare against e.g. 2;3.

The next line flattens this sequence out so we get a set as follows: –

  • 1,2; 1,3
  • 2,1; 2,3
  • 3,1; 3,2

Now we have an sequence of sequence of tuple pairs. The last line simply flattens this out into a single sequence: –

(1,2); (1,3); (2,1); (2,3); (3,1); (3,2)

Performing the comparison

All that we’ve done so far is to build up a set of indexes that we should be comparing against each other. The next stage is to use this list on our isMatch function that we defined in the previous post, and return the total of all the matches as a single number. Here’s the function listing for getCowCount().

image

Again, it’s really just piping sequences of data from one function into another. This is nothing dramatically different from extension methods in C# and Linq; it’s just that we’re doing it a little more here Smile

The first line gets our result set of pairs to check as already discussed.

Then we push each pair into the isMatch function and return a tuple containing the result of the comparison and the guess value that was checked, so we get back: –

[(false, 2); (false, 2); (true, 3); (true, 3); (false, 4); (false, 4)]

In other words, we compared the value 2 against two answer indexes and both were not matches; we compare “3” against two answer indexes and both matched; and compared “4” twice and neither matched.

We then filter out any that didn’t match. This leaves us with just the two instances of “3”. At this point, it appears as though the value “3” is a cow twice. However, we still need to discount duplicates as described in our test cases. The easiest way to do this is to get the total number of occurrences of this number in both the guess and answer, and take the lesser of the two.

We therefore group up the sequence by each item’s value – as all the numbers in our sequence are “3”, we get a single grouping item whose key is “3”; it contains 2 items.

Next, we find out the number of occurrences of the number “3” in our grouping result set and both the guess and answer and return it as a tuple: –

[(2, 1, 2)]

So the value 3 matched twice for us as cows, but only occurs once in the guess, and twice in the answer.

Next we simply take the minimum of these three values in order to remove duplicate matches, so we get just the number “1”.

Finally, we sum the sequence of these “cow counts” up. In our case, we only had one set of cows (the number 3), which matched once.

So the answer is just 1 Smile

Conclusion

I was hoping to discuss a bit more in this post but it’s already gone on too long so I’ll cut it short here. All I’ve done is discuss two functions in detail really. Notice how they differ in terms of how you might solve this problem in a classical C# / imperative manner – there are no for loops here or if then constructs. Instead, we use mapping functions to project data from one format into another, and filters to drop off data that we’re not interested in.

We’re also more interested in building up datasets that represent the real problem rather than just blindly iterating through all combinations of data and then use if / then to deal with them differently.

Finally, consider the above code. We took in data of several types, generated a number of tuples and result sets throughout the course of those two functions and yet did not specify a single type. Not one. No ints, no arrays, no sequences – nothing. F#’s fantastic type inference has done it all for us.

In my next post I want to briefly discuss how we hook the functions we’ve defined so far into the API, and then start looking at how we would use this ability to play as both guesser and guessee.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s