No connection

You are given a list of routes, @routes. Write a script to find the destination with no further outgoing connection.

Examples

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"

Analysis

The simple answer is that any 'to' that doesn't exist as a 'from' is going to be a dead end.

But of course there are some edge cases. Supposing one of the routes is ['A','A']. Clearly 'A' is a dead end, because you can't go anywhere from 'A'.

But wait! What about ['A','B'],['A','A']? Here 'A' isn't a dead end because even if you take the ['A','A'] route and end up where you started, you can then take the ['A','B'] route to get to ['B'] - so 'A' isn't a dead end in this case.

So I believe the algorithm is:

• Make a list of all the 'from's, and a list of all the 'to's, excluding any routes where 'from' and 'to' are identical
• Start a dead-end list with all the distinct 'to's in the 'to'-list for which there is no entry in the 'from'-list.
• Add to the dead-end list the 'to' of any zero-length route where that 'to' isn't in the 'from'-list and isn't already in the dead-end list

Another issue to consider is a loop, for example ['A','B'],['B','C'],['C','A']. My interpretation of the challenge text is that all 3 places, 'A', 'B' and 'C', have an immediate destination with a further outgoing connection, so I am not reporting those.

Not such a simple challenge as at first appears - which is of course what we enjoy.

Detailed task analysis is the highlight of the post as always and don't forget to DIY. Keep it up great work.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-09-02
use utf8;     # Week 285 - task 1 - No connection
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

no_connection(['B', 'C'], ['D', 'B'], ['C', 'A']);
no_connection(['F', 'G'], ['G', 'H'], ['H', 'F']);
no_connection(['B', 'C'], ['A', 'A'], ['B', 'B']);

# longer example - random routes
my ($x, $y);
for (0 .. 24) {
    $x .= qq{['} . chr(int(rand(15)) + ord('A')) . qq{','} .
        chr(int(rand(15)) + ord('A')) . qq{'],}
}
$x =~ s|.$||;
no_connection(eval($x));

sub no_connection {
    
    my (@routes, $r, $input, $output, %from, %to);
    
    # create list of froms and tos where from and to are distinct
    @routes = @_;
    for $r (@routes) {
        $input .= qq{['$r->[0]', '$r->[1]'], };
        next if $r->[1] eq $r->[0]; 
        $from{$r->[0]} = 1;
        $to{$r->[1]} = 1;
    }
    
    # create list of froms and tos where from and to are distinct
    $output = '';
    for $r (@routes) {
        next if $output =~ m|'$r->[1]'|;
        $output .= qq['$r->[1]', ] unless defined $from{$r->[1]};
    }
    
    # edge case of ['X', 'X']
    for $r (@routes) {
        if ($r->[1] eq $r->[0] and not $from{$r->[1]}) {
            $output .= qq['$r->[1]', ] unless $output =~ m|'$r->[1]'|;
        }
    }
    say qq[\nInput:  \@routes = (] . substr($input, 0, -2) . ')';
    say qq[Output: ] . ($output ? substr($output, 0, -2) : 'none');
}

17 lines of code

Output from script

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

Input:  @routes = (['F', 'G'], ['G', 'H'], ['H', 'F'])
Output: none

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

Input:  @routes = (['A', 'L'], ['I', 'K'], ['H', 'K'],
['E', 'L'], ['F', 'B'], ['I', 'A'], ['O', 'H'],
['G', 'A'], ['K', 'F'], ['O', 'G'], ['L', 'N'],
['D', 'K'], ['M', 'C'], ['C', 'A'], ['L', 'A'],
['O', 'C'], ['O', 'J'], ['K', 'M'], ['D', 'K'],
['C', 'K'], ['C', 'H'], ['N', 'L'], ['O', 'K'],
['E', 'A'], ['A', 'D'])
Output: 'B', 'J'