atm - return required sum using minimum amount of 100, 50 and 20 banknotes

[marchello]

Hi all, this is my first Python program, please be patient to me

So, as subject says, it is atm code that should return required sum using minimum amount of 100, 50 and 20 banknotes.
Just to simplify, the input is always positive; also the input is always divisible using mentioned banknotes nominals.

My question is not Python-specific (I know that my knowledge is weak, but I will learn it better soon), it is rather looking for proper algorithm. As far as I can see, looping is not proper way here. For example, it works fine with 290 input value; but in case of 110 it takes one 100 banknote, then 10 is left which doesn't have appropriate banknote; so it should skip 100 and return one 50 plus three 20.

Please advise if you have proper algorithm idea.

Code: Select all

def atm(value):
    rest = value
    result = ''
    var100 = 0
    var50 = 0
    var20 = 0
    if (rest - 100 >= 0):
        while True:
            rest = rest - 100 
            if (rest >= 0):
                var100 = var100 + 1
            else: 
                rest = rest + 100
                break
    if (rest - 50 >= 0):
        while True: 
            rest = rest - 50
            if (rest >= 0):
                var50 = var50 + 1
            else: 
                rest = rest + 50
                break
    if (rest - 20 >= 0):
        while True: 
            rest = rest - 20
            if (rest >= 0):
                var20 = var20 + 1
            else: 
                rest = rest + 20
                break
    result = str(var100) + ' ' + str(var50) + ' ' + str(var20)
    return result

print (atm(290))

[ghp]

The name of the problem is "Change-making_problem".

https://en.wikipedia.org/wiki/Change-making_problem

[Burngate]

Not a Python guru, so can't help with that side, but two things stand out for me.

First, there ain't no answer if you start with 10 or 30, so it might be worth checking for that before you start.

Second, why start with the largest notes and work down - the 100s, then the 50s and end with the 20s?

Instead, start with the lowest denomination - the 20s.
You'll arrive at a number of 20s, with maybe 10 left over.

If you've got 10 left, drop the 20s by two and add one 50 - that takes care of the odd 10 (you'll never need more than one 50)
else drop the 20s by five and add one 100

keep going till you've nowt left.

[DougieLawson]

Second, why start with the largest notes and work down - the 100s, then the 50s and end with the 20s?

That's the way to make change. You have to hand over the fewest number of notes and coins that way. It makes it easier for the customer assistant behind the till to make change and count it out to the customer.

You've just got to love these homework questions.

[HermannSW]

In general these kind of problems can be soleved easily and efficiently by two dimensional array, here of size 3×N where N is the amount of money you want to change.
Initially A[x][y]=0 for all x,y.
A[0][y] is 0 if it cannot be paid with only 20 banknotes, otherwise it is the number of 20 banknotes.
Then iterate over all y=0..49 and set A[1][y]=A[0][y].
Then iterate over y=50..N and do: A[1][y]=min(A[1][y-50]+1,A[0][y]).
Do same with A[2] for 100 banknotes.
Finally you see minimal number of banknotes in A[2][N].
You can go back from that and determine how much 20s, 50s and 100s you need.
Runtime of algrorithm is O(3*N) which is good for any constant number of different banknote values.

[Burngate]

Yes, but ...

Barman, customer ...
The barman was adding it up as he was pulling the pints, and tells the customer what amount he needs.
The customer knows what's in her purse, hands over some amount that's convenient for her, maybe a twenty or two tens.
The barman has to take into account what change is in the till, and may ask for a couple of thruppenny bits; in return he gives her a nine-bob note, if he's got one in the till.
They're both doing stuff in the background, probably without thinking about it.

ATM ...
The customer has no input into the situation - she gets what she's given, and is grateful for what she gets.
The ATM does all its calculations before it starts to count out the notes, so it doesn't have to work "logically"
If it knows it hasn't enough seven-shekel notes to service many more potential customers, it'll find a different way to reach the "right" answer.

"Right" being far more complicated than just "fewest notes"

[DougieLawson]

Barmen are a breed apart, they'll be doing the mental arithmetic in the same way that the guy playing darts is adding up the arrows and subtracting from 501 (or the current remaining total) as each dart is played.

The ATM has counters for everything. The self-scan in Tesco is the same (it's just an ATM with a modified user interface) but they only have coin dispensers for some coins.

You take the price, subtract from the amount tendered then integer divide by each of the denomination that can be dispensed dividing the remainder each time by the next lower note or coin.

So a £8.99 bill paid with a £20 note gets £11.01 made as £10, £1, 1p. £3.12 paid with a £20 is £16.88 with £10, £5, £1, 50p, 20p, 10p, 5p, 2p, 1p. We also get into the realm of "legal tender" in §2 of the Coinage Act (1971) [that's the one that introduced decimalisation in Feb 1971] just to help complicate things http://www.legislation.gov.uk/ukpga/1971/24/section/2.

It gets easier with dollars, quarters, nickels, dimes & pennies as there are fewer steps in the iteratively divide with a remainder process.

I love the way Ireland got rid of €0.01 and €0.02 with some simple rounding rules https://www.irishtimes.com/news/consume ... -1.2397307

This is all an extremely trivial task to program in python.

[hippy]

As burngate notes a self-service till's function is not solely to give the customer the least number of coins or notes in change.

The reason is two-fold; to prevent internal holding capacity being reached and to ensure subsequent customers can be best catered for.

I would expect that last point can also apply to ATM's and there's an additional aspect of what's most useful for a customer. Two £20 and a £10 is usually better than a singe £50 note in your pocket. Ten customers withdrawing £500 as eight £50 and five £20, can be better than nine getting ten £50, with the tenth getting twenty five £20.

"It probably needs an AI solution"