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.

This review may cover either or both challenges for this week.

Try it 

Try running the script with any input:

Your @routes =

example: ['P','E'],['E','R'],['R','L']

⤡

#!/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 = (['N', 'F'], ['D', 'L'], ['D', 'B'], ['F', 'D'],
   ['D', 'A'], ['J', 'B'], ['A', 'J'], ['I', 'C'], ['B', 'J'], ['H',
   'J'], ['N', 'K'], ['L', 'I'], ['F', 'B'], ['C', 'N'], ['K', 'L'],
   ['O', 'C'], ['M', 'E'], ['F', 'A'], ['N', 'I'], ['D', 'M'], ['N',
   'G'], ['D', 'I'], ['A', 'F'], ['I', 'B'], ['G', 'H'])
Output: 'E'