guidance :- Python lower range not considered

Question

class CashMachine:
    def __init__(self):
        self.coins = {0.20: 0, 0.50: 0, 1: 0, 2: 0}
        self.banknotes = {5: 0, 10: 0, 20: 0}

    def load_coins(self, number_of_coins, coin_type):
        if coin_type in self.coins:
            self.coins[coin_type] += number_of_coins

    def exchange(self, amount):
        coins_to_use = []
        banknotes_to_use = []
        remaining_amount = amount

        for coin_value in sorted(self.coins.keys(), reverse=True):
            coin_count = self.coins[coin_value]
            while coin_count > 0 and remaining_amount >= coin_value:  
                coins_to_use.append(coin_value)
                remaining_amount -= coin_value
                coin_count -= 1

        for banknote_value in sorted(self.banknotes.keys(), reverse=True):
            banknote_count = self.banknotes[banknote_value]
            while banknote_count > 0 and remaining_amount >= banknote_value:
                banknotes_to_use.append(banknote_value)
                remaining_amount -= banknote_value
                banknote_count -= 1

        if remaining_amount == 0:
            for coin in coins_to_use:
                self.coins[coin] -= 1
            for banknote in banknotes_to_use:
                self.banknotes[banknote] -= 1
            return coins_to_use, banknotes_to_use
        else:
            return [], []

    def print_machine_status(self):
        coin_counts = [f"{count} {coin}£" for coin, count in self.coins.items() if count > 0]
        banknote_counts = [f"{count} {banknote}£" for banknote, count in self.banknotes.items() if count > 0]
        print(f"= {', '.join(coin_counts)} {', '.join(banknote_counts)}")


    def process_commands(input_file):
        cash_machine = CashMachine()
        with open(input_file, 'r') as file:
            for line in file:
                line = line.strip()
                if line.startswith("LOAD"):
                    print("> " + line)
                    _, number_of_items, item_type = line.split()
                    number_of_items = int(number_of_items)
                    item_type = float(item_type)
                    cash_machine.load_coins(number_of_items, item_type)
                    cash_machine.print_machine_status()
                if line.startswith("EXCHANGE"):
                    print("> " + line)
                    _, amount = line.split()
                    amount = float(amount)
                    coins_used, banknotes_used = cash_machine.exchange(amount)
                    if coins_used or banknotes_used:
                        coin_counts = [f"{coins_used.count(coin)} {coin}£" for coin in set(coins_used)]
                        banknote_counts = [f"{banknotes_used.count(banknote)} {banknote}£" for banknote in set(banknotes_used)]
                        print("< " + " ,".join(coin_counts + banknote_counts))
                    else:
                        print("< CANNOT EXCHANGE")
                    cash_machine.print_machine_status()


    if __name__ == '__main__':
        CashMachine.process_commands("input.txt")

As the code works well ,the main logic is to load 0.20£, 0.50£, 1£, 2£ and convert the banknote of the given amount 5£, 10£, 20£ for an equivalent coin.

           > LOAD 20 1
           = ['20 1£']
           > LOAD 10 2
           = ['20 1£', '10 2£']
           > LOAD 40 0.50
           = ['40 0.5£', '20 1£', '10 2£']
           > EXCHANGE 5
           < 1 1£, 2 2£
           = ['40 0.5£', '19 1£', '8 2£']
           > EXCHANGE 20
           < 4 1£, 8 2£
           = ['40 0.5£', '15 1£']
           > EXCHANGE 20
           < 10 0.5£, 15 1£
           = ['30 0.5£']

works well but when i try with 0.20 values,i am not getting relavant output

           > LOAD 20 1
           = ['20 1£']
           > LOAD 10 2
           = ['20 1£', '10 2£']
           > LOAD 40 0.20
           = ['40 0.2£', '20 1£', '10 2£']
           > EXCHANGE 5
           < CANNOT EXCHANGE
           = ['40 0.2£', '20 1£', '10 2£']
           > EXCHANGE 20
           < CANNOT EXCHANGE
           = ['40 0.2£', '20 1£', '10 2£']
           > EXCHANGE 20
           < CANNOT EXCHANGE
           = ['40 0.2£', '20 1£', '10 2£']

What logic i am missing or what error i am doing,cant understand ,please help me out to understand the logic

And my input.txt structure of

`> LOAD 20 1
 > LOAD 10 2
 > LOAD 40 0.20
 > EXCHANGE 5
 > EXCHANGE 20
 > EXCHANGE 20`

Please show a larger portion of the code. I'm unable to identify an issue here. — Bharel, Jun 09 '23 at 09:35
My guess is that this is due to floating point number accuracy, so when you do your final comparison `remaining_amount >= coin_value` it is not correctly doing what you expect. Just as an example, try running `x = 40.0; while x > 0: print(x); x -= 0.2`. What you'll find is that after the first couple of outputs, the number are not exact factors of 0.2. — Matt Pitkin, Jun 09 '23 at 09:37
@MattPitkin exactly ,i dont know how to overcome,i am still lack of logic behind this,can you help me out by explaining furthur — bharath kumar, Jun 09 '23 at 09:49
@Bharel this is my main coding area where i implemented the logic ,others are just reading input and displaying the output,can you help me out to understand the logic — bharath kumar, Jun 09 '23 at 09:50
Hmm, I'm running this in my head and I'm not sure if the output is equivalent. There's `[]` added to the output out of nowhere. — Bharel, Jun 09 '23 at 15:26

score 1 · Accepted Answer · answered Jun 09 '23 at 15:34

First of all, please refrain from forging the output instead of showing the actual output.

The actual output of your code differs. This:

> LOAD 20 1
= 20 1£ 
> LOAD 10 2
= 20 1£, 10 2£ 
> LOAD 40 0.20
= 40 0.2£, 20 1£, 10 2£ 
> EXCHANGE 5
< 1 1£ ,2 2£
= 40 0.2£, 19 1£, 8 2£ 
> EXCHANGE 20
< 4 1£ ,8 2£
= 40 0.2£, 15 1£ 
> EXCHANGE 20
< CANNOT EXCHANGE
= 40 0.2£, 15 1£

Is different from this:

> LOAD 20 1
= ['20 1£']
> LOAD 10 2
= ['20 1£', '10 2£']
> LOAD 40 0.20
= ['40 0.2£', '20 1£', '10 2£']
> EXCHANGE 5
< CANNOT EXCHANGE
= ['40 0.2£', '20 1£', '10 2£']
> EXCHANGE 20
< CANNOT EXCHANGE
= ['40 0.2£', '20 1£', '10 2£']
> EXCHANGE 20
< CANNOT EXCHANGE
= ['40 0.2£', '20 1£', '10 2£']

Debugging code when we receive wrong information is extremely challenging.

As for the actual issue, it is a floating point summation problem.

Please use decimal.Decimal instead of float for the numbers. Here is the working code:

from decimal import Decimal


class CashMachine:
    def __init__(self):
        self.coins = {Decimal("0.2"): 0, Decimal("0.5"): 0, 1: 0, 2: 0}
        self.banknotes = {5: 0, 10: 0, 20: 0}

    def load_coins(self, number_of_coins, coin_type):
        if coin_type in self.coins:
            self.coins[coin_type] += number_of_coins

    def exchange(self, amount):
        coins_to_use = []
        banknotes_to_use = []
        remaining_amount = amount

        for coin_value in sorted(self.coins.keys(), reverse=True):
            coin_count = self.coins[coin_value]
            while coin_count > 0 and remaining_amount >= coin_value:  
                coins_to_use.append(coin_value)
                remaining_amount -= coin_value
                coin_count -= 1

        for banknote_value in sorted(self.banknotes.keys(), reverse=True):
            banknote_count = self.banknotes[banknote_value]
            while banknote_count > 0 and remaining_amount >= banknote_value:
                banknotes_to_use.append(banknote_value)
                remaining_amount -= banknote_value
                banknote_count -= 1

        if remaining_amount == 0:
            for coin in coins_to_use:
                self.coins[coin] -= 1
            for banknote in banknotes_to_use:
                self.banknotes[banknote] -= 1
            return coins_to_use, banknotes_to_use
        else:
            return [], []

    def print_machine_status(self):
        coin_counts = [f"{count} {coin}£" for coin, count in self.coins.items() if count > 0]
        banknote_counts = [f"{count} {banknote}£" for banknote, count in self.banknotes.items() if count > 0]
        print(f"= {', '.join(coin_counts)} {', '.join(banknote_counts)}")


    def process_commands(input_file):
        cash_machine = CashMachine()
        with open(input_file, 'r') as file:
            for line in file:
                line = line.strip()
                if line.startswith("LOAD"):
                    print("> " + line)
                    _, number_of_items, item_type = line.split()
                    number_of_items = int(number_of_items)
                    item_type = Decimal(item_type)
                    cash_machine.load_coins(number_of_items, item_type)
                    cash_machine.print_machine_status()
                if line.startswith("EXCHANGE"):
                    print("> " + line)
                    _, amount = line.split()
                    amount = Decimal(amount)
                    coins_used, banknotes_used = cash_machine.exchange(amount)
                    if coins_used or banknotes_used:
                        coin_counts = [f"{coins_used.count(coin)} {coin}£" for coin in set(coins_used)]
                        banknote_counts = [f"{banknotes_used.count(banknote)} {banknote}£" for banknote in set(banknotes_used)]
                        print("< " + " ,".join(coin_counts + banknote_counts))
                    else:
                        print("< CANNOT EXCHANGE")
                    cash_machine.print_machine_status()


if __name__ == '__main__':
    CashMachine.process_commands("input.txt")

Output:

> LOAD 20 1
= 20 1£ 
> LOAD 10 2
= 20 1£, 10 2£ 
> LOAD 40 0.20
= 40 0.2£, 20 1£, 10 2£ 
> EXCHANGE 5
< 1 1£ ,2 2£
= 40 0.2£, 19 1£, 8 2£ 
> EXCHANGE 20
< 4 1£ ,8 2£
= 40 0.2£, 15 1£ 
> EXCHANGE 20
< 15 1£ ,25 0.2£
= 15 0.2£

Extremely thanks,didnt mean to forge the output,code got updated while posting the question and while editing the output part here,extremely sorry for that,wont repeat here after — bharath kumar, Jun 09 '23 at 17:34

Matt Pitkin · Answer 2 · 2023-06-09T13:38:06.790

0

Edit: as noted in the comments, this solution does not actually seem to address the cause of the OP's issue, due to the exchanges starting with the highest denomination coins rather than the lowest. So, in the examples shown it should never reach using the 0.2 denomination coins.

Try changing your while loop:

while coin_count > 0 and remaining_amount >= coin_value:
    coins_to_use.append(coin_value)
    remaining_amount -= coin_value
    coin_count -= 1

to be something like:

while coin_count > 0 and abs(remainingamount - coinvalue) > 1e-15 and remainingamount > 0:
    coins_to_use.append(coin_value)
    remaining_amount -= coin_value
    coin_count -= 1

This should be able to deal with the fact that floating point numbers only have a certain precision, which can screw up comparisons in many cases.

As a concrete example, say you have a coinvalue of 0.2 that you've been subtracting from remaining_amount, and you've got to the point where remaining_amount is equal to 0.19999999999996942 (so not exactly 0.2 due to the finite precision of floats), in the original while loop the condition remaining_amount >= coin_value would be False, so the loop would terminate and you'd still have 0.19999999999996942 left over (which wouldn't fit with any of your other denominations). In my suggested solution, when remaining_amount is equal to 0.19999999999996942, the conditions while coin_count > 0 and abs(remainingamount - coinvalue) > 1e-15 and remainingamount > 0 will be True - the residual between 0.2 and 0.19999999999996942 is 3.058664432842306e-14 - so the loop will be entered a final time and the last coin will be added as expected. I use abs(remainingamount - coinvalue) because there could be cases where the residual remainingamount - coinvalue is small positive or negative value, so I want to take care of both situations.

edited Jun 09 '23 at 13:38

answered Jun 09 '23 at 09:53

Matt Pitkin

3,989
1
18
32

If you dont mind can you care to explain it furthur, – bharath kumar Jun 09 '23 at 10:03
Already thought about it, doesn't have anything to do with precision in this case. 5 = 2*2 + 1, non of those are floating points. – Bharel Jun 09 '23 at 13:14
@bharathkumar I've added some further explanation. – Matt Pitkin Jun 09 '23 at 13:18
@Bharel why do you not think it has anything to do with floating point precision? 0.2 is a floating pointing number. – Matt Pitkin Jun 09 '23 at 13:19
@MattPitkin Because if you'll look carefully, he exchanges 5, which is not using any floating point in that path, yet it still fails. Means the input is probably wrong. – Bharel Jun 09 '23 at 13:21
@MattPitkin whether you put 0.5 or you put 0.2, he never reaches that as he sorts in reverse order, meaning he checks 2+2+1. Both paths should be equivalent. Unless he forged the output. – Bharel Jun 09 '23 at 13:23
1

Yes, I see now that they exchange the highest possible denomination first rather than starting at the lowest. – Matt Pitkin Jun 09 '23 at 13:25
I tried withis method also,but the output remains same.@MattPitkin – bharath kumar Jun 09 '23 at 15:15
1

@MattPitkin as expected, output was forged. – Bharel Jun 09 '23 at 15:35

guidance :- Python lower range not considered

2 Answers2