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]
            else
                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
{
    [Test]
    public void AllIndexOfhellInHelloHelloIsCorrect()
    {
        var allIndexOf = new AllIndexOf();
        var result = allIndexOf("hello hello", "hello");
        result.SequenceEqual(0, 6).Should().BeTrue();
    }

}

Now in F#:

[<Test>]
    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 =
    [<Test>]
    let ``the string 'hello hello' contains the string 'hell' at indexes 0 and 6``() =
        allIndexOf "hello hello" "hell" |> should equal [0; 6]

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

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

    [<Test>]
    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)]

    [<Test>]
    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 =
    [<Test>]
    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

    [<Test>]
    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

    [<Test>]
    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

    [<Test>]
    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 =
    [<Test>]
    let ``the grid '444 123 444 555' contains the grid '123 444 555 ``() =
        gridContains  ["444"; "123"; "444"; "555"] ["444"; "123"; "444"] |> should equal true

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

    [<Test>]
    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:

tests

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.