laurent_r

These are some answers to the Week 285, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on September 8, 2024, at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 2: Making Change

Compute the number of ways to make change for given amount in cents. By using the coins e.g. Penny, Nickel, Dime, Quarter and Half-dollar, in how many distinct ways can the total value equal to the given amount? Order of coin selection does not matter.

A penny (P) is equal to 1 cent.
A nickel (N) is equal to 5 cents.
A dime (D) is equal to 10 cents.
A quarter (Q) is equal to 25 cents.
A half-dollar (HD) is equal to 50 cents.

Example 1

Input: $amount = 9
Ouput: 2

1: 9P
2: N + 4P

Example 2

Input: $amount = 15
Ouput: 6

1: D + 5P
2: D + N
3: 3N
4: 2N + 5P
5: N + 10P
6: 15P

Example 3

Input: $amount = 100
Ouput: 292

Making Change in Raku

I first thought of populating a hash which, for each coin value, would provide the number of ways such value could be made of smaller change. But this turned out to be too complicated by hand. So, I thought we could use a recursive subroutine to build that hash, but, at this point, we can use a similar recursive subroutine to compute directly the number of ways to construct the input amount.

Here, make-change is the recursive subroutine. It loops on the coin values (in descending order) and subtract the value from the input amount. If the amount left ($rest) is equal to zero, then we've found a new combination of coins and increment the count. Otherwise, we call recursively the make-change subroutine with the value of $rest.

The initial program did not work as expected because it found duplicate combinations (in different orders). For example, for in input value of 11, it might find the following combinations:

1 10
1 5 5
5 1 5
5 5 1
etc.

To prevent this, a second parameter, $limit, was added to the make-change subroutine by which we forbid the program to use coins with a value larger than the current one.

my @coins = 50, 25, 10, 5, 1;
my $count;

sub make-change ($amount, $limit) {
    for @coins -> $coin {
        next if $coin > $amount;
        # Prevent duplicate combinations in different orders
        next if $coin > $limit;
        my $rest = $amount - $coin;
        if $rest == 0 {
            $count++;
        } else {
            make-change($rest, $coin);
        }
    }
    return $count;
}

my @tests = 9, 15, 100;
for @tests -> $test {
    $count = 0;
    printf "%-5d => ", $test;
    say make-change $test, 50;
}

This program displays the following output:

$ raku ./make-change.raku
9     => 2
15    => 6
100   => 292

Note that I initially had some concerns about performance with all these recursive calls, but it turned out that the program ran quite fast:

$ time raku ./make-change.raku
9     => 2
15    => 6
100   => 292

real    0m0.830s
user    0m0.000s
sys     0m0.015s

Making Change in Perl

This is a port to Perl of the above Raku program. Please refer to the above section if you need explanations.

Note that I had to add the following pragma:

no warnings 'recursion';

to disable a warning about deep recursion, presumably when computing the combinations of pennies with an input value of 100. BTW, with today's computer hardware, the built-in recursion depth limit could be raised to a significantly higher level.

use strict;
use warnings;
no warnings 'recursion';
use feature 'say';

my @coins = (50, 25, 10, 5, 1);
my $count;

sub make_change  {
    my ($amount, $limit) = @_;
    for my $coin (@coins)  {
        next if $coin > $amount;
        # Prevent duplicate combinations in different orders
        next if $coin > $limit;
        my $rest = $amount - $coin;
        if ($rest == 0) {
            $count++;
        } else {
            make_change($rest, $coin);
        }
    }
    return $count;
}

my @tests = (9, 15, 50, 100);
for my $test (@tests) {
    $count = 0;
    printf "%-5d => ", $test;
    say make_change $test, 50;
}

This program displays the following output:

$ perl ./make-change.pl
9     => 2
15    => 6
100   => 292

I also benchmarked this Perl implementation, and it shows that, at least for such highly recursive programs, Perl is still much faster than Raku:

$ time perl ./make-change.pl
9     => 2
15    => 6
100   => 292

real    0m0.035s
user    0m0.000s
sys     0m0.030s

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on September 15, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.