by Arne Sommer

# Fun Route with Raku

 Published 22. April 2023.

This is my response to The Weekly Challenge #213.

## Challenge #213.1: Fun Sort

You are given a list of positive integers.

Write a script to sort the all even integers first then all odds in ascending order.

Example 1: ```Input: @list = (1,2,3,4,5,6) Output: (2,4,6,1,3,5) ``` Example 2: ```Input: @list = (1,2) Output: (2,1) ``` Example 3: ```Input: @list = (1) Output: (1) ```

A straight forward double barrel `grep` does the trick (or tricks):

File: fun-sort-grep ```#! /usr/bin/env raku unit sub MAIN (*@list where @list.elems >= 1 #  && @list.all ~~ Int # [1a] && @list.all > 0, # [1b] :v(:\$verbose)); my @sorted = @list>>.Int.sort; #  my @even = @sorted.grep: * %% 2; #  my @odd = @sorted.grep: * % 2; #  say ":Even: @even[]" if \$verbose; say ":Odd: @odd[]" if \$verbose; my @result = @even; @result.append: @odd; #  say "(" ~ @result.join(",") ~ ")"; #  ```

 A slurpy array, with at least one element, they must all be integers [1a], and greater than zero [1b].

 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...

 Get the even values; the ones that are divisible (`%%`) by 2.

 Get the odd values; the ones that are not integer divisible by 2 (i.e. returns a remainder).

 Combine the two lists as one.

 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`.

File: fun-sort-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' }); #  say ":Classify: { %result.raku }" if \$verbose; my @result = | %result; @result.append: | %result; # [2} say "(" ~ @result.join(",") ~ ")"; ```

 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.

 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(\$), :odd(\$)} (2,1) \$ ./fun-sort-classify -v 1 :Classify: {:odd(\$)} 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(\$)} 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>; #  @result.append: | %result<odd> if %result<odd>; #  say "(" ~ @result.join(",") ~ ")"; ```

 Only add the even part if it does exist.

 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(\$), :odd(\$)} (2,1) \$ ./fun-sort-classify2 -v 1 :Classify: {:odd(\$)} (1) \$ ./fun-sort-classify2 -v 2 :Classify: {:even(\$)} (2) ```

## Challenge #213.2: Shortest Route

You are given a list of bidirectional routes defining a network of nodes, as well as source and destination node numbers.

Write a script to find the route from source to destination that passes through fewest nodes.

Example 1: ```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) ``` Example 2: ```Input: @routes = ([1,2,3], [4,5,6]) \$source = 2 \$destination = 5 Output: -1 ``` Example 2: ```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)); #  my @routes = \$routes.split("|")>>.words>>.Array; #  my %next; #  if \$verbose { say ":Source: \$source"; say ":Routes: { @routes.raku }"; say ":Destination: \$destination"; } for @routes -> @route #  { my \$first = @route.shift; #  while @route #  { my \$second = @route.shift; #  next if \$first eq \$second; #  %next{\$first}.push: \$second; #  %next{\$second}.push: \$first; #  \$first = \$second; #  } } unless %next{\$source} #  { say ":Source not in route(s)" if \$verbose; say '-1'; # [12a] exit; # [12b] } unless %next{\$destination} #  { say ":Destination not in route(s)" if \$verbose; say '-1'; # [13a] exit; # [13b] } say ":Tree: { %next.raku }" if \$verbose; ```

 Named arguments for the source and route, and a regular (positional) one for the routes.

 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.

 The pointers to the next node in the graph will end up here.

 For each route,

 Get the first node.

 As long as there are more nodes.

 Get the first remaining node.

 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.

 The next node.

 And vice versa, as the routes (as given on the command line) are bidirectional (better known as undirectional).

 Prepare for the next iteration.

 Is the source node present in the graph? If not, we can fail right away.

 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); #  while @paths.elems #  { say ":Queue of Paths: { @paths.raku }" if \$verbose; my @path = | @paths.shift; #  my \$current = @path.tail; #  say ":Path: { @path.raku } (current end pos: { \$current.raku }) \ with nexts: { %next{\$current}.raku }" if \$verbose; my \$exits = %next{\$current} // next; #  for @\$exits -> \$next #  { my @copy = @path.clone; #  next if \$next eq any @copy; #  @copy.push: \$next; #  say ":Path: { @copy.raku } (former end pos: { \$current.raku })" if \$verbose; if \$next eq \$destination #  { say "({ @copy.join(",") })"; # [23a] exit; # [23b] } @paths.push: @copy; #  } #  } say "-1"; #  ```

 Initially we have just one partial path in the queue, the starting node itself.

 As long as the queue is not empty.

 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).

 Get the current positition of the path (the last element, obtained with `tail`).

See docs.raku.org/routine/tail for more information about `tail`.

 Get the exits from the current position.

 Iterate over the exits (a list).

 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.

 Do not follow a «next node» path to a node already in the path.

 Add the node to the path.

 Have we reached the destination? If so print the path [23a] and exit [23b].

 Add the partial path to the queue.

 At this point we can have exhausted a path, i.e. not added a modifed version back to the queue.

 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.