Rosetta Code

Count the coins: Difference between revisions

Page Discussion

Count the coins (view source)

Revision as of 10:21, 16 March 2024

6,060 bytes added ,  2 months ago
→‎{{header|RPL}}: typo
m (syntax highlighting fixup automation)
(18 intermediate revisions by 7 users not shown)
Line 999:
 
=={{header|Dart}}==
Simple recursive version plus cached version using a map.
 
=== Dart 1 version: ===
<syntaxhighlight lang="dart">
var cache = new Map();
Line 1,063 ⟶ 1,065:
... completed in 3.604 seconds
</pre>
 
=== Dart 2 version: ===
<syntaxhighlight lang="dart">
 
/// Provides the same result and performance as the Dart 1 version
/// but using the Dart 2 specifications.
Map<String, int> cache = {};
 
void main() {
Stopwatch stopwatch = Stopwatch()..start();
 
/// Use the brute-force recursion for the small problem
int amount = 100;
List<int> coinTypes = [25,10,5,1];
print ("${coins(amount,coinTypes)} ways for $amount using $coinTypes coins.");
 
/// Use the cache version for the big problem
amount = 100000;
coinTypes = [100,50,25,10,5,1];
print ("${cachedCoins(amount,coinTypes)} ways for $amount using $coinTypes coins.");
 
stopwatch.stop();
print ("... completed in ${stopwatch.elapsedMilliseconds/1000} seconds");
 
}
 
int cachedCoins(int amount, List<int> coinTypes) {
int count = 0;
 
/// This is more efficient, looks at last two coins.
/// But not fast enough for the optional exercise.
if(coinTypes.length == 2) return (amount ~/ coinTypes[0] + 1);
 
/// Looks like "100.[25,10,5,1]"
String key = "$amount.$coinTypes";
/// Check whether we have seen this before
var cacheValue = cache[key];
 
if(cacheValue != null) return(cacheValue);
 
count = 0;
/// Same recursion as simple method, but caches all subqueries too
for(int i=0; i<=amount ~/ coinTypes[0]; i++){
count += cachedCoins(amount-(i*coinTypes[0]),coinTypes.sublist(1)); // sublist(1) is like lisp's '(rest ...)'
}
 
/// add this to the cache
cache[key] = count;
return count;
}
 
int coins(int amount, List<int> coinTypes) {
int count = 0;
 
/// Just pennies available, so only one way to make change
if(coinTypes.length == 1) return (1);
 
/// Brute force recursion
for(int i=0; i<=amount ~/ coinTypes[0]; i++){
/// sublist(1) is like lisp's '(rest ...)'
count += coins(amount - (i*coinTypes[0]),coinTypes.sublist(1));
}
 
/// Uncomment if you want to see intermediate steps
/// print("there are " + count.toString() +" ways to count change for ${amount.toString()} using ${coinTypes} coins.");
return count;
}
</syntaxhighlight>
{{out}}
<pre>
242 ways for 100 using [25, 10, 5, 1] coins.
13398445413854501 ways for 100000 using [100, 50, 25, 10, 5, 1] coins.
... completed in 2.921 seconds
 
Process finished with exit code 0
</pre>
 
=={{header|Delphi}}==
{{Trans|C#}}
Line 1,096 ⟶ 1,175:
end.
</syntaxhighlight>
=={{header|Draco}}==
<syntaxhighlight lang="draco">proc main() void:
[4]byte coins = (1, 5, 10, 25);
[101]byte tab;
word m, n;
 
for n from 1 upto 100 do tab[n] := 0 od;
tab[0] := 1;
 
for m from 0 upto 3 do
for n from coins[m] upto 100 do
tab[n] := tab[n] + tab[n - coins[m]]
od
od;
 
writeln(tab[100])
corp</syntaxhighlight>
{{out}}
<pre>242</pre>
 
=={{header|Dyalect}}==
 
Line 1,117 ⟶ 1,216:
 
<pre>242</pre>
 
=={{header|EasyLang}}==
 
<syntaxhighlight lang="easylang">
len cache[] 100000 * 7 + 6
val[] = [ 1 5 10 25 50 100 ]
func count sum kind .
if sum = 0
return 1
.
if sum < 0 or kind = 0
return 0
.
chind = sum * 7 + kind
if cache[chind] > 0
return cache[chind]
.
r2 = count (sum - val[kind]) kind
r1 = count sum (kind - 1)
r = r1 + r2
cache[chind] = r
return r
.
print count 100 4
print count 10000 6
print count 100000 6
# this is not exact, since numbers
# are doubles and r > 2^53
</syntaxhighlight>
 
=={{header|EchoLisp}}==
Line 1,539 ⟶ 1,667:
Running time: 0.029163549 seconds
</syntaxhighlight>
 
=={{header|FOCAL}}==
<syntaxhighlight lang="focal">01.10 S C(1)=1;S C(2)=5;S C(3)=10;S C(4)=25
01.20 F N=1,100;S T(N)=0
01.30 S T(0)=1
01.40 F M=1,4;F N=C(M),100;S T(N)=T(N)+T(N-C(M))
01.50 T %3,T(100),!
01.60 Q</syntaxhighlight>
{{out}}
<pre>= 242</pre>
 
=={{header|Forth}}==
Line 2,285 ⟶ 2,423:
CheckThisToo
</syntaxhighlight>
 
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
DIMENSION TAB(101)
 
THROUGH ZERO, FOR N = 1, 1, N.G.100
ZERO TAB(N) = 0
TAB(0) = 1
 
THROUGH STEP, FOR VALUES OF COIN = 1, 5, 10, 25
THROUGH STEP, FOR N = COIN, 1, N.G.100
STEP TAB(N) = TAB(N) + TAB(N - COIN)
 
VECTOR VALUES FMT = $I3*$
PRINT FORMAT FMT, TAB(100)
END OF PROGRAM</syntaxhighlight>
{{out}}
<pre>242</pre>
 
=={{header|Maple}}==
Line 3,112 ⟶ 3,268:
 
242 ways to make a dollar
</pre>
 
=={{header|RPL}}==
'''Dynamic programming (space optimized)'''
 
Source: [https://www.geeksforgeeks.org/coin-change-dp-7/ GeeksforGeeks website]
« → coins sum
« sum 1 + 1 →LIST 0 CON <span style="color:grey">@ dp[ii] will be storing the # of solutions for ii-1</span>
1 1 PUT <span style="color:grey">@ base case</span>
1 coins SIZE '''FOR''' ii
coins ii GET SWAP
'''IF''' OVER sum ≤ '''THEN'''
<span style="color:grey">@ Pick all coins one by one and update dp[] values </span>
<span style="color:grey">@ after the index greater than or equal to the value of the picked coin </span>
OVER 1 + sum 1 + '''FOR''' j
DUP j GET
OVER j 5 PICK - GET +
j SWAP PUT
'''NEXT'''
'''END''' SWAP DROP
'''NEXT'''
DUP SIZE GET
» » '<span style="color:blue">COUNT</span>' STO
 
{ 1 5 10 25 } 100 <span style="color:blue">COUNT</span>
{{out}}
<pre>
1: 242
</pre>
 
Line 3,396 ⟶ 3,580:
99341140660285639188927260001
</pre>
 
=={{header|SETL}}==
<syntaxhighlight lang="setl">program count_the_coins;
print(count([1, 5, 10, 25], 100));
print(count([1, 5, 10, 25, 50, 100], 1000 * 100));
 
proc count(coins, n);
tab := {[0, 1]};
loop for coin in coins do
loop for i in [coin..n] do
tab(i) +:= tab(i - coin) ? 0;
end loop;
end loop;
return tab(n);
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>242
13398445413854501</pre>
 
=={{header|Sidef}}==
Line 3,732 ⟶ 3,935:
13398445413854501</pre>
 
=={{header|V (Vlang)}}==
{{trans|goGo}}
<syntaxhighlight lang="go">fn main() {
fn main() {
amount := 100
println("amount,: $amount; ways to make change: $amount ${count_change(amount)}"))
}
fn count_change(amount int) i64 {
if amount.str().count('0') > 4 {exit(-1)} // can be too slow
return cc(amount, 4)
}
fn cc(amount int, kinds_of_coins int) i64 {
if amount == 0 {return 1}
else if amount < 0 || kinds_of_coins == 0 {return 10}
} else if amount < 0 || kinds_of_coins == 0 {
return 0
}
return cc(amount, kinds_of_coins-1) +
cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)
Line 3,755 ⟶ 3,957:
fn first_denomination(kinds_of_coins int) int {
match kinds_of_coins {
1 {return 1}
2 {return 15}
3 {return 10}
}
24 {return 25}
else {exit(-2)}
return 5
}
3 {
return 10
}
4 {
return 25
}
}
return kinds_of_coins
}</syntaxhighlight>
}
</syntaxhighlight>
Output:
<pre>
amount, ways to make change: 100 242
</pre>
Alternate:
<syntaxhighlight lang="go">
fn main() {
amount := 100
coins := [25, 10, 5, 1]
println("amount: $amount; ways to make change: ${count(coins, amount)}")
}
 
fn count(coins []int, amount int) int {
mut ways := []int{len: amount + 1}
ways[0] = 1
for coin in coins {
for idx := coin; idx <= amount; idx++ {
ways[idx] += ways[idx - coin]
}
}
return ways[amount]
}
</syntaxhighlight>
Output:
<pre>
amount: 100; ways to make change: 242
</pre>
 
Line 3,778 ⟶ 3,998:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt
import "./fmt" for Fmt
 
var countCoins = Fn.new { |c, m, n|
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327291...362013"