Count the coins: Difference between revisions

=={{header|11l}}==

{{trans|Python}}

V ways = [Int64(0)] * (amount + 1)

ways[0] = 1

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

Output:

=={{header|360 Assembly}}==

{{trans|AWK}}

COINS CSECT

USING COINS,R12

PG DS CL12

YREGS

{{out}}

<pre>

{{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

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

{{trans|Haskell}}

#

Rosetta Code "Count the coins"

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

END

Output:<pre>

+242

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

{{trans|Haskell}}

#

Rosetta Code "Count the coins"

print((ways to make change((1, 5, 10, 25, 50, 100), 100000), newline))

END

Output:<pre>

+242

{{trans|Phix}}

on countCoins(amount, denominations)

-- Potentially long list of counters, initialised with 1 (result for amount 0) and 'amount' zeros.

set c1 to countCoins(100, {25, 10, 5, 1})

set c2 to countCoins(1000 * 100, {100, 50, 25, 10, 5, 1})

{{output}}

=={{header|Applesoft BASIC}}==

{{trans|Commodore BASIC}}

=={{header|Arturo}}==

ways: map 0..amount+1 [x]-> 0

ways\0: 1

print changes 100 [1 5 10 25]

=={{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|C sharp|C#}}==

// Adapted from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

class Program

}

}

=={{header|C++}}==

#include <iostream>

#include <stack>

std::cout << ways << std::endl;

return 0;

{{out}}

=={{header|Clojure}}==

(defn- cc [amount denominations]

(cc amount denominations))

=={{header|COBOL}}==

{{trans|C#}}

identification division.

program-id. CountCoins.

end-perform

.

{{out}}

<pre>242</pre>

{{trans|Python}}

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

for coin of coins

ways[amount]

=={{header|Commodore BASIC}}==

10 print chr$(147);chr$(14);"This program will calculate the number"

11 print "of combinations of 'change' that can be"

265 print left$(en$,2);":";mid$(en$,3,2);":";right$(en$,2);"."

270 end

'''Example 2:''' Commodore 64 with Screen Blanking

Enabling screen blanking (and therefore not printing each result) results in a total time of 1:44.

'''Example 3:''' Commodore 128 with VIC-II blanking, 2MHz fast mode.

Similar to above, however the Commodore 128 is capable of using a faster clock speed at the expense of any VIC-II graphics display. Timed result is 1:18. Add/change the following lines on the Commodore 128:

=={{header|Common Lisp}}==

===Recursive Version With Cache===

&optional

(length (1- (length coins)))

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

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

===Iterative Version===

(setf (aref ways 0) 1)

(loop for coin in coins do

(loop for j from coin upto amount

do (incf (aref ways j) (aref ways (- j coin)))))

=={{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).

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

=={{header|Dart}}==

Simple recursive version plus cached version using a map.

var cache = new Map();

return(count);

}

{{out}}

<pre>

=={{header|Delphi}}==

{{Trans|C#}}

program Count_the_coins;

Readln;

end.

=={{header|Dyalect}}==

var xs = Array.Empty(n + 1, 0)

xs[0] = 1

var coins = [1, 5, 10, 25]

{{out}}

=={{header|EchoLisp}}==

Recursive solution using memoization, adapted from CommonLisp and Racket.

(lib 'compile) ;; for (compile)

(lib 'bigint) ;; integer results > 32 bits

(compile 'ways) ;; speed-up things

{{out}}

(define change '(25 10 5 1))

(define c-1 (list-tail change -1)) ;; pointer to (1)

→ 13398445413854501

=={{header|EDSAC order code}}==

Note: When the table is initialized, not only must the first entry be set to 1, but the other entries must be set to 0. It seems that the C# and Delphi solutions rely on the compiler to do this. In other languages, it may need to be done by the program.

["Count the coins" problem for Rosetta Code.]

[EDSAC program, Initial Orders 2.]

E21Z [define entry point]

PF [enter with acc = 0]

{{out}}

<pre>

=={{header|Elixir}}==

Recursive Dynamic Programming solution in Elixir

def find(coins,lim) do

vals = Map.new(0..lim,&{&1,0}) |> Map.put(0,1)

Coins.find([1,5,10,25],100)

{{out}}

=={{header|Erlang}}==

-module(coins).

-compile(export_all).

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

print(A2,C2).

{{out}}

{{trans|OCaml}}

<p>Forward iteration, which can also be seen in Scala.</p>

let ways = Array.zeroCreate (amount + 1)

ways.[0] <- 1L

printfn "%d" (changes 100 [25; 10; 5; 1]);

printfn "%d" (changes 100000 [100; 50; 25; 10; 5; 1]);

{{out}}

<pre>242

=={{header|Factor}}==

IN: rosetta.coins

: make-change ( cents coins -- ways )

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

From the listener:

One might make use of the rosetta-code.count-the-coins vocabulary as shown:

IN: scratchpad [ 100000 { 1 5 10 25 50 100 } make-change . ] time

13398445413854501

Running time: 0.020869274 seconds

For reference, the implementation is shown next.

USING: arrays locals math math.ranges sequences sets sorting ;

IN: rosetta-code.count-the-coins

: make-change ( cents coins -- ways )

members [ ] inv-sort-with (make-change) ;

Or one could implement the algorithm like described in http://www.cdn.geeksforgeeks.org/dynamic-programming-set-7-coin-change.

USE: math.ranges

13398445413854501

Running time: 0.029163549 seconds

=={{header|Forth}}==

: table create does> swap cells + @ ;

then then ;

=={{header|FreeBASIC}}==

Translation from "Dynamic Programming Solution: Python version" on this webside [http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/]

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>

=={{header|FutureBasic}}==

void local fn Doit

fn DoIt

Output:

=={{header|Go}}==

{{trans|lisp}}

import "fmt"

}

panic(kindsOfCoins)

Output:

<pre>

</pre>

Alternative algorithm, practical for the optional task.

import "fmt"

}

return ways[amount]

Output:

<pre>

{{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 _ = 1

count _ [] = 0

main :: IO ()

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

count = foldr addCoin (1 : repeat 0)

where

main = do

print (count [25, 10, 5, 1] !! 100)

Or equivalently, (reformulating slightly, and adding a further test):

count

, ([100, 50, 25, 10, 5, 1], 1000000)

]

{{Out}}

<pre>242

=={{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}}

Another one:

# coin.icn

# usage: coin value

write(" coins in ", count(coins, money), " different ways.")

end

Output:

<pre>

=={{header|IS-BASIC}}==

110 LET MONEY=100

120 LET COUNT=0

270 NEXT

280 NEXT

=={{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:

Warning: the above version can miss one when the largest coin is equal to the total value.

For British viewers change from £10 using £10 £5 £2 £1 50p 20p 10p 5p 2p and 1p

length1 =: 4 : '1=#y'

f =: 4 : ',/ +/\ (-x) ]\ y'

NB. this is a foldLeft once initialised the intermediate right arguments are arrays

=={{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)

'use strict';

var targetsLength = t + 1;

return t[targetsLength - 1];

{{out}}

JavaScript hits integer limit for optional task

===Recursive===

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

'use strict';

var operandsLength = o.length;

permutate(0, 0);

return solutions;

{{Out}}

Too slow for optional task

===Iterative again===

{{Trans|C#}}

coin = [1, 5, 10, 25]

var t = [1];

for (var ci = coin[i], a = ci; a <= amount; a++)

t[a] += t[a - ci]

{{Out}}

<pre>242</pre>

=={{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''':

[1,5,10,25] | countcoins(100)

=={{header|Julia}}==

{{trans|Python}}

ways = zeros(Int128, amount + 1)

ways[1] = 1

@show changes(100, [1, 5, 10, 25])

{{out}}

=={{header|Kotlin}}==

{{trans|C#}}

fun countCoins(c: IntArray, m: Int, n: Int): Long {

println(countCoins(c, 4, 100))

println(countCoins(c, 6, 1000 * 100))

{{out}}

=={{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

=={{header|Lua}}==

Lua uses one-based indexes but table keys can be any value so you can define an element 0 just as easily as you can define an element "foo"...

local t = {}

for i = 1, amount do t[i] = 0 end

print(countSums(100, {1, 5, 10, 25}))

{{out}}

<pre>242

===Fast O(n*m)===

Works with decimals in table()

Module FindCoins {

Function count(c(), n) {

}

FindCoins

{{out}}

<pre>

Using an inventory (a kind of vector) to save first search (but is slower than previous one)

Module CheckThisToo {

inventory c=" 0 0":=1@

}

CheckThisToo

=={{header|Maple}}==

Straightforward implementation with power series. Not very efficient for large amounts. Note that in the following, all amounts are in '''cents'''.

coin:=unapply(sum(x^(p*n),n=0..infinity),p):

ways:=(amount,purse)->coeff(series(mul(coin(k),k in purse),x,amount+1),x,amount):

ways(100000,[1,5,10,25,50,100]);

A faster implementation.

local a,n,k;

a:=Array(1..amount);

ways2(100000000,[1,5,10,25,50,100]);

Additionally, while it's not proved as is, we can see that the first values for an amount 10^k obey the following simple formula:

for k from 2 to 8 do lprint(P(10^k)) od:

1333983445341383545001

133339833445334138335450001

The polynomial P(n) seems to give the correct number of ways iff n is a multiple of 100 (tested up to n=10000000), i.e. the number of ways for 100n is

=={{header|Mathematica}} / {{header|Wolfram Language}}==

{{trans|Go}}

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

If[ j - coin == 0,

]]

, {coin, coinlist}];

Example usage:

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

=={{header|MATLAB}} / {{header|Octave}}==

%% Count_The_Coins

clear;close all;clc;

end % End for

toc

Example Output:

<pre>Main Challenge: 242

=={{header|Mercury}}==

:- interface.

:- import_module int, io.

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

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

=={{header|Nim}}==

{{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

=={{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

=={{header|Phix}}==

Very fast, from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change

<span style="color: #008080;">function</span> <span style="color: #000000;">coin_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">amount</span><span style="color: #0000FF;">)</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

An attempt to explain this algorithm further seems worthwhile:

<span style="color: #008080;">function</span> <span style="color: #000000;">coin_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">amount</span><span style="color: #0000FF;">)</span>

<span style="color: #000080;font-style:italic;">-- start with 1 known way to achieve 0 (being no coins)

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">1_00</span><span style="color: #0000FF;">))</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">1000_00</span><span style="color: #0000FF;">))</span>

{{out}}

<pre>

Using dynamic programming with tabling.

Problems = [[ 1*100, [25,10,5,1]], % 1 dollar

[ 100*100, [100,50,25,10,5,1]], % 100 dollars

end

end,

{{Output}}

=={{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

Basic version using brute force and constraint programming, the bonus version will work but takes a long time so skipped it.

% Basic, Q = Quarter, D = Dime, N = Nickel, P = Penny

coins_for(T) :-

coins(Q,D,N,P,T),

{{out}}

<pre>

===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

=={{header|Quackery}}==

[ swap dup 1+ lim put

say "With EU coins." cr

100 ' [ 1 2 5 10 20 50 100 200 ] makechange echo cr

{{out}}

=={{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|Raku}}==

{{trans|Ruby}}

sub change-r($amount, @coins) {

my @cache = [1 xx @coins], |([] xx $amount);

say "\nRecursive:";

say change-r 1_00, [1,5,10,25];

{{out}}

<pre>Iterative:

The amount can be specified in cents (as a number), or in dollars (as for instance, &nbsp; $1000).

numeric digits 20 /*be able to handle large amounts of $.*/

parse arg N $ /*obtain optional arguments from the CL*/

if a==$.k then return f+1 /*handle this special case of A=a coin.*/

if a <$.k then return f /* " " " " " A<a coin.*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

===with memoization===

This REXX version is more than a couple of orders of magnitude faster than the 1^st version when using larger amounts.

numeric digits 20 /*be able to handle large amounts of $.*/

parse arg N $ /*obtain optional arguments from the CL*/

if a==$.k then do; !.a.k= f+1; return !.a.k; end /*handle this special case.*/

if a <$.k then do; !.a.k= f ; return f ; end /* " " " " */

{{out|output|text=&nbsp; when using the following input for the optional test case: &nbsp; &nbsp; <tt> $1000 &nbsp; 1 &nbsp; 5 &nbsp; 10 &nbsp; 25 &nbsp; 50 &nbsp; 100 </tt>}}

<pre>

===with error checking===

This REXX version is identical to the previous REXX version, but has error checking for the amount and the coins specified.

numeric digits 20 /*be able to handle large amounts of $.*/

parse arg N $ /*obtain optional arguments from the CL*/

if a==$.k then do; !.a.k= f+1; return !.a.k; end /*handle this special case.*/

if a <$.k then do; !.a.k= f ; return f ; end /* " " " " */

{{out|output|text=&nbsp; is the same as the previous REXX version.}}<br><br>

=={{header|Ring}}==

penny = 1

nickel = 1

next

see count + " ways to make a dollar" + nl

Output:

<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

=={{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

=={{header|Rust}}==

let size = cents + 1;

let mut ways = vec![0; size];

println!("{}", make_change(&[1,5,10,25], 100));

println!("{}", make_change(&[1,5,10,25,50,100], 100_000));

{{output}}

<pre>242

=={{header|SAS}}==

Generate the solutions using CLP solver in SAS/OR:

proc optmodel;

/* declare set and names of coins */

/* print all solutions */

proc print data=sols;

Output:

=={{header|Scala}}==