Coin Sums

Problem Statement

In the United Kingdom the currency is made up of pound (£) and pence §. There are eight coins in general circulation: Comment

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p). It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many different ways can £2 be made using any number of coins?

👉🏻

The code is runnable! And it can be edited through opening it in the editable mode to check other test cases!

Solution

TheTechCruise.com Pyodide Terminal

class NumberOfWays:

    # Initialises the class with denominations if there are denominations and some preprocessing is required to get coins
    def __init__(self,denominations={},usedenominations=False):
        self.denominations = denominations
        self.usedenominations = usedenominations
        self.coins = []
        self.l = 0
        self.d = {}


    # Method to get coins as a list of integers when it is a list of strings with denominations
    # Called when usedenominations is set to true and denominations are given
    def get_coins(self, coins):
        res = []
        for coin in coins:
            denom = 1
            coin_value = ""
            for c in coin:
                if c.isdigit():
                    coin_value += c
                else:
                    denom = self.denominations[c]
            res.append(int(coin_value)*denom)
        return sorted(res)

    # Method 1 to solve the problem
    # Recursive approach which runs recursively on remaining amount
    def getways(self, amount, start=0):
        if amount == 0:
            return 1
        if start == self.l:
            return 0
        if (amount,start) in self.d:
            return self.d[(amount, start)]
        
        ways = 0
        
        for i, coin in enumerate(self.coins[start:], start):
            remaining_amount = amount - coin
            if remaining_amount >= 0:
                curr = self.getways(remaining_amount, i)
                ways += curr
            else:
                break
            
        self.d[(amount, start)] = ways
        return ways
        
    # Method 2 to solve the problem
    # Recursive approach similar to Method1 with a simple optimization to reduce the number of function calls
    def getways1(self, amount, start=0):
        if amount == 0:
            return 1
        if start == self.l:
            return 0
        if (amount,start) in self.d:
            return self.d[(amount, start)]
        
        ways = 0
        
        for i, coin in enumerate(self.coins[start:], start):
            if coin > amount:
                break
            for numcoins in range(1, (amount//coin)+1):
                remaining_amount = amount-(coin*numcoins)
                if remaining_amount >= 0:
                    curr = self.getways1(remaining_amount, i+1)
                    ways += curr
                else:
                    break
        self.d[(amount, start)] = ways
        return ways

    # Method 3 to solve the problem
    # Dynamic Programming with memoization
    def getways2(self, amount):
        dp = [[0]*(amount+1) for c in range(self.l)]
        
        for row in dp: 
            row[0] = 1
    
        for i, row in enumerate(dp):
            for j, col in enumerate(row[1:],1):
                coinIncluded = dp[i][j - self.coins[i]] if (j - self.coins[i] >= 0) else 0
                coinExcluded = dp[i - 1][j] if (i >= 1) else 0;
    
                dp[i][j] = coinIncluded + coinExcluded;
    
        return dp[self.l - 1][amount]

    # Method to perform the tests which calls all the provided solutions and prints the result
    def run_tests(self, tests):
        for (coins, amount) in tests:
            if self.usedenominations:
                self.coins = self.get_coins(coins)
            else:
                self.coins = coins
            self.l = len(coins)
            self.d = {}
            print(f"For {self.coins} and amount = {amount} using getways method")
            print(self.getways(amount))
            self.d = {}
            print(f"For {self.coins} and amount = {amount} using getways1 method")
            print(self.getways1(amount))
            print(f"For {self.coins} and amount = {amount} using getways2 method")
            print(self.getways2(amount))


# Setting up the test cases and denominations
denominations = {'p':1, '£':100}
tests1 = []
tests1.append((['1p', '2p', '5p', '10p', '20p', '50p', '£1', '£2'], 200))
tests1.append((['1p', '2p', '5p'], 8))
tests1.append((['1p', '2p', '5p'], 10))
tests1.append((['1p', '2p', '5p', '10p'], 10))

tests2 = []
tests2.append(([1, 2, 5, 10, 20, 50, 100, 200], 200))
tests2.append(([1, 2, 5, 10, 20, 50, 100, 200], 8))
tests2.append(([1, 2, 5, 10, 20, 50, 100, 200], 10))


# Running the tests
print("Tests running for test suite 1 with denominations")
obj_with_denominations = NumberOfWays(denominations, True)
obj_with_denominations.run_tests(tests1)
print("Tests running for test suite 2 without denominations")
obj_without_denominations = NumberOfWays()
obj_without_denominations.run_tests(tests2)

Sai Manasa Ivaturi