06 September 2024

Challenge 285

Change With No Way Out

• Task 1: No Connection
• Task 2: Making Change

Task 1: No Connection

Submitted by: Mohammad Sajid Anwar

---

You are given a list of routes, @routes.

Write a script to find the destination with no further outgoing connection.

Example 1

Input: @routes = (["B","C"], ["D","B"], ["C","A"])
Output: "A"

"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".

Example 2

Input: @routes = (["A","Z"])
Output: "Z"

---

Solution

Lazy as I am, I build a graph from the given edges and find the sink vertices therein.

use strict;
use warnings;
use Graph::Directed;

sub no_connection {
    Graph::Directed->new(edges => \@_)->sink_vertices;
}

See the full solution to task 1.

Task 2: Making Change

Submitted by: David Ferrone

---

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

---

Solution

Using recursion to solve this task.

Here we’ll consider an amount and a maximum coin. The trivial cases are:

• the maximum coin is the smallest coin: we need to pick the number of coins that make up the amount
• the amount is zero: no smaller coins are selected

In all other cases:

• we pick from zero to the maximum possible number of coins having the maximum allowed value
• we reduce the amount by the selected coins’ value
• we find all possible combinations for the reduced amount using only smaller coins by recursion.

use strict;
use warnings;
use experimental 'signatures';

sub make_change ($amount, $coin = 4) {
    state $coins = [1, 5, 10, 25, 50];
    if ($coin == 0) {
        if ($amount % $coins->[0] == 0) {
            return [$amount / $coins->[0]];
        } else {
            return ();
        }
    }
    my @comb;
    for (my ($cnt, $val) = (0, 0);
        $val <= $amount;
        $cnt++, $val += $coins->[$coin]) {
        if ($val == $amount) {
            push @comb, [(0) x $coin, $cnt];
        } else {
            push @comb, [@$_, $cnt]
                for make_change($amount - $val, $coin - 1);
        }
    }

    @comb;
}

If we want to present the individual combinations as shown in the examples, we need to format the resulting arrays. The requested count is just the size of the result.

sub fmt {
    state $name = [qw(P N D Q HD)];
    my @coins;
    for (my $i = $#_; $i >= 0; $i--) {
        my $c = $_[$i];
        push @coins, $c x ($c != 1) . $name->[$i] if $c;
    }

    join ' + ', @coins;
}

See the full solution to task 2.

---

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.