6
\$\begingroup\$

The program below was made for a game named CheckIO, and it works. I'm just wondering if there is any way to make the code more readable.

edit: hi luke15g

def checkio(maze_map):
    #the walls of the maze are already surrounded by 1's
    start_x,start_y=1,1
    stop_x,stop_y=10,10
    class Point:
        directions={'N':(-1,0),'W':(0,-1),'E':(0,1),'S':(1,0)}
        def __init__(self,other=None,direction=None):
            if other!=None:
                self.road=other.road+direction
                self.x=other.x+Point.directions[direction][0]
                self.y=other.y+Point.directions[direction][1]
            else:
                self.x,self.y=None,None
                self.road=''
        def hit(self):
            return maze_map[self.x][self.y]==1
        def new_point(self):
            for char in Point.directions:
                x=Point(self,char)
                if not x.hit():
                    yield x
        def found_it(self):
            return self.x==stop_x and self.y==stop_y
    p=[Point()]
    p[0].x,p[0].y=start_x,start_y
    begin=0
    maze_map[start_x][start_y]=1
    while begin<=len(p)-1:
        if p[begin].found_it():
            return p[begin].road
        x=p[begin].new_point()
        while 1:
            try:
                new=next(x)
            except StopIteration:
                break
            p.append(new)
            maze_map[new.x][new.y]=1
        begin+=1
\$\endgroup\$
  • \$\begingroup\$ Is this in Python 2.x or 3.x? \$\endgroup\$ – jonrsharpe May 31 '15 at 10:41
  • \$\begingroup\$ It's version 3.3 \$\endgroup\$ – Costea Vlad Alexandru May 31 '15 at 10:58
6
\$\begingroup\$

In terms of readability:

  • There is no reason to nest the class inside the function (your current need to do so is caused by bad design, see below); doing so just distracts the reader from the actual business of the function.
  • Both function and class (and the class's methods) should have docstrings explaining what they do.
  • Python has a bool type, so while 1: is generally written while True:.
  • You mostly follow the style guide, but a bit more whitespace (e.g. around methods, assignments) would be helpful.

On Point itself:

  • directions is a constant, so should be UPPERCASE_WITH_UNDERSCORES to indicate as much: DIRECTIONS.
  • It seems odd to take an other Point instance to __init__. This is particularly awkward when you have p = [Point()]; p[0].x, p[0].y = start_x, start_y - contrast with [Point(start_x, start_y)]. Move the functionality for creating a Point from an existing instance into a @classmethod, so you would call x = Point.from_point(self, char).
  • road, the path of directions taken to get to the current point, could be a list instead of a str.
  • Rather than found_it, refactor to is_at(self, x, y), so you don't have to have stop_x and stop_y in scope (see above) and if p[begin].found_it(): becomes if p[begin].is_at(stop_x, stop_y):, which is a little more explicit.
  • Similarly, hit and new_point should take the maze_map as a parameter, rather than relying on scope.
  • hit is only called within the class, so should probably be private-by-convention (i.e. named _hit instead).
  • Point.directions is also accessible via self.directions, which will handle inheritance better.
  • new_point yields more than one Point, so should be plural (new_points).

With these modifications:

class Point:

    DIRECTIONS = {'N': (-1, 0), 'W': (0, -1), 'E': (0, 1), 'S': (1, 0)}

    def __init__(self, x, y, road=None):
        self.x, self.y = x, y
        self.road = road or []

    @classmethod
    def from_point(cls, other, direction):
        """Create a new point from an existing point and direction."""
        d_x, d_y = cls.DIRECTIONS[direction]
        return cls(
            other.x + d_x, 
            other.y + d_y, 
            other.road + [direction],
        )

    def _hit(self, map):
        """Would this point hit a wall in the map?"""
        return map[self.x][self.y] == 1

    def new_points(self, map):
        """Generate new points from the current point."""
        for char in self.directions:
            new_point = Point.from_point(self, char)
            if not new_point._hit(map):
                yield new_point

    def is_at(self, x, y):
        """Whether the point is at the specified location."""
        return self.x == x and self.y == y

And on the checkio function:

  • You can neaten while begin <= len(p) - 1: to while begin < len(p):.
  • The names are pretty bad - p should be points, begin should be current (it's only begin at the beginning!).
  • The while 1: loop would be much neater if you just iterated over new_points: for point in points[current].new_points():.

As modified:

def checkio(maze_map):
    """Solve the maze.

    The walls of the maze are already surrounded by 1s.

    """
    start_x, start_y = 1, 1
    stop_x, stop_y = 10, 10
    points = [Point(start_x, start_y)]
    current = 0
    maze_map[start_x][start_y] = 1
    while current < len(points):
        if points[current].is_at(stop_x, stop_y):
            return ''.join(points[current].road)
        for new_point in points[current].new_points(maze_map):
            points.append(new_point)
            maze_map[new_point.x][new_point.y] = 1
        current += 1

If you implemented __eq__ and __hash__ on the Point class, you could keep a set of the points you've already visited, rather than adding a "wall" into the map when you visit a particular location.

\$\endgroup\$
2
\$\begingroup\$

Point

It would help a lot if Point did not have to know about how to read the maze. Instead, it should concentrate on being a coordinate and crumbtrail. The hit() and found_it() functionality should move into a Maze class.

The fact that you wrote start_x,start_y and stop_x,stop_y indicates that Point is not doing its job — it should be more like start = Point(1, 1). p=[Point()]; p[0].x,p[0].y=start_x,start_y is even weirder — it should be queue = [start]. The 0 in self.x=other.x+Point.directions[direction][0] is also rather mysterious. The remedy for all of these problems is to make Point into a namedtuple.

According to your directions, the +x axis points south, and the +y axis points east. It would be more conventional to rename x and y as "row" and "column".

Maze

Now that we have a Point, it would be helpful have a way to fetch and set the value at a Point. For that, we define a Maze class, with an overridden [] operator.

With all the clutter out of the way, what remains is a solve() method that processes the queue. I suggest renaming p to queue and using idiomatic iteration techniques.

Suggested solution

from collections import namedtuple

class Point(namedtuple('Point', ['r', 'c'])):
    def __init__(self, r, c):
        self.src = None

    def __add__(self, other):
        return Point(self.r + other.r, self.c + other.c)

    def __sub__(self, other):
        return self + -other

    def __neg__(self):
        return Point(-self.r, -self.c)

    @property
    def neighbors(self):
        for delta in Point.DIRECTIONS:
            p = self + delta
            p.src = self
            yield p

    @property
    def path(self):
        if self.src is not None:
            yield from self.src.path
            yield Point.DIRECTIONS[self - self.src]

Point.DIRECTIONS = {
                        Point(-1, 0): 'N',
        Point(0, -1): 'W',              Point(0, +1): 'E',
                        Point(+1, 0): 'S',
}

class Maze:
    def __init__(self, maze_map):
        """maze_map is a two-dimensional array, where each 1 indicates an
           obstacle.  The walls of the maze must be surrounded by 1's."""
        self.maze_map = [row[:] for row in maze_map]

    def __getitem__(self, point):
        return self.maze_map[point.r][point.c]

    def __setitem__(self, point, value):
        self.maze_map[point.r][point.c] = value

    def solve(self, start=Point(1, 1), goal=Point(10, 10)):
        def enqueue(queue, point):
            if not self[point]:
                self[point] = 1
                queue.append(point)

        queue = []
        if start == goal:
            return start.path
        enqueue(queue, start)

        for point in queue:
            for neighbor in point.neighbors:
                if neighbor == goal:
                    return neighbor.path
                enqueue(queue, neighbor)


maze = Maze(…)
print(''.join(maze.solve()))
\$\endgroup\$
  • \$\begingroup\$ +1 for moving methods out of the Point class. But I still don't like the way this code uses Point.src. It shouldn't be the responsibility of a point to represent a path. \$\endgroup\$ – Gareth Rees Jun 1 '15 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.