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

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, combinator, fix, Haskell, kata, mcnugget, numbers, praxis, programming, y

This entry was posted on April 13, 2012 at 2:38 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply