Summary:

--------

Given: You are given a Python Class template. In this class there is a

class variable vector, is a list of N non-negative integers and are

stored (in positions 0, 1, 2, ... (N-1)), where at least one integer

is 0.

Task: Write a recursive function "findAllPaths" to find all possible

path through V starting at position 0, and ending at

the location of 0, in accordance with the Rule below. If no such path

exists, "paths" should be an empty list. The "findAllPaths"method also

must find the longest path and shortest path from your "paths" list.

You also have to write functions called "getShortest" and "getLongest"

which return respectively the shortest and longest paths as lists.

Rule: From position i, the next position in the path must be either i+x,

or i-x, where x is the non-negative integer stored in position i.

There is no path possible from position i to position i+x if

either of these 2 conditions hold:

position i+x is beyond the end of V.

position i+x is already on the path.

There is no path possible from position i to position i-x if

either of these 2 conditions hold:

position i-x is beyond the start of V.

position i-x is already on the path.

Example:

Suppose V contained the following:

Position: 0 1 2 3 4 5 6 7 8 9 10 11

Integer: 2 8 3 2 7 2 2 3 2 1 3 0

Then one path is:

0 2 5 7 4 11

i.e., you could get from position 0 to position 11 of V by

following the path of positions: 0 2 5 7 4 11

Note that other paths also exist, such as:

0 2 5 3 1 9 8 10 7 4 11

Recursive Algorithm

-------------------

Your solution MUST use a recursive function to identify the paths.

You must implement the recursive function, as follows:

def findAllPaths(self, position, solution):

"findAllPaths" takes the initial part of a solution Path, and

a potential next solution position in the Vector. It explores

paths with the given position appended to the given solution

path so far.

The class variable paths is a list of lists and the function

Approach:

--------

It will be helpful if you do NOT try to write the complete

findAllPaths at once, but, instead, start off with a simple

prototype, get it working, and then incrementally add functionality

to the prototype until you arrive at the completed assignment.

For example:

1. Start off with a prototype "findAllPaths" that simply returns 0

if NO solution path exists, and returns 1 if ANY solution path

exists. This prototype does not keep track of the solution

path. This prototype simply returns 1 the first time it

encounters position who's value is 0 in its explorations.

This prototype has only 2 parameters: position and V.

2. Modify "findAllPaths" to keep track of the solution path found

in part 1 above. Add parameter Solution, and store this

solution path in it. "findAllPaths" returns similarly to

prototype 1 above, except its caller will find a solution

path in the Solution parameter. Add additional parameters

to "findAllPaths" as necessary.

3. Modify "findAllPaths" to continue exploring after the a solution

path is found. The trick is to force the recursion to

keep going even after it finds a solution. It returns only when every

path has been explored (following the Rule).

Example Run:

------------

Example vector: [2, 8, 3, 2, 7, 2, 2, 3, 2, 1, 3, 0]

Valid paths:

0 2 5 7 4 11

0 2 5 3 1 9 10 7 4 11

0 2 5 3 1 9 8 10 7 4 11

0 2 5 3 1 9 8 6 4 11

No Solution example:

3 1 1 1 3 4 2 5 3 0

Some sample test is given in the template. The sample code only shows

the API of how your code should will be tested. You should add to it

to test code such that your lab solution account for all cases.