laurent_r

These are some answers to the Week 285, Task 1, 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 1: No Connection

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"

The task specification isn't very clear, but the examples are more or less self-explanatory. Basically, we're given a list of point pairs (a start- and an end-point) and we look for an end-point which doesn't exist as a start-point.

Although it wouldn't be too difficult to check, we will assume that the input list of routes is correct and that there is always one (and only one) end-point satisfying the above rule.

No Connection in Raku

We're looking for the end-point that is not a start-point. In Raku, this can easily be done using the set difference,infix%E2%88%96) between the list of end-points and the list of start-points. For the sake of clarity, we first built two arrays (@starts and @ends) and then compute the set difference. Note that, if its arguments are lists or arrays, the set difference operator coerces its arguments into sets.

sub no-connection (@in) {
    my @starts = map { .[0] }, @in;
    my @ends = map { .[1] }, @in;
    return ~ (@ends (-) @starts);
}

    my @tests = (("B","C"), ("D","B"), ("C","A")), (("A","Z"),);
for @tests -> @test {
    printf "%-20s => ", @test.gist;
    say no-connection @test;
}

This program displays the following output:

$ raku no-connection.raku
((B C) (D B) (C A))  => A
((A Z))              => Z

Note that the no-connection subroutine could be boiled down to a Raku one-liner:

sub no-connection (@in) {
    return ~((map {.[1]}, @in) (-) (map {.[0]}, @in));
}

This new shorter version yields the same result, but is, in my humble opinion, slightly less clear.

No Connection in Perl

There is no set difference in Perl (and no sets for that matter), but we can easily hand roll the functionality using an array and a hash, keeping the array item that doesn't exist in the hash.

use strict;
use warnings;
use feature 'say';

sub no_connection {
    my %starts = map { $_->[0] => 1} @_;
    my @ends = map { $_->[1] } @_;
    return grep {not exists $starts{$_}} @ends;
}

my @tests = ([["B","C"], ["D","B"], ["C","A"]], [["A","Z"]]);
for my $test (@tests) {
    printf "%-20s => ", join " ", map {"(@{$test->[$_]})"} 
        0..scalar @$test - 1;
    say no_connection @$test;
}

This program displays the following output:

$ perl no-connection.pl
(B C) (D B) (C A)    => A
(A Z)                => Z

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.