---------------------------
Topics:
------
recursion, ADTs
Given: You are given a Python Class template. In this class there is a
class variable vector, is a list of non-negative integers and are
stored (in positions 0, 1, 2, ... (N-1)), where the integer in
position (N-1) is 0.
Task: Write a recursive function "findAllPaths" to find all possible
path through V starting at position 0, and ending at
position (N-1), in accordance with the Rule below. If multiple
paths exist, add all of them to a class variable called "paths."
If no such path exists, "paths" should be an empty list. You also
have to write a function called "getPaths" return paths which is
a list of 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
"getPaths" returns it
Approach:
--------
It will be helpful if you do NOT try to write the complete
finddAllPaths 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 (size-1) 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
hey, faaiza here. I love coding in python as it gives me more freedom than a lot of other languages. I would like to offer you a hand for this pathFinder() implementation. Thanks.
Hello. The project seems to be very interesting from the point of programming. I am ready to start immediately if i would be chosen. I could write a lot about my experience, but hope to prove it by the highest quality of the result.
Hey, I was playing around with your code and found the solution. I want to ask if you are going to provide any more test cases to test the functionality properly? Thanks.