Programming Praxis – Look And Say

In today’s Programming Praxis exercise, our task is to generate the Look and Say sequence (1, 11, 21, 1211, etc.). Let’s get started, shall we?

A quick import:

import Data.List

The algorithm is pretty straightforward: convert the number to a string, replace each sequence of identical digits with the length followed by the digit and convert the result back to an integer. Repeat indefinitely.

lookAndSay :: Integer -> [Integer]
lookAndSay = iterate (read . f . group . show) where
    f = (>>= \x -> show (length x) ++ take 1 x)

A test to see if everything is working properly:

main :: IO ()
main = print $ take 10 (lookAndSay 1) == [1, 11, 21, 1211, 111221,
    312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]

Yup. Unfortunately there doesn’t appear to be a Haskell Package that does run-length encoding, or I might have been able to do it in one line.

About these ads

Tags: , , , , , , ,

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: