Kearney Taaffe Kearney Taaffe - 26 days ago 11
Python Question

Find all possible permutations of change

I had an interesting interview question that I'm having a hard time solving (I have 7 of the 10 permutations)

The question was


Find all possible permutations to make change given the following coins, 25¢, 10¢, 5¢. The answer MUST BE saved in a list, and MUST BE returned as a JSON string when the method is called


Furthermore, the requirements were that when printed, the solution MUST look like this


For instance, given an amount of 50¢, the solution should look like
the following when printed out


25: 2, 10: 0, 5: 0
25: 1, 10: 1, 5: 3
25: 1, 10: 2, 5: 1
25: 1, 10: 0, 5: 5
25: 0, 10: 5, 5: 0
25: 0, 10: 4, 5: 2
25: 0, 10: 3, 5: 4
25: 0, 10: 2, 5: 6
25: 0, 10: 1, 5: 8
25: 0, 10: 0, 5: 10


Needless to say, after 2 hours (the time limit to the test) I was unable to finish. But, it got me wandering, if I could solve the problem. I've tried for the past 6 hours to get the result, but the best I can come up with is

1 => {25: 2, 10: 0, 5: 0}
2 => {25: 1, 10: 1, 5: 3}
3 => {25: 1, 10: 2, 5: 1}
4 => {25: 1, 10: 0, 5: 5}
5 => {25: 0, 10: 5, 5: 0}
6 => {25: 0, 10: 1, 5: 8}
7 => {25: 0, 10: 0, 5: 10}


Using this code

class ChangeMachine(object):
def __init__(self, amount, coins=[25, 10, 5]):
self.amount = amount
self.coins = coins
self.result = []

self.initial_way = {}
for coin in coins:
self.initial_way[coin] = 0

def getAllPermutations(self):
for index in xrange(0, len(self.coins)):
coin = self.coins[index]

self.changeFromSameCoin(self.amount, coin)

self.changeUsingOneCoin(self.amount, coin, self.coins[index + 1:])

def changeFromSameCoin(self, amount, coin):
"""loops through all the coins, finding the ones which can be divided
into the amount evenly

Args:
amount: int
coin: int

Returns:
None
"""
way = dict(self.initial_way)

if amount % coin == 0:
way[coin] = amount / coin
self.result.append(dict(way))

def changeUsingOneCoin(self, amount, initial_coin, coin_list):
"""Makes change using 1 large coin and the rest small coins
Args:
amount: int
initial_coin: int - the "large" denomination that is to be used once
coin_list: list - contains the remainder of the coins
"""

if amount <= initial_coin:
return

remainder = amount - initial_coin
init_way = dict(self.initial_way)
num_coins = len(coin_list)
coin_used = 0

outer_counter = 0

# keep track of the number of times the outer coins are used
# make it 1 because the outer coin has to be used at least once
# even if outer coin is > remainder, we are still trying to use
# it once
outer_coin_used = 1

# since the initial coin MUST BE used at least once, go ahead and
# create an initial dictionary that has the initial coin used
# once
init_way[initial_coin] = 1

while outer_counter < num_coins:
outer_coin = coin_list[outer_counter]

# initialize way on every loop
way = dict(init_way)

# subtract the current outer coin from the remainder. We do this
# because if the remainder is 0, then it means that only 1 of this
# coin and the initial coin are needed to make change
# If the remainder is negative, then, one of the larger coin and
# one of this coin, cannot make change
# The final reason is because if we make change with the other
# coins, we need to check if we double, triple, etc this coin
# that we can still make change.
# This helps us find all permutations
remainder -= (outer_coin * outer_coin_used)

if remainder < 0:
# move to next coin using the outer_counter
outer_counter += 1

# reset the remainder to initial - large coin
remainder = amount - initial_coin

# rest the times the coin was used to 1
outer_coin_used = 1
continue

way[outer_coin] += outer_coin_used

if remainder == 0:
# add the way we just found to our result list
self.result.append(dict(way))

# move to the next element in the list
outer_counter += 1

# reset the remainder, our way result set, and times the
# outer coin was used
remainder = amount - initial_coin
way = dict(init_way)
outer_coin_used = 0

continue

# so, if we got here, the outer coin reduced the remainder, but
# didn't get it to 0
for index in range(outer_counter + 1, num_coins):
# our goal here is to make change with as few of coins as
# possible
inner_coin = coin_list[index]

if remainder % inner_coin == 0:
way[inner_coin] = remainder / inner_coin
remainder = 0
break

if remainder - inner_coin < 0:
# this coin is too large, move onto the next coin
continue

# this coin goes into the remainder some odd number of times
# subtract it from our remainder and move onto the next coin
remainder /= inner_coin
way[inner_coin] += remainder

# end for index in range()

if remainder == 0:
# we found a way to make change, save it
self.result.append(dict(way))

# reset the remainder to initial - large coin
remainder = amount - initial_coin

# increment the outer coin used by 1, because we will try
# to decrement remainder by more than 1 outer coin
outer_coin_used += 1

# end while loop

return
# end def changeUsingOneCoin()
# end class

from pprint import pprint

def main(amount, coins=[25, 10, 5]):
result = []

amount = 50
coins = [25, 10, 5]
cm = ChangeMachine(amount, coins)
# cm.changeUsingOneCoin(amount, coins[0], coins[1:])

cm.getAllPermutations()

counter = 1
for record in cm.result:
print "{} => {}".format(counter, record)
counter += 1

return result

if __name__ == '__main__':

"""
Result MUST BE a list of dictionaries containing all possible answers

For Example: if main(50, [25, 10, 5]) should return

[
{25: 2},
{25: 1, 10: 2, 5: 1},
{25: 1, 10: 1, 5: 3},
{25: 1, 10: 0, 5: 5},
{25: 0, 10: 5, 5: 0},
{25: 0, 10: 4, 5: 2},
{25: 0, 10: 3, 5: 4},
{25: 0, 10: 2, 5: 6},
{25: 0, 10: 1, 5: 8},
{25: 0, 10: 0, 5: 10},
]
"""
result = main(50)


I know I'm not going to get the job. But, I really want to know the solution

Answer Source

This simpler code does it, except that it doesn't write the output as JSON.

I would be suspicious of an employer that calls these 'permutations'. :)

TOTAL = 50

for q in range(0, 1+50//25):
    remainder_q = TOTAL - 25*q
    for d in range(0, 1+remainder_q//10):
        remainder_d = remainder_q - 10*d
        for n in range(0, 1+remainder_d//5):
            remainder_n = remainder_d - 5*d
            if 25*q+10*d+5*n == 50:
                print (q, d, n)
                break
            if 25*q+10*d+5*n > 50:
                break

0 0 10
0 1 8
0 2 6
0 3 4
0 4 2
0 5 0
1 0 5
1 1 3
1 2 1
2 0 0