Hadron DaVinci

Coin Change Problem Mother Function

22 Aug 2020 - Hadron DaVinci

There are so many types of coin change problems and so many different solutions to them. So I created a mother function that could be used to solve multiple types of coin problems. Note, I’m sure there’s probably a faster approach possible but this one is still pretty quick and does a great job at showing the underlying steps.

Coin Problem Question Type

In a coin change problem, we are given a set of coin values, C and a sum S.
And the goal is either to identify one of the following:

1. Number of ways possible (to sum to S)
2. Identify minimum number of coins needed (to sum to S)
3. Identify maximum number of coins needed (to sum to S)

Coin Problems Constraint Type

1. Bounded: For each coin value, you have a finite number of coins to choose from.
2. Unbounded: For each value of coin, you have an infinite number of coins to choose from.

Example: (Bounded, Type1 Coin Problem)

You have three $20 dollar bills, five $10 dollar bills, two $5 dollar bills, and five $1 dollar bills.
How many ways can you make change for a $100 dollar bill?

---

Discussion

Summary:

This approach uses a double-loop along with recursion to generate coin groups.
And coin groups that sum to a target number and are unique are stored in variable called SOLUTIONS.
Use SOLUTIONS to answer any coin question.

Method (Double-Loop, Recursion):

Given the example problem, we can use the code below to determine:

1. Count of unique Solutions
2. Every Possible Unique Solution

   class MCF:
    def __init__(self, c, q, t):
        self.count = 0
        self.solutions = []
        self.process(c, q, t, [])
   

    def process(self, c, q, t, coin_group):
        if t < 0:
            return
        elif t == 0:
            self.count += 1
            self.save_group(coin_group)
   

        for i in range(0, len(c)):
            if c[i] > t:
                continue
            if q[i] <= 0:
                continue
   

            c_remaining = c[i+1:]
            q_remaining = q[i+1:]
   

            for this_quantity in range(1, q[i] + 1):
                local_group = coin_group[:]
                local_group.extend(this_quantity * [c[i]])
                amount_to_remove = this_quantity * c[i]
                new_target = t - amount_to_remove
                self.process(c_remaining, q_remaining, new_target, local_group)
   

    def save_group(self, solution):
        solution.sort()
        if solution not in self.solutions:
            self.solutions.append(solution)
   

---

Example

Type1 Bounded:

coin_values = [20, 10, 5 1]
quantity = [3, 5, 2, 5]
target_value = 100

mcf = MCF(coin_values, quantity, target)
number_of_ways = mcf.count

# answer is 5
print(number_of_ways) 

Type1 Unbounded:

In this scenario, we examine how many ways given an infinite number of coins, for each value.
Notice, the way of simulating infinity is to simply enter a really large integer.

Even though Python3 has no limit to the actual value of an integer, there is a limit how large various
datastructures (such as lists, strings, dictionaries) can be. And this limit is sys.maxsize.

Therefore, sys.maxsize is a reasonable approximation for Infinity.

import sys

coin_values = [20, 10, 5 1]
quantity = [sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize]
target_value = 100

mcf = MCF(coin_values, quantity, target_solutions)
number_of_ways = mcf.count

# answer is 286
print(number_of_ways) 

---

Files

cmf.go

utils.go

cmf.py