Lost Connections and Making Changes

zapwai

Zapwai

Posted on September 2, 2024

Lost Connections and Making Changes

Weekly Challenge 285

Challenge 285 - My Solutions

  1. Task One: No Connection
    Given a list of routes, find the destination with no outgoing connection.
    For example, given [B, C] [D, B] [C, A] we have routes
    B -> C -> A
    D -> B -> C -> A
    C -> A
    Output: A

  2. Task Two: Making Change
    Compute the number of distinct ways to make change for a given amount. (Using Pennies, Nickels, Dimes, Quarters, and Half-Dollars.)
    There are two ways to make change for 9 cents (N + 4P or 9P).
    There are three ways to make change for 10 cents (2N, N + 5P, or 10P).

Solution to task one
I make two lists, in-routes and out-routes, and then I see if there is an out that is not also an in.

use v5.38;
my @routes = (["B","C"], ["D","B"], ["C","A"]);
proc(@routes);
@routes = (["A","Z"]);
proc(@routes);

sub proc(@routes) {
    print "Input: ";
    print join(",", @{$routes[$_]})," " for (0 .. $#routes);
    print "\n";
    my @in;
    my @out;
    foreach (@routes) {
    push @in, ${$_}[0];
    push @out, ${$_}[1];
    }
    my $ans = "a";
    for my $needle (@out) {
    my $found = 0;
    for my $hay (@in) {
        if ($needle eq $hay) {
        $found = 1;
        last;
        }
    }
    if ($found == 0) {
        $ans = $needle;
    }
    }
    say "Output: $ans";
}
Enter fullscreen mode Exit fullscreen mode

Solution to task two
This challenge was inspired by an analysis book of Pólya. (Problems and Theorems in Analysis) The first question is to count the number of ways to make change for a dollar, which is arduous. It's a trivial task for a computer, though.

use v5.38;
my $amt = $ARGV[0] // 100;
my $cnt = 0;
for my $h (0 .. $amt/50) {
    for my $q (0 .. $amt/25) {
    for my $d (0 .. $amt/10) {
        for my $n (0 .. $amt/5) {
        for my $p (0 .. $amt) {
            if (tally($p, $n, $d, $q, $h) == $amt) {
            $cnt++;
            }
        }
        }
    }
    }
}
say "There are $cnt ways to make change for $amt cents";
sub tally($p, $n, $d, $q, $h) { $p + 5*$n + 10*$d + 25*$q + 50*$h
Enter fullscreen mode Exit fullscreen mode

I have used a for loop for each coin, in a stunning display of brute force.

P.S.
The original question was to be done by hand; In a manner similar to the above code, you could first divide to find the max possible number of pennies, nickels, etc that can be used. Then split into cases (i.e. H = 0, 1, or 2; Q = 0, 1, 2, 3, or 4; etc.)

The second question in Pólya's book asks for a function whose coefficients A_n (in a series expansion) would equal the number of ways to make change for n cents.

The concept there is that if you took a product like (1 + x + x^2 + x^3 + ... )(1 + x^5 + x^10 + x^15 + ...) the resulting series has coefficients which provide the number of ways to "make change" using pennies and nickels. (That is, a term like x^6 in our product could only have come from x * x^5 or from x^6 * 1, coinciding with the two unique ways we can make change for 6 cents.)

So theoretically, one could form the correct product (using five such factors, since there are five coins) - then expand and find the coefficient of the 100th term in order to find the number of ways to make change for 100 cents. That's easier said than done, however.

💖 💪 🙅 🚩
zapwai
Zapwai

Posted on September 2, 2024

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Introduction to Messaging Systems with Kafka
distributedsystems Introduction to Messaging Systems with Kafka

November 28, 2024

Cacti Kurulumu
cacti Cacti Kurulumu

November 27, 2024

Perl Weekly #696 - Perl 5 is Perl
perl Perl Weekly #696 - Perl 5 is Perl

November 25, 2024