## Archive for April, 2012

### Programming Praxis – Trabb Pardo Knuth Algorithm

April 27, 2012

In today’s Programming Praxis exercise, our goal is to implement a simple algorithm that could serve as an alternative to FizzBuzz. Let’s get started, shall we?

A quick import:

`import Control.Monad`

The algorithm calls for applying a function to values. We could ofcourse inline it since in Haskell that’s technically still a case of applying a function, but I think making it a separate function better matches the spirit of the description.

```f :: Double -> Double
f x = sqrt (abs x) + 5 * x^3```

The algorithm itself is fairly trivial: read the numbers, reverse them, apply the function and print the result or an overflow message.

```main :: IO ()
main = mapM_ (putStrLn . (\x -> if x > 400 then "TOO LARGE" else show x) . f) .

### Programming Praxis – McNugget Numbers, Revisited

April 13, 2012

In today’s Programming Praxis exercise, our goal is to calculate the number of ways a number can be expressed as a McNugget number. Let’s get started, shall we?

A quick import:

`import Control.Monad.Identity`

We use the same basic technique of building up a table of numbers where each number is the sum of the number above it and the number x spaces to its left, with x being the size of the McNugget box. We construct it differently though; rather than explicitly setting array values we use a bit of laziness to express the whole thing as a fold. The first row is a 1 followed by zeroes. For each subsequent row, we use the same principle as for the typical implementation of the Fibonacci algorithm, namely zipping a list with itself (using the fix function to avoid having to name it). The first x spaces of the previous row are maintained by adding zero to them.

```mcNuggetCount :: Num a => [Int] -> Int -> a
mcNuggetCount xs n = foldl (\a x -> fix \$
zipWith (+) a . (replicate x 0 ++)) (1 : repeat 0) xs !! n```

Some tests to see if everything works properly:

```main :: IO ()
main = do print \$ mcNuggetCount [6,9,20] 1000000 == 462964815
print \$ mcNuggetCount [1,5,10,25,50,100] 100 == 293
print \$ mcNuggetCount [1,2,5,10,20,50,100,200] 200 == 73682```

### Programming Praxis – Galton

April 10, 2012

In today’s Programming Praxis exercise, our goal is to simulate a Galton board and display the frequencies of the different bins as a histogram. Let’s get started, shall we?

Some imports:

```import Control.Applicative
import System.Random```

When dropping a single marble we simulate a number of coin tosses to see which bin the marble ends up in.

```marble :: Int -> IO Int
marble bins = sum . take (bins - 1) . randomRs (0, 1) <\$> newStdGen```

When dropping multiple marbles we count how often each bucket is hit.

```marbles :: Num a => Int -> Int -> IO [a]
marbles n bins = flip fmap (replicateM n \$ marble bins) (\results ->
map (fromIntegral . length . flip filter results . (==)) [0..bins - 1])```

Displaying the histogram is a matter of scaling the values and printing the appropriate amount of asterisks. You can choose the horizontal scaling to get more or less detailed results.

```histogram :: RealFrac a => a -> [a] -> IO ()
histogram w cols = mapM_ (\n ->
putStrLn \$ replicate (ceiling \$ n * w / maximum cols) '*') cols```

The program itself consists of printing the results of the simulation as a histogram.

```main :: IO ()
main = histogram 20 =<< marbles 1000 8```