Count the coins/0-1: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Raku}}: Add a Raku example) |
|||
Line 71: | Line 71: | ||
Number of ways: 464 |
Number of ways: 464 |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
This is pretty much duplicating other tasks, in process if not wording. First part is combinations filtered on a certain property. Second part (extra credit) is permutations of those combinations. 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]], [[Subset sum problem]] and to a large extent [[4-rings or 4-squares puzzle]]. |
|||
<lang perl6>sub which (*@items, :$sum-to) { ^@items .combinations.grep: { @items[$_].sum == $sum-to } } |
|||
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.&which: :sum-to( $sum ) { |
|||
put "\nOrder unimportant:\nCount: { +$_ }\nIndices" ~ ( +$_ > 10 ?? ' (10 random examples):' !! ':' ); |
|||
put .pick(10).sort».join(', ').join: "\n"; |
|||
} |
|||
given @items.&which( :sum-to( $sum ) ).map: { Slip(.permutations) } { |
|||
put "\nOrder important:\nCount: { +$_ }\nIndices" ~ ( +$_ > 10 ?? ' (10 random examples):' !! ':' ); |
|||
put .pick(10).sort».join(', ').join: "\n"; |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>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</pre> |
Revision as of 17:43, 6 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 the 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 Perl for this case.
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
Raku
This is pretty much duplicating other tasks, in process if not wording. First part is combinations filtered on a certain property. Second part (extra credit) is permutations of those combinations. 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, Subset sum problem and to a large extent 4-rings or 4-squares puzzle.
<lang perl6>sub which (*@items, :$sum-to) { ^@items .combinations.grep: { @items[$_].sum == $sum-to } }
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.&which: :sum-to( $sum ) { put "\nOrder unimportant:\nCount: { +$_ }\nIndices" ~ ( +$_ > 10 ?? ' (10 random examples):' !! ':' ); put .pick(10).sort».join(', ').join: "\n"; }
given @items.&which( :sum-to( $sum ) ).map: { Slip(.permutations) } { put "\nOrder important:\nCount: { +$_ }\nIndices" ~ ( +$_ > 10 ?? ' (10 random examples):' !! ':' ); put .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