Count the coins/0-1: Difference between revisions
Added Wren
Thundergnat (talk | contribs) m (→{{header|Raku}}: DRY, reduce to essential complexity) |
(Added Wren) |
||
Line 178:
13, 0, 1, 5, 7, 3, 2, 12
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>
| |||