marchello
Posts: 81
Joined: Fri Oct 11, 2013 8:59 am

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

Thu Jul 09, 2020 5:54 pm

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))
Last edited by marchello on Fri Jul 10, 2020 7:24 pm, edited 1 time in total.

ghp
Posts: 1541
Joined: Wed Jun 12, 2013 12:41 pm
Location: Stuttgart Germany
Contact: Website

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

Thu Jul 09, 2020 8:04 pm

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

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

User avatar
Burngate
Posts: 6329
Joined: Thu Sep 29, 2011 4:34 pm
Location: Berkshire UK Tralfamadore
Contact: Website

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

Fri Jul 10, 2020 9:13 am

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.

User avatar
DougieLawson
Posts: 39560
Joined: Sun Jun 16, 2013 11:19 pm
Location: A small cave in deepest darkest Basingstoke, UK
Contact: Website Twitter

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

Fri Jul 10, 2020 9:32 am

Burngate wrote:
Fri Jul 10, 2020 9:13 am
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.
Note: Any requirement to use a crystal ball or mind reading will result in me ignoring your question.

Criticising any questions is banned on this forum.

Any DMs sent on Twitter will be answered next month.
All fake doctors are on my foes list.

User avatar
HermannSW
Posts: 2777
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

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

Fri Jul 10, 2020 10:20 am

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.
Last edited by HermannSW on Fri Jul 10, 2020 10:28 am, edited 1 time in total.
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/github_repo_i420toh264

User avatar
Burngate
Posts: 6329
Joined: Thu Sep 29, 2011 4:34 pm
Location: Berkshire UK Tralfamadore
Contact: Website

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

Fri Jul 10, 2020 10:23 am

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"

User avatar
DougieLawson
Posts: 39560
Joined: Sun Jun 16, 2013 11:19 pm
Location: A small cave in deepest darkest Basingstoke, UK
Contact: Website Twitter

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

Fri Jul 10, 2020 11:05 am

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.
Note: Any requirement to use a crystal ball or mind reading will result in me ignoring your question.

Criticising any questions is banned on this forum.

Any DMs sent on Twitter will be answered next month.
All fake doctors are on my foes list.

hippy
Posts: 8070
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

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

Fri Jul 10, 2020 12:36 pm

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" :P

Return to “Python”