KataPotter

Having covered the basics of F# at Tryfsharp.org, I went on the hunt for a problem to tackle. KataPotter has a little mathematical quirk that makes it a neat challenge.

A full description of the problem can be found at codingdojo.org; there are also hints, tips and a few acceptance tests with which to test your solution. Essentially, your program must calculate the minimum price for a basket of books. The books all belong to a magical, wizarding series and each costs £8. However, there are group discounts when you buy different volumes together:

  • 2 volumes: 5%
  • 3 volumes: 10%
  • 4 volumes: 20%
  • 5 volumes: 25%

So, if you bought 4 books from the series, 3 of which were different volumes, you would get a 10% discount on those 3 and pay full price for the last one.

My first approach was to implement a naive, greedy algorithm that maximised the number of large groupings:

let price array =
  array
  |> Array.sort

  |> Array.scan (fun (_, previous) current ->
    (current - previous, current)) (0, 0)

  |> Array.map2 (fun groupPrice (num,_) ->
    groupPrice * System.Convert.ToDouble num)
    [|0.; 30.; 25.6; 21.6; 15.2; 8.|]

  |> Array.fold (+) 0.

This price method takes an array representing the basket of books grouped by title. For the above example, this could be [|0; 0; 2; 1; 1;|] to represent 2 copies of the third title and 1 copy of titles four and five. Operation by operation, it then:

  1. Sorts the array into ascending order
    Output: [|0; 0; 1; 1; 2|]
  2. Scans the array to output the location and size of quantity increases. This gives us a grouping for the books that maximises the number of larger groups.
    Output: [|(0,0); (0,0); (0,0); (1,1); (0,1); (1,2)|]
    We can see from the first parts of the pairs that there is 1 group of three titles and 1 individual book.
    Note: Array.scan gives a sixth element in the array, at the beginning, which is the initial value of the state.
  3. Uses Array.map2 to combine the grouping pairs with an array of group prices.
    Output: [|0; 0; 0; 21.6; 0; 8.|]
  4. Folds a total through the array, using the + operator, to give us the result.
    Output: 29.60

This solution works in most cases. Although, it does not satisfy one of the acceptance tests:

51.2 = price [|1; 1; 2; 2; 2|]

Our algorithm gives 51.60. What’s going on here?

The answer lies in the marginal cost of each volume when the discount is applied. If you buy all 5 volumes, the marginal cost of the first book is £8.00; the second book, £7.20; the third, £6.40; the forth, £4.00. However, the fifth book is £4.40. So the marginal cost of the forth book is less than the marginal cost of the fifth. Our algorithm should maximise groups of 4, rather than groups of 5, to give the largest discount.

The acceptance test prices [|1; 1; 2; 2; 2|] as 2 groups of four, rather than a group of three and a group of five, to save the additional £0.40.

We can work this into our algorithm using F#’s pattern matching:

fun array ->
  match array with 
    | [|0; g5; g4; g3; g2; g1|] ->
      let min3and5 = min g5 g3;
        [|0;
          g5 - min3and5;
          g4 + 2 * min3and5;
          g3 - min3and5;
          g2;
          g1|]
    | _ -> [||]

In the full solution, this matching function acts on the array of groupings found by the greedy algorithm. Notionally, it moves as many books as possible from 5-groups to 3-groups, in order to maximise the number of 4-groups and achieve the largest discount.

With this change, our algorithm prices [|1; 1; 2; 2; 2|] correctly, as £51.20.

A Functional Mindset

For the last few days of my Project365, I have been taking a look at F#. Although I have some experience with function objects in C++11, I have never worked with a formally functional language. What better place to start than a good old-fashioned tutorial?

Tryfsharp.org seemed like as good a choice as any. They start from the absolute basics (exactly what I need) and also have a Silverlight hosted REPL to test snippets directly in the browser.

All sounding great so far.

So there I was, learning about the forward pipe operator; Discriminated Unions and Currying – minding my own business – when I was presented with:

let string2opt (s:string) =
  let mutable ret = RegexOptions.ECMAScript
  for c in s do
    match c with
    | 's' -> ret <- ret ||| RegexOptions.Singleline
    | 'm' -> ret <- ret ||| RegexOptions.Multiline
    | 'i' -> ret <- ret ||| RegexOptions.IgnoreCase
    | _ -> ()
  ret

Operator Definition and Overloading
  – Revised Regular Expression Operators

If the syntax is a little confusing, this function returns a bitwise flag representation of some regular expression options, based on the presence of control characters in the string argument. Actually, what surprised me was how familiar it looked – a syntactic transliteration of the C++ solution I would write:

int Convert(std::string s)
{
  int ret = 0x01;
  for(auto c : s)
  {
  switch (c)
    {
    case 's': ret |= 0x02; break;
    case 'm': ret |= 0x04; break;
    case 'i': ret |= 0x08; break;
    default: break;
    }
  }
  return ret;
}

We have a mutable variable (the exception, rather than the norm, in F#); an explicit for-loop and a simple switch statement. A suspiciously imperative code block that does not conform to the ethos of functional programming, so far as I understand it.

For additional credit, could I make an improvement?

let string2opt2 (s:string) =
  ["s", RegexOptions.Singleline;
   "m", RegexOptions.Multiline;
   "i", RegexOptions.IgnoreCase]
  |> Seq.filter (fun (c,_) -> s.Contains c)
  |> Seq.fold (fun state (_,opt) -> state ||| opt) RegexOptions.ECMAScript

This certainly looks cooler! We take all the available options and filter them based on the argument string. We then fold the sequence using a bitwise-or operator to obtain the result.

In reality, it is such a compact requirement that this probably constitutes over-thinking. However, functional programming is so unfamiliar to me that the mindset should be reinforced at every opportunity, especially in the context of a tutorial. Otherwise I will always escape to the relative safety of imperative techniques.

Bah, everyone’s a critic…

Tic-Tac-Toe


My first mini-project as part of Project365 is here. A JavaScript mini-games, as promised!

Ok, so there are plenty of Tic-Tac-Toe examples out there – nothing groundbreaking. However, I thought I would try a bit of Test Driven Development and needed a non-trivial problem to tackle.

(Not too non-trivial though, I wanted to be able to hack it together if everything went pear-shaped! It wouldn’t be very motivational if the first mini-project were to fail…)

So what did I learn?

  • Unit tests start out full of bugs

    This was an epiphany for me, having never actually tried TDD before in practice. Unit tests start out full of bugs because they themselves are untested! I couldn’t believe how many times I wrote and committed a bank of failing tests, only to bug fix them individually as I implemented the unit itself – calling the wrong mock framework method; returning incorrect data from stubs or expecting an exception that matched an undesired one. Naively, I had thought that TDD would be a magic way of writing bug free code, but it is not. Units and tests have a symbiotic relationship; one will be full of bugs without the other.

  • Writing tests has to be enjoyable

    Test code: 548 lines
    Prod code: 226 lines

    I accept that this is not the perfect measure of expended effort, but I certainly didn’t copy and paste 80 identical tests or write any uber-lines in production. The truth is that writing tests, especially valuable ones, takes significant time. I had to retrain my psyche to enjoy the warm, comforting taste of testing-porridge just as much as new-functionality-Kool-Aid. Otherwise TDD feels like pausing your favourite video game every 10 minutes for half an hour of watching paint dry.

  • You need a good Unit Testing and Mocking framework

    Alright smartie-pants, obvious. The point is that you have to decide on all of this before you write a single line of code. I settled on QUnit as a testing framework and sinon as a mocking framework – they are both standalone; easy to get to grips with and feature rich. Was the decision rushed? Of course, I had a day to write my first line of code (which in TDD is a test, of course!). They are safe choices, with well documented APIs and tons of snippets on the interwebs.

  • Loose coupling is inevitable

    Normally when I’m writing in-browser JavaScript, everything ends up tightly coupled to the host webpage. It is so easy to use html objects as global memory, rely on browser events or manipulate the DOM directly. Even the application’s execution environment (the browser itself) is a perfectly good IDE!! In general, my applications end up functional, but with a pretty ropey design. However during this exercise, I didn’t need to slap a user interface on the game as soon as possible just to test it. The unit tests provided entry points so that I could prototype approaches in isolation.

  • It rocks!

    I experienced my first Red-Green-Refactor and I must say, AWESOME. I originally implemented the board layout as a string dictionary of values. Each square was indexed by its Cartesian coordinates – (x,y). This layout was wrapped in a Board unit that defined how external code could interact with it. When I decided on how the UI would work, it was clear that the Board unit was going to be my ViewModel, but I needed the layout as a 2 dimensional matrix of knockout observables. I refactored the Board unit internally until I had the structure I needed and the unit tests all passed again – voilà!

Full code

Project365

  • Write some code every day
  • Make it available publicly

This hare-brained idea to code something every day for a year has got me interested, so I’m going to attempt it. I’m not going to promise anything additional here, the rules are deliberately succinct. Suffice it to say that my code will be on GitHub. My thoughts will appear as posts here, if any of them turn out to be cogent. Failing that, I will try to commit my mental state to digi-paper weekly.

I suspect, but do not guarantee (nearly got me there!), that the year will be broken up into many small projects. If possible, I would like the functionality to be as readily available as the source code is going to be; we all know that happy code is executing code. Does this mean lots of web development? That is more than I want to commit to now, but is certainly a consideration.

Let the development of JavaScript mini-games commence!

Follow

Get every new post on this blog delivered to your Inbox.

Join other followers: