Hi! I need to know why my answer to this Python problem about recursion and ADTs is not passing the tester. I will post the problem description, the tester, and my code. Unfortunately, indentation might be an issue - please post a screenshot if you post a solution so I can see indents.

Problem description:

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

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

my code (problemattempt.py:)

class Pathfinder(): def __init__(self, vector): # Initialize the Pathfinder object self.vector = vector self.paths = [] #self.findAllPaths(0,[])

#updated the method signature to use default value of 0 for position and empty list for solution #so that the method can simply be invoked by findAllPaths() without any arguments def findAllPaths(self, position=0, solution=[]): #if position is invalid or already in solution, returning from method #(base case 1) if position = len(self.vector) or position in solution: return #flag here #otherwise appending position to solution solution.append(position) #if this is last position, appending this solution to self.paths list (base case 2) if position == len(self.vector) - 1: self.paths.append(solution) else: #otherwise, finding value contained at this position value = self.vector[position] #recursively finding all paths value locations away from this position, # forward and backward. passing a copy of solution list as parameter to each call. self.findAllPaths(position + value, solution.copy()) self.findAllPaths(position - value, solution.copy())

def getPaths(self): # Return the list of viable paths, or [None] if there are no solutions if self.paths == []: #returning a list containing None return [None] else: #returning the paths list return self.paths

ProblemTester.py:

import random import string import re #Module Imports import sys from importlib import import_module

def generate(size): arr = [None] * size

arr[size-1] = 0 for i in range(0, size-2): arr[i] = random.randint(1, size)

return arr

def pathTest(vector, path): def pathTest_(vector, path, position, location): if(location == len(path)-1): if(position == len(vector) -1 ): return True else: return False elif location >= len(vector) or location

return pathTest_(vector, path, 0,0)

def Test(lib, seed=0, size=10, verbose=False): known = [ ([2, 8, 3, 2, 7, 2, 2, 3, 2, 1, 3, 0], 4), # Many solutions, handle it ([2,3,1,1,0], 2), # Simple infinite loops ([3, 1, 1, 1, 3, 4, 2, 5, 3, 0], 0), # Zero solutions ([4,3,1,2,3,5,4,2,2,1,1,0], 5), # Complicated loops ([4,4,1,2,3,1,8,2,0],0) # Infinite loops, zero solutions ] for (vector, solutions) in known: finder = lib.Pathfinder(vector) count = 0 if verbose: print(f"Vector: {vector}") for path in finder.getPaths(): if pathTest(vector, path): count+= 1 if verbose: print("Valid soltion: ", end="") print(path) else: if verbose: print("Error: Invalid path returned") return False if count != solutions: if verbose: print("Error: Incorrect number of solutions") return False if verbose: print()

yield True if __name__ == "__main__": if len(sys.argv)

print(f"Test result: {score}/5")

ProblemAttempt.py

Error:

Error:

(base) C:\Users\Tr\Downloads>python ProblemTester.py problemattempt.py Testing module problemattempt Vector: [2, 8, 3, 2, 7, 2, 2, 3, 2, 1, 3, 0] Traceback (most recent call last): File "ProblemTester.py", line 76, in for i in Test(module,seed=123456, size=20, verbose=True): File "ProblemTester.py", line 48, in Test if pathTest(vector, path): File "ProblemTester.py", line 30, in pathTest return pathTest_(vector, path, 0,0) File "ProblemTester.py", line 20, in pathTest_ if(location == len(path)-1): TypeError: object of type 'NoneType' has no len()

OU AWNA ProblemTester.py X problemattempt.py X 1 class Pathfinder(): def_init__(self, vector): # Initialize the Pathfinder object self.vector = vector self.paths = [] #self. findAllPaths(,[] 10 #updated the method signature to use default value of 9 for position and empty list for solution #so that the method can simply be invoked by findAllPaths without any arguments def findAllPaths(self, position=0, solution=[]): #if position is invalid or already in solution, returning from method #(base case 1) if position = len(self.vector) or position in solution: return #flag here #otherwise appending position to solution solution.append(position) #if this is Last position, appending this solution to self.paths List (base case 2) if position == len(self.vector) - 1: self.paths.append( solution) else: #otherwise, finding value contained at this position value = self.vector position #recursively finding all paths value Locations away from this position, # forward and backward. passing a copy of solution List as parameter to each call. self.findAllPaths (position + value, solution.copy()) self.findAllPaths (position - value, solution.copy) def getPaths(self): # Return the list of viable paths, or [None] if there are no solutions if self.paths == []: #returning a list containing None return [None] else: #returning the paths List return self.paths A ProblemTester.py problemattempt.py 3 1 import random 2 import string 3 import re 4 Module Imports 5 import sys 6 from importlib import import module 8 def generate(size): arr = [None) * size 11 12 arr[size-1] - 14 for i in range(e, size-2): arr[1] = random.randint(1, size) 16 return arr 17 18 def pathTest(vector, path); def pathtest_(vector, path, position, location): if(location == len(path)-1): if(position -- len(vector) -1 ): return True else: return false elif location >= len(vector) or location python ProblemTester.py problemattempt.py Testing module problemattempt Vector: [2, 8, 3, 2, 7, 2, 2, 3, 2, 1, 3, 0] Traceback (most recent call last): File "ProblemTester.py", line 76, in for i in Test(module, seed=123456, size=20, verbose=True): File "ProblemTester.py", line 48, in Test if pathTest(vector, path): File "ProblemTester.py", line 30, in pathTest return pathTest_(vector, path, 0,0) File "ProblemTester.py", line 20, in pathTest_ if(location == len(path)-1): TypeError: object of type 'None Type' has no len() (base) C:\Users\ r \Downloads>