6
\$\begingroup\$

You bought a tasty Orange in the supermarket and got 78 cents change. How many possible ways the supermarket guy can give you the change using 1,5,10 or 25 coins

  • Input: Change amount
  • Output: The number of possible ways to give the change.

Order is not important 1,5 is same as 5,1

Win conditions:

  1. Best performance
  2. Shortest code

Also please add the result for 78 in your title.

\$\endgroup\$
  • 1
    \$\begingroup\$ wait, what, the task is to discard the input and output a constant? \$\endgroup\$ – John Dvorak Dec 13 '13 at 9:14
  • \$\begingroup\$ @JanDvorak is it more clear to you now? \$\endgroup\$ – Ilya Gazman Dec 13 '13 at 9:21
  • \$\begingroup\$ If the input is not guaranteed to be 78, perhaps you should specify that? So far, it's "output a precomputed constant" \$\endgroup\$ – John Dvorak Dec 13 '13 at 9:22
  • 3
    \$\begingroup\$ How are you planning to measure "best performance"? (Also, I've retagged from code-golf to code-challenge on the grounds that you're asking for a criterion other than length of code. Although code-challenge is a stretch too because it's a trivial problem). \$\endgroup\$ – Peter Taylor Dec 13 '13 at 9:30
  • 3
    \$\begingroup\$ Your winning conditions are not very objective. Which is more important? Speed or chars? What about lengthy but speedy answers? What about short but not-so-fast answers? \$\endgroup\$ – Justin Dec 13 '13 at 18:25
4
\$\begingroup\$

Mathematica answer= 121, chars=74 37

[121 ways to give change of $0.78, in pennies, nickels, dimes, and quarters.]

Method 1: FroebeniusSolve

This gives all the ways to solve the Frobenius equation p + 5n + 10d + 25q = c:

FrobeniusSolve[{1, 5, 10, 25}, #]&

The number of ways is (37 chars):

Length@FrobeniusSolve[{1,5,10,25},#]&

Examples

Solutions are of the form, {pennies, nickels, dimes, quarters}:

 FrobeniusSolve[{1, 5, 10, 25}, #]&[21]

{{1,0,2,0}, {1,2,1,0}, {1,4,0,0}, {6,1,1,0}, {6,3,0,0}, {11,0,1,0}, {11,2,0,0}, {16,1,0, 0}, {21,0,0,0}}


Length@FrobeniusSolve[{1,5,10,25},#]&[78]

121


How many ways are there to give change to (.01 to $2.50)?

    Length@FrobeniusSolve[{1,5,10,25},#]&/@Range[250] // AbsoluteTiming

Timing: 2.004 sec

{2.00398, {{1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 2}, {6, 2}, {7, 2}, {8, 2}, {9, 2}, {10, 4}, {11, 4}, {12, 4}, {13, 4}, {14, 4}, {15, 6}, {16, 6}, {17, 6}, {18, 6}, {19, 6}, {20, 9}, {21, 9}, {22, 9}, {23, 9}, {24, 9}, {25, 13}, {26, 13}, {27, 13}, {28, 13}, {29, 13}, {30, 18}, {31, 18}, {32, 18}, {33, 18}, {34, 18}, {35, 24}, {36, 24}, {37, 24}, {38, 24}, {39, 24}, {40, 31}, {41, 31}, {42, 31}, {43, 31}, {44, 31}, {45, 39}, {46, 39}, {47, 39}, {48, 39}, {49, 39}, {50, 49}, {51, 49}, {52, 49}, {53, 49}, {54, 49}, {55, 60}, {56, 60}, {57, 60}, {58, 60}, {59, 60}, {60, 73}, {61, 73}, {62, 73}, {63, 73}, {64, 73}, {65, 87}, {66, 87}, {67, 87}, {68, 87}, {69, 87}, {70, 103}, {71, 103}, {72, 103}, {73, 103}, {74, 103}, {75, 121}, {76, 121}, {77, 121}, {78, 121}, {79, 121}, {80, 141}, {81, 141}, {82, 141}, {83, 141}, {84, 141}, {85, 163}, {86, 163}, {87, 163}, {88, 163}, {89, 163}, {90, 187}, {91, 187}, {92, 187}, {93, 187}, {94, 187}, {95, 213}, {96, 213}, {97, 213}, {98, 213}, {99, 213}, {100, 242}, {101, 242}, {102, 242}, {103, 242}, {104, 242}, {105, 273}, {106, 273}, {107, 273}, {108, 273}, {109, 273}, {110, 307}, {111, 307}, {112, 307}, {113, 307}, {114, 307}, {115, 343}, {116, 343}, {117, 343}, {118, 343}, {119, 343}, {120, 382}, {121, 382}, {122, 382}, {123, 382}, {124, 382}, {125, 424}, {126, 424}, {127, 424}, {128, 424}, {129, 424}, {130, 469}, {131, 469}, {132, 469}, {133, 469}, {134, 469}, {135, 517}, {136, 517}, {137, 517}, {138, 517}, {139, 517}, {140, 568}, {141, 568}, {142, 568}, {143, 568}, {144, 568}, {145, 622}, {146, 622}, {147, 622}, {148, 622}, {149, 622}, {150, 680}, {151, 680}, {152, 680}, {153, 680}, {154, 680}, {155, 741}, {156, 741}, {157, 741}, {158, 741}, {159, 741}, {160, 806}, {161, 806}, {162, 806}, {163, 806}, {164, 806}, {165, 874}, {166, 874}, {167, 874}, {168, 874}, {169, 874}, {170, 946}, {171, 946}, {172, 946}, {173, 946}, {174, 946}, {175, 1022}, {176, 1022}, {177, 1022}, {178, 1022}, {179, 1022}, {180, 1102}, {181, 1102}, {182, 1102}, {183, 1102}, {184, 1102}, {185, 1186}, {186, 1186}, {187, 1186}, {188, 1186}, {189, 1186}, {190, 1274}, {191, 1274}, {192, 1274}, {193, 1274}, {194, 1274}, {195, 1366}, {196, 1366}, {197, 1366}, {198, 1366}, {199, 1366}, {200, 1463}, {201, 1463}, {202, 1463}, {203, 1463}, {204, 1463}, {205, 1564}, {206, 1564}, {207, 1564}, {208, 1564}, {209, 1564}, {210, 1670}, {211, 1670}, {212, 1670}, {213, 1670}, {214, 1670}, {215, 1780}, {216, 1780}, {217, 1780}, {218, 1780}, {219, 1780}, {220, 1895}, {221, 1895}, {222, 1895}, {223, 1895}, {224, 1895}, {225, 2015}, {226, 2015}, {227, 2015}, {228, 2015}, {229, 2015}, {230, 2140}, {231, 2140}, {232, 2140}, {233, 2140}, {234, 2140}, {235, 2270}, {236, 2270}, {237, 2270}, {238, 2270}, {239, 2270}, {240, 2405}, {241, 2405}, {242, 2405}, {243, 2405}, {244, 2405}, {245, 2545}, {246, 2545}, {247, 2545}, {248, 2545}, {249, 2545}, {250, 2691}}}


Method 2: Solution by Solve (66 chars).

This solves the same equation listed in Method 1, albeit by a more standard method, Solve:

f[c_]:=Solve[p +5n+10d+25q==c &&p>=0&&n>= 0&&d>=0&&q>= 0,{p,n,d,q},Integers]

The number of ways is (74 chars):

g@c_:= Length@Solve[p +5n+10d+25q==c &&p>=0&&n>= 0&&d>=0&&q>= 0,{p,n,d,q},Integers]

Examples

 f[21]

{{p → 1, n → 0, d → 2, q → 0}, {p → 1, n → 2, d → 1, q → 0}, {p → 1, n → 4, d → 0, q → 0}, {p → 6, n → 1, d → 1, q → 0}, {p → 6, n → 3, d → 0, q → 0}, {p → 11, n → 0, d → 1, q → 0}, {p → 11, n → 2, d → 0, q → 0}, {p → 16, n → 1, d → 0, q → 0}, {p → 21, n → 0, d → 0, q → 0}}


 Length[f[78]]

121


How many ways are there to give change to (.01 to $2.50)?

{#, g[#]} & /@ Range[250] // AbsoluteTiming

Timing: 4.72 sec

\$\endgroup\$
  • \$\begingroup\$ Lots of space used on those constraints. Mathematica must have good support for generating functions: is that any shorter? \$\endgroup\$ – Peter Taylor Dec 13 '13 at 15:08
  • \$\begingroup\$ There may be a shorter way to specify the set of non-negative integers, but I haven't found it. Anyway, I just found a distinct approach that only returns non-negative integers. \$\endgroup\$ – DavidC Dec 13 '13 at 15:24
3
\$\begingroup\$

K3 (kona), 121.

Simple dynamic progamming. 57 chars.

cg:{*{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]}

  cg 78
121

Calculate all results up to 250 cents

  {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 250
2691 2545 2545 2545 2545 2545 2405 2405 2405 2405 2405 2270 2270 2270 2270 2270 2140 2140 2140 2140 2140 2015 2015 2015 2015 2015 1895 1895 1895 1895 1895 1780 1780 1780 1780 1780 1670 1670 1670 1670 1670 1564 1564 1564 1564 1564 1463 1463 1463 1463 1463 1366 1366 1366 1366 1366 1274 1274 1274 1274 1274 1186 1186 1186 1186 1186 1102 1102 1102 1102 1102 1022 1022 1022 1022 1022 946 946 946 946 946 874 874 874 874 874 806 806 806 806 806 741 741 741 741 741 680 680 680 680 680 622 622 622 622 622 568 568 568 568 568 517 517 517 517 517 469 469 469 469 469 424 424 424 424 424 382 382 382 382 382 343 343 343 343 343 307 307 307 307 307 273 273 273 273 273 242 242 242 242 242 213 213 213 213 213 187 187 187 187 187 163 163 163 163 163 141 141 141 141 141 121 121 121 121 121 103 103 103 103 103 87 87 87 87 87 73 73 73 73 73 60 60 60 60 60 49 49 49 49 49 39 39 39 39 39 31 31 31 31 31 24 24 24 24 24 18 18 18 18 18 13 13 13 13 13 9 9 9 9 9 6 6 6 6 6 4 4 4 4 4 2 2 2 2 2 1 1 1 1 1

Time to do so (in milliseconds)

 \t {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 250
10

Time to calculate up to 5000 cents: \t {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 5000 360

\$\endgroup\$
2
\$\begingroup\$

result=121, javascript with memoize (160 chars)

c=[25,10,5,1]
d=[[1],[1],[1],[1]]
function f(x,y){
    return d[x][y]||(d[x][y]=c.slice(x).reduce(function(i,j,k){
        return i+(j>y?0:f(x+k,y-j))
    },0))
}
alert(f(0,prompt()))

result=121, javascript without memoize (126 chars)

c=[25,10,5,1]
function f(x,y){
    return y?c.slice(x).reduce(function(i,j,k){
        return i+(j>y?0:f(x+k,y-j))
    },0):1
}
alert(f(0,prompt()))
\$\endgroup\$
1
\$\begingroup\$

J, 50 48 40

result: 121

g=.{[:+//.@(*/)/0=1 5 10 25|"0 _ ]@i.@>:

Using generating functions approach. I'd say performance is not bad and can be easily made much better.

g 78
121
g 248
2545

Timing:

time'g 78'
0.000254s
\$\endgroup\$
0
\$\begingroup\$

Haskell - 51 / 69

Answer: 121

_%0=1;[]%_=0;(x:y)%m=sum[y%(m-i*x)|i<-[0..m`div`x]]

Call notation: [1,5,10,25]%78

Or more complete with an extra line:

f=([1,5,10,25]%)

The call is just: f 78

Efficiency test (should be comparable with David Carraher):

main=mapM_(print.([1,5,10,25]%))[1..250]

> ghc -O2 frob.hs && time ./frob
 - -
./frob  1.81s user 0.02s system 99% cpu 1.843 total
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.