This is my response to The Weekly Challenge #285.
@routes.
Input: @routes = (["B","C"], ["D","B"], ["C","A"])
Output: "A"
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
Input: @routes = (["A","Z"])
Output: "Z"
The challenge describes a directed graph, without naming it as such. See e.g. my Seven Bridges to Raku article for a massive dose of graph stuff in Raku.
File: no-connection
#! /usr/bin/env raku
unit sub MAIN (*@routes where @routes.elems > 0, :v(:$verbose)); # [1]
my %outgoing; # [2]
for @routes -> $route # [3]
{
my ($from, $to) = $route.split(/\s+/); # [4]
say ": Route from '$from' to '$to'" if $verbose;
%outgoing{$from}++; # [5]
%outgoing{$to} = 0 unless defined %outgoing{$to}; # [6]
}
if $verbose
{
for sort keys %outgoing -> $key
{
say ": '$key' has %outgoing{$key} outgoing connectiuon(s)" if $verbose;
}
}
say %outgoing.grep( *.value == 0 )>>.key.join(", "); # [7]
[1] The routes as strings, and at least one of them.
[2] This will tell us if any given node has an outgoing connection.
[3] Iterate over the routes.
[4] Split on space(s), giving the from and to nodes.
[5] Register that the from node has an outgoing connection.
[6] Register that the to node does not have any outgoing connection, if it is missing in the outgoing hash.
[7] Use grep to extract nodes without outgoing
connections (a value of zero), then use >>.keys to get the keys
(node names), and finally join to pretty print the result if we
get more than one answer.
See docs.raku.org/routine/grep for more information about grep.
Running it:
$ ./no-connection "B C" "D B" "C A"
A
$ ./no-connection "A Z"
Z
Looking good.
With verbose mode:
$ ./no-connection -v "B C" "D B" "C A"
: Route from 'B' to 'C'
: Route from 'D' to 'B'
: Route from 'C' to 'A'
: 'A' has 0 outgoing connectiuon(s)
: 'B' has 1 outgoing connectiuon(s)
: 'C' has 1 outgoing connectiuon(s)
: 'D' has 1 outgoing connectiuon(s)
A
$ ./no-connection -v "A Z"
: Route from 'A' to 'Z'
: 'A' has 1 outgoing connectiuon(s)
: 'Z' has 0 outgoing connectiuon(s)
Z
Circular graphs are not a problem, as we do not actually traverse them:
$ ./no-connection -v "A Z" "X X"
: Route from 'A' to 'Z'
: Route from 'X' to 'X'
: 'A' has 1 outgoing connectiuon(s)
: 'X' has 1 outgoing connectiuon(s)
: 'Z' has 0 outgoing connectiuon(s)
Z
$ ./no-connection -v "A Z" "Z A"
: Route from 'A' to 'Z'
: Route from 'Z' to 'A'
: 'A' has 1 outgoing connectiuon(s)
: 'Z' has 1 outgoing connectiuon(s)
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.
Input: $amount = 9
Ouput: 2
1: 9P
2: N + 4P
Input: $amount = 15
Ouput: 6
1: D + 5P
2: D + N
3: 3N
4: 2N + 5P
5: N + 10P
6: 15P
Input: $amount = 100
Ouput: 292
#! /usr/bin/env raku
unit sub MAIN (UInt $amount, :v(:$verbose)); # [1]
my %value; # [2]
%value<penny> = 1; # [2p]
%value<nickel> = 5; # [2n]
%value<dime> = 10; # [2d]
%value<quarter> = 25; # [2q]
%value<half-dollar> = 50; # [2h]
my $ok = 0; # [3]
for 0 .. $amount -> $penny # [4p]
{
for 0 .. $amount div %value<nickel -> $nickel # [4n]
{
for 0 .. $amount div %value<dime> -> $dime # [4d]
{
for 0 .. $amount div %value<quarter> -> $quarter # [4q]
{
for 0 .. $amount div %value<half-dollar -> $half-dollar # [4h]
{
if $amount == # [5]
$penny +
$nickel * %value<nickel> +
$dime * %value<dime> +
$quarter * %value<quarter> +
$half-dollar * %value<half-dollar>
{
$ok++; # [5a]
say ": " ~
(
prettyish($penny, 'P'),
prettyish($nickel, 'N'),
prettyish($dime, 'D'),
prettyish($quarter, 'Q'),
prettyish($half-dollar, 'HD')
).grep( *.defined ).join(" + ") if $verbose;
}
}
}
}
}
}
sub prettyish ($value, $letter)
{
return unless $value;
return $letter if $value == 1;
return "$value$letter";
}
say $ok; # [6]
[1] The amount, as an unsigned integer. Zero is ok.
[2] The values of the different coins.
[3] The number of legal combinations.
[4] Iterate over the possible number of each coin type. Note the upper limits.
The loops are not optimal, as we should exit each one when the sum is higher than the target amount - as we cannot match it by adding even more coins. We will fix this, later on.
[5] Have we reached the target? If so, increase the count.
[6] Print the result.
Running it:
$ ./making-change 9
2
$ ./making-change 15
6
$ ./making-change 100
292
Looking good.
With verbose mode:
$ ./making-change -v 9
: 4P + N
: 9P
2
$ ./making-change -v 15
: N + D
: 3N
: 5P + D
: 5P + 2N
: 10P + N
: 15P
6
$ ./making-change -v 100
: 2HD
: 2Q + HD
: 4Q
: 5D + HD
: 5D + 2Q
: 10D
: N + 2D + Q + HD
: N + 2D + 3Q
: N + 7D + Q
: 2N + 4D + HD
: 2N + 4D + 2Q
: 2N + 9D
: 3N + D + Q + HD
: 3N + D + 3Q
: 3N + 6D + Q
: 4N + 3D + HD
: 4N + 3D + 2Q
: 4N + 8D
: 5N + Q + HD
: 5N + 3Q
: 5N + 5D + Q
: 6N + 2D + HD
: 6N + 2D + 2Q
: 6N + 7D
: 7N + 4D + Q
: 8N + D + HD
: 8N + D + 2Q
: 8N + 6D
: 9N + 3D + Q
: 10N + HD
: 10N + 2Q
: 10N + 5D
: 11N + 2D + Q
: 12N + 4D
: 13N + D + Q
: 14N + 3D
: 15N + Q
: 16N + 2D
: 18N + D
: 20N
: 5P + 2D + Q + HD
: 5P + 2D + 3Q
: 5P + 7D + Q
: 5P + N + 4D + HD
: 5P + N + 4D + 2Q
: 5P + N + 9D
: 5P + 2N + D + Q + HD
: 5P + 2N + D + 3Q
: 5P + 2N + 6D + Q
: 5P + 3N + 3D + HD
: 5P + 3N + 3D + 2Q
: 5P + 3N + 8D
: 5P + 4N + Q + HD
: 5P + 4N + 3Q
: 5P + 4N + 5D + Q
: 5P + 5N + 2D + HD
: 5P + 5N + 2D + 2Q
: 5P + 5N + 7D
: 5P + 6N + 4D + Q
: 5P + 7N + D + HD
: 5P + 7N + D + 2Q
: 5P + 7N + 6D
: 5P + 8N + 3D + Q
: 5P + 9N + HD
: 5P + 9N + 2Q
: 5P + 9N + 5D
: 5P + 10N + 2D + Q
: 5P + 11N + 4D
: 5P + 12N + D + Q
: 5P + 13N + 3D
: 5P + 14N + Q
: 5P + 15N + 2D
: 5P + 17N + D
: 5P + 19N
: 10P + 4D + HD
: 10P + 4D + 2Q
: 10P + 9D
: 10P + N + D + Q + HD
: 10P + N + D + 3Q
: 10P + N + 6D + Q
: 10P + 2N + 3D + HD
: 10P + 2N + 3D + 2Q
: 10P + 2N + 8D
: 10P + 3N + Q + HD
: 10P + 3N + 3Q
: 10P + 3N + 5D + Q
: 10P + 4N + 2D + HD
: 10P + 4N + 2D + 2Q
: 10P + 4N + 7D
: 10P + 5N + 4D + Q
: 10P + 6N + D + HD
: 10P + 6N + D + 2Q
: 10P + 6N + 6D
: 10P + 7N + 3D + Q
: 10P + 8N + HD
: 10P + 8N + 2Q
: 10P + 8N + 5D
: 10P + 9N + 2D + Q
: 10P + 10N + 4D
: 10P + 11N + D + Q
: 10P + 12N + 3D
: 10P + 13N + Q
: 10P + 14N + 2D
: 10P + 16N + D
: 10P + 18N
: 15P + D + Q + HD
: 15P + D + 3Q
: 15P + 6D + Q
: 15P + N + 3D + HD
: 15P + N + 3D + 2Q
: 15P + N + 8D
: 15P + 2N + Q + HD
: 15P + 2N + 3Q
: 15P + 2N + 5D + Q
: 15P + 3N + 2D + HD
: 15P + 3N + 2D + 2Q
: 15P + 3N + 7D
: 15P + 4N + 4D + Q
: 15P + 5N + D + HD
: 15P + 5N + D + 2Q
: 15P + 5N + 6D
: 15P + 6N + 3D + Q
: 15P + 7N + HD
: 15P + 7N + 2Q
: 15P + 7N + 5D
: 15P + 8N + 2D + Q
: 15P + 9N + 4D
: 15P + 10N + D + Q
: 15P + 11N + 3D
: 15P + 12N + Q
: 15P + 13N + 2D
: 15P + 15N + D
: 15P + 17N
: 20P + 3D + HD
: 20P + 3D + 2Q
: 20P + 8D
: 20P + N + Q + HD
: 20P + N + 3Q
: 20P + N + 5D + Q
: 20P + 2N + 2D + HD
: 20P + 2N + 2D + 2Q
: 20P + 2N + 7D
: 20P + 3N + 4D + Q
: 20P + 4N + D + HD
: 20P + 4N + D + 2Q
: 20P + 4N + 6D
: 20P + 5N + 3D + Q
: 20P + 6N + HD
: 20P + 6N + 2Q
: 20P + 6N + 5D
: 20P + 7N + 2D + Q
: 20P + 8N + 4D
: 20P + 9N + D + Q
: 20P + 10N + 3D
: 20P + 11N + Q
: 20P + 12N + 2D
: 20P + 14N + D
: 20P + 16N
: 25P + Q + HD
: 25P + 3Q
: 25P + 5D + Q
: 25P + N + 2D + HD
: 25P + N + 2D + 2Q
: 25P + N + 7D
: 25P + 2N + 4D + Q
: 25P + 3N + D + HD
: 25P + 3N + D + 2Q
: 25P + 3N + 6D
: 25P + 4N + 3D + Q
: 25P + 5N + HD
: 25P + 5N + 2Q
: 25P + 5N + 5D
: 25P + 6N + 2D + Q
: 25P + 7N + 4D
: 25P + 8N + D + Q
: 25P + 9N + 3D
: 25P + 10N + Q
: 25P + 11N + 2D
: 25P + 13N + D
: 25P + 15N
: 30P + 2D + HD
: 30P + 2D + 2Q
: 30P + 7D
: 30P + N + 4D + Q
: 30P + 2N + D + HD
: 30P + 2N + D + 2Q
: 30P + 2N + 6D
: 30P + 3N + 3D + Q
: 30P + 4N + HD
: 30P + 4N + 2Q
: 30P + 4N + 5D
: 30P + 5N + 2D + Q
: 30P + 6N + 4D
: 30P + 7N + D + Q
: 30P + 8N + 3D
: 30P + 9N + Q
: 30P + 10N + 2D
: 30P + 12N + D
: 30P + 14N
: 35P + 4D + Q
: 35P + N + D + HD
: 35P + N + D + 2Q
: 35P + N + 6D
: 35P + 2N + 3D + Q
: 35P + 3N + HD
: 35P + 3N + 2Q
: 35P + 3N + 5D
: 35P + 4N + 2D + Q
: 35P + 5N + 4D
: 35P + 6N + D + Q
: 35P + 7N + 3D
: 35P + 8N + Q
: 35P + 9N + 2D
: 35P + 11N + D
: 35P + 13N
: 40P + D + HD
: 40P + D + 2Q
: 40P + 6D
: 40P + N + 3D + Q
: 40P + 2N + HD
: 40P + 2N + 2Q
: 40P + 2N + 5D
: 40P + 3N + 2D + Q
: 40P + 4N + 4D
: 40P + 5N + D + Q
: 40P + 6N + 3D
: 40P + 7N + Q
: 40P + 8N + 2D
: 40P + 10N + D
: 40P + 12N
: 45P + 3D + Q
: 45P + N + HD
: 45P + N + 2Q
: 45P + N + 5D
: 45P + 2N + 2D + Q
: 45P + 3N + 4D
: 45P + 4N + D + Q
: 45P + 5N + 3D
: 45P + 6N + Q
: 45P + 7N + 2D
: 45P + 9N + D
: 45P + 11N
: 50P + HD
: 50P + 2Q
: 50P + 5D
: 50P + N + 2D + Q
: 50P + 2N + 4D
: 50P + 3N + D + Q
: 50P + 4N + 3D
: 50P + 5N + Q
: 50P + 6N + 2D
: 50P + 8N + D
: 50P + 10N
: 55P + 2D + Q
: 55P + N + 4D
: 55P + 2N + D + Q
: 55P + 3N + 3D
: 55P + 4N + Q
: 55P + 5N + 2D
: 55P + 7N + D
: 55P + 9N
: 60P + 4D
: 60P + N + D + Q
: 60P + 2N + 3D
: 60P + 3N + Q
: 60P + 4N + 2D
: 60P + 6N + D
: 60P + 8N
: 65P + D + Q
: 65P + N + 3D
: 65P + 2N + Q
: 65P + 3N + 2D
: 65P + 5N + D
: 65P + 7N
: 70P + 3D
: 70P + N + Q
: 70P + 2N + 2D
: 70P + 4N + D
: 70P + 6N
: 75P + Q
: 75P + N + 2D
: 75P + 3N + D
: 75P + 5N
: 80P + 2D
: 80P + 2N + D
: 80P + 4N
: 85P + N + D
: 85P + 3N
: 90P + D
: 90P + 2N
: 95P + N
: 100P
292
Then the optimised version:
File: making-change-last
#! /usr/bin/env raku
unit sub MAIN (UInt $amount, :v(:$verbose));
my %value;
%value<penny> = 1;
%value<nickel> = 5;
%value<dime> = 10;
%value<quarter> = 25;
%value<half-dollar> = 50;
my $ok = 0;
for 0 .. $amount -> $penny
{
my $sum-p = $penny * %value<penny>; # [1]
for 0 .. $amount -> $nickel # [2]
{
my $sum-pn = $sum-p + $nickel * %value<nickel>; # [1a]
last if $sum-pn > $amount; # [2a]
for 0 .. $amount -> $dime
{
my $sum-pnd = $sum-pn + $dime * %value<dime>;
last if $sum-pnd > $amount;
for 0 .. $amount -> $quarter
{
my $sum-pndq = $sum-pnd + $quarter * %value<quarter>;
last if $sum-pndq > $amount;
for 0 .. $amount -> $half-dollar
{
my $sum = $sum-pndq + $half-dollar * %value<half-dollar>;
last if $sum > $amount;
if $sum == $amount # [3]
{
$ok++;
say ": " ~
(
prettyish($penny, 'P'),
prettyish($nickel, 'N'),
prettyish($dime, 'D'),
prettyish($quarter, 'Q'),
prettyish($half-dollar, 'HD')
).grep( *.defined ).join(" + ") if $verbose;
}
}
}
}
}
}
sub prettyish ($value, $letter)
{
return unless $value;
return $letter if $value == 1;
return "$value$letter";
}
say $ok;
[1] We add up the total coin value after each iteration of each loop.
[2] We do not need a smart upper limit for the loops, as the last
statements will exit the current loop when we have overshot the target
value.
[3] We already have the sum, making the comparison easy.
Running it gives the expected result:
$ ./making-change-last 9
2
$ ./making-change-last 15
6
$ ./making-change-last 100
292
And that's it.