Programming Praxis – Coin Change, Part 1, C# Solutions

This post presents C# solutions to a coin change problem as described in http://programmingpraxis.com/2013/05/17/coin-change-part-1.

It is a classic problem from computer science to determine the number of ways in which coins can be combined to form a particular target; as an example, there are 31 ways to form 40 cents from an unlimited supply of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), ranging from the 3-coin set (5 10 25) to the 40-coin set consisting only of pennies.

Your task is to write two functions, one to determine the count and one to determine the list of coins. 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.

As the original post for this problem states, it appears to be most easily solvable using a recursive approach. Let’s start the thought process of solving such a problem like this. I naturally would begin by figuring out a systematic process of coming up with all the possibilities of combinations. Once the process is devised, you can the deduce an algorithm.

Start out with a simple concrete example. Naturally I thought: “at each step in the process, keep subtracting the largest allowable coin from the remaining total, until you reach a solution”. A coin would be allowable if it is equal or less than the remaining total. So if n = 40:

n = 40, set = []

Step 1: The largest allowable coin is 25 (25 < 40)

n = 15 (40 - 25), set = [25]

Step 2: The largest allowable coin is 10 (10 < 15)

n = 5 (10 - 15), set = [25, 10]

Step 3: The largest allowable coin is 5 (5 < 10)

n = 0 (5 - 5), set = [25, 10, 5]

Done!

Where to from here? Well lets enumerate all solutions with the 25 coin:

25, 10, 5

25, 10, 1, 1, 1, 1, 1

25, 5, 5, 5

25, 5, 5, 1,1,1,1,1

25, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

25, 1,1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

For each successive solution, we are breaking down each coin from the previous solution in as many ways as possible. However you wouldn’t want to break down the same coin in a previous solution more than once. e.g. for set [25,5,5,5] you wouldn’t want break down the coin 5 any more than once: [25, 5, 5, 1,1,1,1,1], [25, 5, 1,1,1,1,1, 5], [25, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1] etc. How do you avoid this? Look at the concrete example of coin sets above. Notice any patterns? There are a few. In relation to these cases we want to avoid, we could avoid duplicating coin sets by ensuring that for each breakdown the new coin selection is less or equal to the previous step’s selected coin (see the concrete example above, all the coins are ordered descendingly). Lets code it using recursion:

public class CoinChange1
{
	private int[] cs = new [] {25, 10, 5, 1};

	private List<ICollection<int>> solutions = new List<ICollection<int>> ();

	public static IList<ICollection<int>> GetCoinSets(int total) {
		// Handle corner case outside of recursive solution
		if (total == 0)
			return new List<ICollection<int>> ();

		// Get all possible sets
		var cc = new CoinChange1 ();
		cc.GetCoinSets (total, 0, new Stack<int>());
		return cc.solutions;
	}

	private void GetCoinSets(int n, int csi, Stack<int> combo) {
	        // Find largest allowable coin (exploiting that cs is ordered descendingly)
		while (cs[csi] > n)
			csi++;
		int c = cs [csi];

		combo.Push (c); // Track coin selection
		if (n == c)
			solutions.Add(combo.ToArray()); // Base case
		else
			GetCoinSets (n - c, csi, combo); // Recursion 1: with a selected coin
		combo.Pop ();

		// Recurse for all other possibilities beyond this point with a combo of smaller coin units
		if(csi < (cs.Length - 1))
			GetCoinSets (n, csi + 1, combo);
	}
}

And there we have it. This problem does have overlapping subsolutions, and so it could possibly be optimized using memoization. However this would add a lot of overhead: as it would mean caching collections of all possible coin subsets, and many memory copy operations to build up new sub-sets off other sub solutions. Sounds more costly than being worthwhile. So we will stick with this solution.

But we are not finished: the problem statement said to write another function to count the total possible coin sets for a given total (n). A naive approach would be to re-use our solution above, and return the length of the collection. But we can do better:

        private int GetCoinSetCount(int n, int csi) {
		while (cs[csi] > n)
			csi++;
		int c = cs [csi];

		int count;
		if (n == c)
			count = 1;
		else
			count = GetCoinSetCount (n - c, csi);

		if(csi < (cs.Length - 1))
			count += GetCoinSetCount (n, csi + 1);

		return count;
	}

I’ve omitted a wrapper function to neatly package the API (passing 0 for csi argument and a sanity check for total = 0). The performance has improved since we don’t need to maintain a list of selected coins throughout the recursive calls. But we can still do better!

Now that we don’t have to deal with passing around complex data per sub solution (lists), and so memoization is worthwhile here:

public class CoinChange1
{
	private Dictionary<ulong, uint> cache = new Dictionary<ulong, uint>();

	public static uint GetCountSetCount(uint total) {
		if (total == 0)
			return 0;
		return new CoinChange1().GetCoinSetCount (total, 0);
	}

	private uint GetCoinSetCount(uint n, byte csi) {
		while (cs[csi] > n)
			csi++;
		uint c = (uint)cs [csi];

		uint count;
		if (n == c) {
			count = 1;
		} else {
			uint nextn = n - c;
			ulong key = ((ulong)nextn << 32) | (ulong)csi;
			if(!cache.TryGetValue(key, out count)) {
				count = GetCoinSetCount (nextn, csi);
				cache[key] = count;
			}
		}

		if(csi < (cs.Length - 1)) {
			ulong key = ((ulong)n << 32) | ((ulong)csi + 1);
			uint subCount;
			if(!cache.TryGetValue(key, out subCount)) {
				subCount = GetCoinSetCount (n, (byte)(csi + 1));
				cache[key] = subCount;
			}
			count += subCount;
		}
		return count;
	}
}

I’ve changed the arguments and return types to unsigned, since I’m making a performance enhancement for the cache key. Since the key is composite (the arguments to the recursive functions), I pack them in a single unsigned long rather than using a Tuple or some custom class/struct. A petty improvement but an improvement nonetheless.

About these ads

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