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)));
 }
}

Answer 1

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.

• Tobias Grothe: 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).
• radarbob: 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'

Answer 2

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.

• Tobias Grothe: 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.

Answer 3

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.

• Tobias Grothe: "next()" does several things other than just return a boolean value, I don't think the JNCs are directly applicable here.
• Timothy Truckle: @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?
• Tobias Grothe: I'm not criticizing the naming conventions, but rather applying them incorrectly. As I said, "next()" also contains application logic.
• Timothy Truckle: @TobiasGrothe: "As I said, "next()" also contains application logic." -- As I said, that is a design problem.
• Tobias Grothe: Then, every Iterator has a design problem in Java...