1

I have a homework assignment in which I have to write a program that outputs the change to be given by a vending machine using the lowest number of coins. E.g. £3.67 can be dispensed as 1x£2 + 1x£1 + 1x50p + 1x10p + 1x5p + 1x2p.

However, I'm not getting the right answers and suspect that this might be due to a rounding problem.

change=float(input("Input change"))

twocount=0
onecount=0
halfcount=0
pttwocount=0
ptonecount=0

while change!=0:
     if change-2>=0:
          change=change-2
          twocount+=1
     else:
          if change-1>=0:
               change=change-1
               onecount+=1
          else:
               if change-0.5>=0:
                    change=change-0.5
                    halfcount+=1
               else:
                    if change-0.2>=0:
                         change=change-0.2
                         pttwocount+=1
                    else:
                         if change-0.1>=0:
                              change=change-0.1
                              ptonecount+=1
                         else:
                              break

print(twocount,onecount,halfcount,pttwocount,ptonecount)

RESULTS:

Input: 2.3
Output: 10010
i.e. 2.2

Input: 3.4
Output: 11011
i.e. 3.3

Some actually work:

Input: 3.2
Output: 11010
i.e. 3.2

Input: 1.1
Output: 01001
i.e. 1.1
Improve this question

1 Answer 1

Reset to default
1

Floating point accuracy

Your approach is correct, but as you guessed, the rounding errors are causing trouble. This can be debugged by simply printing the change variable and information about which branch your code took on each iteration of the loop:

initial value: 3.4
taking a 2...   new value: 1.4
taking a 1...   new value: 0.3999999999999999   <-- uh oh
taking a 0.2... new value: 0.1999999999999999
taking a 0.1... new value: 0.0999999999999999
1 1 0 1 1

If you wish to keep floats for output and input, multiply by 100 on the way in (cast to integer with int(round(change))) and divide by 100 on the way out of your function, allowing you to operate on integers.

Additionally, without the 5p, 2p and 1p values, you'll be restricted in the precision you can handle, so don't forget to add those. Multiplying all of your code by 100 gives:

initial value: 340
taking a 200... new value: 140
taking a 100... new value: 40
taking a 20...  new value: 20
taking a 20...  new value: 0
1 1 0 2 0

Avoid deeply nested conditionals

Beyond the decimal issue, the nested conditionals make your logic very difficult to reason about. This is a common code smell; the more you can eliminate branching, the better. If you find yourself going beyond about 3 levels deep, stop and think about how to simplify.

Additionally, with a lot of branching and hand-typed code, it's very likely that a subtle bug or typo will go unnoticed or that a denomination will be left out.

Use data structures

Consider using dictionaries and lists in place of blocks like:

twocount=0
onecount=0
halfcount=0
pttwocount=0
ptonecount=0

which can be elegantly and extensibly represented as:

denominations = [200, 100, 50, 10, 5, 2, 1]
used = {x: 0 for x in denominations}

In terms of efficiency, you can use math to handle amounts for each denomination in one fell swoop. Divide the remaining amount by each available denomination in descending order to determine how many of each coin will be chosen and subtract accordingly. For each denomination, we can now write a simple loop and eliminate branching completely:

for val in denominations:
    used[val] += amount // val
    amount -= val * used[val]

and print or show a final result of used like:

278 => {200: 1, 100: 0, 50: 1, 10: 2, 5: 1, 2: 1, 1: 1}

The end result of this is that we've reduced 27 lines down to 5 while improving efficiency, maintainability and dynamism.

By the way, if the denominations were a different currency, it's not guaranteed that this greedy approach will work. For example, if our available denominations are 25, 20 and 1 cents and we want to make change for 63 cents, the optimal solution is 6 coins (3x 20 and 3x 1). But the greedy algorithm produces 15 (2x 25 and 13x 1). Once you're comfortable with the greedy approach, research and try solving the problem using a non-greedy approach.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you very much for your detailed answer, I really appreciate it! But it's still not working. For example, Input: 2.3, Output:{200: 1.0, 100: 0.0, 50: 0.0, 20: 1.0, 10: 0.0, 5: 1.0, 2: 2.0, 1: 0.0} My code is as follows:change=float(input("Input change")) change=change*100 denominations = [200, 100, 50, 20, 10, 5, 2, 1] used = {x: 0 for x in denominations} for val in denominations: used[val] += change // val change -= val * used[val] print(used)
However, I've noticed that if I delete change=change*100 and simply input the change as 230 (i.e. times by a hundred by itself), it gives me the correct answer!
Yup, you're still in the realm of floating point even after the change *= 100. Cast to integer with change = int(round(change * 100)) and you should be fine. You can debug this yourself by printing the value to see 229.99999999999997 after the multiplication--clearly problematic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.