Another ATMs cash-out (denomination) algorithm in Java

Question

Related to this question and this answer, I would like to have a second review from you on a modified version.

The problem I tried to solve

Some kind of "Minimum count of numbers required from given array to represent S" (see here).

Algorithms that I used

Some kind of dynamic programming array (see here), but I don't know the exact name.

Java Code

import java.util.Arrays;

public class CashMachineWithDynamicProgrammingArray {
    private final int[] billValues;
    private final int[] billAmounts;
    private final int maxBillAmount;
    private int currentBillAmountIndex = 0;

    public CashMachineWithDynamicProgrammingArray(final int[] billValues, final int maxDepth) {
        this.billValues = billValues;
        billAmounts = new int[billValues.length];
        maxBillAmount = maxDepth;
    }

    private boolean next() {
        billAmounts[currentBillAmountIndex]++;
        if (billAmounts[currentBillAmountIndex] >= maxBillAmount) {
            do {
                billAmounts[currentBillAmountIndex] = 0;
                currentBillAmountIndex++;
                if (currentBillAmountIndex >= billAmounts.length) {
                    currentBillAmountIndex = 0;
                    return false;
                }
            } while (billAmounts[currentBillAmountIndex] >= maxBillAmount);
            billAmounts[currentBillAmountIndex]++;
            currentBillAmountIndex = 0;
        }
        return true;
    }

    private void skipCurrentBillIndexIncrementation() {
        billAmounts[currentBillAmountIndex] = maxBillAmount;
    }

    private int calculateBillsAmount() {
        int amount = 0;
        for (int i = 0; i < billValues.length; i++) {
            amount += billValues[i] * billAmounts[i];
        }
        return amount;
    }

    private int calculateBillsSum() {
        int sum = 0;
        for (final int billAmount : billAmounts) {
            sum += billAmount;
        }
        return sum;
    }

    public int[] calculateBillAmountsWithLowestSum(final int amountToLookFor) {
        int lowestSum = 0;
        int[] billAmountsWithLowestSum = new int[billValues.length];
        do {
            int amount = calculateBillsAmount();
            if (amount >= amountToLookFor) {
                if (amount == amountToLookFor) {
                    int sum = calculateBillsSum();
                    if (lowestSum == 0 || sum < lowestSum) {
                        lowestSum = sum;
                        System.arraycopy(billAmounts, 0, billAmountsWithLowestSum, 0, billAmounts.length);
                    }
                }
                skipCurrentBillIndexIncrementation();
            }
        } while (next());
        return billAmountsWithLowestSum;
    }

    public static void main(final String[] args) {
        int[] billValues = {1, 29, 59, 109, 209, 509, 1000, 2000, 5000};
        int maxDepth = 5;
        CashMachineWithDynamicProgrammingArray cashMachine = new CashMachineWithDynamicProgrammingArray(billValues, maxDepth);
        System.out.println(Arrays.toString(cashMachine.calculateBillAmountsWithLowestSum(1)));
        System.out.println(Arrays.toString(cashMachine.calculateBillAmountsWithLowestSum(30)));
        System.out.println(Arrays.toString(cashMachine.calculateBillAmountsWithLowestSum(5000)));
        System.out.println(Arrays.toString(cashMachine.calculateBillAmountsWithLowestSum(25114)));
    }
}

radarbob · Accepted Answer · 2023-11-01 03:14:23Z

Use banknote for name of physical currency and withdrawl for the target/requested amount. I think this solves most of the program's understandability problem.

Name things for what they are, not how they are implemented.

CashMachineWithDynamicProgrammingArray ---> CashMachine

skipCurrentBillIndexIncrementation

Do not make a method out of that one code line.

"skip" means to pass over or ignore, so why is there a method that does nothing?
The method does not do what it says. It is setting a default value, it is not skipping.
The surrounding code logic is doing the skipping. This method is only the processing of that condition.
Even with an accurate name the method hurts understanding. After all the details of working with array indexes, buried 3 "if"s deep you hide the detail of an "else" fall-through branch. A very simple detail it turns out. Ouch.

calculateBillSum - "calculate" is superfluous. "Sum" is a verb (in this use) and very specific - add a list of numbers. "calculate" can mean anything.

It is OK to name methods as if they are properties because it is a given that properties return values.

calculateBillAmountsWithLowestSum ---> BillLowestSum or LowestBillSum

for-each makes code shorter, cleaner, and easier on the eyes.

Physically order the algorithm methods with cashMachine.calculateBillAmountsWithLowestSum at the top and the rest in depth/call order.

Return immediately on terminating conditions.

Nested redundant evaluation is bad. It hides simpler logic that must stand out.

     if (amount >= amountToLookFor) {
            if (amount == amountToLookFor) {

Much Better:

     if (amount > amountToLookFor) { addLargestBanknote(); }

     if (amount == amountToLookFor) {
        int sum = calculateBillsSum();
        
        if (lowestSum == 0 || sum < lowestSum) {
            lowestSum = sum;
            System.arraycopy(billAmounts, 0, billAmountsWithLowestSum, 0, billAmounts.length);
        }
     }
   } while (next());

    return billAmountsWithLowestSum;     
 }

Blank space around conditional code blocks really, totally, for sure, helps comprehension speed and readability.

NOTE: After this refactoring - and "skip..." method name change - I take back almost everything I said about that method earlier.

Cover all conditions.

The refactor above made me realize there is no 'less than' condition. Never say it will never happen.

If the oversight is intentional, add a comment. Alternatively add a line of code that "skips" for that condition.

However if higher level / caller code explicitly takes care of the possibility then ignoring it is ok. The Object constructor is the best place to set complete, valid execution state.

You forgot: Even if "amount == amountToLookFor" is true, "addLargestBanknote()" should be called (in both cases, a better solution cannot be found with the current combination). That was one of the reasons I nested the if conditions (avoid DRY). — Tobias Grothe
– Tobias Grothe, Commented Nov 1, 2023 at 19:57
then do you even need that first if (amount >= amountToLookFor)? Or do does it serve to not execute it in the implied 'less than' condition? If so I'd write 'less than' explicitly and still avoids the nested redundant 'equals' — radarbob
– radarbob, Commented Nov 1, 2023 at 22:18

RoToRa · Accepted Answer · 2023-10-31 13:09:04Z

Unfortunately this is really broken in many ways.

It starts at a readability issue by using the word "amount" for two different meanings: the number of bills and the total value of bills. This makes the code very difficult to understand.

Then, what is maxDepth (or maxBillAmount)? Why does the same thing have two different names? Why isn't it calculated by the algorithm itself? By setting it to the arbitrarily value of 5 it breaks the algorithm. Try running the example for values between 6 and 28.

The algorithm also seems to be broken or at least extraordinarily inefficient. Even for the trivial case of 1 the code runs through all (I believe 10.000.000) combinations of bills. One reason for this maybe because you are using the same billAmounts array for each call of calculateBillAmountsWithLowestSum with its old contents from the previous call. billAmounts and currentBillAmountIndex need to be local variables in calculateBillAmountsWithLowestSum and not a fields of the class.

Thanks. "code runs through all (I believe 10.000.000) combinations of bills." not through all, there is some kind of "pruning"... but true, for maxDepth 5 and values between 6 and 28 he wouldn't find a solution. There might be another answer to come, otherwise I would mark this as the most helpful. — Tobias Grothe
– Tobias Grothe, Commented Oct 31, 2023 at 17:50

Timothy Truckle · Accepted Answer · 2023-10-31 19:22:42Z

0

As stated in the Java Naming Conventions variables holding and methods returning boolean values sould start with is..., has..., can... or alike. So your method next() might better be named isCalculationCompleted() (inverting its current logic...).

Also it looks like you are "hiding" the actual alorithm fro finding the number of a certain bill needed in this next() method.

answered Oct 31, 2023 at 19:22

Timothy Truckle

7,29115 silver badges24 bronze badges

\$\begingroup\$ "next()" does several things other than just return a boolean value, I don't think the JNCs are directly applicable here. \$\endgroup\$

Tobias Grothe
– Tobias Grothe

2023-11-01 19:46:44 +00:00
Commented Nov 1, 2023 at 19:46
\$\begingroup\$ @TobiasGrothe Don't you thing that questioning your design would be more appropriate then questioning the JNC? Don't you value the single responsibility pattern? \$\endgroup\$

Timothy Truckle
– Timothy Truckle

2023-11-01 20:12:48 +00:00
Commented Nov 1, 2023 at 20:12
\$\begingroup\$ I'm not criticizing the naming conventions, but rather applying them incorrectly. As I said, "next()" also contains application logic. \$\endgroup\$

Tobias Grothe
– Tobias Grothe

2023-11-02 15:24:45 +00:00
Commented Nov 2, 2023 at 15:24
\$\begingroup\$ @TobiasGrothe: "As I said, "next()" also contains application logic." -- As I said, that is a design problem. \$\endgroup\$

Timothy Truckle
– Timothy Truckle

2023-11-02 23:52:45 +00:00
Commented Nov 2, 2023 at 23:52
\$\begingroup\$ Then, every Iterator has a design problem in Java... \$\endgroup\$

Tobias Grothe
– Tobias Grothe

2023-11-05 07:52:29 +00:00
Commented Nov 5, 2023 at 7:52

| Show 2 more comments

Stack Exchange Network

Another ATMs cash-out (denomination) algorithm in Java

3 Answers 3

You must log in to answer this question.

Linked

Hot Network Questions