# Change-making problem with specific constraints

I am a new Pythoner. I have solved a OJ project with Python. Can you tell me how can I solve it more Pythonically?

Problem Description: There are n coin denominations, each with an unlimited supply of coins. Use them to make a given total amount m.

Requirements:

1. Every denomination must be used
2. The number of coins of small denominations must be greater than the number of large denomination coins
3. The total number of coins must be minimum
4. If there is no combination of conditions to meet the conditions 1 and 2, the output "NA"

Input parameters:

1. coin types n: 2 < n < 10
2. The total amount m: m < 1000
3. The largest denomination is less than 20

Program input: First line: the total amount requested Second row: each coin denomination (in half-space separated)

Program output: First line: total number of coins Second row: the number of small to large denomination of each coin (in half-space separated)

Sample input:

20
1 2 5


Sample output:

9
4 3 2

#!/bin/bash/env python3
import copy

def coinChange():
amount, coins = int(input()), list(sorted(map(int, input().split(sep=' '))))
min_package = [x for x in range(len(coins), 0, -1)]
min_sum = sum(map(lambda x, y:x * y, min_package , coins))

if amount < min_sum:
print('NA')
return

dp, dp[0] = [amount + 1] * (amount + 1), 0
packages = [[0] * len(coins)] * (len(dp))
for i in range(len(dp)):
for j, coin in enumerate (coins):
if coin <= i:
last = i - coin
package = copy.deepcopy(packages[last])
if dp[i] > dp[last] + 1 and (j == 0 or package[j - 1] > package[j] + 1):
dp[i], package[j], packages[i] = dp[last] + 1, package[j] + 1, package
else:
break

if dp[-1] > amount or packages[-1][-1] < 1:
print('NA')
else:
print(sum(packages[-1]))
print(' '.join([str(x) for x in packages[-1]]))

if __name__ == '__main__':
coinChange()


## 2 Answers

### 1. Review

1. The function coinChange carries out three tasks: (i) read the input; (ii) solve the problem; (iii) print the solution. This makes it hard to test, because it's hard to run the code on different problem instances (you have to feed it the problem in text form on standard input), and becaue it's hard to automatically check the output (you have to capture the standard output).

It would be easier to test the code if task (ii) were refactored into a separate function. I'd write something like this:

class NoSolution(Exception):
pass

def coin_change(amount, coins):
"""Given a target amount and a sorted list of coins denominations,
determine how to make change for amount with the minimum number of
coins, subject to the restrictions that every denomination is used
and the number of coins of a small denomination must be greater
than the number of coins of a large denomination. Return a list
giving the number of coins of each denomination, or raise
NoSolution if making change is impossible under the constraints.

"""
# ... see below ...

def main():
"""Read coin change problem from standard input and write solution to
standard output, or NA if there is no solution.

"""
amount, coins = int(input()), list(sorted(map(int, input().split())))
try:
result = coin_change(amount, coins)
except NoSolution:
print('NA')
else:
print(sum(result))
print(*result)


and now it's easy to test the code, for example from the interactive interpreter:

>>> coin_change(20, [1, 2, 5])
[4, 3, 2]

2. sorted already returns a list, so there is no need to pass the result to list.

3. str.split splits on whitespace by default, so there is no need to pass sep=' ' in this case.

4. Note in the code above that I handle an exceptional result by raising an exception (instead of returning some exceptional value). This is more robust because it is easy to forget to check the result of a function, causing exceptional cases to be silently mishandled.

5. These lines are unnecessary:

min_package = [x for x in range(len(coins), 0, -1)]
min_sum = sum(map(lambda x, y:x * y, min_package , coins))

if amount < min_sum:
print('NA')
return


That's because there is already logic for detecting unsolvable problem instances later in the function. There's no point in doing this twice: duplicate code has twice the opportunties for bugs.

6. The line:

dp, dp[0] = [amount + 1] * (amount + 1), 0


is kind of tricksy (the reader would need to be very sure of Python's order-of-evaluation rules to know that dp[0] is evaluated after dp is assigned), and so it would be simpler to write something like:

dp = [amount + 1] * (amount + 1)
dp[0] = 0


or alternatively,

dp = [0] + [amount + 1] * amount

7. The only role of amount + 1 in this line is to be greater than every possible number of coins. I think it would be clearer to use a value like float('inf') here.

8. This loop:

for i in range(len(dp)):


would be better written like this:

for i in range(1, amount + 1):


This is because there's no point in considering making change for 0, so we might as well start at 1, and because amount + 1 makes it clear that we consider all values up to amount, without having to remember how many elements there are in the list dp.

9. In Python we prefer not to use tuple assignment just to save on lines of code (only when we really do have a tuple to assign). This kind of code is hard to follow:

dp[i], package[j], packages[i] = dp[last] + 1, package[j] + 1, package


because you have to count carefully to see which expression on the right is assigned to which expression on the left. I think it's clearer to write:

dp[i] = dp[last] + 1
package[j] += 1
packages[i] = package


Notice that I can use the += operator here, which wasn't possible in the tuple assignment version of the code.

10. Making a deep copy of packages[last] is unecessary: this is a list of integers, and so a shallow copy would work.

11. There's no need to import the copy module just to take a shallow copy of a list. It's simpler to use the built-in function list.

12. The code takes a copy of packages[last] before testing whether coin could be used. But this is a waste if coin in fact cannot be used. It would be better to take the copy after the test, like this:

package = packages[last]
if dp[i] > dp[last] + 1 and (j == 0 or package[j - 1] > package[j] + 1):
dp[i] = dp[last] + 1
new_package = list(package)
new_package[j] += 1
packages[i] = new_package

13. The meaning of the name dp is not clear to me. The value dp[i] is the smallest number of coins found so far that makes change for i under the restrictions of the problem. Even knowing this, I can't work out what "dp" stands for! I would use a name like min_coins together with a comment explaining the meaning.

Update: does "dp" stand for "dynamic programming"??

14. The meaning of the name package is also not clear. The value packages[i][j] is the number of coins of the j'th denomination in the best solution found so far that makes change for i under the restrictions of the problem. So I'd use a name like solutions together with a comment.

15. Instead of:

    if coin <= i:
# ...
else:
break


I would write:

    if coin > i:
break
# ...


which saves a level of indentation. In general, it's a good idea to dispose of exceptional cases first.

16. At the end of the function, the code uses packages[-1] to get the solution for amount. It would be clearer to write packages[amount]. Then the reader wouldn't have to remember how many elements there are in the list packages.

17. In the line:

if dp[-1] > amount or packages[-1][-1] < 1:


the first part of the condition (dp[-1] > amount) is unnecessary; the second part of the condition suffices.

### 2. Revised code

def coin_change(amount, coins):
"""Given a target amount and a sorted list of coins denominations,
determine how to make change for amount with the minimum number of
coins, subject to the restrictions that every denomination is used
and the number of coins of a small denomination must be greater
than the number of coins of a large denomination. Return a list
giving the number of coins of each denomination, or raise
NoSolution if making change is impossible under the constraints.

"""
# min_coins[i] is smallest number of coins found making change for i.
min_coins = [0] + [float('inf')] * amount

# solutions[i][j] is the number of coins of the j'th denomination in
# the best solution found making change for i.
solutions = [[0] * len(coins)] * (amount + 1)

for i in range(1, amount + 1):
for j, coin in enumerate(coins):
if coin > i:
break
last = i - coin
solution = solutions[last]
if (min_coins[i] > min_coins[last] + 1
and (j == 0 or solution[j - 1] > solution[j] + 1)):
min_coins[i] = min_coins[last] + 1
new_solution = list(solution)
new_solution[j] += 1
solutions[i] = new_solution

if solutions[amount][-1] == 0:
raise NoSolution()
else:
return solutions[amount]


### 3. Improved algorithm

The data structure packages ends up containing len(coins) * (amount + 1) values. But this is a waste of memory and computation, because you ought to be able to describe each solution by giving only the denomination of the highest coin used in that solution. Then you could subtract that coin and look up the remainder to get the next coin, and so on.

But if you try to implement this then you'll struggle, because in the revised data structure you can't apply the restriction that every denomination is used and the number of coins of a small denomination must be greater than the number of coins of a large denomination.

However, there's a way to transform the problem so that it turns into an ordinary (unrestricted) change-making problem. The idea is that if you're given the problem instance:

make change for 20 using fewest coins with values 1, 2, 5 (with the restriction)

then you transform it into:

make change for 8 using fewest coins with values 1, 3, 8 (without the restriction)

which has the solution 0, 0, 1 which transforms into the solution 4, 3, 2 in the original problem.

No doubt you're asking, what is this transformation and how does it work? There are two steps in the transformation:

1. Any solution has to contain at least one of the highest denomination of coin (because all denominations have to be included), at least two of the second highest denomination (because the number of coins of a small denomination must be greater than the number of coins of a large denomination), at least three of the third highest denomination, and so on. So we can start by subtracting all these coins from the amount, and then drop the restriction that all denominations have to be included.

In the example above, we know that the solution has to include at least 3×1, 2×2 and 1×5, so we start by subtracting 12 from the amount, getting 8.

2. Now, whenever we add a coin of some denomination to the solution we're building up, we have to add coins of all smaller denominations too, to maintain the restriction that number of coins of a small denomination must be greater than the number of coins of a large denomination. So if we add a coin of denomination 2, then we have to add a coin of denomination 1 too. And if we add a 5, we have to add 2 and 1 too.

But if a 2 always has to be accompanied by a 1, this is almost the same as having a coin of denomination 3. And if 5 always has to be accompanied by a 2 and a 1, this is almost the same as having a coin of denomination 8. So we can transform the problem into one where the coins have values 1, 3, and 8, and then drop the restriction that number of coins of a small denomination must be greater than the number of coins of a large denomination.

I wrote "almost the same" above because there is a difference in how we have to count the number of coins in order to ensure we meet the "minimum number of coins" condition. See the line marked "(A)" in the code below.

In the transformed problem we can represent the solutions more compactly as discussed above, and then reconstruct the full solution coin by coin at the end. Here's an implementation.

from itertools import accumulate

def coin_change(amount, coins):
"""Given a target amount and a sorted list of coins denominations,
determine how to make change for amount with the minimum number of
coins, subject to the restrictions that every denomination is used
and the number of coins of a small denomination must be greater
than the number of coins of a large denomination. Return a list
giving the number of coins of each denomination, or raise
NoSolution if making change is impossible under the constraints.

"""
# Transform problem into (almost) standard change-making problem.
coins = list(accumulate(coins))                    # see (2) above
amount -= sum(coins)                               # see (1) above
if amount < 0:
raise NoSolution()

# min_coins[i] is smallest number of coins found making change for i.
min_coins = [0] + [float('inf')] * amount

# solutions[i] is the index of the highest coin in the best
# solution found making change for i, or -1 if no solution has
# been found.
solutions = [-1] * (amount + 1)

# Solve the transformed problem
for i in range(1, amount + 1):
for j, coin in enumerate(coins):
if coin > i:
break
last = i - coin
new_coins = min_coins[last] + j + 1        # (A)
if min_coins[i] > new_coins:
min_coins[i] = new_coins
solutions[i] = j

# Reconstruct solution in the transformed problem.
result = [0] * len(coins)
while True:
j = solutions[amount]
if j == -1:
break
result[j] += 1
amount -= coins[j]
if amount != 0:
raise NoSolution()

# Transform solution back again.
return list(accumulate(r + 1 for r in reversed(result)))[::-1]


In general it is better to make your function return your results rather than printing. This way you can reuse you function at a later point, or use its result for something else.

You should separate the input from the logic. Move asking the user for the values outside of the function and pass it as parameters. Normally you would pack them into their own function and add input validation. The way it is now, if the user enters garbage your script will throw an error (which is not a big problem with the guaranteed correct input from the challenge, but will be if you ever want to use this function again).

I also fixed some whitespace. PEP8 recommends putting a blank after a comma in an argument list and after a :. But no space after a function name and before the accompanying (). It also specifies using lower_case for variables and function names. Lastly, you should limit your lines to a width of 80 characters to improve readability.

split splits by default on whitespace, so no need for split(sep=" ").

I did not have a very thorough look at your algorithm itself, leaving this for later (and/or for others).

#!/bin/bash/env python3
import copy

def coin_change(amount, coins):
min_package = [x for x in range(len(coins), 0, -1)]
min_sum = sum(map(lambda x, y: x*y, min_package, coins))

if amount < min_sum:
return 0, "NA"

dp, dp[0] = [amount + 1] * (amount + 1), 0
len_dp = len(dp)
packages = [[0] * len(coins)] * len_dp
for i in range(len_dp):
for j, coin in enumerate(coins):
if coin <= i:
last = i - coin
package = copy.deepcopy(packages[last])
if dp[i] > dp[last] + 1 and (j == 0 or package[j - 1] > package[j] + 1):
dp[i], package[j], packages[i] = dp[last] + 1, package[j] + 1, package
else:
break

if dp[-1] > amount or packages[-1][-1] < 1:
return 0, "NA"
else:
return sum(packages[-1]), " ".join([str(x) for x in packages[-1]])

if __name__ == "__main__":
amount, coins = int(input()), list(sorted(map(int, input().split())))
total, min_coins = coin_change(amount, coins)
if total:
print(total)
print(min_coins)

• Thank you very much!Since it's a OJ project, I don't check input. – Cherlex Aug 16 '16 at 11:56
• @Cherlex Yes, which is why I did not implement the input validation ;) – Graipher Aug 16 '16 at 12:01
• The lines in your version are still too long (a horizontal scroll bar in the posted code is a nice indicator). Your answer would be more helpful if it included tips on how to avoid long lines. – mkrieger1 Aug 16 '16 at 13:45