Archive for June, 2012

Programming Praxis – Sliding Median

June 29, 2012

In today’s Programming Praxis exercise, our goal is to determine the median values of a sliding window over a stream of numbers. Let’s get started, shall we?

A quick import:

import Data.List

Sinze Haskell is lazy by default, we don’t have to do anything special to only load the needed part of the list. We can just use tails and take to generate all the needed windows, after which we sort each window and take either the middle or the average of the middle two values, depending on whether the window contains an even or an odd number of elements.

slidingMedian :: (Ord a, Fractional a) => Int -> Int -> [a] -> [a]
slidingMedian size count =
    map ((\ ~(x:xs) -> if odd size then x else (x + head xs) / 2) .
         drop (div (size - 1) 2) . sort . take size) . take count . tails

A test to see if everything is working properly:

main :: IO ()
main = mapM_ print $ slidingMedian 5 12
    [13, 28, 94, 34, 32, 78, 12, 10, 84, 93, 45, 66, 67, 52, 24, 49]
Advertisements

Programming Praxis – Billboard Challenge, Part 2

June 26, 2012

In today’s Programming Praxis challenge, our goal is to solve the second part of the billboard test, which is to find the fifth group of ten digits of e that sum up to 49. Reusing our definition of stream_e from the previous exercise, the solution becomes a simple one-liner:

main :: IO ()
main = print $ [x | x <- map (take 10) $ tails stream_e, sum x == 49] !! 4

Programming Praxis – Billboard Challenge, Part 1

June 22, 2012

In today’s Programming Praxis exercise, our goal is to solve the problem posed to potential employees by a tech firm a couple of years ago: find the first 10-digit prime in the digits of e. Let’s get started, shall we?

A quick import:

import Data.List

First we reuse the unbounded spigot algorithm for calculating e from the last exercise;

stream :: Integral a => (a, a) -> (a, a, a) -> [(a, a, a)] -> [a]
stream (lo, hi) z ~(x:xs) = if lbound == approx z hi
    then lbound : stream (lo, hi) (mul (10, -10*lbound, 1) z) (x:xs)
    else stream (lo, hi) (mul z x) xs
    where lbound = approx z lo
          approx (a,b,c) n = div (a*n + b) c
          mul (a,b,c) (d,e,f) = (a*d, a*e + b*f, c*f)

streamDigits :: (Num a, Integral a, Enum a) => (a -> (a, a, a)) -> (a, a) -> [a]
streamDigits f range = stream range (1,0,1) [(n, a*d, d) | (n,d,a) <- map f [1..]]

stream_e :: [Integer]
stream_e     = streamDigits (\k -> (1, k, 1)) (1, 2)

Next we need a function to test if a number is prime. In the interest of simplicity we just use trial division. To speed things up, we use the three simplest optimizations: only testing odd numbers, only testing up to the square root of the tested number, and only testing with primes. The list of all primes is defined at root level so Haskell memoizes it.

primes :: [Integer]
primes = 2 : filter prime [3,5..]

prime :: Integer -> Bool
prime n = all ((> 0) . mod n) $ takeWhile (\p -> p * p <= n) primes

With those two building blocks out of the way, the rest is trivial: take all groups of 10 consecutive digits, convert them to numbers and find the first prime.

main :: IO ()
main = print $ find prime . map (foldl1 ((+) . (10 *)) . take 10) $ tails stream_e

Programming Praxis – Digits Of E

June 19, 2012

In today’s Programming Praxis exercise, our goal is to implement two algorithms to calculate the digits of e using a spigot algorithm: one bounded and one unbounded version. My solution for the unbounded version is already posted in the exercise itself, so I’ll only cover the bounded version here. Let’s get started, shall we?

A quick import:

import Data.List

The main trick used for the whole carry and modulo stuff is the use of mapAccumR; it allows us to produce a list of the modulos while also producing the resulting digit. Other than that, the implementation is straightforward: call the function n-1 times with an initial argument of n+1 ones and tack a 2 on the front.

spigot_e :: Int -> [Int]
spigot_e n = 2 : take (n - 1) (f $ replicate (n + 1) 1) where
    f = (\(d,xs) -> d : f xs) .
        mapAccumR (\a (i,x) -> divMod (10*x+a) i) 0 . zip [2..]

A test to see if everything is working properly:

main :: IO ()
main = print $ spigot_e 30