1

I am taking a discrete math course that requires me to write some short code for it. Here is the problem that I am tasked with:

Develop a Python method change(amount) that for any integer amount in the range from 24 to 1000 returns a list consisting of numbers 5 and 7 only, such that their sum is equal to amount. For example, change(28) may return [7, 7, 7, 7], while change(49) may return [7, 7, 7, 7, 7, 7, 7] or [5, 5, 5, 5, 5, 5, 5, 7, 7] or [7, 5, 5, 5, 5, 5, 5, 5, 7].

(To solve this quiz, implement the method change(amount) on your machine, test it on several inputs, and then paste your code in the field below and press the submit quiz button.)

And here is the code I wrote:

def change(amount):
  if amount < 24:
  return 0
  assert(amount >= 24)
  if amount == 24:
    return [5, 5, 7, 7]
  if amount == 25:
    return [5, 5, 5, 5, 5]
  if amount == 26:
    return [5, 7, 7, 7]
  if amount > 1000:
    return 0

  coins = change(amount - 5)
  coins.append(5)
  return coins

When I test my code on a code visualizer program (http://www.pythontutor.com/visualize.html#mode=edit) it seems to be working fine, but when I enter it as the answer for the quiz I get an error:

RuntimeErrorElement(RuntimeError,Error on line 16: coins.append(5) AttributeError: 'int' object has no attribute 'append' )

I am not sure what is going on. Do note that the class is an online one and I am typing the code into an online platform, so I am sure there is something the algorithm is checking for, but I am unsure what.

Improve this question
4
  • 2
    If change returns 0, then you're trying to do 0.append(5), which doesn't make any sense. Commented Jul 21, 2018 at 23:32
  • Changing return 0 to return [0] should make it work, though Patrick's comment is still valid. Specifying return [], i.e. an empty list, might make more sense, depending on the context. Commented Jul 21, 2018 at 23:45
  • Your first return 0 line should be indented. jshamble has removed the error you note. But if that is done, your code still returns wrong answers values of amount that end in the decimal digit 2, 3, 7, or 8. See my answer for working code. Commented Jul 22, 2018 at 0:19
  • Thanks everyone, each of your comments and contributions were very helpful. I have posted below my fixed code. Turns out my problem was more an error in my thinking than anything else. Thanks again for setting me straight! Commented Jul 22, 2018 at 9:26

4 Answers 4

Reset to default
1

Make sure all your return values are the same type. You need to use arrays but you're using ints when you return zero. Fixed:

def change(amount):
  if amount < 24:
    return [0]
  assert(amount >= 24)
  if amount == 24:
    return [5, 5, 7, 7]
  if amount == 25:
    return [5, 5, 5, 5, 5]
  if amount == 26:
    return [5, 7, 7, 7]
  if amount > 1000:
    return [0]

  coins = change(amount - 5)
  coins.append(5)
  return coins
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Your code does indeed run and removes the error in the OP. So this does answer the question that was asked. However, your code returns wrong answers for many values of amount such as 27 and 28.
1

Thanks everyone! After reading your comments and re examining where I went wrong I see the error in my logic. I would not have been able to adjust my thinking accordingly without your help, and I have rewritten my code below. I know it is not the most elegant of answers, but I wanted to give an answer that is within the parameters of my knowledge of Python and not simply copy another's work. That being said, seeing how everyone solved this problem helped me look at it in another angle.

In summary, my error in logic was forgetting there was a situation in which there are only 7's and adding or subtrating a 5 "coin" would not solve it.

Code:

def change(amount):
  assert(amount >= 24)
  if amount == 24:
    return [5, 5, 7, 7]
  if amount == 25:
    return [5, 5, 5, 5, 5]
  if amount == 26:
    return [5, 7, 7, 7]
  if amount == 27:
    return [5, 5, 5, 5 , 7 ]
  if amount == 28:
    return [ 7, 7, 7, 7]
  if amount > 1000:
    return 0

  coins = change(amount - 5)
  coins.append(5)
  return coins
Improve this answer

Comments

1

I'm not sure what you are studying in your Discrete Mathematics class, but if you have studied number theory, especially linear Diophantine equations, the extended Euclidean algorithm, or continued fractions, here is alternative and really "short code." This returns the shortest possible list given your restrictions. I have tested this for all values of amount between 24 and 1000. Ask if you both want and need an explanation.

def change(amount):
    if not (24 <= amount <= 1000):
        return [0]
    k = int(3 * amount / 7)
    return [5] * (3*amount-7*k) + [7] * (5*k-2*amount)

By popular demand, here is a partial explanation of that code.

If we call our target number n, count the number of 5s in the solution list and call it r, and count the number of 7s and call it s, we can restate the problem as finding nonnegative integers r, s for which

5 * r + 7 * s = n

We first want to solve that equation for n=1 and allow r or s to be negative. I quickly used continued fractions to solve that, a technique similar to the extended Euclidean algorithm. I'll skip the details, but I quickly came up with

5 * 3 + 7 * -2 = 1

We now multiply both sides of that equation by n and get

5 * (3*n) + 7 * (-2*n) = n

Since we found one solution, number theory tells us there are actually infinitely many solutions, all of them in the form

5 * (3*n - 7*k) + 7 * (-2*n + 5*k) = n

where k is an arbitrary integer. We are almost done, but we need to find k so that those multipliers are nonnegative. We also want to make our solution list as short as possible, so we want as many 7s and as few 5s as possible. So we require the multiplier of 5 to be nonnegative and desire it to be small which means we want k to be large. So we require

3 * n - 7 * k >= 0

Solve that for k and we get

k <= 3 * n / 7

The largest integer that satisfies that is

k = int(3 * n / 7)

which explains the next-to-last line in my code. So we want 3*n-7*k number of 5s in our list and -2*n+5*k which is 5*k-2*n number of 7s in our result list. We finally use Python's list multiplier syntax, which means that if mylist is a list value, then mylist * t is a list containing t copies of mylist concatenated to each other. Therefore I used that notation twice to return a list with the desired number of 5s followed by the desired number of 7s.

Finally, number theory tells us that we get nonnegative values for those list multipliers for any value of n that is at least (5-1) * (7-1) which is 24. That explains the lower bound in the problem. There is no upper bound in the mathematical problem--I assume the computing problem gives an upper bound of 1000 to allow for quick checking.

Improve this answer

2 Comments

That's brilliant! If you don't mind me asking, could you explain how you came up with your last two lines? That is, how did you come up with the number of coins for each denomination?
Thank you! After reading, and puzzling over your code, I understand where I went wrong. I rewrote mine in a different way ( per the parameters of the course, sorry I wanted to make it work without simply copying and pasting), but it really made me examine what I was doing.
0 
def change(amount):
  if amount < 24:
    return [0]
  assert(amount >= 24)
  if amount == 24:
    return [5, 5, 7, 7]
  if amount == 25:
    return [5, 5, 5, 5, 5]
  if amount == 26:
    return [5, 7, 7, 7]
  if amount==27:
    return [5,5,5,5,7]
  if amount==28 :
    return [7, 7, 7 ,7]
  if amount > 1000:
    return [0]
  coins = change(amount - 5)
  coins.append(5)
  return coins 


    enter code here


change(987)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.