A little puzzle

October 14, 2007

A couple of years ago, I learned about a fun little puzzle. The question is: what’s the next element in the following sequence:

1 1
2 1
1 2 1 1
1 1 1 2 2 1

Once I solved the puzzle, I wanted to see if I could come up with a short function that generates this sequence. This is my haskell version:

next [] = []
next (x:xs) = [length start + 1,x] ++ next end
where (start, end) = span (== x) xs

You can call it like this:

main = mapM (putStrLn . unwords . map show) (iterate next [1])

Update: Martijn told me about some background behind this sequence. It’s called the Look and Say Sequence, and it’s a quite interesting sequence indeed.


One comment

  1. My initial haskell implementation looked a lot like yours, with a couple of very minor differences:

    morris = iterate nextMorris “1”
    nextMorris [] = “”
    nextMorris s@(c:cs) = show (length a) ++ c:nextMorris b
    where (a,b) = span (==c) s

    using the @-pattern to decompose s into c:cs lets us still refer to s in the span call. This way, you don’t have to add 1 to the length. Even without the @-pattern, you could have used “span (==c) x:xs” and avoid the “length + 1”.

    Just today I was looking at this code and I rewrote it using concatMap and group instead of cons-recursion:

    import Data.List (group)
    nextMorris = concatMap (\a -> show (length a) ++ [head a]) . group

    Mine works with strings; it would be easy enough to replace show (length a) with [a], and then it would work on [Int] instead.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: