Apparently simple code

-

Sometimes what looks sim­ple is com­plex and what looks com­plex is sim­ple. See if you can un­der­stand how this one cal­cu­lates all the pos­si­ble ways to give change for a cer­tain amount of money given some kinds of coins. You MIT guys out there don’t count, you prob­a­bly have read the so­lu­tion in the same book I have.

BTW: the code works with the LINQ May CTP …

using System;

using System.Collections.Generic;

using System.Text;

using System.Query;

using System.Xml.XLinq;
class Program
{
static void Main(string[] args)
{
var coins = new int[] { 1, 5, 10, 25, 50 };

var i = ChangeComb(100, coins);
Console.WriteLine(i);
}

static int ChangeComb(int amount, IEnumerable<int> coins)
{
if (amount == 0) return 1;
if (amount < 0) return 0;
if (coins.Count() == 0) return 0;

return ChangeComb(amount, coins.Skip(1)) +
ChangeComb(amount - coins.First(), coins);
}
}

Tags

5 Comments

Comments

barrkel

2007-02-01T17:24:22Z

I don’t get it - the code is straight­for­ward re­cur­sion, there’s noth­ing com­plex about it at all. If you’ve com­peted in any pro­gram­ming com­pe­ti­tions, these kinds of prob­lems are en­try-level stuff.
The num­ber of ways is 1 if there’s no sum left, oth­er­wise it’s the num­ber of ways by us­ing all the re­main­ing coins (i.e. skip­ping this de­nom­i­na­tion) plus the num­ber of ways by us­ing the coin (i.e. sub­tract­ing its value from the amount). It’s im­me­di­ately ob­vi­ous.

lucabol

2007-02-01T20:56:09Z

Well … to me it is not ‘immediately ob­vi­ous’. I had to sketch it on my white­board to vi­su­al­ize it. I guess I’m a much worse pro­gram­mer than you are.
Anyhow, I would have never thought of this algo if some­one gave me the text of the prob­lem. I would have come up with some­thing way more con­vo­luted.
But again, that’s just me …

Charlie Calvert's Community Bl

2007-02-19T13:08:37Z

Welcome to the twenty-first Community Convergence. I’m Charlie Calvert, the C# Community PM, and this

choatea

2007-02-26T17:49:49Z

This does­n’t work. (At least past 9)  It counts giv­ing (one 5 and five 1′s) and (five 1′s and one 5) and sim­i­lar re­ver­sals as be­ing dis­tinct.  It’s still pretty cool though.  I im­ple­mented this to run on .NET 1.1 to check it out.  When it gave these re­sults, I thought it was strange, so I down­loaded and ran it on the LINQ May CTP that you orig­i­nally tested it on, and they give the same re­sult.  I guess if you con­sider the or­der in which you give the types of coins, it works.  Small gripe I know…

lucabol

2007-02-27T17:54:32Z

When I try to get 10 with [1,5] or [5,1] it gives me 3 as a re­sult:(111111111)(111115)(55). It is not dou­ble count­ing the re­ver­sal. When I try to get 15 with [1,5] it gives me 4, which is cor­rect again. Am I mis­un­der­stand­ing you?
BTW: if you try [1,5,5] you get 10. It con­sid­ers the two 5s as dif­fer­ent coins. If you don’t want this be­hav­ior you can sim­ply re­name ChangeComb as ChangeCompTemp and add:
sta­tic int ChangeComb(int amount, IEnumerable<int> coins)
{
     return ChangeCompTemp(amount, coins.Dis­tinct());
}