Posts Tagged ‘look and say’

Programming Praxis – Look And Say, Revisited

March 28, 2011

In today’s Programming Praxis exercise, our goal is to calculate Conway’s constant. Let’s get started, shall we?

First we need to represent the polynomial that we’re going to take the root of.

conway :: Num a => a -> a
conway x = sum $ zipWith (*) (iterate (* x) 1)
    [ -6,  3,-6, 12,-4, 7,-7, 1, 0, 5,-2, -4,-12, 2, 7,12,-7,-10
    , -4,  3, 9, -7, 0,-8,14,-3, 9, 2,-3,-10, -2,-6, 1,10,-3,  1
    ,  7, -7, 7,-12,-5, 8, 6,10,-8,-8,-7, -3,  9, 1, 6, 6,-2, -3
    ,-10, -2, 3,  5, 2,-1,-1,-1,-1,-1, 1,  2,  2,-1,-2,-1, 0,  1]

Next, we calculate the root by halving the interval until the value at the middle is sufficiently close to 0.

root :: (Fractional a, Ord a) => (a -> a) -> a -> a -> a -> a
root f lo hi e | abs (f mid) < e = mid
               | f mid > 0       = root f lo mid e
               | otherwise       = root f mid hi e
               where mid = (lo + hi) / 2

Since we know the root lies somewhere between 1 and 2, we use those as the starting values.

main :: IO ()
main = print $ root conway 1 2 1e-7 == 1.303577269034296

We get the correct answer, so everything seems to be working properly.

Programming Praxis – Look And Say

March 15, 2011

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.