6
1
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
Order is not important 1,5 is same as 5,1
Win conditions:
Also please add the result for 78 in your title.
Ilya Gazman
Posted 2013-12-13T08:56:41.850
Reputation: 569
4
[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
DavidC
Posted 2013-12-13T08:56:41.850
Reputation: 24 524
Lots of space used on those constraints. Mathematica must have good support for generating functions: is that any shorter? – Peter Taylor – 2013-12-13T15:08:04.757
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. – DavidC – 2013-12-13T15:24:13.230
3
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
user10959
Posted 2013-12-13T08:56:41.850
Reputation: 31
2
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()))
Chaowlert Chaisrichalermpol
Posted 2013-12-13T08:56:41.850
Reputation: 121
1
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
Eelvex
Posted 2013-12-13T08:56:41.850
Reputation: 5 204
0
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
shiona
Posted 2013-12-13T08:56:41.850
Reputation: 2 889
1wait, what, the task is to discard the input and output a constant? – John Dvorak – 2013-12-13T09:14:25.303
@JanDvorak is it more clear to you now? – Ilya Gazman – 2013-12-13T09:21:37.863
If the input is not guaranteed to be 78, perhaps you should specify that? So far, it's "output a precomputed constant" – John Dvorak – 2013-12-13T09:22:07.830
@JanDvorak just did – Ilya Gazman – 2013-12-13T09:27:08.807
Negative. The input is still a constant 78. Did you mean "got n cents change ... add the result for n=78"? – John Dvorak – 2013-12-13T09:27:55.913
3How are you planning to measure "best performance"? (Also, I've retagged from [tag:code-golf] to [tag:code-challenge] on the grounds that you're asking for a criterion other than length of code. Although [tag:code-challenge] is a stretch too because it's a trivial problem). – Peter Taylor – 2013-12-13T09:30:49.897
or, should I edit the question myself when I get home (just leaving)? – John Dvorak – 2013-12-13T10:01:15.450
@JanDvorak yeah please edit it. – Ilya Gazman – 2013-12-13T10:03:57.200
@Babibu also, you should clarify if 5+1 counts the same as 1+5 – John Dvorak – 2013-12-13T10:53:46.610
@JanDvorak done – Ilya Gazman – 2013-12-13T11:19:36.177
If the output should be "[t]he number of possible ways to give the change", how can
1,5or5,1be valid outputs? – Sven Hohenstein – 2013-12-13T12:28:16.353@SvenHohenstein 5,1 is a way to pay six cents, not the program output. – John Dvorak – 2013-12-13T12:32:33.053
@SvenHohenstein So just edit by your self – Ilya Gazman – 2013-12-13T14:31:46.267
3Your 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? – Justin – 2013-12-13T18:25:19.880
@Quincunx 1 is more important then 2. You are welcome to edit the post to make it more clear – Ilya Gazman – 2013-12-14T10:24:13.287