Count the coins/0-1: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 29:
=={{header|Go}}==
{{trans|Wren}}
<
import "fmt"
Line 86:
countCoins(6, []int{1, 1, 2, 3, 3, 4, 5}, 9)
countCoins(40, []int{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 20)
}</
{{out}}
Line 129:
=={{header|J}}==
Implementation:<
ccoins=: {{ (#i), +/!x:+/"1 i=. x selcoins y }}</
<code>selcoins</code> identifies the valid selections of the coins. <code>ccoins</code> counts them, giving two counts (first is where coin order does not matter, second is where each permutation of physical coins is counted separately).
Task examples:<
3 10
6 ccoins 1 1 2 3 3 4 5
9 38
40 ccoins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
464 3782932</
Some example coin selections:<
2 4
1 5
Line 164:
15 15 10
5 10 25
5 10 25</
=={{header|jq}}==
Line 172:
The solutions presented in this section use generic `combinations` and `permutations`
functions defined as follows:
<syntaxhighlight lang="jq">
# Input: an array of arrays
# Output: a stream of arrays corresponding to the selection of exactly one item
Line 191:
| [.[$i]] + (del(.[$i])|permutations)
end ;
</syntaxhighlight>
<syntaxhighlight lang="jq">
## Generic helper functions:
def count(s): reduce s as $x (0; .+1);
Line 199:
# Output: [ [a,0], [b,0],... ] | combinations
def zero_or_one: [ .[] | [., 0] ] | combinations;
</syntaxhighlight>
'''The task'''
<syntaxhighlight lang="jq">
def count_combinations_with_sum($sum):
count( zero_or_one | select(add == $sum));
Line 222:
[[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]
| task</
{{out}}
<pre>
Line 239:
=={{header|Julia}}==
<
function coinsum(coins, targetsum; verbose=true)
Line 260:
coinsum([1, 1, 2, 3, 3, 4, 5], 6)
coinsum([1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40, verbose=false)
</
<pre>
Coins are [1, 2, 3, 4, 5], target sum is 6:
Line 333:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
CoinSums[coins_List, sum_] := Module[{c, len, max, bin, sel, out},
c = {Range[Length[coins]], coins} // Transpose;
Line 355:
CoinSums[{1, 2, 3, 4, 5}, 6]
CoinSums[{1, 1, 2, 3, 3, 4, 5}, 6]
CoinSums[{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 40] // Take[#, UpTo[10]] &</
{{out}}
Note that the indexing is 1-based and that for the last case only the first 10 solutions are shown:
Line 367:
=={{header|MiniZinc}}==
; coins = [1, 2, 3, 4, 5] and sum = 6
<syntaxhighlight lang="minizinc">
%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e};
Line 374:
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=6;
</syntaxhighlight>
{{out}}
<pre>
Line 398:
</pre>
; coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6
<syntaxhighlight lang="minizinc">
%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e,f,g};
Line 405:
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=6;
</syntaxhighlight>
{{out}}
<pre>
Line 441:
</pre>
; coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40
<syntaxhighlight 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};
Line 448:
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=40;
</syntaxhighlight>
{{out}}
<pre>
Line 501:
Using a solver object rather than global variables.
<
type Solver = object
Line 538:
countCoins(6, [1, 2, 3, 4, 5], 5)
countCoins(6, [1, 1, 2, 3, 3, 4, 5], 7)
countCoins(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)</
{{out}}
Line 579:
=={{header|Pascal}}==
first count all combinations by brute force.Order is important.Modified nQueens.<BR>Next adding weigths by index.<BR>Using Phix wording 'silly'.
<
{$IFDEF FPC}
{$MODE DELPHI}
Line 690:
CheckAll(High(coins3),40);
end.
</syntaxhighlight>
{{out}}
<pre>
Line 702:
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1
Line 733:
count( $want, $used, $sum, \@rest);
}
}</
{{out}}
<pre>
Line 749:
=== sane way ===
In the second test, this counts [1,2,3] as one way to get 6, not counting the other [1,2,3] or the other [1,2,3] or the other [1,2,3].
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">choices</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
Line 769:
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">choices</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
<pre>
Line 776:
=== silly way ===
In the second test, this counts [1,2,3] as four ways to get 6, since there are two 1s and two 3s... ("order unimportant")
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">silly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
Line 793:
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">silly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
<pre>
Line 800:
=== very silly way ===
In the second test, this counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s, and 6 ways to order them ("order important")
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">very_silly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
Line 817:
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">40</span><span style="color: #0000FF;">}}</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">very_silly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
<pre>
Line 823:
</pre>
=={{header|Python}}==
<
fact = lambda n: n and n*fact(n - 1) or 1
Line 840:
for s, c in cases:
print(f'{combo_count(s, c, perm):7d} ways for {s:2d} total from coins {c}')
print()</
{{out}}
<pre>Order matters: False
Line 857:
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]].
<syntaxhighlight lang="raku"
,<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
Line 873:
put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' );
put $list.pick(10).sort».join(', ').join: "\n"
}</
{{out}}
<pre>How many combinations of [1, 2, 3, 4, 5] sum to 6?
Line 963:
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.
<
import "/math" for Int
Line 1,002:
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)</
{{out}}
| |||