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.

About these ads

Pages: 1 2

9 Responses to “The Twelve Days Of Christmas”

  1. Dan said

    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.

  2. Matthew Feng said

    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.

  3. Matthew Feng said

    An edit to my previous post, 2**n-1 doesn’t work, sorry.

  4. Ben said

    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

  5. Ben E Oliver said

    sum $ map (\x -> (1+x) * (x/2)) [1..12]

  6. [...] The Twelve Days Of Christmas (programmingpraxis.com) [...]

  7. [...] The Twelve Days Of Christmas (programmingpraxis.com) [...]

  8. Globules said
    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 cs
    

    When run, this produces:

    $ ./xmas 12
    The total number of gifts after 12 days is 364.
    A polynomial for the total number of gifts is 1/3n^1 + 1/2n^2 + 1/6n^3
    $ 
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 617 other followers

%d bloggers like this: