13
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ I've modified the formatting somewhat to increase readability. What Python version did you write this for? \$\endgroup\$ Commented Jul 17, 2018 at 12:28
  • \$\begingroup\$ @Mast All the submitted code is run in Python 2.7.6 \$\endgroup\$ Commented Jul 17, 2018 at 14:26

1 Answer 1

Reset to default
5
\$\begingroup\$

SPOILER ALERT

This puzzle is a very slight modification of the well-known 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.

\$\endgroup\$
4
  • \$\begingroup\$ Quite right, very good review! \$\endgroup\$ Commented Jul 18, 2018 at 5:26
  • 1
    \$\begingroup\$ "So that's how they expect you to do it". It might be, but I think that (unless you have an undisclosed connection to the team behind the contest site) this overstates the case because there's another (asymptotically) equally efficient approach: run single-source shortest paths from the start and the end, allowing entry into the blocked squares but not exit; and then find the minimum over all squares of the total distance from the two ends. \$\endgroup\$ Commented Jul 18, 2018 at 6:33
  • \$\begingroup\$ @PeterTaylor: I do not have such an undisclosed connection (although if I did, by definition I wouldn't disclose it ;)) — and you're right, that's an equally valid solution. I imagine it might do a little more work than A* in this case, but it'd definitely fix OP's running-time problem just as thoroughly. \$\endgroup\$ Commented Jul 18, 2018 at 19:28
  • \$\begingroup\$ Thank you @Quuxplusone! After using A* search as you suggested, my solution passed all test cases without the "time-limit-exceeded" error, and was accepted. \$\endgroup\$ Commented Jul 20, 2018 at 12:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.