Code Kata - Coin Change Problem

(Ported from the original post on Mad Props!)

Remember the old problem you had to tackle when you were first learning to program, where you had to output how many of each coin denomination made up a given value? I thought I’d tackle it using Linq to see how it might look in modern C#.

Here’s my first attempt:

var coins = new[] { 1, 2, 5, 10, 20, 50, 100 };
var amount = 3347;

var solution = coins
    .OrderByDescending(c => c)
    .TakeWhile(_ => amount > 0)
    .Select(c => new { Coin = c, Number = amount / c, Remainder = (amount %= c) })
    .Where(i => i.Number > 0);

foreach (var i in solution)
{
    Console.WriteLine("{0} x {1}c", i.Number, i.Coin);
}

This uses OrderByDescending so that the coins don’t need to be defined in any particular order, and reduces the “amount” each time inside the assignment to the “Remainder” property.

What do you think? It’s interesting, tackling these age-old problems with fresh approaches. If you search for “code kata” you’ll find many people writing modern code to do things like finding prime numbers etc. I haven’t seen this particular problem being attacked (perhaps because it’s so simple). If you have a better way to do it, let me know in a comment or a post of your own.

kata .net c#
Posted by: Matt Hamilton
Last revised: 28 Jul, 2010 05:10 AM History

Comments

22 Aug, 2010 03:50 AM

If you're aiming for the least amount of coins (which is often a requirement of the coin change problem, your algorithm fails on:
5c, 10c, 20c, 25c to make 40c.
Greedy solution: 25c, 10c, 5c
Optimal solution: 2 x 20c

Nor does it find a correct solution to:
coins: 10, 20, 25
amount: 30

No new comments are allowed on this post.