The fast, the right and the smart

Working my way through the puzzles in Project Euler is pretty enlightening at times.  I made it to level 1 yesterday to much acclaim and adulation.  Taking this as an opportunity to look back at the sort of  patterns I have been coding threw up a couple of interesting practises which I have been performing.

Manipulating strings to and from numbers

A large number of the problems involving the rearrangement of numbers, for example, finding which pair of two-digit primes when rearranged in ascending order and concatenated give the cube of the difference of the original primes (I just made that up – there may well not be an answer).  In this example, if our two primes were represented as ab and cd then we would need to perform the rearrangement to get ba and dc as well. The tactic I have been adopting for this is judicious use of show and read.  For the example I just gave, the call would something like

reverseNum = read.reverse.show

In order to find all the two-digit numbers my current ploy is to make use of the permutations function in Data.List and apply it to a string of digits.  After a bit of processing, the correct answers pop out. For example, here is the code to return all nine-digit numbers without zeros:

nineDigitsWithStrings = map read $ permutations "123456789"

Its short and clear, and not a lot can go wrong with it. But the use of read just looks a bit ugly. I had a nagging feeling that the right way to do this was to actually do the conversion “properly” by stepping though the list multiplying by ten at each step, to get the same, proper answer. Something like this in fact:

nineDigitsWithNums = map makeNum $ permutations [1..9]
   where
   makeNum ds = makeNum' (reverse ds)
   makeNum' [] = 0
   makeNum' (n:ns) = n + 10 * makeNum' ns

A couple of things to note – firstly, the reverse is required so that  the proper digits get more multiplications.  Second – it appears to be a lot more complicated than the string version, but let’s be honest, there is a lot of complexity hiding within a call to read of which there is none in this version. I had no idea which might be faster so I created a quick test to see if one was clearly more efficient than the other. The results were somewhat surprising – the quick and dirty string-based method was around 20% faster and used about 20% less memory.  So much for doing things the “right” way!  Why this is the case I do not know (yet), but the reverse calls might be the culprit.  Unfortunately, they are somewhat important in getting the right answer.

Dealing with sorted lists

Another pattern I noticed using occurred when dealing with sorted infinite lists.  These keep cropping up – for example the list of primes is a prime (ho-ho!) example.

In this case, I would often want to grab the members of the list smaller than a given number.  Naively, I would write

filter (<n) primes

but this would never complete, due to the infiniteness of the list.  Knowing that the list is sorted, the correct effect can be obtained by a slight tweak:

takeWhile (<n) primes

which completes quite happily. This sort of thinking is also useful when interrogating a list for the existence of a particular element.  Again, a naive approach would be to use

elem n primes

which again doesn’t complete due to the infiniteness of the list.  Adopting the same sort of approach as before, we can re-write this as

(head $ dropWhile (<n) primes) == n

which (once you get your head around what it is actually doing) is simple, and more to the point works.

Having these solutions at your fingertips allows you to avoid the problem of arbitrarily truncating the infinite list, which would be the other option.  It isn’t a good option though – truncate too early and you miss the elements you need.  But truncate too late and you spend far more time than you need to in dealing with the list.  Haskell’s lazy lists are a real boon in this situation.

No related posts.

Tagged as: Haskell, project euler