The Luhny Bin Challenge

Last week Bob Lee (@crazybob), from Square, set an interesting coding challenge. All the details can be found here: http://corner.squareup.com/2011/11/luhny-bin.html. I decided this sounded like a bit of fun a set to work on a Scala implementation. I'm pleased with my final result, but also learnt something interesting along the way. My full solution is available on my github account: https://github.com/skipoleschris/luhnybin.

The challenge was an interesting one, and more difficult that initial reading would suggest. In particular, the ability to deal with overlapping card number and the need to mask them both added significantly to the difficulty of the problem.

My Algorithm

The approach I selected was fairly simple. Work through the input string until a digit character was encountered. Walk forward from there consuming digit, space of hyphen characters until either the end of the string was reached, an different character was encountered or 16 digits had been collected. Next try to mach the LUHN, first on 16 digits, then 15 and finally 14. Record an object describing the index and how many characters to mask. Repeat for the next digit character and so on. After visiting all characters in the string, apply all the masks to the input.

There were some optimisations along the way. For example, if encountering 14 or less characters then there was no chance of an overlapping card number so you could safely skip over these remaining digits after the first one had been evaluated.

My Implementation

I decided to implement in Scala as this is my language of choice at the moment. I considered both a traditional imperative approach as well as a more functional programming solution. In the end I went for a very functional implementation, based around immutable data. My main reason for this choice was because I'm working on improving my functional programming skills and I though it looked like an interesting problem to try and solve in this way.

The implementation consist of for main pieces of code. Each implements a transformation of input into output, is fairly self contained. I fell that by writing them in this way I have created code that is possible to reason about and also reuse in other scenarios. I tried for elegant code rather then optimising for the most efficient and minimal code base. I think I achieved my goals.

Conclusion

While I am very happy with my solution and had great fun building it, it was very interesting to look at other solutions that had been attempted. In particular it's quite clear that the ~900ms that I was able to active on my mid-2010 MBP was a number of times slower than the fastest solutions. The inevitable conclusion being that in some cases adopting a more mutable and imperative approach may be preferable. This is a typical example of this case, when we are in effect creating a logging filter, and speed of operation could easily be argued as more important than adhering to the principles of immutability. An interesting conclusion.