A little puzzle
October 14, 2007A 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 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.
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.