Count the coins/0-1: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Raku}}: DRY, reduce to essential complexity) |
(Added Wren) |
||
Line 178: | Line 178: | ||
13, 0, 1, 5, 7, 3, 2, 12 |
13, 0, 1, 5, 7, 3, 2, 12 |
||
13, 6, 10, 1, 4, 3, 2, 0</pre> |
13, 6, 10, 1, 4, 3, 2, 0</pre> |
||
=={{header|Wren}}== |
|||
{{trans|Perl}} |
|||
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) 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> |
|||
{{out}} |
|||
<pre> |
|||
Sum 6 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 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 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> |