The weekly challenge 285 - Task 2: Making Change

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-285/#TASK2
 3 #
 4 # Task 2: Making Change
 5 # =====================
 6 #
 7 # Compute the number of ways to make change for given amount in cents. By using
 8 # the coins e.g. Penny, Nickel, Dime, Quarter and Half-dollar, in how many
 9 # distinct ways can the total value equal to the given amount? Order of coin
10 # selection does not matter.
11 #
12 # A penny (P) is equal to 1 cent.
13 # A nickel (N) is equal to 5 cents.
14 # A dime (D) is equal to 10 cents.
15 # A quarter (Q) is equal to 25 cents.
16 # A half-dollar (HD) is equal to 50 cents.
17 #
18 ## Example 1
19 ##
20 ## Input: $amount = 9
21 ## Ouput: 2
22 ##
23 ## 1: 9P
24 ## 2: N + 4P
25 #
26 ## Example 2
27 ##
28 ## Input: $amount = 15
29 ## Ouput: 6
30 ##
31 ## 1: D + 5P
32 ## 2: D + N
33 ## 3: 3N
34 ## 4: 2N + 5P
35 ## 5: N + 10P
36 ## 6: 15P
37 #
38 ## Example 3
39 ##
40 ## Input: $amount = 100
41 ## Ouput: 292
42 #
43 ############################################################
44 ##
45 ## discussion
46 ##
47 ############################################################
48 #
49 # Let's use a recursive function. If we can still use the biggest
50 # available coin, calculate the amount of possible solutions with
51 # the amount reduced by this coin and add it to the result. In
52 # any case, calculate the result if the biggest available coin is
53 # the second available coin in order to find all solutions without the
54 # biggest coin. Summing those two numbers up yields the result.
55 # Of course, if the amount for which to calculate the combinations is
56 # 0, we have found a leaf in the tree of solutions, so we return 1.
57 
58 use strict;
59 use warnings;
60 
61 making_change(9);
62 making_change(15);
63 making_change(100);
64 
65 sub making_change {
66    my $amount = shift;
67    print "Input: $amount\n";
68    my @coins = (50, 25, 10, 5, 1);
69    my $result = calculate($amount, @coins);
70    print "Output: $result\n";
71 }
72 
73 sub calculate {
74    my ($amount, @coins) = @_;
75    my $result = 0;
76    return 1 if $amount <= 0;
77    return $result unless @coins;
78    if($amount >= $coins[0]) {
79       # print "$amount -> $coins[0]\n";
80       $result+=calculate($amount - $coins[0], @coins);
81    }
82    $result += calculate($amount, @coins[1..$#coins]);
83    return $result;
84 }
85