Count the coins/0-1: Difference between revisions
m
→{{header|11l}}: Void
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 26:
* Show an example of coins you used to reach the given sum and their indices. See Raku for this case.
=={{header|11l}}==
{{trans|Nim}}
<syntaxhighlight lang="11l">T Solver
Int want, width
count1 = 0
count2 = 0
F (want, width)
.want = want
.width = width
F count(Int sum; [Int] used, have, uindices, rindices) -> Void
I sum == .want
.count1++
.count2 += factorial(used.len)
I .count1 < 11
V uindiceStr = uindices.join(‘ ’).ljust(.width)
print(‘ indices ’uindiceStr‘ => used ’used.join(‘ ’))
E I sum < .want & !have.empty
V thisCoin = have[0]
V index = rindices[0]
V rest = have[1..]
V new_rindices = rindices[1..]
.count(sum + thisCoin, used [+] thisCoin, rest, uindices [+] index, new_rindices)
.count(sum, used, rest, uindices, new_rindices)
F count_coins(Int want, [Int] &coins, Int width)
print(‘Sum ’want‘ from coins ’coins.join(‘ ’))
V solver = Solver(want, width)
V rindices = Array(0 .< coins.len)
solver.count(0, [Int](), coins, [Int](), rindices)
I solver.count1 > 10
print(‘ .......’)
print(‘ (only the first 10 ways generated are shown)’)
print(‘Number of ways - order unimportant : ’(solver.count1)‘ (as above)’)
print(‘Number of ways - order important : ’(solver.count2)" (all perms of above indices)\n")
count_coins(6, &[1, 2, 3, 4, 5], 5)
count_coins(6, &[1, 1, 2, 3, 3, 4, 5], 7)
count_coins(40, &[1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
=={{header|ALGOL 68}}==
{{Trans|Go}}which is{{Trans|Wren}}
<syntaxhighlight lang="algol68">
BEGIN # count the ways of summing coins to a particular number - translation of the Go sample #
INT countu := 0; # order unimportant #
INT counti := 0; # order important #
INT width := 0; # for printing purposes #
PROC factorial = (INT n )INT:
BEGIN
INT prod := 1;
FOR i FROM 2 TO n DO
prod *:= i
OD;
prod
END # factorial # ;
OP LEN = ( []INT a )INT: ( UPB a - LWB a ) + 1;
OP LEN = ( STRING a )INT: ( UPB a - LWB a ) + 1;
PROC append = ( []INT a, INT b )[]INT:
BEGIN
[ 1 : LEN a + 1 ]INT result;
result[ 1 : LEN a ] := a;
result[ LEN a + 1 ] := b;
result
END # append # ;
OP TOSTRING = ( []INT a )STRING:
BEGIN
STRING result := "[";
STRING separator := "";
FOR i FROM LWB a TO UPB a DO
result +:= separator + whole( a[ i ], 0 );
separator := " "
OD;
result +:= "]"
END # TOSTRING # ;
PROC pad = ( STRING a, INT width )STRING:
IF INT len a = LEN a; len a >= width THEN a ELSE a + ( " " * ( width - len a ) ) FI;
PROC count = ( INT want, []INT used, INT sum, []INT have, uindices, rindices )VOID:
IF sum = want THEN
countu +:= 1;
counti +:= factorial( LEN used );
IF countu < 11 THEN
STRING uindices str = TOSTRING uindices;
print( ( " indices ", pad( uindices str, width ), " => used ", TOSTRING used, newline ) )
FI
ELIF sum < want AND LEN have /= 0 THEN
INT this coin = have[ LWB have ];
INT index = rindices[ LWB rindices ];
[]INT rest = have[ LWB have + 1 : ];
count( want, append( used, this coin ), sum + this coin, rest,
append( uindices, index ), rindices[ LWB rindices + 1 : ] );
count( want, used, sum, rest, uindices, rindices[ LWB rindices + 1 : ] )
FI # count # ;
PROC count coins = ( INT want, []INT coins, INT rqd width )VOID:
BEGIN
print( ( "Sum ", whole( want, 0 ), " from coins ", TOSTRING coins, newline ) );
countu := 0;
counti := 0;
width := rqd width;
[ 0 : LEN coins - 1 ]INT rindices;
FOR i FROM LWB rindices TO UPB rindices DO
rindices[ i ] := i
OD;
count( want, []INT(), 0, coins, []INT(), rindices );
IF countu > 10 THEN
print( ( " .......", newline ) );
print( ( " (only the first 10 ways generated are shown)", newline ) )
FI;
print( ( "Number of ways - order unimportant : ", whole( countu, 0 )
, " (as above)", newline ) );
print( ( "Number of ways - order important : ", whole( counti, 0 )
, " (all perms of above indices)", newline, newline ) )
END # count coins # ;
BEGIN # task #
count coins( 6, ( 1, 2, 3, 4, 5 ), 7 );
count coins( 6, ( 1, 1, 2, 3, 3, 4, 5 ), 9 );
count coins( 40, ( 1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100 ), 20 )
END
END
</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
=={{header|FreeBASIC}}==
Based on the Phix entry and the Nim entry
<syntaxhighlight lang="vb">#define factorial(n) Iif(n<2, 1, n*factorial1(n-1))
REM silly way
Function silly(coins() As Short, tgt As Short, cdx As Short = 1) As Integer
Dim As Integer count = 0
If tgt = 0 Then
count += 1
Elseif tgt > 0 And cdx <= Ubound(coins) Then
count += silly(coins(), tgt-coins(cdx), cdx+1)
count += silly(coins(), tgt, cdx+1)
End If
Return count
End Function
REM very silly way
Function very_silly(coins() As Short, tgt As Short, cdx As Short = 1, taken As Short = 0) As Integer
Dim As Integer count = 0
If tgt = 0 Then
count += factorial(taken)
Elseif tgt > 0 And cdx <= Ubound(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
Sub countCoins(coins() As Short, tgt As Short)
Print "Sum"; tgt; " from coins ";
For a As Short = 1 To Ubound(coins)
Print coins(a);
Next a
Print !"\nNumber of ways - order unimportant:"; silly(coins(), tgt)
Print "Number of ways - order important :"; very_silly(coins(), tgt); !"\n"
End Sub
Dim As Short test0(1 To ...) = {1, 2, 3, 4, 5}
countCoins(test0(), 6)
Dim As Short test1(1 To ...) = {1, 1, 2, 3, 3, 4, 5}
countCoins(test1(), 6)
Dim As Short test2(1 To ...) = {1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100}
countCoins(test2(), 40)
Sleep</syntaxhighlight>
{{out}}
<pre>Sum 6 from coins 1 2 3 4 5
Number of ways - order unimportant: 3
Number of ways - order important : 10
Sum 6 from coins 1 1 2 3 3 4 5
Number of ways - order unimportant: 9
Number of ways - order important : 38
Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
Number of ways - order unimportant: 464
Number of ways - order important : 3782932</pre>
=={{header|Go}}==
Line 963 ⟶ 1,228:
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.
<syntaxhighlight lang="
import "./math" for Int
var cnt = 0 // order unimportant
| |||