trjhtr

I've exceeded the time limit for my challenge at this point, so I was curious what further optimizations I could have made to my code, as it was exceeding the execution time limit allowed.

import sys
class maze_search_with_wall_removal():
 def __init__(self, input_maze):
 #pre-compute the range of values in our len of x and y dimensions
 self.maze = input_maze
 self.x_len = len(input_maze)
 self.y_len = len(input_maze[-1])
 # set values to be very large for comparison's sake
 self.cost = [[sys.maxsize for x in range(self.x_len)] for y in range(self.y_len)]
 self.x_range = range(self.x_len)
 self.y_range = range(self.y_len)

 def dfs_recursive(self, x, y, current_cost=1, wall_consumed=False):
 # proceed if our current state is within bounds of maze
 if current_cost > self.cost[self.x_len - 1][self.y_len - 1]:
 return
 #check if the cost is worth considering the rest of these computations
 if current_cost > self.cost[x][y]:
 return
 if current_cost < self.cost[x][y]:
 self.cost[x][y] = current_cost

 #if the position we are considering is a wall
 if self.isWall(x, y):
 if wall_consumed == True:
 return
 else:
 wall_consumed = True

 x_y = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 for positions in x_y:
 x_i, y_i = x + positions[0], y + positions[1]
 if x_i not in self.x_range or y_i not in self.y_range:
 continue
 self.dfs_recursive(x_i, y_i, current_cost+1, wall_consumed)

 def isWall(self, x, y):
 if self.maze[x][y] == 1:
 return True
 else:
 return False

 def get_terminal_cost(self):
 return self.cost[self.x_len - 1][self.y_len - 1]

def answer(maze):
 #must be a square with a dimensional range of [2, 20] inclusive
 if len(maze) in range(2, 20) and len(maze[0]) in range(2,20):
 my_maze = maze_search_with_wall_removal(maze)
 my_maze.dfs_recursive(0, 0)
 return my_maze.get_terminal_cost()
 else:
 return 0

I was thinking that would have to cut the recursion out- but I don't think that would be such a huge source of inefficiency.

Likewise, I tried pre-computing whether or not the x_i and y_i values were within an acceptable range so as to avoid additional/needless function calls.