How to resolve the algorithm Count the coins step by step in the Picat programming language

Published on 12 May 2024 09:40 PM
#Picat

How to resolve the algorithm Count the coins step by step in the Picat programming language

Table of Contents

Problem Statement

There are four types of common coins in   US   currency:

There are six ways to make change for 15 cents:

How many ways are there to make change for a dollar using these common coins?     (1 dollar = 100 cents).

Less common are dollar coins (100 cents);   and very rare are half dollars (50 cents).   With the addition of these two coins, how many ways are there to make change for $1000? (Note:   the answer is larger than   232).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Count the coins step by step in the Picat programming language

Source code in the picat programming language

go =>
  Problems = [[      1*100, [25,10,5,1]],            % 1 dollar
              [    100*100, [100,50,25,10,5,1]],   % 100 dollars
              [  1_000*100, [100,50,25,10,5,1]],  % 1000 dollars
              [ 10_000*100, [100,50,25,10,5,1]], % 10000 dollars
              [100_000*100, [100,50,25,10,5,1]] % 100000 dollars
              ],
  foreach([N,L] in Problems)
     initialize_table, % clear the tabling from previous run
     println([n=N,l=L]),
     time(println(num_sols=coins(L,N,1)))
  end.

table
coins(Coins, Money, M) = Sum =>
    Sum1 = 0,
    Len = Coins.length,
    if M == Len then
      Sum1 := 1,
    else 
       foreach(I in M..Len)
         if Money - Coins[I] == 0 then
            Sum1 := Sum1 + 1
         end,
         if Money - Coins[I] > 0 then
            Sum1 := Sum1 + coins(Coins, Money-Coins[I], I)
         end,
       end
    end,
    Sum = Sum1.

You may also check:How to resolve the algorithm Closures/Value capture step by step in the Perl programming language
You may also check:How to resolve the algorithm Rot-13 step by step in the Pascal programming language
You may also check:How to resolve the algorithm Wagstaff primes step by step in the Python programming language
You may also check:How to resolve the algorithm Ethiopian multiplication step by step in the Forth programming language
You may also check:How to resolve the algorithm Disarium numbers step by step in the Forth programming language