trjhtr

I'm currently working through the google FooBar challenge, and I'm on the third level, in which I have to find the distance between the top left and bottom right points on a grid. The grid is filled by ones and zeros, with zeros representing crossable spaces and ones representing non-crossable spaces (a typical grid would look like this):

[[0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 1, 1, 1, 1, 1],
 [0, 1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 0]]

In each grid you must find the length (int) of the shortest route with from the top left to bottom right, but are allowed to replace any singular one with a zero. My code (shown below) solves through these grids, but doesn't run fast enough to satisfy google's runtime limit. I'd greatly appreciate any advice on how to shorten or make more efficient my code. An in-depth explanation of each class method is below the code itself.

from itertools import chain
from copy import copy, deepcopy

class Map(object):

 def __init__(self, map):
 self.orig_map = deepcopy(map)
 self.map = map
 self.current_point = None
 self.current_neighbors = None
 self.entrance = (0, 0)
 self.exit = (len(self.map[0])-1, len(self.map)-1)
 self.zero_relations = None
 self.ones_positions = None
 self.min_path = None
 self.min_path_length = None

 def check_neighbors(self):
 self.current_neighbors = 
 "l": 
 "value": 1 if (self.current_point[0] == 0) else self.map[self.current_point[1]][self.current_point[0] - 1],
 "coord": (self.current_point[0]-1, self.current_point[1])
 ,
 "u": 
 "value": 1 if (self.current_point[1] == 0) else self.map[self.current_point[1] - 1][self.current_point[0]],
 "coord": (self.current_point[0], self.current_point[1]-1)
 ,
 "r": 
 "value": 1 if (self.current_point[0] == len(self.map[0]) - 1) else self.map[self.current_point[1]][
 self.current_point[0] + 1],
 "coord": (self.current_point[0] + 1, self.current_point[1])
 ,
 "d": 
 "value": 1 if (self.current_point[1] == len(self.map)-1) else self.map[self.current_point[1] + 1][self.current_point[0]],
 "coord": (self.current_point[0], self.current_point[1]+1)
 
 

 def check_value(self, point):
 return self.map[point[1]][point[0]]

 def map_zero_relations(self):
 all_relations = 
 for index, value in enumerate(list(chain.from_iterable(self.map))):
 point = (index%len(self.map), int(index/len(self.map)))
 self.current_point = point
 self.check_neighbors()
 neighbors = self.current_neighbors
 all_relations[point] = [neighbors[neighbor]["coord"] for neighbor in neighbors if (neighbors[neighbor]["value"]==0 and self.check_value(point)==0)]
 self.zero_relations = all_relations
 self.current_point = None

 def find_min_path(self, start, end, path=):
 path = path + [start]
 if start == end:
 self.min_path = path
 return
 if start not in self.zero_relations:
 return None
 shortest = None
 for node in self.zero_relations[start]:
 if node not in path:
 newpath = self.find_min_path(node, end, path)
 if newpath:
 if not shortest or len(newpath) < len(shortest):
 shortest = newpath
 return shortest

 def locate_passable_ones(self):
 points = [(index%len(self.map), int(index/len(self.map))) for index, value in enumerate(list(chain.from_iterable(self.map)))]
 ones_positions = [point for point in points if self.check_value(point) == 1]
 for point in copy(ones_positions):
 self.current_point = point
 self.check_neighbors()
 if [self.current_neighbors[neighbor]["value"] for neighbor in self.current_neighbors].count(1) >= 3:
 ones_positions.remove(point)
 self.current_point = None
 self.ones_positions = ones_positions

 def find_escape_min_length(self):
 self.find_min_path(self.entrance, self.exit)
 current_min_path = self.min_path
 orig_map = self.orig_map
 for wall in self.ones_positions:
 self.map = deepcopy(orig_map)
 self.map[wall[1]][wall[0]] = 0
 self.map_zero_relations()
 self.find_min_path(self.entrance, self.exit)
 if current_min_path is None:
 current_min_path = self.min_path
 continue
 if len(self.min_path) < len(current_min_path):
 current_min_path = self.min_path
 self.map = orig_map
 self.map_zero_relations()
 self.min_path = current_min_path
 self.min_path_length = len(current_min_path)

def answer(n):
 foo = Map(n)
 foo.map_zero_relations()
 foo.locate_passable_ones()
 foo.find_escape_min_length()
 return foo.min_path_length

NOTE: grid is read with the top left as (0,0) and the bottom right as (max_x, max_y).

Map Methods

Map.check_neighbors() -
sets the value of Map.current_neighbors to a dict with the value and coordinates of the left, right, upper, and lower points from Map.current_point

Map.check_value() -
returns the value of a point given its coordinate on the grid

Map.map_zero_relations() -
sets Map.zero_relations to a dict with each zero on the grid and a list of the coordinates of all zeros that point is connected to. The dict for above grid would be:

(0, 0): [(1, 0)],
 (0, 1): ,
 (0, 2): [(1, 2), (0, 3)],
 (0, 3): [(0, 2), (0, 4)],
 (0, 4): [(0, 3), (0, 5)],
 (0, 5): [(0, 4), (1, 5)],
 (1, 0): [(0, 0), (2, 0)],
 (1, 1): ,
 (1, 2): [(0, 2), (2, 2)],
 (1, 3): ,
 (1, 4): ,
 (1, 5): [(0, 5), (2, 5)],
 (2, 0): [(1, 0), (3, 0)],
 (2, 1): ,
 (2, 2): [(1, 2), (3, 2)],
 (2, 3): ,
 (2, 4): ,
 (2, 5): [(1, 5), (3, 5)],
 (3, 0): [(2, 0), (4, 0)],
 (3, 1): ,
 (3, 2): [(2, 2), (4, 2)],
 (3, 3): ,
 (3, 4): ,
 (3, 5): [(2, 5), (4, 5)],
 (4, 0): [(3, 0), (5, 0)],
 (4, 1): ,
 (4, 2): [(3, 2), (5, 2)],
 (4, 3): ,
 (4, 4): ,
 (4, 5): [(3, 5), (5, 5)],
 (5, 0): [(4, 0), (5, 1)],
 (5, 1): [(5, 0), (5, 2)],
 (5, 2): [(4, 2), (5, 1)],
 (5, 3): ,
 (5, 4): ,
 (5, 5): [(4, 5)]

Map.find_min_path() - If unobstructed path between start and end is possible, sets Map.min_path to a list of coords you'd travel over in the shortest path. If not possible, sets Map.min_path to None.

Map.locate_passable_ones() - Sets Map.ones_positions a list of coordinates with the value of 1 that should be removed and tested to find shorter routes in Map.find_escape_min_length(). Ones with 3 or more neighboring ones are removed.

Map.find_escape_min_length() - Finds shortest path without removing any ones. Then tries finding shortest path while individually replacing each point in Map.ones_positions with zeros. Sets self.min_path and self.min_path_length to the shortest path and path length found.

Map Attributes

Map.orig_map - Stores original state of the grid

Map.map - Stores current state of the grid

Map.current_point - Stores current coordinate (used in Map.check_neighbors)

Map.current_neighbors - Stores the current point's neighbor's coords and values

Map.entrance - stores the grid start point (always (0,0) )

Map.exit - stores the grid end point ( (max_x, max_y) )

Map.zero_relations - stores dict with all zeros and connected zeros on grid

Map.ones_positions - stores list of ones to be removed and tested for shorter path lengths

Map.min_path - stores current minimum path from start to end of grid

Map.min_path_length - stores length of minimum path

SPOILER ALERT

This puzzle is a very slight modification of the well-known fuzzy string matching problem, which can be solved efficiently using (what else?) dynamic programming. Imagine you're a bunny running through the maze; and your "change a 1 to a 0" superpower is represented by a physical inventory item, such as a bomb. Then the solution is to do your usual path-finding algorithm (e.g., use something like A-star), but in addition to the usual state stuff (e.g. "x coordinate", "y coordinate", and "estimated distance to goal"), you also keep one extra boolean: "Did I use my bomb yet?"

When evaluating the possible routes out of a given state (x, y, estimated, used_bomb), if used_bomb is false, then any direction is treated as passable (but if passing through a wall, the resulting state will end up with used_bomb=true). If used_bomb is true, then only directions without walls are treated as passable.

So that's how they expect you to do it.

END SPOILERS

Style-wise, I have a few nits to pick on your current solution anyway.

First, Map is a pretty confusing name for your God Object. Python already has a map function, and a dict type that's known as map in some other languages, but your Map doesn't resemble either of those. Of course you should get rid of the God Object altogether; but if you must keep it, you should name it something like Solver or BunnyPuzzle — something that indicates exactly how domain-specific it really is.

Speaking of names, n is an awful name for anything that is not an integer! In your case, I believe it's a list-of-lists?

I would tend to rewrite your main function (answer) so that the flow of data becomes clear... and especially so that we see where your quadratic behavior is coming from — that for loop that used to be hidden inside find_escape_min_length! Now it's out in the open, where the maintainer can see it and think about ways to remove it (see SPOILER, above).

def answer(grid):
 width = len(grid[0])
 height = len(grid)
 ones = [(x,y) for x in range(width) for y in range(height) if grid[y][x] == 1]
 min_length = float('inf')
 for x,y in ones:
 newgrid = deepcopy(grid)
 newgrid[x][y] = 0
 min_length = min(min_length, get_path_length(newgrid))
 return min_length

Writing get_path_length is left as an exercise for the reader; but again, A-star seems like the right idea.