Sorting Routes
Tags: perl, python, theweeklychallenge
Published: 2023-04-23 07:51:49

## Weekly Challenge 213

[Challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-213/), [My solution](https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-213/sgreen)

## Task 1: Fun Sort

### Task

You are given a list of positive integers.

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

### My solution

This is relatively straight forward. A less experienced developer might sort all the even numbers first and then all the odd numbers, and that would (IMHO) be a perfectly acceptable solution for this task.

However, we know that both Perl and Python allow us to use a custom sorting method. In Perl, this is expressed as `{ $a % 2 <=> $b % 2 || $a <=> $b }`. `$a` and `$b` are global variables that the [sort](https://perldoc.perl.org/functions/sort) function uses to achieve this. `<=>` provides a numerical comparison between two values, returning `1` if `$b` is greater, `-1` if `$a` is greater, or `0` if they are the same.

Python is a little more straight forward with it's lambda function. The syntax used here is `array.sort(key=lambda x: (x % 2, x))`, which means we first search by evenness (evens first), and then numerically.

### Examples

```bash
$ ./ch-1.py 1 2 3 4 5 6
2, 4, 6, 1, 3, 5

$ ./ch-1.py 1 2
2, 1

$ ./ch-1.py 1
1

```

## Task 2: Shortest Route

### Task

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.

### My solution

This task on the other hand is much more complex. I have submitted only a Python solution. A Perl solution would simply be a transliteration of it.

To begin with I parse the input. The first value is a JSON string converted into a list of lists, while the second and third values represent the start and end numbers.

I then loop through each number in the node until I find the starting points, there may be more than one. For each starting point, I call the recursive function `find_routers` with the original list, the starting point, and the end value.

The `find_routers` recursive function has the original list of nodes, a list of nodes/position pairs of routes we've visited, and the target number. For the current node, I go backwards from the current number, and then go forwards. For each new number, I call the `find_pairs` function to see any connected nodes that we have not already seen. For each occurrence of this, I call the recursive function again, updating the second value with what node/position pairs we have already seen.

The return of this function is a list of node/number pairs. We keep a track of the solution of the shortest one found so far, and update it if the current one is shorter.

If there is no solution, I print `-1` and exit. The last step is to convert the list of node/position pairs into a list of numbers, and display the new list.

### Examples

```bash
$ ./ch-2.py "[[1,2,6], [5,6,7]]" 1 7
1,2,6,7

$ ./ch-2.py "[[1,2,3], [4,5,6]]" 2 5
-1

$ ./ch-2.py "[[1,2,3], [4,5,6], [3,8,9], [7,8]]" 1 7
1,2,3,8,7

$ ./ch-2.py '[[1,2,3,4,5,6,7], [7,1], [9,1]]' 6 9
6,7,1,9
```