Monday, February 25, 2008

Shake Ya Tailfeathers (A Haskell Puzzle)

Deciding that the Scala bandwagon is far too hot right now (in the sense that I should wait a bit till I'll be eligible to late-adopt it) I've started learning Haskell instead.

After reading and processing the first some chapters of YAHT and still not getting CPS, I nevertheless wanted to produce something, so came up with this:

It's a puzzle I've learned a long time ago called Tailfeather.
Tailfeather is a number-sequence, where the very first element is lress than the last one, the second element is lress than the second to last element and so on.
The task is to write a function with the specification:

tailfeather :: Int -> Int
{- tailfeather n = b
where 'b' > 1 is the smallest radix in which
the digits written of 'n'
form a Tailfeather sequence of numbers

A very nice, very entry-level stuff. And the very beauty of it all is that implementing this solution was absolutely straighforward: I was able to focus on the actual problem without worrying about the underlying details (like how to represent a number-sequence -- is that an ArrayList or and array?)
Actually there are two sub-problems: A) rewriting a decimal number to another radix and B) determining whether a sequence is a Tailfeather.

Starting with the latter subtask, all you have to do is break a list into three parts, and solve the task recursively, like so:

tailfeather0 (x:xs) =
(x < last xs) &&
(tailfeather0 (init xs))

First we check if the Tailfeather property holds for the first and the last elements, then cut those elements from the list (that is take the init of the tail) and check the remaining part.

Of course the recursion must be terminated (and this next code MUST appear before the previous fragment):

tailfeather0 [] = True
tailfeather0 [x] = True


Let's see problem A. If you don't know the proper algorithm for converting from decimal to another radix, it is given here (if the site is down use Wikipedia).
My first naive rewrite of the example provided on the linked page yielded the following:

convert2base2 0 = []
convert2base2 n = (mod n 2) : convert2base2 (div n 2)

Looks tight, the only problem is that it returns the digits in reverse order (starting with the least significant bit). Reversing the list after the whole computation would be an option, instead I do it in place:

convert2base2 n = convert2base2 (div n 2) ++ [mod n 2]

Generalizing the converter to accept any base (don't use this one with b <= 1):

convert2base _ 0 = []
convert2base b n = convert2base b (div n b) ++ [mod n b]

Now that we have our building blocks, let's combine them:

tailfeather n = tailfeather1 2 n

tailfeather1 b n =
if (b == n)
then b+1
else if tailfeather0 (convert2base b n)
then b
else tailfeather1 (b+1) n

That's it.