Archive for the ‘Uncategorized’ Category

h1

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 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.

Advertisements