Calculating the note mix to dispense

Question

I need to figure out a cash mix algorithm to dispense notes from the ATM. The goals of the algorithm are:

To calculate the note mix to dispense the required amount to the customer.
While doing so, to attempt the emptying of the cash cassettes as evenly as possible, so ideally (but not mandatory), the cash will run out in all cassettes at the same time.

The user wants to get different amounts of cash, such as 500$, 1200$, 6000$, etc. There is no average. The algorithm needs to figure out which notes and how many of them to dispense. Of course, the cassettes in the ATM can change to different values / counts.

Another limitation is that the ATM can present only 30 notes at the time, so the algorithm has to divide the notes in bunches, if calculated number of notes exceeds this limit, while considering the goal above (equal emptying).

Here is what i came up with:

//Represents a typical cash cassette.
class Cassette
{
   public int Denom { get; set; } //Denomination: (USD)50, (USD)100, etc.
   public int Count { get; set; } //Number of notes.
}

//Our cassettes.
List OriginalCashCassettes = new List();
List CloneCashCassettes = new List();

//Populated.
OriginalCashCassettes.Add(new Cassette { Denom = 50, Count = 1000 });
OriginalCashCassettes.Add(new Cassette { Denom = 100, Count = 1000 });
OriginalCashCassettes.Add(new Cassette { Denom = 200, Count = 1000 });

//Pass original cassettes to clone cassettes.
CloneCashCassettes = OriginalCashCassettes;

//Calculate mix for requested amount.
CalculateNoteMix(6000);

And the calculation itself:

private void CalculateNoteMix(int reqAmount)
{
    //1. Check if the amount is higher than combined counts.
    int totalCounts = 0;
    foreach (var item in CloneCashCassettes)
    {
        totalCounts += item.Denom * item.Count;
    }

    if (totalCounts < reqAmount)
    {
        Console.WriteLine("You're trying too high - maximum amount available is: " + totalCounts);
        return;
    }

    //2. Check if the amount is dispensable with current denoms.
    int lowestDenom = CloneCashCassettes.Min(c => c.Denom);
    if (reqAmount % lowestDenom != 0)
    {
        Console.WriteLine("Unable to dispense amount with current denoms");
        return;
    }

    //3. Calculate note mix to dispense.
    List noteMix = new List();

    do
    {
        //Sort cash cassettes by highest count first.
        CloneCashCassettes = CloneCashCassettes.OrderByDescending(c => c.Count).ToList();

        //Check if highest count denom can cover the amount.
        if (CloneCashCassettes[0].Denom <= reqAmount)
        {

            //Check if this denom already exists in the mix.
            Cassette noteMixCassette = noteMix.Find(n => n.Denom == CloneCashCassettes[0].Denom);
            if (noteMixCassette == null)
            {
                //Add denom to the note mix.
                noteMix.Add(new Cassette { Denom = CloneCashCassettes[0].Denom, Count = 1 });
            }
            else
            {
                //Increase denom count in the note mix.
                noteMixCassette.Count += 1;
            }

            //Reduce denom count in the cash cassette.
            CloneCashCassettes[0].Count -= 1;
            //Reduce the amount by denom.
            reqAmount -= CloneCashCassettes[0].Denom;
        }
        else
        {
            //The amount is smaller than denom => the denom is unusable - remove it.
            CloneCashCassettes.RemoveAt(0);
        }

    //Keep looping until the amount is 0.
    } while (reqAmount > 0);

    //Print resulting note mix.
    Console.WriteLine("For the amount of " + reqAmount + ", our note mix is:");
    foreach (var item in noteMix)
    {
        Console.WriteLine("Denom: " + item.Denom + " x " + "Count: " + item.Count + " = " + item.Denom * item.Count);
    }
}

Using this code, if the user asks for $400, then the note mix is:

Denom: 50 x Count: 2 = 100
Denom: 100 x Count: 1 = 100
Denom: 200 x Count: 1 = 200

Or if the user asks for $25,000, then:

Denom: 50 x Count: 72 = 3600
Denom: 100 x Count: 72 = 7200
Denom: 200 x Count: 71 = 14200

Problems:

This code appears to work fine with denoms of 50 and higher. However, it has a problem with the denom of 20. Any idea how to resolve it?

Example:
```
    OriginalCashCassettes.Add(new Cassette { Denom = 20, Count = 1000 });
    OriginalCashCassettes.Add(new Cassette { Denom = 50, Count = 1000 });
    OriginalCashCassettes.Add(new Cassette { Denom = 100, Count = 1000 });
```
The user asks for $200, which is dispensable. I start to subtract: 200-100-50-20 = 30 - 20 = 10 -> unable to dispense.
Same problem with denom of 20 exists in the check if the amount is dispensable (#2 in code).

Example: The cassettes configured as above with denom of 20. User asks for $210, which should be dispensable (100+50+20+20+20).
Any ideas how to improve this algorithm in general, so it will be more efficient / faster?

Thanks.

Calculating the note mix to dispense

Answers (1)

Related Questions