Sorting Routes

Weekly Challenge 213

Challenge, My solution

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

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

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