Apparently simple code - Luca Bolognese

Apparently simple code

Luca -

☕ 1 min. read

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);
}
}
5 Comments

Comments

barrkel

2007-02-01T17:24:22Z

I don't get it - the code is straightforward recursion, there's nothing complex about it at all. If you've competed in any programming competitions, these kinds of problems are entry-level stuff.
The number of ways is 1 if there's no sum left, otherwise it's the number of ways by using all the remaining coins (i.e. skipping this denomination) plus the number of ways by using the coin (i.e. subtracting its value from the amount). It's immediately obvious.

lucabol

2007-02-01T20:56:09Z

Well ... to me it is not 'immediately obvious'. I had to sketch it on my whiteboard to visualize it. I guess I'm a much worse programmer than you are.
Anyhow, I would have never thought of this algo if someone gave me the text of the problem. I would have come up with something way more convoluted.
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 doesn't work. (At least past 9)  It counts giving (one 5 and five 1's) and (five 1's and one 5) and similar reversals as being distinct.  It's still pretty cool though.  I implemented this to run on .NET 1.1 to check it out.  When it gave these results, I thought it was strange, so I downloaded and ran it on the LINQ May CTP that you originally tested it on, and they give the same result.  I guess if you consider the order 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 result:(111111111)(111115)(55). It is not double counting the reversal. When I try to get 15 with [1,5] it gives me 4, which is correct again. Am I misunderstanding you?
BTW: if you try [1,5,5] you get 10. It considers the two 5s as different coins. If you don't want this behavior you can simply rename ChangeComb as ChangeCompTemp and add:
static int ChangeComb(int amount, IEnumerable<int> coins)
{
     return ChangeCompTemp(amount, coins.Distinct());
}

0 Webmentions

These are webmentions via the IndieWeb and webmention.io.