Count the coins: Difference between revisions

{{task}}

 

 

 

 

 

=={{header|Ada}}==

{{Works with|gnat/gcc}}

 

 

procedure Count_The_Coins is

Print(Count( 1_00, (25, 10, 5, 1)));

Print(Count(1000_00, (100, 50, 25, 10, 5, 1)));

 

Output:<pre> 242

13398445413854501</pre>

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.4.1}}

{{trans|Haskell}}

#

Rosetta Code "Count the coins"

LWB > UPB <=> []

print((ways to make change(denoms, 100), newline))

END

Output:<pre>

+242

</pre>

 

=={{header|AutoHotkey}}==

{{trans|Go}}

{{Works with|AutoHotkey_L}}

return cc(amount, 4)

}

return [1, 5, 10, 25][kindsOfCoins]

}

 

=={{header|AWK}}==

Iterative implementation, derived from Run BASIC:

 

 

BEGIN {

return count;

}

 

Run time:

Recursive implementation (derived from Scheme example):

 

 

BEGIN {

return koins[1]

}

 

Run time:

=={{header|BBC BASIC}}==

Non-recursive solution:

uscoins%() = 1, 5, 10, 25

PRINT FNchange(100, uscoins%()) " ways of making $1"

NEXT

= table(P%-1)

Output (BBC BASIC does not have large enough integers for the optional task):

<pre> 242 ways of making $1

=={{header|C}}==

Using some crude 128-bit integer type.

#include <stdlib.h>

#include <stdint.h>

 

return 0;

13398445413854501

1333983445341383545001

10056050940818192726001

99341140660285639188927260001

 

=={{header|Clojure}}==

 

(defn- cc [amount denominations]

(cc amount denominations))

 

 

=={{header|Coco}}==

{{trans|Python}}

 

ways = [1].concat [0] * amount

for coin of coins

ways[amount]

 

 

 

; (compile 'count-change) ; for CLISP

(print (count-change 100 '(25 10 5 1))) ; = 242

(print (count-change 100000 '(100 50 25 10 5 1))) ; = 13398445413854501

 

=={{header|D}}==

===Basic Version===

{{trans|Go}}

 

auto changes(int amount, int[] coins) {

changes( 1_00, [25, 10, 5, 1]).writeln;

changes(1000_00, [100, 50, 25, 10, 5, 1]).writeln;

{{out}}

<pre>242

===Safe Ulong Version===

This version is very similar to the precedent, but it uses a faster ulong type, and performs a checked sum to detect overflows at run-time.

 

auto changes(int amount, int[] coins, ref bool overflow) {

if (overflow)

"Overflow".puts;

The output is the same.

 

===Faster Version===

{{trans|C}}

 

BigInt countChanges(in int amount, in int[] coins) pure /*nothrow*/ {

writeln;

}

{{out}}

<pre>242

A much faster version that mixes high-level and low-level style programming. This version uses basic 128-bit unsigned integers, like the C version. The output is the same as the second D version.

{{trans|C}}

 

struct Ucent { /// Simplified 128-bit integer (like ucent).

static immutable one = Ucent(0, 1);

 

this.hi += y.hi;

if (this.lo >= ~y.lo)

}

 

return text((this.hi.BigInt << 64) + this.lo);

}

writeln;

}

 

===Printing Version===

This version prints all the solutions (so it can be used on the smaller input):

 

void printChange(in uint tot, in uint[] coins)

void main() {

printChange(1_00, [1, 5, 10, 25]);

{{out}}

<pre>1:5 5:1 10:4 25:2

10:10

25:4

</pre>

 

=={{header|Erlang}}==

-module(coins).

-compile(export_all).

A2 = 100000, C2 = [100, 50, 25, 10, 5, 1],

print(A2,C2).

 

{{out}}

13398445413854501 ways to make change for 100000 cents with [100,50,25,10,5,1] coins

ok

 

=={{header|Factor}}==

IN: rosetta.coins

 

: make-change ( cents coins -- ways )

members [ ] inv-sort-with ! Sort coins in descending order.

 

From the listener:

 

This algorithm is '''slow'''. A test machine needed '''1 minute''' to run ''100000 { 100 50 25 10 5 1 } make-change .'' and get 13398445413854501. The same machine needed less than 1 second to run the Common Lisp ([[SBCL]]), Ruby ([[MRI]]) or Tcl ([[tclsh]]) programs and get the same answer.

 

=={{header|Forth}}==

 

: table create does> swap cells + @ ;

then then ;

 

 

=={{header|Go}}==

 

import "fmt"

}

panic(kindsOfCoins)

Output:

<pre>

</pre>

Alternative algorithm, practical for the optional task.

 

import "fmt"

}

return ways[amount]

Output:

<pre>

amount, ways to make change: 100000 13398445413854501

</pre>

=={{header|Groovy}}==

{{trans|Go}}

Intuitive Recursive Solution:

ccR = { BigInteger tot, List<BigInteger> coins ->

BigInteger n = coins.size()

ccR(tot - coins[0], coins)

}

 

Fast Iterative Solution:

List<BigInteger> ways = [0g] * (tot+1)

ways[0] = 1g

}

ways[tot]

 

Test:

[iterative: ccI, recursive: ccR].each { label, cc ->

print "${label} "

def ways = ccI(1000g * 100, [100g, 50g, 25g, 10g, 5g, 1g])

def elapsed = System.currentTimeMillis() - start

 

Output:

=={{header|Haskell}}==

Naive implementation:

count _ [] = 0

 

 

Much faster, probably harder to read, is to update results from bottom up:

main = do

 

=={{header|Icon}} and {{header|Unicon}}==

 

US_coins := [1, 5, 10, 25]

every (s := "[ ") ||:= !L || " "

return s || "]"

 

This is a naive implementation and very slow.

{{improve|Icon|Needs a better algorithm.}}

local count

static S

return (amt ~= 0) | 1

}

 

{{libheader|Icon Programming Library}}

There are 242 ways to count change for 100 using [ 1 5 10 25 ] coins.

^c</pre>

 

=={{header|J}}==

In this draft intermediate results are a two column array. The first column is tallies -- the number of ways we have for reaching the total represented in the second column, which is unallocated value (which we will assume are pennies). We will have one row for each different in-range value which can be represented using only nickles (0, 5, 10, ... 95, 100).

 

count=: {.@] <@,. {:@] - [ * [ i.@>:@<.@%~ {:@]

init=: (1 ,. ,.)^:(0=#@$)

 

This implementation special cases the handling of pennies and assumes that the lowest coin value in the argument is 1. If I needed additional performance, I would next special case the handling of nickles/penny combinations...

Thus:

 

 

And, on a 64 bit machine with sufficient memory:

 

 

=={{header|Java}}==

{{trans|D}}

{{works with|Java|1.5+}}

import java.math.BigInteger;

 

}

}

Output:

<pre>242

Efficient iterative algorithm (cleverly calculates number of combinations without permuting them)

 

 

 

 

 

 

{{out}}

JavaScript hits integer limit for optional task

 

===Recursive===

Inefficient recursive algorithm (naively calculates number of combinations by actually permuting them)

 

 

 

 

 

Too slow for optional task

 

=={{header|jq}}==

Currently jq uses IEEE 754 64-bit numbers. Large integers are approximated by floats, and therefore the answer that the following program provides for the optional task is only correct for the first 15 digits.

# denominations as input.

# The strategy is to record at total[n] the number of ways to make n cents.

end

end ) )

'''Example''':

{{Out}}

242

 

=={{header|Lasso}}==

Inspired by the javascript iterative example for the same task

target::integer,

operands::array

cointcoins(100, array(1,5,10,25,))

'<br />'

Output:

<pre>242

13398445413854501</pre>

 

{{trans|Go}}

Do[For[j = coin, j <= amount, j++,

If[ j - coin == 0,

]]

, {coin, coinlist}];

Example usage:

<pre>CountCoins[100, {25, 10, 5}]

CountCoins[100000, {100, 50, 25, 10, 5}]

-> 13398445413854501</pre>

 

=={{header|Mercury}}==

:- interface.

:- import_module int, io.

show([P|T], !IO) :-

io.write(P, !IO), io.nl(!IO),

 

{{trans|Python}}

var ways = @[1]

ways.setLen(amount+1)

 

echo changes(100, [1, 5, 10, 25])

Output:

<pre>242

Translation of the D minimal version:

 

let ways = Array.make (amount + 1) 0L in

ways.(0) <- 1L;

Printf.printf "%Ld\n" (changes 1_00 [25; 10; 5; 1]);

Printf.printf "%Ld\n" (changes 1000_00 [100; 50; 25; 10; 5; 1]);

 

Output:

 

=={{header|PARI/GP}}==

ways(v,n)=polcoeff(coins(v)+O('x^(n+1)),n);

ways([1,5,10,25],100)

Output:

<pre>%1 = 242

%2 = 13398445413854501</pre>

=={{header|Perl}}==

use Memoize;

 

say 'Ways to change $ 1000 with addition of less common coins: ',

cc_optimized( 1000 * 100, 1, 5, 10, 25, 50, 100 );

{{out}}

Ways to change $ 1 with common coins: 242

Ways to change $ 1000 with addition of less common coins: 13398445413854501

 

 

 

 

 

 

=={{header|PicoLisp}}==

{{trans|C}}

(let (Buf (mapcar '((N) (cons 1 (need (dec N) 0))) Coins) Prev)

(do Sum

(inc (rot L) Prev)

(setq Prev (car L)) ) )

Test:

(println (coins 100 (cddr Coins)))

(println (coins (* 1000 100) Coins))

(println (coins (* 10000 100) Coins))

(println (coins (* 100000 100) Coins))

Output:

<pre>242

99341140660285639188927260001

992198221207406412424859964272600001</pre>

 

=={{header|Python}}==

===Simple version===

{{trans|Go}}

ways = [0] * (amount + 1)

ways[0] = 1

 

print changes(100, [1, 5, 10, 25])

Output:

<pre>242

===Fast version===

{{trans|C}}

import psyco

psyco.full()

print count_changes(10000000, coins), "\n"

 

Output:

<pre>242

99341140660285639188927260001

992198221207406412424859964272600001</pre>

 

=={{header|Racket}}==

This is the basic recursive way:

(define (ways-to-make-change cents coins)

(cond ((null? coins) 0)

 

(ways-to-make-change 100 '(25 10 5 1)) ; -> 242

This works for the small numbers, but the optional task is just too slow with this solution, so with little change to the code we can use memoization:

(define memos (make-hash))

 

cpu time: 20223 real time: 20673 gc time: 10233

 

=={{header|REXX}}==

 

 

<pre>

ways to make change with coins of the following denominations: 1 5 10 25

</pre>

 

'''Recursive, with caching'''

 

@cache = Array.new(amount+1){|i| Array.new(coins.size, i.zero? ? 1 : nil)}

@coins = coins

 

p make_change( 1_00, [1,5,10,25])

 

outputs

'''Iterative'''

 

n, m = amount, coins.size

table = Array.new(n+1){|i| Array.new(m, i.zero? ? 1 : nil)}

 

p make_change2( 1_00, [1,5,10,25])

outputs

<pre>242

13398445413854501</pre>

 

=={{header|Run BASIC}}==

for nickel = 0 to 20

for dime = 0 to 10

next nickel

next penny

<pre>0 pennies 0 nickels 0 dimes 4 quarters

0 pennies 0 nickels 5 dimes 2 quarters

.....

242 ways to make a buck</pre>

 

=={{header|Scala}}==

val ways = Array.fill(amount + 1)(0)

ways(0) = 1

 

countChange (15, List(1, 5, 10, 25))

Output:

<pre>res0: Int = 6

</pre>

 

=={{header|Scheme}}==

A simple recursive implementation:

(lambda (x coins)

(cond

[else (+ (ways-to-make-change x (cdr coins)) (ways-to-make-change (- x (car coins)) coins))])))

 

Output:

<pre>242</pre>

 

=={{header|Seed7}}==

include "bigint.s7i";

writeln(changeCount( 100000, euCoins));

writeln(changeCount(1000000, euCoins));

 

Output:

10056050940818192726001

99341140660285639188927260001

</pre>

 

=={{header|Tcl}}==

{{trans|Ruby}}

 

proc makeChange {amount coins} {

# Making change with the EU coin set:

puts [makeChange 100 {1 2 5 10 20 50 100 200}]

Output:

<pre>

4563

10056050940818192726001

</pre>

 

=={{header|zkl}}==

{{trans|Scheme}}

if(not coins) return(0);

if(x<0) return(0);

ways_to_make_change(x, coins[1,*]) + ways_to_make_change(x - coins[0], coins)

}

{{out}}

<pre>242</pre>

 

{{trans|Ruby}}

n, m := amount, coins.len();

table := (0).pump(n+1,List, (0).pump(m,List().write,1).copy);

 

println(make_change2( 100, T(1,5,10,25)));

{{out}}

<pre>

13,398,445,413,854,501

</pre>