This is my response to The Weekly Challenge #213.
Input: @list = (1,2,3,4,5,6)
Output: (2,4,6,1,3,5)
Input: @list = (1,2)
Output: (2,1)
Input: @list = (1)
Output: (1)
A straight forward double barrel grep does the trick (or tricks):
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems >= 1 # [1]
&& @list.all ~~ Int # [1a]
&& @list.all > 0, # [1b]
:v(:$verbose));
my @sorted = @list>>.Int.sort; # [2]
my @even = @sorted.grep: * %% 2; # [3]
my @odd = @sorted.grep: * % 2; # [4]
say ":Even: @even[]" if $verbose;
say ":Odd: @odd[]" if $verbose;
my @result = @even; @result.append: @odd; # [5]
say "(" ~ @result.join(",") ~ ")"; # [6]
[1] A slurpy array, with at least one element, they must all be integers [1a], and greater than zero [1b].
[2] Sort the values, after coercing them to integers (from the IntStr type), to ensure numeric sorting order. Raku is probably doing the right thing here by default, but being absolutely sure cannot be a bad thing...
[3] Get the even values; the ones that are divisible (%%) by 2.
[4] Get the odd values; the ones that are not integer divisible by 2 (i.e. returns a remainder).
[5] Combine the two lists as one.
[6] Print the result, with the requried formatting.
Running it:
$ ./fun-sort-grep 1 2 3 4 5 6
(2,4,6,1,3,5)
$ ./fun-sort-grep 1 2
(2,1)
$ ./fun-sort-grep 1
(1)
Looking good.
With verbose mode:
$ ./fun-sort-grep -v 1 2 3 4 5 6
:Even: 2 4 6
:Odd: 1 3 5
(2,4,6,1,3,5)
$ ./fun-sort-grep -v 1 2
:Even: 2
:Odd: 1
(2,1)
$ ./fun-sort-grep -v 1
:Even:
:Odd: 1
(1)
Doing grep twice seems silly (or even stupid). We
should look for a way that splits (or unzips) the input list in two. And luckily
Raku has a classify routine that does just that (and more, much more.
But that is a topic for a future article. Perhaps...)
See
docs.raku.org/routine/classify
for more information about classify.
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems >= 1
&& @list.all ~~ Int
&& @list.all > 0,
:v(:$verbose));
my %result = @list>>.Int.sort.classify({ $_ %% 2 ?? 'even' !! 'odd' }); # [1]
say ":Classify: { %result.raku }" if $verbose;
my @result = | %result; @result.append: | %result; # [2}
say "(" ~ @result.join(",") ~ ")";
[1] Use classify to sort the values in two buckets; «even» and «odd»,
after coercing the values to integers (the code marked with green) so that the
verbose mode output looks nicer. You can safely remove that coercer, if
that makes you feel better.
[2] Fetch the even and odd values from the
hash returned by classify. Note that we get a list, so we have to
flatten that (the | flattening operator) to get a one dimentional
result.
See
docs.raku.org/routine/| for more
information about |.
Running it gives the same result as before, except the verbose output:
$ ./fun-sort-classify -v 1 2 3 4 5 6
:Classify: {:even($[2, 4, 6]), :odd($[1, 3, 5])}
(2,4,6,1,3,5)
$ ./fun-sort-classify -v 1 2
:Classify: {:even($[2]), :odd($[1])}
(2,1)
$ ./fun-sort-classify -v 1
:Classify: {:odd($[1])}
Use of uninitialized value @result of type Any in string context.
Methods .^name, .raku, .gist, or .say can be used to stringify it to something
meaningful.
in sub MAIN at ./fun-sort-classify line 11
(,1)
Oops.
An empty even value part wreaks havoc with my program. As does an empty odd part:
$ ./fun-sort-classify -v 2
:Classify: {:even($[2])}
Use of uninitialized value @result of type Any in string context.
Methods .^name, .raku, .gist, or .say can be used to stringify it to something
meaningful.
in sub MAIN at ./fun-sort-classify line 11
(2,)
This is fixable:
File: fun-sort-classify2
#! /usr/bin/env raku
unit sub MAIN (*@list where @list.elems >= 1
&& @list.all ~~ Int
&& @list.all > 0,
:v(:$verbose));
my %result = @list>>.Int.sort.classify({ $_ %% 2 ?? 'even' !! 'odd' });
say ":Classify: { %result.raku }" if $verbose;
my @result;
@result = | %result<even> if %result<even>; # [1]
@result.append: | %result<odd> if %result<odd>; # [2]
say "(" ~ @result.join(",") ~ ")";
[1] Only add the even part if it does exist.
[2] Only add the odd part if it does exist.
Running it gives the expected result:
$ ./fun-sort-classify2 -v 1 2 3 4 5 6
:Classify: {:even($[2, 4, 6]), :odd($[1, 3, 5])}
(2,4,6,1,3,5)
$ ./fun-sort-classify2 -v 1 2
:Classify: {:even($[2]), :odd($[1])}
(2,1)
$ ./fun-sort-classify2 -v 1
:Classify: {:odd($[1])}
(1)
$ ./fun-sort-classify2 -v 2
:Classify: {:even($[2])}
(2)
Input: @routes = ([1,2,6], [5,6,7])
$source = 1
$destination = 7
Output: (1,2,6,7)
Source (1) is part of route [1,2,6] so the journey looks like 1 -> 2 -> 6
then jump to route [5,6,7] and takes the route 6 -> 7.
So the final route is (1,2,6,7)
Input: @routes = ([1,2,3], [4,5,6])
$source = 2
$destination = 5
Output: -1
Input: @routes = ([1,2,3], [4,5,6], [3,8,9], [7,8])
$source = 1
$destination = 7
Output: (1,2,3,8,7)
Source (1) is part of route [1,2,3] so the journey looks like 1 -> 2 -> 3
then jump to route [3,8,9] and takes the route 3 -> 8
then jump to route [7,8] and takes the route 8 -> 7
So the final route is (1,2,3,8,7)
This is in a sense a response (in a «kick in the posterior» sense) to the missing sixth instalment «Shortest Path» of my five part Seven Bridges to Raku article from July and August 2020.
Graph traversal, which this is, can either be done Depth first or Breadth first. We are looking for the shortest path (or rather, one of possibly many equally short paths). This is suitable for Breadth First, where we take one step at a time in each direction, saving the resulting path for later (by adding it to the end of the list of unfinished paths, forming a queue) after each step. When (or rather, if) we reach the target, we have a (as in one) shortest path.
I have decided to write a program where we specify the values on the command line, using the same «bar and space» syntax as used in the first part of The Same Toeplitz, my response to Challenge 211.
The first part of the program reads in the values, sets up the graph in a hash of next values (between the nodes), and does some trivial error checking:
File: shortest-route (partial)
#! /usr/bin/env raku
unit sub MAIN ($routes, :s(:$source), :d(:$destination), :v(:$verbose)); # [1]
my @routes = $routes.split("|")>>.words>>.Array; # [2]
my %next; # [3]
if $verbose
{
say ":Source: $source";
say ":Routes: { @routes.raku }";
say ":Destination: $destination";
}
for @routes -> @route # [4]
{
my $first = @route.shift; # [5]
while @route # [6]
{
my $second = @route.shift; # [7]
next if $first eq $second; # [8]
%next{$first}.push: $second; # [9]
%next{$second}.push: $first; # [10]
$first = $second; # [11]
}
}
unless %next{$source} # [12]
{
say ":Source not in route(s)" if $verbose;
say '-1'; # [12a]
exit; # [12b]
}
unless %next{$destination} # [13]
{
say ":Destination not in route(s)" if $verbose;
say '-1'; # [13a]
exit; # [13b]
}
say ":Tree: { %next.raku }" if $verbose;
[1] Named arguments for the source and route, and a regular (positional) one for the routes.
[2] Get the routes. Note the trailing >>.Array to get each part
as an array (that we can use and reuse) instead of the default sequence.
[3] The pointers to the next node in the graph will end up here.
[4] For each route,
[5] Get the first node.
[6] As long as there are more nodes.
[7] Get the first remaining node.
[8] Skip the node if it is the same as the previous one. This should be illegal anyway, and saves us from trouble in the second part of the program.
[9] The next node.
[10] And vice versa, as the routes (as given on the command line) are bidirectional (better known as undirectional).
[11] Prepare for the next iteration.
[12] Is the source node present in the graph? If not, we can fail right away.
[13] Ditto for the destination node.
The second part of the program does the traversal, Breadth First:
File: shortest-route (the rest)
my @paths = ($source.Str); # [14]
while @paths.elems # [15]
{
say ":Queue of Paths: { @paths.raku }" if $verbose;
my @path = | @paths.shift; # [16]
my $current = @path.tail; # [17]
say ":Path: { @path.raku } (current end pos: { $current.raku }) \
with nexts: { %next{$current}.raku }" if $verbose;
my $exits = %next{$current} // next; # [18]
for @$exits -> $next # [19]
{
my @copy = @path.clone; # [20]
next if $next eq any @copy; # [21]
@copy.push: $next; # [22]
say ":Path: { @copy.raku } (former end pos: { $current.raku })"
if $verbose;
if $next eq $destination # [23]
{
say "({ @copy.join(",") })"; # [23a]
exit; # [23b]
}
@paths.push: @copy; # [24]
} # [25]
}
say "-1"; # [26]
[14] Initially we have just one partial path in the queue, the starting node itself.
[15] As long as the queue is not empty.
[16] Get the first path from the queue. Note the prefix flattening operator
| so that we get the elements, and not the list (a single element).
[17] Get the current positition of the path (the last element,
obtained with tail).
See
docs.raku.org/routine/tail
for more information about tail.
[18] Get the exits from the current position.
[19] Iterate over the exits (a list).
[20] Get a copy of the current path (with clone),
so that we can add to it without clobbering up the original path.
See
docs.raku.org/routine/clone for
more information about the clone method.
[21] Do not follow a «next node» path to a node already in the path.
[22] Add the node to the path.
[23] Have we reached the destination? If so print the path [23a] and exit [23b].
[24] Add the partial path to the queue.
[25] At this point we can have exhausted a path, i.e. not added a modifed version back to the queue.
[26] We have failed to find a path to the target. Say so.
Running it:
$ ./shortest-route -s=1 -d=7 "1 2 6 | 5 6 7"
(1,2,6,7)
$ ./shortest-route -s=2 -d=5 "1 2 3 | 4 5 6"
-1
$ ./shortest-route -s=1 -d=7 "1 2 3 | 4 5 6 | 3 8 9 | 7 8"
(1,2,3,8,7)
Looking good.
With verbose mode:
$ ./shortest-route -s=1 -d=7 -v "1 2 6 | 5 6 7"
:Source: 1
:Routes: [["1", "2", "6"], ["5", "6", "7"]]
:Destination: 7
:Tree: {"1" => $["2"], "2" => $["1", "6"], "5" => $["6"],
"6" => $["2", "5", "7"], "7" => $["6"]}
:Queue of Paths: ["1"]
:Path: ["1"] (current end pos: "1") with nexts: $["2"]
:Path: ["1", "2"] (former end pos: "1")
:Queue of Paths: [["1", "2"],]
:Path: ["1", "2"] (current end pos: "2") with nexts: $["1", "6"]
:Path: ["1", "2", "6"] (former end pos: "2")
:Queue of Paths: [["1", "2", "6"],]
:Path: ["1", "2", "6"] (current end pos: "6") with nexts: $["2", "5", "7"]
:Path: ["1", "2", "6", "5"] (former end pos: "6")
:Path: ["1", "2", "6", "7"] (former end pos: "6")
(1,2,6,7)
$ ./shortest-route -s=2 -d=5 -v "1 2 3 | 4 5 6"
:Source: 2
:Routes: [["1", "2", "3"], ["4", "5", "6"]]
:Destination: 5
:Tree: {"1" => $["2"], "2" => $["1", "3"], "3" => $["2"],
"4" => $["5"], "5" => $["4", "6"], "6" => $["5"]}
:Queue of Paths: ["2"]
:Path: ["2"] (current end pos: "2") with nexts: $["1", "3"]
:Path: ["2", "1"] (former end pos: "2")
:Path: ["2", "3"] (former end pos: "2")
:Queue of Paths: [["2", "1"], ["2", "3"]]
:Path: ["2", "1"] (current end pos: "1") with nexts: $["2"]
:Queue of Paths: [["2", "3"],]
:Path: ["2", "3"] (current end pos: "3") with nexts: $["2"]
$ ./shortest-route -s=1 -d=7 -v "1 2 3 | 4 5 6 | 3 8 9 | 7 8"
:Source: 1
:Routes: [["1", "2", "3"], ["4", "5", "6"], ["3", "8", "9"], ["7", "8"]]
:Destination: 7
:Tree: {"1" => $["2"], "2" => $["1", "3"], "3" => $["2", "8"],
"4" => $["5"], "5" => $["4", "6"], "6" => $["5"],
"7" => $["8"], "8" => $["3", "9", "7"], "9" => $["8"]}
:Queue of Paths: ["1"]
:Path: ["1"] (current end pos: "1") with nexts: $["2"]
:Path: ["1", "2"] (former end pos: "1")
:Queue of Paths: [["1", "2"],]
:Path: ["1", "2"] (current end pos: "2") with nexts: $["1", "3"]
:Path: ["1", "2", "3"] (former end pos: "2")
:Queue of Paths: [["1", "2", "3"],]
:Path: ["1", "2", "3"] (current end pos: "3") with nexts: $["2", "8"]
:Path: ["1", "2", "3", "8"] (former end pos: "3")
:Queue of Paths: [["1", "2", "3", "8"],]
:Path: ["1", "2", "3", "8"] (current end pos: "8") with
nexts: $["3", "9", "7"]
:Path: ["1", "2", "3", "8", "9"] (former end pos: "8")
:Path: ["1", "2", "3", "8", "7"] (former end pos: "8")
(1,2,3,8,7)
And that's it.