5 ms·

Combining coins to reach a target sum (C, Python)

33 points by ttsiodras 15y ago

gwern 15y ago
Very nice example of memoization.
- yoklov 15y ago
  Specifically of the memoization technique known as dynamic programming.
owenmarshall 15y ago
This problem is closely related to the Frobenius coin problem: http://en.wikipedia.org/wiki/Coin_problem http://en.wikipedia.org/wiki/Coin_problem It's an interesting problem. My gut reaction was to solve X1 + X2 + (...) + X6 = 200; X1, ..., X6 < 0, which would be C(205, 200), but that ignores the denominations of each coin, so it doesn't really generate what you want.
cperciva 15y ago
Alternatively, you can ask Wolfram Alpha to compute a power series: http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29*%281-x%5E2%29*%281-x%5E5%29*%281-x%5E10%29*%281-x%5E20%29*%281-x%5E50%29*%281-x%5E100%29*%281-x%5E200%29%29+at+x%3D0+to+order+200 http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29...
- ttsiodras 15y ago
  Wow - speechless :-) The correlation with my program's results is clear (the coefficients are my last column) - any references as to why?
  - cperciva 15y ago
    The power series for 1/(1-x^n) is 1 + x^n + x^2n + x^3n + ... in which the term x^i is the number of ways of forming i as a sum of zero or more n. Multiplying two power series maintains that property -- the x^j term in the product of two power series comes from x^i in one power series and x^(j-i) in the other power series, just like a sum of j pence made out of two types of coins has to be i pence worth of one type of coin and j-i pence worth of the other type of coin. Converting (1/(1-x)) * (1/(1-x^2)) * ... into 1/((1-x) * (1-x^2) * ...) is just routine algebraic manipulation, which I claim without proof is valid for power series.
    - owenmarshall 15y ago
      This is why you should treat Project Euler more as a way to learn mathematics and less as a way to practice code. Most of their problems can, and IMO should, be solved by pen and paper alone.
      - cperciva 15y ago
        To be fair, I wouldn't want to compute the 200th term of a power series by hand. I could do it, but it would probably take me several attempts to do that much arithmetic without making a mistake somewhere along the way.
        owenmarshall 15y ago
        (sorry to necrobump!) That's a fair point. I should revisit my critique: IMO, PE should be used to practice conceptual mathematics; if you're trying to perform an exhaustive search, for example, you might want to see if there's a better way.
  - pmiller2 15y ago
    That's because the series is the generating function for the number of ways to make 2 pounds with those coins.
smcdow 15y ago
FWIW, printf() is not async-signal-safe. It's bad form to call such routines from within a signal handler. Here's a list of async-signal-safe functions (scroll down): http://pubs.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_04.html http://pubs.opengroup.org/onlinepubs/009695399/functions/xsh... I know I'm missing the point of the post, but it is a particular nit that I pick. You'd be surprised at how often this happens in production code, and how often it causes mysterious, hard-to-reproduce bugs.
- nkurz 15y ago
  I don't disagree with your logic, but how would you recommend that he solve this in a safer manner? Fork() and printf()? Ignore signals before printf()? Use write()? Some other manner of triggering besides Ctrl-C?
  - smcdow 15y ago
    I'd keep an int flag, initialized to zero. The sighandler sets the flag. The flag is checked (and reset) on entry to newCoin(). Not exactly pretty, but using signals to trigger to produce reports isn't exactly pretty either. Unfortunately, signals are often abused in this manner. Not a big deal for such for this small piece of software, but in larger systems this kind of abuse can cause very hard to fix bugs.
    - cperciva 15y ago
      I'd keep an int flag, initialized to zero. If you do, your code is buggy: sig_atomic_t is the only type you can safely use inside and outside a signal handler.
      - smcdow 15y ago
        Please explain why this would be true for single-threaded applications.
        15y ago
d0mine 15y ago
`[(y,x)]` is the same thing as `[y,x]` `,` creates a tuple, not parentheses (empty tuple is an exception).
- ttsiodras 15y ago
  Thank you, didn't know this! Code updated.
sur 15y ago
It's possible to do this using just a one-dimensional array. Since we only need the last column of the matrix we calculated to calculate the next column, the array can be updated in-place. coins = [1, 2, 5, 10, 20, 50, 100, 200] total = 200 matrix = [0] * (total + 1) matrix[0] = 1 for coin in coins: for j in range(coin, len(matrix)): matrix[j] += matrix[j - coin]

33 points by ttsiodras 15y ago

gwern 15y ago

Very nice example of memoization.

yoklov 15y ago
Specifically of the memoization technique known as dynamic programming.

owenmarshall 15y ago

This problem is closely related to the Frobenius coin problem: http://en.wikipedia.org/wiki/Coin_problem http://en.wikipedia.org/wiki/Coin_problem It's an interesting problem. My gut reaction was to solve X1 + X2 + (...) + X6 = 200; X1, ..., X6 < 0, which would be C(205, 200), but that ignores the denominations of each coin, so it doesn't really generate what you want.

cperciva 15y ago

Alternatively, you can ask Wolfram Alpha to compute a power series: http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29*%281-x%5E2%29*%281-x%5E5%29*%281-x%5E10%29*%281-x%5E20%29*%281-x%5E50%29*%281-x%5E100%29*%281-x%5E200%29%29+at+x%3D0+to+order+200 http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29...

ttsiodras 15y ago
Wow - speechless :-) The correlation with my program's results is clear (the coefficients are my last column) - any references as to why?
- cperciva 15y ago
  The power series for 1/(1-x^n) is 1 + x^n + x^2n + x^3n + ... in which the term x^i is the number of ways of forming i as a sum of zero or more n. Multiplying two power series maintains that property -- the x^j term in the product of two power series comes from x^i in one power series and x^(j-i) in the other power series, just like a sum of j pence made out of two types of coins has to be i pence worth of one type of coin and j-i pence worth of the other type of coin. Converting (1/(1-x)) * (1/(1-x^2)) * ... into 1/((1-x) * (1-x^2) * ...) is just routine algebraic manipulation, which I claim without proof is valid for power series.
  - owenmarshall 15y ago
    This is why you should treat Project Euler more as a way to learn mathematics and less as a way to practice code. Most of their problems can, and IMO should, be solved by pen and paper alone.
    - cperciva 15y ago
      To be fair, I wouldn't want to compute the 200th term of a power series by hand. I could do it, but it would probably take me several attempts to do that much arithmetic without making a mistake somewhere along the way.
      - owenmarshall 15y ago
        (sorry to necrobump!) That's a fair point. I should revisit my critique: IMO, PE should be used to practice conceptual mathematics; if you're trying to perform an exhaustive search, for example, you might want to see if there's a better way.
- pmiller2 15y ago
  That's because the series is the generating function for the number of ways to make 2 pounds with those coins.

smcdow 15y ago

FWIW, printf() is not async-signal-safe. It's bad form to call such routines from within a signal handler. Here's a list of async-signal-safe functions (scroll down): http://pubs.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_04.html http://pubs.opengroup.org/onlinepubs/009695399/functions/xsh... I know I'm missing the point of the post, but it is a particular nit that I pick. You'd be surprised at how often this happens in production code, and how often it causes mysterious, hard-to-reproduce bugs.

nkurz 15y ago
I don't disagree with your logic, but how would you recommend that he solve this in a safer manner? Fork() and printf()? Ignore signals before printf()? Use write()? Some other manner of triggering besides Ctrl-C?
- smcdow 15y ago
  I'd keep an int flag, initialized to zero. The sighandler sets the flag. The flag is checked (and reset) on entry to newCoin(). Not exactly pretty, but using signals to trigger to produce reports isn't exactly pretty either. Unfortunately, signals are often abused in this manner. Not a big deal for such for this small piece of software, but in larger systems this kind of abuse can cause very hard to fix bugs.
  - cperciva 15y ago
    I'd keep an int flag, initialized to zero. If you do, your code is buggy: sig_atomic_t is the only type you can safely use inside and outside a signal handler.
    - smcdow 15y ago
      Please explain why this would be true for single-threaded applications.
      - 15y ago

d0mine 15y ago

`[(y,x)]` is the same thing as `[y,x]` `,` creates a tuple, not parentheses (empty tuple is an exception).

ttsiodras 15y ago
Thank you, didn't know this! Code updated.

sur 15y ago

It's possible to do this using just a one-dimensional array. Since we only need the last column of the matrix we calculated to calculate the next column, the array can be updated in-place. coins = [1, 2, 5, 10, 20, 50, 100, 200] total = 200 matrix = [0] * (total + 1) matrix[0] = 1 for coin in coins: for j in range(coin, len(matrix)): matrix[j] += matrix[j - coin]