Dead end coins
Weekly challenge 285 — 2 September 2024
Week 285: 2 Sep 2024
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 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:
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.
#!/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'); }
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'
Any content of this website which has been created by Peter Campbell Smith is in the public domain