Count the coins/0-1: Difference between revisions
m (→{{header|Wren}}: Minor changes.) |
(→{{header|Phix}}: well...) |
||
Line 201: | Line 201: | ||
sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 |
sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 |
||
Number of ways: 464 |
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> |
</pre> |
||
Revision as of 01:49, 8 January 2021
Let say you have some coins in your wallet and you want to have a given sum.
You can use each coin zero or one time.
How many ways can you do it ?
The result should be a number.
For instance the answer is 10 when coins = [1, 2, 3, 4, 5] and sum = 6.
- Task
Show the result for the following examples:
- coins = [1, 2, 3, 4, 5] and sum = 6
- coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
- coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
- Extra
- Show the result of the same examples when the order you take the coins doesn't matter. For instance the answer is 3 when coins = [1, 2, 3, 4, 5] and sum = 6.
- Show an example of coins you used to reach the given sum and their indices. See Raku for this case.
MiniZinc
- coins = [1, 2, 3, 4, 5] and sum = 6
<lang MiniZinc> %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e}; array[Items] of int: weight=[1,2,3,4,5]; var set of Items: selected; var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=6; </lang>
- Output:
selected = {a, b, c}; ---------- selected = {a, e}; ---------- selected = {b, d}; ---------- ========== %%%mzn-stat: initTime=0 %%%mzn-stat: solveTime=0.001 %%%mzn-stat: solutions=3 %%%mzn-stat: variables=21 %%%mzn-stat: propagators=31 %%%mzn-stat: propagations=236 %%%mzn-stat: nodes=11 %%%mzn-stat: failures=3 %%%mzn-stat: restarts=0 %%%mzn-stat: peakDepth=3 %%%mzn-stat-end Finished in 172msec
- coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
<lang MiniZinc> %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e,f,g}; array[Items] of int: weight=[1,1,2,3,3,4,5]; var set of Items: selected; var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=6; </lang>
- Output:
selected = {a, b, f}; ---------- selected = {a, c, d}; ---------- selected = {a, c, e}; ---------- selected = {a, g}; ---------- selected = {b, c, d}; ---------- selected = {b, c, e}; ---------- selected = {b, g}; ---------- selected = {c, f}; ---------- selected = {d, e}; ---------- ========== %%%mzn-stat: initTime=0 %%%mzn-stat: solveTime=0.001 %%%mzn-stat: solutions=9 %%%mzn-stat: variables=29 %%%mzn-stat: propagators=43 %%%mzn-stat: propagations=820 %%%mzn-stat: nodes=35 %%%mzn-stat: failures=9 %%%mzn-stat: restarts=0 %%%mzn-stat: peakDepth=4 %%%mzn-stat-end Finished in 187msec
- coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
<lang MiniZinc> %Subset sum. Nigel Galloway: January 6th., 2021. enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}; array[Items] of int: weight=[1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100]; var set of Items: selected; var int: wSelected=sum(n in selected)(weight[n]); constraint wSelected=40; </lang>
- Output:
selected = {a, b, c, d, e, f, g, h, k}; ---------- selected = {a, b, c, d, e, f, g, h, l}; ---------- [ 0 more solutions ] selected = {a, b, c, d, e, f, g, h, m}; ---------- [ 1 more solutions ] selected = {a, b, c, d, e, f, g, i}; ---------- [ 3 more solutions ] selected = {a, b, c, d, e, f, k, l}; ---------- [ 7 more solutions ] selected = {a, b, c, d, e, g, k, l}; ---------- [ 15 more solutions ] selected = {a, b, c, d, e, j, k}; ---------- [ 31 more solutions ] selected = {a, b, c, d, g, h, l, n}; ---------- [ 63 more solutions ] selected = {a, d, e, h, i, l}; ---------- [ 127 more solutions ] selected = {b, c, e, l, m, n}; ---------- [ 206 more solutions ] selected = {k, l, m, n}; ---------- ========== %%%mzn-stat: initTime=0.001 %%%mzn-stat: solveTime=0.011 %%%mzn-stat: solutions=464 %%%mzn-stat: variables=65 %%%mzn-stat: propagators=91 %%%mzn-stat: propagations=122926 %%%mzn-stat: nodes=4203 %%%mzn-stat: failures=1638 %%%mzn-stat: restarts=0 %%%mzn-stat: peakDepth=13 %%%mzn-stat-end Finished in 207msec
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1 use warnings;
countcoins( 6, [1, 2, 3, 4, 5] ); countcoins( 6, [1, 1, 2, 3, 3, 4, 5] ); countcoins( 40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] );
my $count;
sub countcoins
{ my ($want, $coins) = @_; print "\nsum $want coins @$coins\n"; $count = 0; count($want, [], 0, $coins); print "Number of ways: $count\n"; }
sub count
{ my ($want, $used, $sum, $have) = @_; if( $sum == $want ) { $count++ } elsif( $sum > $want or @$have == 0 ) {} else { my ($thiscoin, @rest) = @$have; count( $want, [@$used, $thiscoin], $sum + $thiscoin, \@rest); count( $want, $used, $sum, \@rest); } }</lang>
- Output:
sum 6 coins 1 2 3 4 5 Number of ways: 3 sum 6 coins 1 1 2 3 3 4 5 Number of ways: 9 sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100 Number of ways: 464
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>
- Output:
{3,5,33}
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>
- Output:
{3,9,464}
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>
- Output:
{10,38,3782932}
Raku
First part is combinations filtered on a certain property. Second part (extra credit) is permutations of those combinations.
This is pretty much duplicating other tasks, in process if not wording. Even though I am adding a solution, my vote would be for deletion as it doesn't really add anything to the other tasks; Combinations, Permutations, Subset sum problem and to a large extent 4-rings or 4-squares puzzle.
<lang perl6>for <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 -> @items, $sum {
put "\n\nHow many combinations of [{ @items.join: ', ' }] sum to $sum?";
given ^@items .combinations.grep: { @items[$_].sum == $sum } { .&display; display .race.map( { Slip(.permutations) } ), ; }
}
sub display ($list, $un = 'un') {
put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' ); put $list.pick(10).sort».join(', ').join: "\n"
}</lang>
- Output:
How many combinations of [1, 2, 3, 4, 5] sum to 6? Order unimportant: Count: 3 Indices: 0, 1, 2 0, 4 1, 3 Order important: Count: 10 Indices: 0, 1, 2 0, 2, 1 0, 4 1, 0, 2 1, 2, 0 1, 3 2, 0, 1 2, 1, 0 3, 1 4, 0 How many combinations of [1, 1, 2, 3, 3, 4, 5] sum to 6? Order unimportant: Count: 9 Indices: 0, 1, 5 0, 2, 3 0, 2, 4 0, 6 1, 2, 3 1, 2, 4 1, 6 2, 5 3, 4 Order important: Count: 38 Indices (10 random examples): 0, 4, 2 1, 2, 3 1, 2, 4 1, 5, 0 1, 6 2, 1, 3 2, 1, 4 2, 4, 0 3, 2, 0 6, 0 How many combinations of [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] sum to 40? Order unimportant: Count: 464 Indices (10 random examples): 0, 1, 2, 3, 5, 7, 10, 11 0, 1, 2, 3, 5, 8, 12 0, 1, 2, 3, 6, 7, 11, 13 0, 3, 5, 7, 9, 13 0, 3, 9, 10, 11 1, 2, 5, 7, 9, 13 4, 5, 10, 12, 13 5, 6, 7, 9, 10 5, 6, 10, 11, 12 5, 8, 10, 12 Order important: Count: 3782932 Indices (10 random examples): 0, 11, 3, 4, 7, 5, 6, 1, 2 1, 10, 5, 4, 6, 2, 0, 3, 7 2, 7, 13, 4, 1, 3, 5, 6, 0 2, 12, 4, 13, 10, 1 3, 0, 5, 4, 7, 13, 6, 2, 1 5, 7, 9, 4, 0, 1, 2, 3 6, 2, 7, 11, 0, 3, 5, 1, 4 10, 0, 12, 6, 5, 3, 4 13, 0, 1, 5, 7, 3, 2, 12 13, 6, 10, 1, 4, 3, 2, 0
Wren
Well, after some huffing and puffing, the house is still standing so I thought I'd have a go at it. Based on the Perl algorithm but modified to deal with the extra credit. <lang ecmascript>import "/fmt" for Fmt import "/math" for Int
var cnt = 0 // order unimportant var cnt2 = 0 // order important var wdth = 0 // for printing purposes
var count // recursive count = Fn.new { |want, used, sum, have, uindices, rindices|
if (sum == want) { cnt = cnt + 1 cnt2 = cnt2 + Int.factorial(used.count) if (cnt < 11) Fmt.print(" indices $*n => used $n", wdth, uindices, used) } else if (sum < want && !have.isEmpty) { var thisCoin = have[0] var index = rindices[0] var rest = have.skip(1).toList var rindices = rindices.skip(1).toList count.call(want, used + [thisCoin], sum + thisCoin, rest, uindices + [index], rindices) count.call(want, used, sum, rest, uindices, rindices) }
}
var countCoins = Fn.new { |want, coins, width|
System.print("Sum %(want) from coins %(coins)") cnt = 0 cnt2 = 0 wdth = -width count.call(want, [], 0, coins, [], (0...coins.count).toList) if (cnt > 10) { System.print(" .......") System.print(" (only the first 10 ways generated are shown)") } System.print("Number of ways - order unimportant : %(cnt) (as above)") System.print("Number of ways - order important : %(cnt2) (all perms of above indices)\n")
}
countCoins.call(6, [1, 2, 3, 4, 5], 9) countCoins.call(6, [1, 1, 2, 3, 3, 4, 5], 9) countCoins.call(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 28)</lang>
- Output:
Sum 6 from coins [1, 2, 3, 4, 5] indices [0, 1, 2] => used [1, 2, 3] indices [0, 4] => used [1, 5] indices [1, 3] => used [2, 4] Number of ways - order unimportant : 3 (as above) Number of ways - order important : 10 (all perms of above indices) Sum 6 from coins [1, 1, 2, 3, 3, 4, 5] indices [0, 1, 5] => used [1, 1, 4] indices [0, 2, 3] => used [1, 2, 3] indices [0, 2, 4] => used [1, 2, 3] indices [0, 6] => used [1, 5] indices [1, 2, 3] => used [1, 2, 3] indices [1, 2, 4] => used [1, 2, 3] indices [1, 6] => used [1, 5] indices [2, 5] => used [2, 4] indices [3, 4] => used [3, 3] Number of ways - order unimportant : 9 (as above) Number of ways - order important : 38 (all perms of above indices) Sum 40 from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] indices [0, 1, 2, 3, 4, 5, 6, 7, 10] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 7, 11] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 7, 12] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 7, 13] => used [1, 2, 3, 4, 5, 5, 5, 5, 10] indices [0, 1, 2, 3, 4, 5, 6, 8] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 6, 9] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 7, 8] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 7, 9] => used [1, 2, 3, 4, 5, 5, 5, 15] indices [0, 1, 2, 3, 4, 5, 10, 11] => used [1, 2, 3, 4, 5, 5, 10, 10] indices [0, 1, 2, 3, 4, 5, 10, 12] => used [1, 2, 3, 4, 5, 5, 10, 10] ....... (only the first 10 ways generated are shown) Number of ways - order unimportant : 464 (as above) Number of ways - order important : 3782932 (all perms of above indices)