Question

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

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

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

The following template is given:

def getName():
# Use the name displayed on D2L (easier for us to find)
   return "Haque, Mohammad"
  
class Pathfinder():
def __init__(self, vector):
# Initialize the Pathfinder object
self.vector = vector
self.paths = []
self.findAllPaths(0,[])

def findAllPaths(self, position, solution):
# Recursively explore the possible paths and store valid paths
# This method will not be tested, so you can modify the parameters as needed
print("hi")
pass

def getLongest(self):
# Return the longest of all paths found or [] if no paths exist
# If multiple paths with the longest length exist, return one of them
pass

def getShortest(self):
# Return the shortest of all paths found or [] if no paths exist
# If multiple paths with the shortest length exist, return one of them
pass

Any help will very much appreciated

Answer 1

Complete code of Solution:-

# Path finder class
class Pathfinder:

   # constructor of Path finder class.
   def __init__(self, vector):
       self.vector = vector
       self.paths = []

   # Recursive method to find all possible paths
   # 'self' is for refering current object, same as 'this' of java and c++
   # 'pos' is the index of element in 'self.vector' list where am I currently at.
   # 'path' is current path
   # 'idx' is for indexing in 'path' list.
   def findAllPaths(self, pos, path):

       # place 'pos' at index where -1 appeared first time in 'path'.
       path[path.index(-1)] = pos

       # if value at position denoting by 'pos' in 'self.vector' list is equal to 0
       # list elements in the range 0 to idx(inclusive) is representing one possible path.
       if self.vector[pos] == 0:

           # Appending one possible path into our 'paths' list.
           self.paths.append(path[0:path.index(-1)])

           # removing current position from 'path'
           path[path.index(-1)-1] = -1
           return

       # if we can move one step ahead (pos+x) from this position then make recursive call.
       if (pos+self.vector[pos]) not in path and (pos+self.vector[pos]) < len(self.vector):
           self.findAllPaths((pos+self.vector[pos]), path)

       # if we can move one step back (pos-x) from this position then make recursive call.
       if (pos-self.vector[pos]) not in path and (pos-self.vector[pos]) > -1:
           self.findAllPaths((pos-self.vector[pos]), path)

       # removing current position from 'path'
       path[path.index(-1)-1] = -1

   # This method will return one of the shortest paths.
   def shortesPath(self):
       ans = []
       for path in self.paths:
           if len(ans) == 0 or len(path) < len(ans):
               ans.clear()
               ans = path
       return ans

   # This method will return one of the longest paths.
   def longestPath(self):
       ans = []
       for path in self.paths:
           if len(ans) == 0 or len(path) > len(ans):
               ans.clear()
               ans = path
       return ans

# Creating object of 'Pathfinder' class.
Path = Pathfinder([3, 1, 1, 1, 3, 4, 2, 5, 3, 0])

# Initializing path will all '-1', denoting that path is empty now.
path = [-1 for i in range(len(Path.vector)+2)]
Path.findAllPaths(0, path)

# printing all paths.
print("All Paths-------------")
for path in Path.paths:
   print(path)

print("\nShortest path")
print(Path.shortesPath())
print("\nLongest path")
print(Path.longestPath())

Screenshot of Output:-

For first output, input list is [3, 1, 1, 1, 3, 4, 2, 5, 3, 0], so there won't be any possible path.

For second output, input list is [2, 8, 3, 2, 7, 2, 2, 3, 2, 1, 3, 0].