Posts Tagged ‘digits’

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

Programming Praxis – Same Five Digits

April 19, 2011

In today’s Programming Praxis exercise, our goal is to solve a numeric riddle. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.List.Key as K

The relevant squares are the ones that consists only of the digits 1 through 5. The explanation as to why can be found in the provided solution.

squares :: [Integer]
squares = filter (all (`elem` "12345") . show) .
          takeWhile (< 100000) $ map (^2) [100..]

The rest of the riddle can be solved with picking the correct element out of a list comprehension. Note the conditions that a < b and b < c. This prevents the same triple occurring in different permutations. I originally hadn’t included these, which is why I couldn’t get it working initially.

sameFive :: Maybe (Integer, Integer, Integer)
sameFive = fmap (fst . head) . find (null . tail) . K.group snd $ K.sort snd
           [ ((a,b,c), findIndex (== 1) dc)
           | a <- squares, b <- squares, a < b, c <- squares, b < c
           , let dc = map length . group . sort $ show =<< [a,b,c]
           , sort dc == [1..5], and $ zipWith (/=) dc [1..5]
           ]

All that’s left to do is to see if we get the correct answer.

main :: IO ()
main = print sameFive