I was reading about the “Vending Machine Change” problem the other day. This is a well known problem, which I’m afraid to admit I had never heard of, but I thought it was interesting enough to take a look at now.
Basically the problem that we’re trying to solve is – you need to write the software to calculate the minimum number of coins required to return an amount of change to the user. In other words if a vending machine had the coins 1, 2, 5 & 10, what is the minimum number of coins required to make up the change of 43 pence (or whatever units of currency you want to use).
The coin denominations should be supplied, so the algorithm is not specific to the UK or any other country and the amount in change should also be supplied to the algorithm.
First Look
This is a standard solution to the Vending Machine problem (please note: this code is all over the internet in various languages, I’ve just made a couple of unimpressive changes to it)
static int Calculate(int[] coins, int change)
{
int[] counts = new int[change + 1];
counts[0] = 0;
for(int i = 1; i <= change; i++)
{
int count = int.MaxValue;
foreach(int coin in coins)
{
int total = i - coin;
if(total >= 0 && count > counts[total])
{
count = counts[total];
}
}
counts[i] = (count < int.MaxValue) ? count + 1 : int.MaxValue;
}
return counts[change];
}
What happens in this code is that we create an array counts which will contains the minimum number of coins for each value between 1 and the amount of change required. We use the 0 index as a counter start value (hence we set counts[0] to 0).
Next we look through each possible change value calculating the number of coins required to make up each value, we use the int.MaxValue to indicate no coins could be found to match the amount of change.
This algorithm assumes an infinite number of coins of each denomination, but this is obviously an unrealistic scenario, so let’s have a look at my attempt to solve this problem for a finite number of each coin.
Let’s try to make things a little more complex
So, as mentioned above, I want to now try to calculate the minimum number of coins to produce the amount of change required, where the number of coins of each denomination is finite.
Let’s start by defining a Coin class
public class Coin
{
public Coin(int denomition, int count)
{
Denomination = denomition;
Count = count;
}
public int Denomination { get; set; }
public int Count { get; set; }
}
Before I introduce my attempt at a solution, let’s write some tests, I’ve not got great names for many of the tests, they’re mainly for me to try different test scenarios out, but I’m sure you get the idea.
public class VendingMachineTests
{
private bool Expects(IList<Coin> coins, int denomination, int count)
{
Coin c = coins.FirstOrDefault(x => x.Denomination == denomination);
return c == null ? false : c.Count == count;
}
[Fact]
public void Test1()
{
List<Coin> coins = new List<Coin>
{
new Coin(10, 100),
new Coin(5, 100),
new Coin(2, 100),
new Coin(1, 100),
};
IList<Coin> results = VendingMachine.Calculate(coins, 15);
Assert.Equal(2, results.Count);
Assert.True(Expects(results, 10, 1));
Assert.True(Expects(results, 5, 1));
}
[Fact]
public void Test2()
{
List<Coin> coins = new List<Coin>
{
new Coin(10, 100),
new Coin(5, 100),
new Coin(2, 100),
new Coin(1, 100),
};
IList<Coin> results = VendingMachine.Calculate(coins, 1);
Assert.Equal(1, results.Count);
Assert.True(Expects(results, 1, 1));
}
[Fact]
public void Test3()
{
List<Coin> coins = new List<Coin>
{
new Coin(10, 1),
new Coin(5, 1),
new Coin(2, 100),
new Coin(1, 100),
};
IList<Coin> results = VendingMachine.Calculate(coins, 20);
Assert.Equal(4, results.Count);
Assert.True(Expects(results, 10, 1));
Assert.True(Expects(results, 5, 1));
Assert.True(Expects(results, 2, 2));
Assert.True(Expects(results, 1, 1));
}
[Fact]
public void NoMatchDueToNoCoins()
{
List<Coin> coins = new List<Coin>
{
new Coin(10, 0),
new Coin(5, 0),
new Coin(2, 0),
new Coin(1, 0),
};
Assert.Null(VendingMachine.Calculate(coins, 20));
}
[Fact]
public void NoMatchDueToNotEnoughCoins()
{
List<Coin> coins = new List<Coin>
{
new Coin(10, 5),
new Coin(5, 0),
new Coin(2, 0),
new Coin(1, 0),
};
Assert.Null(VendingMachine.Calculate(coins, 100));
}
[Fact]
public void Test4()
{
List<Coin> coins = new List<Coin>
{
new Coin(10, 1),
new Coin(5, 1),
new Coin(2, 100),
new Coin(1, 100),
};
IList<Coin> results = VendingMachine.Calculate(coins, 3);
Assert.Equal(2, results.Count);
Assert.True(Expects(results, 2, 1));
Assert.True(Expects(results, 1, 1));
}
[Fact]
public void Test5()
{
List<Coin> coins = new List<Coin>
{
new Coin(10, 0),
new Coin(5, 0),
new Coin(2, 0),
new Coin(1, 100),
};
IList<Coin> results = VendingMachine.Calculate(coins, 34);
Assert.Equal(1, results.Count);
Assert.True(Expects(results, 1, 34));
}
[Fact]
public void Test6()
{
List<Coin> coins = new List<Coin>
{
new Coin(50, 2),
new Coin(20, 1),
new Coin(10, 4),
new Coin(1, int.MaxValue),
};
IList<Coin> results = VendingMachine.Calculate(coins, 98);
Assert.Equal(4, results.Count);
Assert.True(Expects(results, 50, 1));
Assert.True(Expects(results, 20, 1));
Assert.True(Expects(results, 10, 2));
Assert.True(Expects(results, 1, 8));
}
[Fact]
public void Test7()
{
List<Coin> coins = new List<Coin>
{
new Coin(50, 1),
new Coin(20, 2),
new Coin(15, 1),
new Coin(10, 1),
new Coin(1, 8),
};
IList<Coin> results = VendingMachine.Calculate(coins, 98);
Assert.Equal(3, results.Count);
Assert.True(Expects(results, 50, 1));
Assert.True(Expects(results, 20, 2));
Assert.True(Expects(results, 1, 8));
}
}
Now, here’s the code for my attempt at solving this problem, it uses a “Greedy” algorithm, i.e. trying to find the largest coin(s) first. The code therefore requires that the coins are sorted largest to smallest, I have not put the sort within the Calculate method because it’s recursively called, so it’s down to the calling code to handle this.
There may well be a better way to implement this algorithm, obviously one might prefer to remove the recursion (I may revisit the code when I have time to implement that change).
public static class VendingMachine
{
public static IList<Coin> Calculate(IList<Coin> coins, int change, int start = 0)
{
for (int i = start; i < coins.Count; i++)
{
Coin coin = coins[i];
// no point calculating anything if no coins exist or the
// current denomination is too high
if (coin.Count > 0 && coin.Denomination <= change)
{
int remainder = change % coin.Denomination;
if (remainder < change)
{
int howMany = Math.Min(coin.Count,
(change - remainder) / coin.Denomination);
List<Coin> matches = new List<Coin>();
matches.Add(new Coin(coin.Denomination, howMany));
int amount = howMany * coin.Denomination;
int changeLeft = change - amount;
if (changeLeft == 0)
{
return matches;
}
IList<Coin> subCalc = Calculate(coins, changeLeft, i + 1);
if (subCalc != null)
{
matches.AddRange(subCalc);
return matches;
}
}
}
}
return null;
}
}
Issues with this solution
Whilst this solution does the job pretty well, it’s not perfect. If we had the coins, 50, 20, 11, 10 and 1 the optimal minimum number of coins to find the change for 33 would be 3 * 11 coins. But in the algorithm listed above, the result would be 1 * 20, 1 * 11 and then 2 * 1 coins.
Ofcourse the above example assumed we have 3 of the 11 unit coins in the Vending machine
To solve this we could call the same algorithm but for each call we remove the largest coin type each time. Let’s look at this by first adding the unit test
[Fact]
public void Test8()
{
List<Coin> coins = new List<Coin>
{
new Coin(50, 1),
new Coin(20, 2),
new Coin(11, 3),
new Coin(10, 1),
new Coin(1, 8),
};
IList<Coin> results = VendingMachine.CalculateMinimum(coins, 33);
Assert.Equal(1, results.Count);
Assert.True(Expects(results, 11, 3));
}
To just transition the previous solution to the new improved solution, we’ve simply added a new method named CalculateMinimum. The purpose of this method is to try and find the best solution by calculate with all coins, then we reduce the types of available coins by remove the largest coin, then find the best solution, then remove the next largest coin and so on. Here’s some code which might better demonstrate this
public static IList<Coin> CalculateMinimum(IList<Coin> coins, int change)
{
// used to store the minimum matches
IList<Coin> minimalMatch = null;
int minimalCount = -1;
IList<Coin> subset = coins;
for (int i = 0; i < coins.Count; i++)
{
IList<Coin> matches = Calculate(subset, change);
if (matches != null)
{
int matchCount = matches.Sum(c => c.Count);
if (minimalMatch == null || matchCount < minimalCount)
{
minimalMatch = matches;
minimalCount = matchCount;
}
}
// reduce the list of possible coins
subset = subset.Skip(1).ToList();
}
return minimalMatch;
}
Performance wise, this (in conjunction with the Calculate method) are sub-optimal if we needed to calculate such minimum numbers of coins many times in a short period of time. A lack of state means we may end up calculating the same change multiple times. Ofcourse we might save such previous calculations and first check whether the algorithm already has a valid solution each time we calculate change if performance was a concern and/or me might calculate a “standard” set of results at start up. For example if we’re selling can’s of drinks for 80 pence we could pre-calculate change based upon likely inputs to the vending machine, i.e. 90p, £1 or £2 coins.
On and we might prefer to remove to use of the Linq code such as Skip and ToList to better utilise memory etc.
References
http://onestopinterviewprep.blogspot.co.uk/2014/03/vending-machine-problem-dynamic.html
http://codercareer.blogspot.co.uk/2011/12/no-26-minimal-number-of-coins-for.html
http://techieme.in/techieme/minimum-number-of-coins/
http://www.careercup.com/question?id=15139685