Count the coins/0-1: Difference between revisions
→{{header|Phix}}: well...
m (→{{header|Wren}}: Minor changes.) |
(→{{header|Phix}}: well...) |
||
Line 201:
sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
Number of ways: 464
</pre>
=={{header|Phix}}==
=== sane way ===
This counts [1,2,3] as one way, not counting [in 2nd test] the other [1,2,3] or the other [1,2,3] or the other [1,2,3].
<lang Phix>function choices(sequence coins, integer tgt, cdx=1)
integer count = 0
if tgt=0 then
count += 1
elsif tgt>0 and cdx<=length(coins) then
object ci = coins[cdx]
integer {c,n} = iff(sequence(ci)?ci:{ci,1})
for j=0 to n do
count += choices(coins,tgt-j*c,cdx+1)
end for
end if
return count
end function
constant tests = {{{1,2,3,4,5},6},
{{{1,2},2,{3,2},4,5},6},
{{1,2,3,4,{5,4},{15,2},{10,4},25,100},40}}
?apply(false,choices,tests)</lang>
{{out}}
<pre>
{3,5,33}
</pre>
=== silly way ===
This counts [1,2,3] as four ways to get 6, since [in 2nd test] there are two 1s and two 3s... (order unimportant)
<lang Phix>function silly(sequence coins, integer tgt, cdx=1)
integer count = 0
if tgt=0 then
count += 1
elsif tgt>0 and cdx<=length(coins) then
count += silly(coins,tgt-coins[cdx],cdx+1)
count += silly(coins,tgt,cdx+1)
end if
return count
end function
constant tests = {{{1,2,3,4,5},6},
{{1,1,2,3,3,4,5},6},
{{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}}
?apply(false,silly,tests)</lang>
{{out}}
<pre>
{3,9,464}
</pre>
=== very silly way ===
This counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s [in 2nd test], and 6 ways to order them (order important)
<lang Phix>function very_silly(sequence coins, integer tgt, cdx=1, taken=0)
integer count = 0
if tgt=0 then
count += factorial(taken)
elsif tgt>0 and cdx<=length(coins) then
count += very_silly(coins,tgt-coins[cdx],cdx+1,taken+1)
count += very_silly(coins,tgt,cdx+1,taken)
end if
return count
end function
constant tests = {{{1,2,3,4,5},6},
{{1,1,2,3,3,4,5},6},
{{1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100},40}}
?apply(false,very_silly,tests)</lang>
{{out}}
<pre>
{10,38,3782932}
</pre>
| |||