Computer Science - Coloured Routes

The Problem

A group of towns is connected by a rail network. To help travel around the network some routes have been given colours; each station has one `red' route leaving it, and one `blue' route. Routes have an associated direction, so a route from A to B does not necessarily mean there is a corresponding route from B to A.

You are trying to give directions to a friend, so that you can meet them at a station of your choosing. Unfortunately you do not know which station your friend will start from, and due to their identical layouts they cannot be distinguished. To direct your friend, you need to give them a sequence of coloured routes to take, so that they will finish at your chosen station irrespective of where they start.

Due to limitations on the rail tickets and the placement of barriers, it is not enough that they pass through this station before the end of the sequence.

Write a program which reads in details of the rail network, and returns a sequence of coloured routes. To make life simple for your friend, you should return the shortest route possible.

The first line of your input will be an integer 2 ≤ x ≤ 16, specifying how many towns are connected in the network.

There will then follow x lines of two integers; the first integer on the ith of these lines is the destination of the red route from town i, and the second the destination of the blue route. Towns are numbered from 1 to x.

You should output the length of the shortest possible route sequence, followed by an example sequence, using r and b to denote the two types of route, and the town your friend will finish in. If there is no possible route sequence you should just output ‘Impossible’.

The Solution

Background
A brute force method can be applied to this problem.

Initially, the length of a route can be chosen as two steps (according to the problem above). There are 2n combinations of routes for two steps. i.e. r,r or r,b or b,r or b,b. If r,r steps are followed from each city in turn, then the destination city can be noted and compared. If the final destination in both cases is the same then we have a solution. If not, then we move on to the next combination of routes which would be r,b and a similar check can be made. If there are no solutions for n=2, then we can increase the number of routes to 3 and repeat the method and go on incrementing the number of routes until we find a solution. Two cases are shown below for the code and its output. You will observe that more than one solution can be found.

CODED SOLUTION 1 using the Brute Force Method and Recursion to generate combinations of routes (Table 1) by Dr Curtis
The features of this particular piece of code include the use of functions to break down the problem into parts and the use of recursion to generate all combinations of routes depending on the number of routes that are being explored. The main program starts on line 65 and runs for two cases. The first case includes 4 cities and the variable ‘destinations’ on line 75 defines the red and blue routes between cities. The function using recursion is called def generateAllBinaryStrings() on lines 40-61. Recursion is where a function calls itself until a condition is met called the terminal condition. Recursion is often considered to be a more efficient way of writing code. The program has to keep track of the function calling itself multiple times and it does this using a Stack.

The output for Case 1 shows that there is only one solution involving just 5 steps with destination city 3 from all other cities, whereas, there are a number of other possible solutions if 6 steps are allowed. Case 2 shows the solution for the problem described at the beginning of this article. In fact there are 3 solutions using 6 steps that will guarantee our friend will end up in a particular city no matter the starting city. e.g.  Solution :  6 [1, 1, 0, 0, 1, 0] 4 means that it will take 6 steps following route blue, blue, red, red, blue and red from any city to guarantee that my friend will arrive at city 4 as their final destination, so I will be able to meet my friend in city 4.

CODED SOLUTION 2 using the Brute Force Method (Table 2) by Alexander Will (L6)
This second coded solution uses a Python module called itertools. This module is a library of methods which is great module for creating your own iterators. The tools provided by itertools are fast and memory efficient. They can be used for efficient looping. Itertools as a module is particularly useful for this problem as it contains a function called itertools.product allowing the n value, which will be raised to the power of 2, to be input directly. This returns all of the binary value sets for the equivalent value of n. This is helpful as the binary values can be used to represent the red and blue pathways possible from one city to another. Once the possible binary pathway sets have been collected the program evaluates each option. If all the binary pathway sets from every city end up in the same single city the program will detect the binary pathway as a possible solution to the problem. All the solutions are collected and analysed to determine which route has the least number of steps to reach the destination city for the specific route. This is done by counting the number of digits in the binary route pattern and comparing them to one another, once every solution has been compared to one another a concluding solution will be output along with the number of steps it takes and the destination city from every other city.