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

Current Code:

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 for i in range(0,len(self.vector)): l=[] j=i l.append(i) while(self.vector[j]!=0): x = self.vector[j] if (j-x)>=0: l.append(j-x) j=j-x else: l.append(j+x) j=j+x if len(l)>1: solution.append(l)

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 maximum = 0 for i in self.solution: a = len(i) if a>maximum: maximum = a l = i return l

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 minimum = 999 for i in self.solution: a = len(i) if a

def getPaths(self): # Return the list of all paths found or [] if no paths exist return self.solution

if __name__ == "__main__": v= [4,4,1,2,3,1,8,2,0] v = [4,3,1,2,3,5,4,2,2,1,1,0] v = [2,8,3,2,7,2,2,3,2,1,3,0] pf = Pathfinder(v) print("Solving " + str(v)) for p in pf.getPaths(): print(p) print(f"shortest: {pf.getShortest()}") print(f"longest: {pf.getLongest()}")

Error:

Solving [2, 8, 3, 2, 7, 2, 2, 3, 2, 1, 3, 0] Traceback (most recent call last): File "", line 60, in File "", line 50, in getPaths AttributeError: 'Pathfinder' object has no attribute 'solution'