Jan
30
2008
Coding Challenge

2008 Coding Challenge I

An article by ehosca No Comments

The United States Postal Service currently sells stamps in the following denominations :

$0.01, $0.02, $0.03, $0.04, $0.05, $0.10, $0.24, $0.37, $0.39, $0.41, $0.48, $0.60, $0.63, $0.70,$0.75, $0.80, $0.83, $0.84, $0.87, $1.00, $3.85, $4.05, $4.60, $5.00, $14.40

James is preparing a small package to send out to his friend. The particular box that James has chosen has only enough room for 10 stamps after the address label is affixed.

What is the *minimum* amount of postage that cannot be placed on the box assuming James has an infinite number of stamps in each denomination ?

 

its : $89.96 which would require 11 stamp from the given denominations ...

 

using System;
using System.Collections.Generic;
using System.Linq;

namespace PostOfficePuzzle
{
    internal static class Program
    {
        /// 
        /// The main entry point for the application.
        /// 
        [STAThread]
        private static void Main()
        {
            var denominations =
                new List{1,2,3,4,5,10,24,37,39,41,48,60,63,70,
                              75,80,83,84,87,100,385,405,460,500,1440};
            // list of stamps
            List postage;

            // list of list of stamps 
            var solutions = new List>();

            // init single stamp solutions 
            foreach (int i in denominations)
                solutions.Add(new List(new[] {i}));

            for (int targetPostage = 0; targetPostage < int.MaxValue; targetPostage++)
            {
                postage = (from d in denominations
                           from s in solutions
                           where (d + s.Sum(i => i)).Equals(targetPostage)
                           orderby s.Count descending
                           select (new List(new[] {d}.Concat(s)))).LastOrDefault();

                if (postage != null)
                {
                    solutions.Add(postage);
                    WritePostage(postage);

                    // exit condition
                    if (postage.Count > 10)
                        Console.ReadLine();
                }
            }
        }

        private static void WritePostage(List postage)
        {
            string stampsList = string.Join(" , "
                                            , postage.ConvertAll(s => string.Format("{0:C}"
                                                                , (double) s/100)).ToArray());

            Console.WriteLine(string.Format("Postage = {0:C} Count = {1} Stamps = {2}"
                                            , (double) postage.Sum(i => i)/100
                                            , postage.Count
                                            , stampsList));
        }
    }
}

 

Month List