# Decimal Quantities needed to meet cost

I asked this question recently: Finding the number of capital letters in a word grouped by letter. The answerer answered my specific question so I have marked it as answered. However, I would like to ask a similar question. The reason I am asking a similar question is because the code in my last question was too simple i.e. simple string manipulations. Therefore I have made this code a little more complex in the hope that my question about rich domain models (question one below) will be answered.

The code below calculates the currency that should be provided in order to meet a cost going from highest to lowest. For example, if the cost is: 152.45, then the following decimals (unit of currencies are required):

3 * £50 note
1* £2 coin
2 * £0.20
1 * 0.5


Client App - this is the same for both options

DecimalCounter dc = new DecimalCounter(1552.78M);


Option 1

   public class DecimalCounter
{
public decimal Cost { get; set; }
List<KeyValuePair<decimal, int>> DecimalsToUseList;

public DecimalCounter(decimal _Cost)
{
Cost = _Cost;
DecimalQuantities cq = new DecimalQuantities();
DecimalsToUseList = cq.GetDecimalsToUse(_Cost);
}

public class DecimalQuantities
{
int _Quantity;
decimal _Amount;

public List<decimal> GetDecimalList()
{
List<decimal> DecimalList = new List<decimal>();
DecimalList = new List<decimal>();
return DecimalList;
}

public List<KeyValuePair<decimal, int>> GetDecimalsToUse(decimal Cost)
{
List<KeyValuePair<decimal, int>> DecimalQuantitiesList = new List<KeyValuePair<decimal, int>>();

List<decimal> DecimalList = GetDecimalList();
decimal QuantityOfDecimal = 0;
foreach (decimal DecimalAmount in DecimalList)
{
if (Cost >= DecimalAmount)
{
QuantityOfDecimal = Cost / DecimalAmount;
if (QuantityOfDecimal > 0)
{
int QuantityOfDecimalInt = (int)Math.Floor(QuantityOfDecimal);
{
DecimalQuantitiesList = new List<KeyValuePair<decimal, int>>();
}
//KeyValuePair<decimal, int> test = new KeyValuePair<decimal, int>(DecimalAmount, QuantityOfDecimalInt);
Cost = Cost - (QuantityOfDecimalInt * DecimalAmount);
}
}
}
return DecimalQuantitiesList;

}

}
}


Option 2

public class DecimalCounter
{
public decimal Cost { get; set; }
private List<decimal> DecimalList { get; set; }
List<KeyValuePair<decimal, int>> DecimalQuantitiesList;

public DecimalCounter(decimal _Cost)
{
Cost = _Cost;
GetDecimalList();
GetDecimalsToUse();
}

public void GetDecimalList()
{
DecimalList = new List<decimal>();
}

private void GetDecimalsToUse()
{
decimal CostOutStanding=Cost;
decimal QuantityOfDecimal = 0;
foreach (decimal DecimalAmount in DecimalList)
{
if (CostOutStanding >= DecimalAmount)
{
QuantityOfDecimal = CostOutStanding / DecimalAmount;
if (QuantityOfDecimal > 0)
{
int QuantityOfDecimalInt = (int)Math.Floor(QuantityOfDecimal);
{
DecimalQuantitiesList = new List<KeyValuePair<decimal, int>>();
}
//KeyValuePair<decimal, int> test = new KeyValuePair<decimal, int>(DecimalAmount, QuantityOfDecimalInt);
CostOutStanding = CostOutStanding - (QuantityOfDecimalInt * DecimalAmount);
}
}
}

}
}


Analysis

The difference between the two options is that option one stores the decimal quantities in a dictionary and in option 2, there is a class for decimal quantities.

1. Which option is "better" from a Domain Driven Development (Rich Domain Model)/unit testing point of view? (this is the most important question). Is there a better option than the options I have provided?

2. In option 1; can I use a decimal as the key of the KeyValuePair? The answerer of my previous question (see hyperlink in first paragraph) said I can use strings and integers but was unsure about decimals. I believe I can because I believe the decimals are always unique.

3. Should I be using Singletons for these types? They are value types and they do not have an ID so I believe I should.

• For speed check out the integer version I added to my answer. Jun 7 '17 at 17:34

This applies everywhere but parameters to methods should be camelCase:

public DecimalCounter(decimal _Cost)


should be

public DecimalCounter(decimal cost)


I'd advise you to look at the naming guidelines on msdn.

I'd say that neither of your solutions are particularly good from either a rich domain or a TDD point of view. It's all too coupled.

Why does DecimalCounter provide it's own list of denominations? It's also poorly named.

Why not abstract the available denominations?

public interface ICurrency
{
string Name { get; }
IEnumerable<int> AvailableDenominations { get; }
}


Then your CurrencyCalculator:

public class CurrencyCalculator
{

public CurrencyCalculator(ICurrency currency)
{
this.currency = currency;
}

public IEnumerable<KeyValuePair<int, int>> CalculateDenominationsFor(int cost)
{
var target = cost;
foreach (var denomination in currency.AvailableDenominations.OrderByDescending(a => a))
{
var numberRequired = target / denomination;
if (numberRequired > 0)
{
yield return new KeyValuePair<int, int>(denomination, numberRequired);
}
target = target - (numberRequired * denomination);
}
}
}


You'll notice that I've converted everything to int. If you just work in the base unit for a currency (e.g. pence, cents etc.) then you don't have to work with decimal at all.

This more decoupled code adds a few benefits:

1. You can test against different currencies which have different denominations available
2. CalculateDenominationsFor returns a value which makes unit testing easier

# Update

I added an implementation to the CalculateDenominationsFor method and here's a working example:

public class Gbp : ICurrency
{
public string Name { get; } = "Pound Sterling";

public IEnumerable<int> AvailableDenominations {get;} =
new List<int>
{
1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000
};
}

void Main()
{
var calculator = new CurrencyCalculator(new Gbp());
var result = calculator.CalculateDenominationsFor(123);
// { { 100, 1 }, { 20, 1 }, { 2, 1 }, { 1, 1 } }
}


# Update 2

One thing I didn't mention was that by working in the base unit with an int the maximum value you can calculate is quite limited. If you need to work with bigger numbers, use long instead :)

Also, if efficiency is key, you can change the code to only adjust the target value when you need to. It won't make a big difference but I think the code makes more sense to look at anyway.

if (numberRequired > 0)
{
yield return new KeyValuePair<int, int>(denomination, numberRequired);
target = target - (numberRequired * denomination);
}

• Thanks. Where is ICurrency implemented? Could you change all your references of Currency to Decimal e.g. DecimalCalculator. Jun 2 '17 at 13:46
• @w0051977 I haven't implemented ICurrency. It's example/pseudo code. Why would you call it DecimalXyz when you're talking about currency? There's no reason you couldn't but given that I also switched to int decimal would be a really weird choice of name.
– RobH
Jun 2 '17 at 14:23
• Thanks, I assume you would have an implementation of ICurrency for each currency type e.g. pounds,dollars,yen etc. Then you inject the ICurrency into the calculator. Have I understood that correctly? +1 for the comprehensive answer. Jun 2 '17 at 14:52
• @w0051977 - that's it exactly.
– RobH
Jun 2 '17 at 15:00
• thanks. One more thing - why use an integer rather than a decimal? Jun 2 '17 at 17:17

There are somethings that I didn't mention on my last answer but perhaps I should mention now. One bad thing about this two implementations is that both classes take a value on the constructor.

What this means is that you are obligated to create multiple instances of the class if you want to make multiple calculations. This is not a problem per se because instantiation is not problematic performance wise and you can bet that the garbage collector will be occupied with a whole lot of other objects besides this.

The point is that having object state (DecimalQuantitiesList, DecimalList, DecimalQuantitiesList) does not make sense for this kind of operations.

Instead you could see them as some kind of mathematical functions that receive a bunch of parameters and return a value.

There are other issues on the code. Per instance it would be sensible to have a static list with the possible values instead of having that GetDecimalList method:

private static readonly IEnumerable<decimal> ValidMoney = new []{50, 20, 10, 5, 2, 1,
0.5, 0.2, 0.1, 0.05, 0.02, 0.01};


Also (int)Math.Floor(QuantityOfDecimal) could simply become (int)QuantityOfDecimal due to truncation.

So this would lead into the following structure (if you really want to have a class for it):

public class DecimalCounter{
private static readonly IEnumerable<decimal> ValidMoney = new []{50, 20, 10, 5, 2, 1,
0.5, 0.2, 0.1, 0.05, 0.02, 0.01};

public IEnumerable<KeyValuePair<decimal, int>> GetDecimalQuantities(decimal value){
//implementation goes here
}
}


As you can see this looks already completely different from both approaches that you have. There is no constructor, the class is able to process multiple values, the possible values are easily recognized and are instantiated only once in run-time. It just looks cleaner.

However I would argue that this can also go into some kind of Mathematical utility class as a static method, perhaps without being an extension method.

public static IEnumerable<KeyValuePair<decimal, int>> ValueToUsableTokens(decimal value, params decimal[] tokens){
if(value == 0){
return new Dictionary<decimal, int>();
}

var result = new Dictionary<decimal, int>();
for(var i = 0; i < tokens.Length; ++i){
var quotient = (int)(value / tokens[i]);
if(quotient > 0){
result[tokens[i]] = (int)quotient;
}
value = value - quotient * tokens[i];
}
return result;
}


I took the freedom of adding a parameters so this particular method is not dependent on using those specific values. Usage would be:

ValueToUsableTokens(152.45M, new []{50M, 20M, 10M, 5M, 2M, 1M,
0.5M, 0.2M, 0.1M, 0.05M, 0.02M, 0.01M})

• Thanks for answering again. All your answers suggest using static functions. This is what I dislike about static functions: misko.hevery.com/2008/12/15/… Jun 2 '17 at 13:37
• @w0051977 I am aware of all concerns of using static functions. But the reality is that they just work as fine in this kind of scenarios. Plus it is really easy to drop out of being static if you want to. Jun 2 '17 at 13:43
• @w0051977 There's also nothing stopping you from having both a static and non static methods, perhaps in different classes. Jun 2 '17 at 13:54
• were would you put the validation for the cost (value)? +1. Feb 12 '18 at 19:38
• @w0051977 I wouldn’t. If you had paid attention I changed the algorithm in such way that “validation “ is no longer needed. Or should I say it was replaced by a different one. Feb 13 '18 at 0:58

I agree that the DecimalCounter has too many responsibilities which currently are:

• denominating
• grouping
• counting

This should be splitted into smaller pieces to improve its testability however I wouldn't go with a full currency class/interfaces for this yet because I think it's not necessasry. Instead I would try to make it more LINQ friendly thus I'm going to suggest an extension that I call Split, just like the string.Split but this one is for decimals.

public static IEnumerable<decimal> Split(this decimal value, IEnumerable<decimal> denominations)
{
...
}


It should just return an IEnumerable<decimal> that gives you a lot of freedom to deal with.

You can count it, you can sum it, you can group it, you can do all kind of LINQ stuff with it if you want.

Example:

var denominations = new[] { 50M, 20M, 10M, 5M, 2M, 1M, 0.5M, 0.2M, 0.1M, 0.05M, 0.02M, 0.01M };

var value = 152.78m;
var denominated = value.Split(denominations);
var oldValue = denominated.Sum();
var denominationCounts =
denominated
.GroupBy(x => x).Select(g => new
{
Denomination = g.Key,
Count = g.Count()
});


This means do just what needs to be done, this is, denominate. Everything else you can do with what's already there so let LINQ do the rest.

Lastly I changed your algorithm. I don't think you need to multiply or divide anything. Just subtract the next largest denomination until there is nothing left.

public static IEnumerable<decimal> Split(this decimal value, IEnumerable<decimal> denominations)
{
foreach (var denomination in denominations.OrderByDescending(d => d))
{
while ((value -= denomination) >= 0)
{
yield return denomination;
}
// Did we denominate too much?
if (value < 0)
{
// Undo the last denomination.
value += denomination;
}
}
}

• The problem with your last suggestion is if you are dealing with big quantities (i.e billions 1 000 000 000). If you put that into 50 note bills you would get 20 000 000 iterations. Conclusion: Let the ALU make the division Jun 5 '17 at 8:34
• @BrunoCosta perhaps but it's an insane number ;-) and there's always one for every algorithm that brings it to its knees. Jun 5 '17 at 8:44
• Well it's not necessarily an insane number, if you deal with things like GDP or Country debt. With 1 000 000 you still get 20 000 iterations, which put you into lottery prizes, wealth of a company / rich person, or a price of a mansion with all bells and whistles. Jun 5 '17 at 8:52
• @BrunoCosta Lottery is not paid out in bills. Jun 7 '17 at 16:31
• @Paparazzi I never said it was nor I suggested it was. Jun 7 '17 at 16:52

I know code only answer are frowned upon but I think there is a simpler approach
The count loop is still pretty fast and it makes for simpler math
Even with 1111111552.78M it runs in less than 3 seconds

public class DecimalCounter
{
private static readonly IEnumerable<decimal> ValidMoney =
new[]{50M, 20M, 10M, 5M, 2M, 1M, 0.5M, 0.2M, 0.1M, 0.05M, 0.02M, 0.01M};

public IEnumerable<KeyValuePair<decimal, int>> GetDecimalQuantities(decimal value)
{
int count;
foreach(decimal note in ValidMoney)
{
count = 0;
while(value >= note)
{
count++;
value -= note;
}
if(count > 0)
{
yield return new KeyValuePair<decimal, int>(note, count);
}
if (value == 0)
break;
}
}
public DecimalCounter()
{
Test();
}
private void Test()
{
Stopwatch sw = new Stopwatch();
sw.Start();
foreach(KeyValuePair<decimal, int> kvp in GetDecimalQuantities(1552.78M))
{
Debug.WriteLine("{0}  {1}", kvp.Key, kvp.Value);
}
sw.Stop();
Debug.WriteLine("DONE " + sw.ElapsedMilliseconds);
}
}


I am getting grief on speed
So I wrote one for speed - integer math is faster

public class DecimalIntCounter
{
private static readonly IEnumerable<int> IntMoney = new[] { 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
public IEnumerable<KeyValuePair<decimal, int>> GetDecimalQuantities(decimal value)
{
int count;
long valueInt = (long)(value * 100);
foreach (int note in IntMoney)
{
count = (int)(valueInt / note);
if (count > 0)
{
yield return new KeyValuePair<decimal, int>( note / 100M, count);
valueInt = valueInt % note;
}
if (value == 0)
break;
}
}
public DecimalIntCounter()
{
Test();
}
private void Test()
{
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (KeyValuePair<decimal, int> kvp in GetDecimalQuantities(1111111552.78M))  // 1552.78M
{
int i = kvp.Value;
decimal d = kvp.Key;
//Debug.WriteLine("{0}  {1}", kvp.Key, kvp.Value);
}
sw.Stop();
Debug.WriteLine("DONE " + sw.ElapsedMilliseconds);
}
}

• This code has the same potential problem as t3chb0t's solution above. It will have a really poor performance for large input values due to while(value >= note) loop. Jun 7 '17 at 15:50
• @NikitaB How big of numbers do you think this would be used for? Even 1111111552.78M runs in less than 3 seconds. I don't call that really poor performance. Jun 7 '17 at 15:57
• @Paparazzi Nowadays anythings that takes over 10milliseconds on the windows operating system is considered to be time consuming and is usually a candidate to run asynchronously. You may think 3 seconds is nothing on human time and you are right. But I will let you know that 3 seconds is a lot of CPU time. One of the most expensive operations is hashing a password and even that should take about 1 second to compute (this should take always the same time no matter what your hardware is, at least, if you upgrade it). Jun 7 '17 at 16:16
• @Paparazzi you probably forgot to enumerate your implementation. I took 5kk as input, and your code takes 4.5s to execute it 1000 times. Same code using division (OP's original implementation) takes 2ms. I would in fact call it a significant performance difference. LinqPad test: gist.github.com/anonymous/b9e1f97b4367bf74886a8d2a252bb66e Jun 7 '17 at 16:21
• It is indeed faster by a factor of ~1.5 however. Don't forget to warm up your performance tests. But doesn't really matter what the factor is really. I only participated on this whole debate so you would acknowledge that dividing is a better approach if you are dealing with bigger numbers, which you already did. Now I am still not upvoting because you don't state what the improvements of your code are relating to the OP code. we shouldn't be the focus. The Op should though. Jun 7 '17 at 17:30

Keep it simple

Here's my code. I wanted to keep it simple. Note the total length of the code vs the length of code posted above. do you find it more understandable? simpler?

Other implementations possible

If you wanted to go all out hardcore OOP, then you could add a factory method. But there's really no need at this stage. You could use a dictionary to return the results you were after - simple enough to implement. Or if you wanted to have coins incorporated you could do that. but i wanted to keep it as simple as possible. rather than commenting on your own code, i thought it perhaps more beneficial to you to see how someone else has worked through the same problem.

I hope it helps you and all readers too.

The Class

namespace CoinCounterII
{
public class CurrencyCounter
{
private decimal total;

public CurrencyCounter(decimal total)
{
this.total = total;
}

/// <summary>
/// Return an array containing all the currency required to total
/// the relevant amount. The easiest accumulation of notes will be
/// returned. If you have $20 then i'll give you a$20 note, rather
/// than 4 x $5 notes. Let's start with$26 as an example. First i'll subtract
/// the biggest denomination possible: that's $20 so i'm left with$6.
/// Then i'll subtract the next biggest denomination possible: that's
/// $5 so i'm left with$1. Then i subtract the next denomination and
/// I subtract $1 to return 0. I subtract my way to success to finally /// return: 25, 5, and 1 in an array. You could return a dictionary if you like /// but note the simplicity of the code. /// </summary> /// <returns></returns> public List<decimal> Change() { List<decimal> kitty = new List<decimal>(); while (total > 0) { // get maximum note you can use to deduct from the total // if you wanted to go hardCore OOP then you could return // a class method here. Let's call it the money // class: Money m = Money.Factory(total) // then you would have child classes of //$5 notes, $10 notes,$20 notes. But why complicate it
// let's not extract the class. We can extract it when we have more information
// in the future.
decimal legalTenderUnit = TenderAmount();

// after adding to the kitty don't forget to reduce the
// total amount owed
total -= legalTenderUnit;
}

return kitty;
}

/// <summary>
/// Return highest denomination possible to reduce the
/// total by, given the total amount.
/// </summary>
/// <returns></returns>
private decimal TenderAmount()
{
if (total < 5)
{
return 1M;
}
else if (total < 10)
{
return 5M;
}
else if (total < 20)
{
return 10M;
}
else if (total < 50)
{
return 20M;
}
else if (total < 100)
{
return 50M;
}
else
{
return 100M;
}
}
}
}


My Tests

using NUnit.Framework;
using System.Collections.Generic;

namespace CoinCounterII
{
[TestFixture]
internal class CurrencyCounterTests
{
[TestCase]
public void change_oneDollar_1()
{
CurrencyCounter cc = new CurrencyCounter(1M);
List<decimal> change = cc.Change();

CollectionAssert.AreEqual(change, new List<decimal>() { 1M });
}

[TestCase]
public void change_twoDollars_2()
{
CurrencyCounter cc = new CurrencyCounter(2M);
List<decimal> change = cc.Change();

CollectionAssert.AreEqual(change, new List<decimal>() { 1M, 1M });
}

[TestCase]
public void change_25Dollars_25()
{
CurrencyCounter cc = new CurrencyCounter(25M);
List<decimal> change = cc.Change();

CollectionAssert.AreEqual(change, new List<decimal>() { 20M, 5M });
}
}
}


EDIT - a polymorphic approach

if you want to go for polymorphism here's an approach you can try. but there's not much benefit to it. hope that helps.