XBehave – Exporting your Given, Then, When to html

For a project in my day job we have been using the excellent XBehave for our integration tests. I love XBehave in that it lets you use a Given, When, Then syntax over the top of XUnit. There are a couple of issues with XBehave that I have yet to find a neat solution for (unless I am missing something please tell me if this is the case). The issues are

1) There is not a nice way to extract the Given, When, Then gherkin syntax out of the C# assembly for reporting
2) The runner treats each step in the scenario as a separate test

To solve these to problems I am writing an open source parser that takes the xml produced by the XUnit console runner and parses it to a C# model. I can then use razor to render these models as html and spit out the resultant html.

This will mean that I can take the html and post it up to a wiki so every time a new build runs the tests it would be able to update the wiki with the latest set of tests that are in the code and even say whether the tests pass or fail. Allowing a business/product owner to review the tests, see which pieces of functionality are covered and which features have been completed.

To this end I have created the XUnit.Reporter github repository. This article will cover the parsing of the xml into a C# model.

A neat class that I am using inside the XUnit.Reporter is the AssemblyResource class. This class allows easy access to embedded assembly resources. Which means that I can run the XUnit console runner for a test, take the resultant output and add it to the test assembly as an embedded resource. I can then use the AssemblyResource class to load back the text from the xml file by using the following line of code:

AssemblyResource.InAssembly(typeof(ParserScenarios).Assembly, "singlepassingscenario.xml").GetText())

To produce the test xml files for the tests I simply set up a console app, added XBehave and then created a test in the state I wanted for example a single scenario that passes. I then ran the XUnit console runner with the -xml flag set to produce the xml output. I then copied the xml output to a test file and named it accordingly.

The statistics for the assembly model and test collection model are not aligned to what I think you would want from an XBehave test. For example if you have this single XBehave test:

public class MyTest
public void MyScenario()
"Given something"
._(() => { });

"When something"
._(() => { });

"Then something should be true"
._(() => { });

"And then another thing"
._(() => { });

Then the resultant xml produced by the console runner is:

<?xml version="1.0" encoding="utf-8"?>
<assembly name="C:\projects\CommandScratchpad\CommandScratchpad\bin\Debug\CommandScratchpad.EXE" environment="64-bit .NET 4.0.30319.42000 [collection-per-class, parallel (2 threads)]" test-framework="xUnit.net" run-date="2017-01-27" run-time="17:16:00" config-file="C:\projects\CommandScratchpad\CommandScratchpad\bin\Debug\CommandScratchpad.exe.config" total="4" passed="4" failed="0" skipped="0" time="0.161" errors="0">
<errors />
<collection total="4" passed="4" failed="0" skipped="0" name="Test collection for RandomNamespace.MyTest" time="0.010">
<test name="RandomNamespace.MyTest.MyScenario() [01] Given something" type="RandomNamespace.MyTest" method="MyScenario" time="0.0023842" result="Pass" />
<test name="RandomNamespace.MyTest.MyScenario() [02] When something" type="RandomNamespace.MyTest" method="MyScenario" time="0.0000648" result="Pass" />
<test name="RandomNamespace.MyTest.MyScenario() [03] Then something should be true" type="RandomNamespace.MyTest" method="MyScenario" time="0.0000365" result="Pass" />
<test name="RandomNamespace.MyTest.MyScenario() [04] And then another thing" type="RandomNamespace.MyTest" method="MyScenario" time="0.000032" result="Pass" />

If you look carefully at the xml you will notice a number of things which are counter-intuative. Firstly look at the total in the assembly element it says 4, when we only had a single test. This is because the runner is considering each step to be a separate test. The same goes for the other totals and the totals in the collection element. The next thing that you will notice is that the step names in the original test have had a load of junk added to the front of them.

In the parser I produce a model with the results that I would expect. So for the above xml it I produce an assembly model with a total of 1 test, 1 passed, 0 failed, 0 skipped and 0 errors. Which I think makes much more sense for XBehave tests.

Feel free to clone the repository and look through the parsing code (warning it is a big ugly). Next time I will be talking through the remainder of this app which is rendering the test results to html using razor.

SqlJuxt – Implementing the builder pattern in F#

As an imperative programmer by trade a pattern that I often like to use is the builder pattern for building objects. This pattern is especially useful for test code.

The reasons the builder pattern is so useful is because:

  • It means you only have to “new” the object up in a single place meaning your test code effectively goes through an API (the builder API) to create the object
  • It makes you code really readable so you can understand exactly what it is doing without having to look into how the code works

In my SqlJuxt project I started by coding it in C#. I wanted a builder to make a table create script. This would mean that in my integration tests I could fluently create a script that would create a table and then I could run it in to a real database and then run the comparison. This makes the tests very readable and easy to write. In C# using the table builder looks like:

    var table = Sql.BuildScript()
                   .WithTableNamed("MyTable", t => t.WithColumns(c => c.NullableVarchar("First", 23)

I think that is pretty nice code. You can easily read that code and tell that it will create a table named “MyTable” with a nullable varchar column and a nullable int column.

I wanted to achieve the same thing in F# but the catch is I did not just want to translate the C# in to F# (which is possible) I wanted to write proper functional code. Which means you should not really create classes or mutable types! The whole way the builder pattern works is you store state on the builder and then with each method call you change the state of the builder and then return yourself. When the build method is called at the end you use all of the state to build the object (note an implicit call to the Build method is not needed in the above code as I have overridden the implicit conversion operator).

I hunted around for inspiration and found it in the form of how the TopShelf guys had written their fluent API.

This is how using the table builder looks in F#:

    let table = CreateTable "TestTable"
                    |> WithNullableInt "Column1"
                    |> Build 

I think that is pretty sweet! The trick to making this work is to have a type that represents a database table. Obviously the type is immutable. The CreateTable function takes a name and then returns a new instance of the table type with the name set:

    let CreateTable name =
        {name = name; columns = []}

Then each of the functions to create a column take the table and a name in the case of a nullable int column and then return a new immutable table instance with the column appended to the list of columns. The trick is to take the table type as the last parameter to the function. This means you do not have to implicitly pass it around. As you can see from the CreateTable code above. The Build function then takes the table and translates it in to a sql script ready to be run in to the database.

Here is an example of a complete test to create a table:

    let ``should be able to build a table with a mixture of columns``() =
       CreateTable "MultiColumnTable"
           |> WithVarchar "MyVarchar" 10
           |> WithInt "MyInt"
           |> WithNullableVarchar "NullVarchar" 55
           |> WithNullableInt "NullInt"
           |> Build 
           |> should equal @"CREATE TABLE [dbo].[MultiColumnTable]( [MyVarchar] [varchar](10) NOT NULL, [MyInt] [int] NOT NULL, [NullVarchar] [varchar](55) NULL, [NullInt] [int] NULL )

I think that test is really readable and explains exactly what it is doing. Which is exactly what a test should do.

If you want to follow along with the project then check out the SqlJuxt GitHub repository.

SqlJuxt – A database comparison tool written in F#

As part of a new project I have decided to write a Sql database comparison tool in F#. I wanted a project that I could learn F# with (having dabbled a bit in the past). I have just finished re-reading the excellent Thinking Functionally series on the F# for fun and profit site. Scott has done a fantastic job on there of explaining F# concepts from the perspective of an imperative programmer. Kudos to Scott for that.

So what is the database comparison tool going to be? Well it is initially going to be an API library written in F# that allows you to compare two Sql databases to find the differences. Then from there I might extend it to allow you to script the differences to make the databases the same and then possibly write a front end for it. The other idea I have in mind is to write a C# shim to allow you to use the library nicely from F#. Although the shim library is not strictly necessary using F# from C# or vice versa can be a bit cumbersome unless you put a bit of effort in to making it work well.

That’s it for now stay tuned as I blog about my foray into the world of functional programming. If you want to keep up with how the project is going then you can check out the Sql Juxt GitHub repository.

Converting decimal numbers to Roman Numerals in C#

I decided to create a little project to implement converting decimal numbers to Roman Numerals in C#. You can solve this problem in quite a few different ways, I wanted to talk through the pattern based approach that I went for.

The Roman Numerals from 0 to 9 are as follows:

  • 0 = “” (empty string)
  • 1 = I
  • 2 = II
  • 3 = III
  • 4 = IV
  • 5 = V
  • 6 = VI
  • 7 = VII
  • 8 = VIII
  • 9 = IX

To start the project I wrote a set of tests that checked these first 10 cases. I like taking this approach as it allows you to solve for the simple base case, then you can refactor your solution to be more generic. Our first implementation that solves for the first ten numbers is:

public static string ToRomanNumeral(this int integer)
     var mapping = new Dictionary<int, string>
         {0, ""},
         {1, "I"},
         {2, "II"},
         {3, "III"},
         {4, "IV"},
         {5, "V"},
         {6, "VI"},
         {7, "VII"},
         {8, "VIII"},
         {9, "IX"},

     return mapping[integer];

Obviously there is no error checking etc we are just solving for the 10 first cases. I decided to implement the method as an extension method on int as it makes the code look neat as it will allow you to write:

    var romanNumeral = 9.ToRomanNumeral();

The next step is to look at the Roman Numerals up to 100 and see if we can spot any patterns. We don’t want to have to manually type out a dictionary for every Roman Numeral! If we look at the Roman Numeral representation for the tens column from 0 to 100 we find they are:

  • 0 = “” (empty string)
  • 10 = X
  • 20 = XX
  • 30 = XXX
  • 40 = XL
  • 50 = L
  • 60 = LX
  • 70 = LXX
  • 80 = LXXX
  • 90 = XC

We can straight away see that it is exactly the same as the numbers from 0 to 9 except you replace I with X, V with L and X with C. So lets pull that pattern out into something that can create a mapping dictionary given the 3 symbols. Doing this gives you the following method:

private static Dictionary<int, string> CreateMapping(string baseSymbol, string midSymbol, string upperSymbol)
    return new Dictionary<int, string>
        {0, ""},
        {1, baseSymbol},
        {2, baseSymbol + baseSymbol},
        {3, baseSymbol + baseSymbol + baseSymbol},
        {4, baseSymbol + midSymbol},
        {5, midSymbol},
        {6, midSymbol + baseSymbol},
        {7, midSymbol + baseSymbol + baseSymbol},
        {8, midSymbol + baseSymbol + baseSymbol + baseSymbol},
        {9, baseSymbol + upperSymbol},

We can now call the above method with the symbols for the column we want to calculate passing in the correct symbols. So for the units column we would write:

    var unitMapping = CreateMapping("I", "V", "X");

Now we have this we it is straight forward to create the mapping for the hundreds column. To complete our implementation we want to add some error checks as we are only going to support Roman Numerals from 0 to 4000. The full solution is now quite trivial. We simply check the input is in our valid range (between 0 and 4000). Then we loop through each column looking up the symbol for that column in our mapping dictionary that we generate using our function above. Then we simply concatenate the symbols together using a StringBuilder and return the result.

The full solution with all of the tests is available on my GitHub repository: https://github.com/kevholditch/RomanNumerals.

Partially applying functions in F#

A cool feature of a functional language like F# is the ability to partially apply a function. Take this add function:

let add x y = x + y

By partially applying this function we can create new functions like this:

let plus1 = add 1
let plus5 = add 5

The functions we have created plus1 and plus5 both have the signature int -> int. We have partially applied add to a single parameter leaving us with a function that takes one more int and returns us an int. This is a really neat idea.

Building on this if we want to do the same thing with subtract we find that it does not quite work:

let subtract x y = x - y
let minus1 = subtract 1
printfn "%i" (minus1 7)

The code above prints -6 when we wanted our minus1 function to subtract 1 from the argument given. This is because unlike with add it matters the order that you give the arguments to subtract. We have another cool trick up our sleeves to solve this:

let subtract x y = x - y
let swap f x y = f y x
let minus = swap subtract
let minus1 = minus 1
printfn "%i" (minus1 7)

The minus1 function above now does what we would expect. To make this work we defined a swap function that swaps the order of the arguments. We can then pass our subtract function to our swap function to produce a new subtract function that takes its arguments in the opposite order. We can now partially apply the new function minus with 1 to give us a new function minus1 that works how we would expect. Having functions as a first class citizen really does lead to some neat code.

Simple Web API OWIN host using F#

I thought it would be good to write a simple OWIN Web Api host using F# to show how easy it is to interop between the two languages and as a fun experiment. You can find all of the source code from this blog post at the FSharpWebApi github repository.

If you open the Program.fs solution in the github repository you will see the following two lines of code are reponsible for starting the web server:

let hostAddress = "http://localhost:8000"
let server = WebApp.Start(hostAddress, getAppBuilder())

The getAppBuilder function is defined in the WebServerBuilder module as follows:

let getAppBuilder() =
    let config = new HttpConfiguration()
    config.Routes.MapHttpRoute("default", "{controller}") |> ignore
    fun (appBuilder:IAppBuilder) -> appBuilder.UseWebApi(config) |> ignore

The getAppBuilder function returns a function with the signature (IAppBuilder) -> (). This signature is the same as the one expected by the first parameter of WebApp.Start. The reason for breaking this function off into its own module is so that it can be tested.

The cool thing about the Web Api Owin Self host stack is that there is a nuget package that allows you to test your server without going over http. This is great because it saves you all of the hassle of hosting an endpoint for your tests and tearing it down again. The test framework preserves all of the semantics so the requests will go through the same pipeline it’s just at the final moment they won’t go over http. The nuget package for this is Microsoft.Owin.Testing.

To use the Microsoft.Owin.Testing nuget package you have to call the static method TestServer.Create(IAppBuilder -> ()). You can see that the test server create method takes the same function that is returned by our getAppBuilder function. Which is the reason for isolating this code. The getAppBuilder function contains the logic for how your server will behave (routes, media formatters etc) so by pulling that out into a function we can test it.

As I’ve mentioned before testing in F# is very terse and to the point. Here is the full test suite for my simple hello world server:

module WebServerTests =
    let createTestServer = fun () -> TestServer.Create(new Action<IAppBuilder>(getAppBuilder()))

    let ``get /Hello should return "get - hello world"``() =
        let testServer = createTestServer()
        let client = testServer.HttpClient

            |> should equal "\"get - hello world\""   

    let ``post /Hello should return "post - hello world"``() =
        let testServer = createTestServer()
        let client = testServer.HttpClient

        client.PostAsync("/Hello", new StringContent("")).Result.Content.ReadAsStringAsync().Result 
            |> should equal "\"post - hello world\"" 

To test the web server you need to get the http client that hangs off of the test server (let client = testServer.HttpClient). This gives you a special http client that is wired up directly to your web server. We can now test that we get the correct responses when issuing a get or post request to /Hello.

It is a bit of a shame that there is not an implicit conversion from Action in C# to T -> () in F#. This is the reason that the create test server line at the top of the tests is ugly. We have to new up an action of IAppBuilder and pass our getAppBuilder function into the constructor to convert our F# “action” into a C# one.

The last piece of the puzzle to make the server work is the Hello controller which can be seen below:

type HelloController () =
    inherit ApiController()

    member this.Get () = 
            "get - hello world"

    member this.Post () =
            "post - hello world"

F# shines again. Look how easy and readable this controller class is. Even if you have never written a line of F# code I reckon you could have a pretty good guess at what this controller does. The member keyword is used to provide the semantics of exposing a public property or method. The reason we need the brackets is to cause it to become a method rather than a property.

Apart from the slight ugliness of having to convert from a F# function type to a C# Action type, it is much clener in my opinion to write the code in F#. There is so much less noise. Here is the equivilent HelloController in C#:

public class HelloController : ApiController
    public string Get()
        return "get - hello world";

    public string Post()
        return "post - hello world";

All of the brackets clutter up this simple class. The brackets do not add anything to the code they just help the compiler parse it.

As already mentioned all of the code is up on a github repository for you to view at your leisure. If you have any feedback, comments or questions I would be happy to hear from you.

Manses and the Stones Hacker Rank Problem in F#

The next problem from Hacker Rank that I’m tackling in F# is a problem called Mansasa and the stones (catchy name). The basics of the problem are that you are given 2 numbers and a length and you have to give all of the distinct sums of those numbers of the lists that can be made up of length l. An example is if stone 1 has the value 2 and stone 2 has the value 4 and the length is 3 we get:

0, 2, 2 = sum 4
0, 2, 4 = sum 6
0, 4, 2 = sum 6
0, 4, 4 = sum 8

Note the problem states that we should start with 0 for each entry. This means that the distinct sums in this example would be 4 6 8 (in order).

My idea to solve this problem was to write a function that takes a list and a length and then gives you all permutations for that list of that length. In the example above if you passed this function 2 and 4 and a length of 2 it would give the 4 possible ways of arranging 2 and 4 shown above. Once I have this function I can simply sum the numbers, do a distinct and then format the result. Simples, or so I thought more on that later.

Now that I’ve got a great way to write tests for my code I started with the unit tests for the function:

module combinations =

module combinations =
    let ``combinations for [2;3] of length 2 should be [[2;2];[2;3];[3;2];[3;3]]``() =
        combinations [2;3] 2 |> should equal [[2;2];[2;3];[3;2];[3;3]]

    let ``combinations for [2;3] of length 3 should be [[2;2;2];[2;2;3];[2;3;2];[2;3;3];[3;2;2];[3;2;3];[3;3;2];[3;3;3]]``() =
        combinations [2;3] 3 |> should equal [[2;2;2];[2;2;3];[2;3;2];[2;3;3];[3;2;2];[3;2;3];[3;3;2];[3;3;3]]

    let ``combinations for [1;4] of length 1 should be [[1];[4]]``() =
        combinations [1;4] 1 |> should equal [[1];[4]]

I think it is so neat that the tests describe themselves. I was stuck on writing this function in a recursive way for a little while. I’m still finding it hard to think functionally. I put this problem to my friend Sam Owens who came up with a great solution:

let combination list length =
    let rec solve letters len =     
        seq {
            if len = 1 then 
                for l in letters do yield [l]
                let theRest = solve letters (len-1) 
                for l in letters do
                    for r in theRest do 
                        yield l::r
    solve list length

I thought this solution was ingenious. Before I talk through how it works let me show you the more functional version. I created this by translating Sam’s function above to use pattern matching:

let combinations list length =
    let rec solve lst len =
        match len with
        | 1 -> lst |> Seq.map(fun x -> [x])
        | i -> lst |> Seq.map(fun l -> solve lst (len-1) |> Seq.map(fun r -> l::r)) 
                            |> Seq.collect(fun x -> x) 
    solve list length

Both of these functions are exactly the same (kudos to Sam for coming up with this way of doing it). I think the 2nd function is much more elegantly written and more readable. It’s much terser and really shows the power of F#’s pattern matching.

This function works by the fact that it knows how to print out every combination of a list of length 1. Which is shown on the first line of the match statement. To do this it simply maps out all of the elements as a list of one item. If the function is called with a length greater than one then it calls itself with length – 1 and appends the results from that on to each element in the list passed in.

With this function written composing the function to solve the whole problem was pretty straight forward:

let findMansaNumbers steps (stone1:int) (stone2:int) =
    combinations [stone1; stone2] (steps-1) |> Seq.map(fun l -> Seq.sum(l)) 
                                            |> Seq.distinct 
                                            |> Seq.sort
                                            |> fun x -> String.Join(" ", x)

All we have to do is run the combinations function passing it a list of the two stone numbers and a length. We then sum the numbers from each combination, get a distinct list of the sums, sort them in to order and then print them out in a string where each number is separted by a space. The way that F# lends itself well to composing small building blocks together makes it a fun language to program in.

Here comes the kicker. Although this solution works, it passes the first three test cases on the hacker rank problem page it then times out. The reason for this is that the number of combinations the combinations function will return is given by the formula 2^length. This is exponential growth so for big lengths the time to compute all combinations is too long. As a short aside the fact that hackerrank run the code on their server and then time out if your solution takes too long is a good thing. It stops you from being able to brute force the problems which is one of the things that plagues project Euler in my opinion.

So it’s back to the drawing board with this problem. The code is on the repository under slow solution in the MansasaAndStones.fs file in the Hacker Rank in F# repository on github.

To solve this problem it is actually very straight forward. I was just taking completely the wrong approach. If you think of the case where you have 2 stones of values 2 and 4 and are asked to find 3 steps then you can think of this as:

0, 4, 4 = sum 8 = (0*2) + (2*4)
0, 2, 4 = sum 6 = (1*2) + (1*4)
0, 2, 2 = sum 4 = (2*2) + (0*4)

So the distinct sums are 4, 6 and 8. This is calculated by having two loops, one starting and 0 and incrementing, one starting at the number of steps – 1 (as we the first step is always 0 in the problem) and then multiplying one of the loops by the first stone and one by the second.

let findNumbers steps (stone1:int) (stone2:int) =
    let list1 = [0..steps-1]
    let list2 = [0..steps-1] |> List.rev
    List.zip list1 list2 |> Seq.map(fun (x, y) -> (x*stone1)+(y*stone2))
                         |> Seq.distinct
                         |> Seq.sort
                         |> fun x -> String.Join(" ", x)

The code above is the full solution to the problem. Instead of looping twice we use the zip function to produce tuples of the loop values we can then feed this into the map function which makes the code neater. After that we just have to make sure the list is distinct (as the problem states no duplicates) and then sort it (as the problem states that the values should be in order) then we have to produce a space separated string for each answer.

I really went around the houses with this problem but I did learn some cool things in F#. Solving the combinations problem was fun and helped me practice my skills of turning C# into functional F#. Once I realised I only needed two loops I was quite happy with how nice the solution is. One thing I’m learning more and more about functional programming is that you can write really expressive beautiful code. Erik Meijer would be proud!

To look at the final solution check out the ManasaAndStones module and the solution function from the github repository. As always I would be keen to hear your feedback.

Unit testing in F# is a breath of fresh air

I want to start this post off by saying that I was simply blown away with unit testing in F#. Before I go on I want to give reference to the excellent F# for fun and profit blog for getting me started.

Unit testing and F# are a match made in heaven. I think the best thing to do before I go on is to show you a unit test in C#:

public class AllIndexOfTests
    public void AllIndexOfhellInHelloHelloIsCorrect()
        var allIndexOf = new AllIndexOf();
        var result = allIndexOf("hello hello", "hello");
        result.SequenceEqual(0, 6).Should().BeTrue();


Now in F#:

    let ``the string 'hello hello' contains the string 'hell' at indexes 0 and 6``() =
        allIndexOf "hello hello" "hell" |> should equal [0; 6]

Check out how the F# code is self describing. Due to the fact that in F# you can put whitespace in a function by escaping the name with the double back tick, the function name can be self describing with spaces which makes it readable. To get the C# code to look as clean as above requires the use of quite a lot of libraries and careful design of your code. Even then you can’t get that close. The F# just reads like English. I would go as far as to say someone who did not understand code could read that test and understand what the function should do.

The testing framework I am using to obtain this syntax is FsUnit. Which is built on top of NUnit. Here are the complete set of tests for the GridSearch solution to the HackerRank problem I went through last time:

module allIndexOf =
    let ``the string 'hello hello' contains the string 'hell' at indexes 0 and 6``() =
        allIndexOf "hello hello" "hell" |> should equal [0; 6]

    let ``the string 'hello world' does not contain the string 'kevin' ``() =
        allIndexOf "hello world" "kevin" |> should equal []

module find =
    let ``the string '123' is in the grid '444 123 444' at [(0,1)]``() =
        find ["444"; "123"; "444"] "123" 0 |> should equal [(0,1)]

    let ``the string '123' is in the grid '444123 981231 123122' at [(0,1)]``() =
        find ["444123"; "981231"; "123122"] "123" 0 |> should equal [(3,0); (2,1); (0, 2)]

    let ``the string '123' is not in the grid '123 777 444' when the first row is skipped ``() =
        find ["123"; "777"; "444"] "123" 1 |> should equal []

module findExact =
    let ``the string '123' is in the grid '444 123 444' is exactly at 0, 1``() =
        findExact ["444"; "123"; "444"] "123" 0 1 |> should equal true

    let ``the string '77' is in the grid '9999 9977 0987 0987' is exactly at 2, 1``() =
        findExact ["9999"; "9977"; "0987"; "0987"] "77" 2 1 |> should equal true

    let ``the string '865' is not in the grid '9999 9977 0987 0987' is exactly at 2, 1``() =
        findExact ["9999"; "9977"; "0987"; "0987"] "865" 2 1 |> should equal false

    let ``the string '77' is not in the grid '9999 9977 0987 0987' is exactly at 3, 3``() =
        findExact ["9999"; "9977"; "0987"; "0987"] "77" 3 3 |> should equal false

module gridContains =
    let ``the grid '444 123 444 555' contains the grid '123 444 555 ``() =
        gridContains  ["444"; "123"; "444"; "555"] ["444"; "123"; "444"] |> should equal true

    let ``the grid '44488 12311 44490 55598 778899' contains the grid '44 55 ``() =
        gridContains  ["44488"; "12311"; "44490"; "55598"; "778899";] ["44"; "55"] |> should equal true

    let ``the grid '44488 12311 44490 55598 778899' does not contain the grid '88 88 ``() =
        gridContains  ["44488"; "12311"; "44490"; "55598"; "778899";] ["88"; "88"] |> should equal false

The fact this fits in such a small space, is succinct and to the point makes it such a good fit for unit testing. I would even argue that even if you use C# for your main application writing your tests in F# could save you time and make your tests much more readable.

If you look at the code listing you will see that I have created the tests all inside the module GridSearchTests. I have then grouped each set of tests under a module that is named the same as the function they are testing. This means in the resharper test runner you get the following:


Which I think is really sweet. Each function is listed along with the test cases that can be read in normal English. Rather than in C# you often name your test cases using camel casing. Meaning that when the test cases become long it can be hard to read them.

To check out the code from this post clone my HackerRankInFSharp repository on github. Please feed back your F# unit testing experiences in the comments.

Grid Search Problem Solved Using F#

As mentioned in my last post I’ve recently got into solving HackerRank problems in F#. I’m trying to use F# with a functional programming style not writing in an imperative style as I would in C# and use the F# syntax (which is possible).

I want to go through how I solved the Grid Search Problem so if you don’t want to know a solution look away now!

The problem is that you are given two grids of numbers and you have to write “YES” if the second grid is contained anywhere in the first grid and “NO” if it isn’t.

I’m quite new to functional programming but the way I approached this was to break the problem up into smaller functions and then the answer would be a composition of those smaller functions.

If you clone my HackerRankInFSharp repository from github it contains all of the code that you can follow along to. To view the code for this problem open the file GridSearch.fs in the HackerRank project.

At the bottom of the GridSearch.fs file you will see a solution function defined. This function runs the test case from the input file and is where you should start reading the file from.

When you run your code on hackerrank your program needs to interact with the console. To save typing the inputs in each time I wanted to test my program I copied the test cases into a text file and then simply mapped a read function to reading a line from a file like so:

let reader = new StreamReader("TextFile1.txt")
let read = reader.ReadLine

This is one of the neat things about F#. As it’s a functional language and functions are first class citizens you can assign them into variables and then just pass them around. By writing my code in this way I could simply copy all of my solution into HackerRank when it is complete and just change the read function to map to console readline (let read = Console.ReadLine) and leave the rest of my code the same.

The next three functions that I wrote are to help read the input data:

let t = read() |> Convert.ToInt32

let num = fun() -> read().Split(' ') 
                |> Seq.head
                |> Convert.ToInt32

let fetch = fun() -> [for _ in 1..num() do yield read()]  

The first two simply read the values for t (the amount of test cases) and num I use to be the amount of rows in the grid. The input data also gives you the length of each row but as the rows are separated by new lines you don’t need this. The last function fetch returns a sequence of strings of length num (the amount of rows in the grid). The function fetch will be used to read a grid into a variable and is generic so can be used both for the reference and search grids. The terminology I’m going to use is reference grid to refer to the bigger grid and search grid will be what we are looking for inside the reference grid.

Now I’ve got the input my idea was to write a function get all indexes of a smaller string in a bigger string. The reason for this is that I thought to search for the search grid inside the reference grid we would first start with just the first line of the search grid. We want to look at each line of the reference grid and know if the first line of the search grid is contained within it. If it is we want to a list of the indexes of where it is.

let allIndexOf (str:string) (c:string) =
    let rec inner (s:string) l offset =
        match (s.IndexOf(c), (s.IndexOf(c)+1) = s.Length) with
        | (-1, _) -> l
        | (x, true) -> (x+offset)::l
        | (x, false) -> inner(s.Substring(x+1)) ((x+offset)::l) (x+1)
    inner str [] 0

In my last post I talked about the awesome help I got off the community with this function. This function works recursively which is one of the mantras of functional programming. allIndexOf takes 2 strings. The first string is the reference string (str) and the second string is the one you are looking for (c). The first line of the function declares a recursive function that takes a string (s) a list of int (l) and an int (offset). There are a few interesting points on this line. Firstly the keyword “rec” is not optional, it means it is a recursive function. The next interesting part is that the parameters l and offset do not have any type annotations. This is one of the things that makes F# very clean. The reason for this is that the compiler can figure out the types of the functions nearly all of the time for you so the type annotations are completely optional. This removes a lot of the excess clutter. The next line (match) is another very cool feature of F# The pattern matching. What it is saying is create a tuple that as the values (s.IndexOf(c), (s.IndexOf(c) +1 = s.Length)) which is of type (int, bool). Once that tuple is created it is then matched on one of the next three lines. If s.IndexOf(c) returns -1 then it doesn’t matter what the second part of the tuple is as we match with the wildcard _. In that case we return l the list that was passed in. If the s.IndexOf(c) evaluates to anything other than -1 then we match the 2nd line if the bool part is true. If the bool part is false then we match the last line. The last line of the function then calls the recursive function with the string you have passed in, an empty list and an offset of 0.

To see how this function works lets look at a simple example if we pass in “hello hell” and “hell” we would expect the indexes returned to be 0, 6. When we call the function inner with “hello hell” [] 0. The match clause will then produce the tuple (0, false) which will match to the third line. This will then call inner again with “ello hell” [0] 1. This time the match clause will evaluate to (2, false) which will then call inner with “ell” [0, 6] 6. This time the match clause will return the tuple (-1, false) so it will match with the first line of the match clause and return the list [0, 6] which is the correct answer.

The way you can combine functions together to perform the tasks you need will become clear as I go through the rest of the solution. The next function uses the allIndexOf function to return the co-ordinates of every occurrence of a string in a list of strings (aka a grid).

let find g str start = g  |> Seq.skip start
                          |> Seq.mapi (fun i x -> (allIndexOf x str) |> Seq.map (fun u -> (u, i+start))) 
                          |> Seq.collect (fun x -> x)

You can read the |> operator as pipes data from left to right. What we are doing here is for each row in the grid skipping as many rows as are passed in via the start parameter (note this is an optimisation as further on we can reuse this function to search the remainder of the grid). We then pipe the result from that into a map function that returns a tuple where the first element is the index of the string (x co-ordinate) and the indexer is the y co-ordinate of the string. The y co-ordinate of the string is known as we are looping through each string in the grid using the mapi function. The mapi function gives you each element (x) and the index of the element (i). The index of the element will be the y co-ordinate as that corresponds to the row in the grid. We then have to use the Seq.collect function to unwind a double sequence. This is the equivalent to a select many.

let findExact g str x y = find g str y
                              |> Seq.exists(fun (a, b) -> x = a && y = b)

The findExact function then extends the find function to return a bool if and only if that string is found in the grid at the co-ordinates specified. The reason for this function is my idea to solve the problem is to call the find function for the first row of the search in the reference grid giving you all of the co-ordinates of where that appears. Then all you need to do to tell if the whole search grid is there is loop through subsequent rows and add one on to the y co-ordinate each time. For example if we called find and we got back (2, 3) and (5, 6) and the search grid was 3 strings deep. Then to tell if the search grid is in the reference grid we would simply need to know if the second string was at (2, 4) and the third at (2, 5) or if the second string was at (5, 7) and the third at (5, 8). In either case the answer is yes, if any of those return false the answer is no.

let gridContains g (s: string list) = 
    let matches = find g s.[0] 0 
    let numStrs = s |> Seq.skip 1
        |> Seq.mapi(fun i line -> (i, line))
    matches |> Seq.map(fun (a, b) -> numStrs |> Seq.map(fun (i, line) -> findExact g line a (b+i+1)))
        |> Seq.exists(fun b -> b |> Seq.forall(fun x -> x))

The function above does exactly that. The first row assigns all of the co-ordinates of the first row of the search grid that are found in the reference grid into the variable matches. The next line essentially numbers each string in the search grid but not the first row making it easier to write the last part of the function. The last part of that function then pipes matches into a function that for each co-ordinate in matches adds on i (the current loop value) to the y value and 1 (due to 0 starting value) and returns a bool as to whether that string is contained in that position. That will then return a sequence of sequence of bool. The last part is then to see if any of those sequences of bool contain a set of all true. It even reads how I’ve just described it “does a sequence exist where there is a sequence for all of which are true”.

To run the solution clone theHackerRank repo on github. Then in the program.fs file uncomment the line //GridSearch.solution.

I’m still new to functional programming so if there is anything you would improve or do different please feel free to leave a comment below.

The StackOverflow community rocks!

Recently I stumbled upon a site called HackerRank. Before I go into why this relates to StackOverflow I want to briefly explain HackerRank. HackerRank is a site where you are challenged to solve a problem in pretty much any language you want. You have to take a program that gets an input and gives a desired output based on a problem. The site will then run your code against some test cases and determine if your code passes that problem.

HackerRank gets very addictive quickly. The problems start off easy such as add two numbers to get you used to how it all works but they ramp up pretty fast.

For a while now I’ve had a passing interest in F#. I’ve used the language to solve Project Euler problems in that past. HackerRank in my view is a better Project Euler the reason I think this is because with the Project Euler problems many of them can be brute forced on today’s hardware. Meaning you can solve them in a way that the author didn’t quite intend. The other issue with some of the problems is they are deep in maths. So deep in maths that I sometimes needed to spend quite a bit of time reading up on advanced algebra just to get to the point where I could start the problem. As much as I enjoyed this it detracted from the problem solving. Anyway I digress, I decided that HackerRank would be an excellent way to learn F#.

I was trying to write a function allIndexOf that takes two strings and returns a list of integers of the first positions of all of the occurrences of the second string in the first string. I couldn’t get my function to compile in F# so I posted this question on StackOverflow. Within 2 minutes someone had posted the answer that I missing a set of parentheses due to the way that F# binds it’s function arguments. Now is cool that you can get an answer within 2 minutes. What was even more amazing and blew me away was that someone then in the comments took the time to point out a bug in my function.

Here is my original function see if you can spot the bug:

let allIndexOf (str:string) (c:string) =
    let rec inner (s:string) l =
        match (s.IndexOf(c), (s.IndexOf(c)+1) = s.Length) with
        | (-1, _) -> l
        | (x, true) -> x::l
        | (x, false) -> inner(s.Substring(x+1) x::l)
    inner str []

Not only that but they made this F# Fiddle showing my function with some inputs and why it was wrong and also giving 3 ways to do the function. Using comprehension, recursion with an accumulator and recursion with a continuation.

The bug was that during the recursive call to “inner” if it matched then the value that x would be bound to would not be the index of the next occurrence of the string in the original string but the truncated string. To fix this in my version of the code I just needed to pass along the amount of string that was missing so this could be added on to x.

Fixed code:

let allIndexOf (str:string) (c:string) =
    let rec inner (s:string) l offset =
        match (s.IndexOf(c), (s.IndexOf(c)+1) = s.Length) with
        | (-1, _) -> l
        | (x, true) -> (x+offset)::l
        | (x, false) -> inner(s.Substring(x+1)) ((x+offset)::l) (x+1)
    inner str [] 0

Now this code is actually inefficient due to the fact I am creating a new string upon each recursive call. This is something Sehnsucht points out on StackOverlow. I think it says a lot about the dev community that people are willing to firstly give up their time to answer your questions but also that they will go the extra mile to point out where you are going wrong and how you can improve.

If you have some spare time why not get on StackOverflow and pay it back…