The Twelve Days Of Christmas
December 25, 2012
You all know the old song:
On the first day of Christmas my true love gave to me a partridge in a pear tree.
On the second day of Christmas my true love gave to me two turtle doves and a partridge in a pear tree.
On the third day of Christmas my true love gave to me three French hens, two turtle doves and a partridge in a pear tree.
On the fourth day of Christmas my true love gave to me four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the fifth day of Christmas my true love gave to me five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the sixth day of Christmas my true love gave to me six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the seventh day of Christmas my true love gave to me seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the eighth day of Christmas my true love gave to me eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the ninth day of Christmas my true love gave to me nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the tenth day of Christmas my true love gave to me ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the eleventh day of Christmas my true love gave to me eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
On the twelfth day of Christmas my true love gave to me twelve drummers drumming, eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.
Your task is to write a program that determines how many gifts were given in N days, and use it to compute the number of gifts given in 12 days. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
This problem statement leaves some ambiguity, as the number of gifts given in N days depends exactly on which of the 12 days gifts were given. In addition to the parameter N, a consecutive range or non-consecutive set of days must be specified in order to know how many gifts were given in total.
Gifts that day: 2**n-1 or n(n+1)/2
Gifts total: n**2
At least I think that is what it is, assuming the following:
1. The number of gifts received is not modular, and
2. The gifts received = n + n-1 + n-2 + n-3 + … + 1.
An edit to my previous post, 2**n-1 doesn’t work, sorry.
Not so elegant solutions, the first is recursive,
— recursive
crimbo presents 0 = presents
crimbo presents days = crimbo (presents + loot) (days-1)
where loot = sum [1..days]
twelve_days = crimbo 0
— using map
f a b = (a + b) * ((1 + (b – a)) / 2)
tolv_dager days = sum $ map (f 1) [1..days]
*Main> twelve_days 12
364
*Main> tolv_dager 12
364.0
sum $ map (\x -> (1+x) * (x/2)) [1..12]
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]
My Java solution here.
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]
import Data.List (genericLength, mapAccumL, intercalate) import Data.Ratio import RecMath.GaussElim import System.Environment -- For efficiency (and fun!), we can find a polynomial that is equivalent to the -- function totalGifts. We calculate the differences between successive values -- of the function, differences of the differences, and so on. For example, -- using our 12 days problem: -- -- n 1 2 3 4 5 ... -- f(n) 1 4 10 20 35 ... -- d(1) 3 6 10 15 ... -- d(2) 3 4 5 ... -- d(3) 1 1 ... -- d(4) 0 ... -- -- If the i'th difference is equal to 0 then we use the first i function values -- to construct a linear system of equations to solve for the coefficients of -- the polynomial. The equations are generated by plugging into: -- -- c n^(i-1) + c n^(i-2) + ... + c n + c = f(n) -- i-1 i-2 1 0 -- -- the i different values. In our 12 days problem, this leads to: -- -- a + b + c + d = 1 -- 8a + 4b + 2c + d = 4 -- 27a + 9b + 3c + d = 10 -- 64a + 16b + 4c + d = 20 -- -- Upon solving this system we get a=1/6, b=1/2, c=1/3 and d=0. So, the -- resulting polynomial is: -- -- 1/6 n^3 + 1/2 n^2 + 1/3 n -- -- Of course, all of the above depends on the ability to represent our function -- with a polynomial. -- -- See http://www.math.cmu.edu/~bkell/21110-2010s/formula.html for more detail. -- Given a function, f, and an initial value, i, return the coefficients of a -- polynomial equivalent to the function. It's assumed that f can be -- represented by a polynomial. coefs :: (Integral a, Integral b) => (a -> b) -> a -> [Rational] coefs f i = let vs = values f i sz = length vs m = map (mkRow sz . fromIntegral . fst) vs x = map (fromIntegral . snd) vs in linearSolve m x where mkRow len = scanl (*) 1 . replicate (len-1) -- Given a function, f, and an initial value, i, return the list of pairs, -- [(i, f(i)), (i+1, f(i+1)), ..., (n, f(n))], sufficient to allow the -- calculation of the equivalent polynomial. values :: (Integral a, Eq b, Num b) => (a -> b) -> a -> [(a, b)] values f i = map (\k -> (k, f k)) [i..i+n-1] where n = genericLength $ last diffs diffs = takeWhile ((/=0) . last) . tail . scanl step [] $ map f [i..] step = flip $ scanl (-) -- Evaluate a polynomial at a given value. The polynomial is represented by a -- list of coefficients. eval :: (Num a, Integral b) => [a] -> b -> a eval cs n = let n' = fromIntegral n in foldr (\l r -> l+n'*r) 0 cs showRat :: Rational -> String showRat r | denominator r == 1 = show $ numerator r | otherwise = show (numerator r) ++ "/" ++ show (denominator r) showPoly :: [Rational] -> String showPoly cs = let terms = snd $ mapAccumL (\n c -> (n+1, term c n)) 0 cs in intercalate " + " $ filter (not . null) terms where term 0 _ = "" term c p = showRat c ++ "n^" ++ show p -------------------------------------------------------------------------------- giftsOnDay :: [Int] giftsOnDay = 0 : [n | i <- [1..], let n = i + giftsOnDay !! (i-1)] totalGifts :: Int -> Int totalGifts n = sum $ take (n+1) giftsOnDay main :: IO () main = do args <- getArgs let nDays = read $ head args :: Int tot = eval cs nDays cs = coefs totalGifts 1 putStrLn $ "The total number of gifts after " ++ show nDays ++ " days is " ++ showRat tot ++ "." putStrLn $ "A polynomial for the total number of gifts is " ++ showPoly csWhen run, this produces:
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]