6
\$\begingroup\$

One week ago, an answer was given on Stack Overflow to help someone with a game that was being written. In particular, the question was regarding how to place boats on a finite grid so that they were not adjacent to each other. Most answers given were functional in nature, but the solution brought here is object-oriented. The following class is submitted for review.

Please provide any critiques you wish against the code below. However, please keep the algorithm the same so that I can improve coding in this domain.

class Board:
    def __init__(self, width, height):
        self.__width = width
        self.__height = height
        self.__matrix = [[False] * height for _ in range(width)]
        self.__available = {Point(x, y)
                            for x in range(width)
                            for y in range(height)}

    def __str__(self):
        width = self.__width * 2 + 1
        height = self.__height * 2 + 1
        grid = [[' '] * width for _ in range(height)]
        for yo, xo, character in (0, 1, '|'), (1, 0, '-'), (1, 1, '+'):
            for y in range(yo, height, 2):
                for x in range(xo, width, 2):
                    grid[y][x] = character
        for x, column in enumerate(self.__matrix):
            for y, cell in enumerate(column):
                if cell:
                    grid[y << 1][x << 1] = '#'
        return '\n'.join(''.join(row) for row in grid)

    # noinspection PyAssignmentToLoopOrWithParameter
    def place_boats(self, sizes, patience=10):
        matrix_backup = [column.copy() for column in self.__matrix]
        available_backup = self.__available.copy()
        for _ in range(patience):
            # try to place all the boats
            for size in sizes:
                for _ in range(patience):
                    # try to place boat of current size
                    point = random.choice(tuple(self.__available))
                    method = random.choice(tuple(Orientation))
                    try:
                        # try to place a boat; does not mangle the matrix
                        self.make_boat(point, size, method)
                    except RuntimeError:
                        pass
                    else:
                        # break out of inner patience loop; go to next size
                        break  # on success
                else:
                    # break to outer patience loop; start from beginning
                    self.__matrix = [column.copy() for column in matrix_backup]
                    self.__available = available_backup.copy()
                    break  # on failure
            else:
                # break out of outer patience loop; all sizes were placed
                break  # on success
        else:
            raise RuntimeError('could not place the requested boats')

    def make_boat(self, point, size, method):
        backup = [column.copy() for column in self.__matrix]
        unusable = set()
        for offset in range(size):
            if method is Orientation.HORIZONTAL:
                block = self.mark_cell(point, x_offset=offset)
            elif method is Orientation.VERTICAL:
                block = self.mark_cell(point, y_offset=offset)
            else:
                raise ValueError('method was not understood')
            if block:
                unusable.update(block)
            else:
                self.__matrix = backup
                raise RuntimeError('cannot place boat')
        self.__available -= unusable

    def mark_cell(self, point, *, x_offset=0, y_offset=0):
        target = Point(point.x + x_offset, point.y + y_offset)
        if target in self.__available and \
                0 <= target.x < self.__width and \
                0 <= target.y < self.__height:
            self.__matrix[target.x][target.y] = True
            return {Point(target.x + xo, target.y + yo)
                    for xo in range(-1, 2)
                    for yo in range(-1, 2)}

In case you are wondering what the method in question looked like in its original form, it is provided below for comparison. The original version was demonstrably incorrect, less efficient, and commented poorly. The biggest issue with it is the difficulty in trying to wrap one's mind around the usage of the for, else, and break keywords. What happens at each level can be difficult to follow, and that is why extensive comments were added to the version shown above.

    def place_boats(self, sizes, patience=100):
        primary_matrix_backup = copy.deepcopy(self.matrix)
        primary_available_backup = copy.deepcopy(self.available)
        for _ in range(patience):
            # try to place all the boats
            for size in sizes:
                secondary_matrix_backup = copy.deepcopy(self.matrix)
                secondary_available_backup = copy.deepcopy(self.available)
                for _ in range(patience):
                    # try to place boat of current size
                    y, x = random.choice(tuple(self.available))
                    method = random.choice(('horizontal', 'vertical'))
                    try:
                        unusable = self.make_boat(y, x, size, method)
                    except ValueError:
                        pass
                    else:
                        self.available -= unusable
                        break  # on success
                else:
                    self.matrix = secondary_matrix_backup
                    self.available = secondary_available_backup
                    break  # on failure
            else:
                break  # on success
        else:
            self.matrix = primary_matrix_backup
            self.available = primary_available_backup
            raise ValueError('could not place the requested boats')

Is the place_boats method sufficiently clear and understandable, and were the three keywords used in a way becoming to the language?

\$\endgroup\$
3
\$\begingroup\$

On for ... else constructs

else blocks on loops are difficult to graps, no matter what. Don't get me wrong, I love them, but:

  • they are named poorly: else is already associated to if and except for which they have an obvious meaning. for ... else on the other hand (or while ... else for that matter) does not have an obvious meaning and can't easily carry the "if the for did not break" they are meant to implement. nobreak would have been better for that matter.
  • they are structures that are not present in other major languages, thus reader are most likely not used to the idiom.

For these reasons, I would recommend to use them sparingly. Not 3 at once. And especially not in association with a try ... except ... else; which add to the already existing confusion.

More often than not, you can save yourself the use of an else block by using return rather than break. But this can mean breaking out of too many loops, so a second thing to do is to split nested loops into several functions where you could return safely. A first rewrite of place_boats would yield:

def place_boats(self, sizes, patience=10):
    matrix_backup = [column.copy() for column in self.__matrix]
    available_backup = self.__available.copy()
    for _ in range(patience):
        # try to place all the boats
        for size in sizes:
            if not self.place_selected_boat(size, patience):
                # break to outer patience loop; start from beginning
                self.__matrix = [column.copy() for column in matrix_backup]
                self.__available = available_backup.copy()
                break  # on failure
        else:
            return

    raise RuntimeError('could not place the requested boats')

def place_selected_boat(self, size, patience):
    for _ in range(patience):
        # try to place boat of current size
        point = random.choice(tuple(self.__available))
        method = random.choice(tuple(Orientation))
        try:
            # try to place a boat; does not mangle the matrix
            self.make_boat(point, size, method)
        except RuntimeError:
            pass
        else:
            return True

(if you don't like the implicit return None you can still add a return False statement at the very end of place_selected_boat)

The code already seems more manageable, but we can remove this last for ... else by "inverting" the if and the for thanks to all():

def place_boats(self, sizes, patience=10):
    matrix_backup = [column.copy() for column in self.__matrix]
    available_backup = self.__available.copy()
    for _ in range(patience):
        if all(self.place_selected_boat(size, patience) for size in sizes):
            return
        else:
            self.__matrix = [column.copy() for column in matrix_backup]
            self.__available = available_backup.copy()

    raise RuntimeError('could not place the requested boats')

def place_selected_boat(self, size, patience):
    for _ in range(patience):
        # try to place boat of current size
        point = random.choice(tuple(self.__available))
        method = random.choice(tuple(Orientation))
        try:
            # try to place a boat; does not mangle the matrix
            self.make_boat(point, size, method)
        except RuntimeError:
            pass
        else:
            return True

Which seems more understandable at first.

On using exceptions

RuntimeError is a very generic exception that can happen for a variety of reasons. This feels off as an exception to raise manually.

The recommendation is to:

Design exception hierarchies based on the distinctions that code catching the exceptions is likely to need, rather than the locations where the exceptions are raised. Aim to answer the question "What went wrong?" programmatically, rather than only stating that "A problem occurred" (see PEP 3151 for an example of this lesson being learned for the builtin exception hierarchy)

So you most likely want to build something like:

class BaseBoatPlacerException(Exception):
    pass

class IncorrectDirectionException(BaseBoatPlacerException, ValueError):
    pass

class UnplaceableBoatException(BaseBoatPlacerException):
    pass

And use the last two exceptions instead of ValueErrors and RuntimeErrors.

You can also simplify your exception handling by using contextlib.suppress rather than empty except blocks:

def place_boats(self, sizes, patience=10):
    matrix_backup = [column.copy() for column in self.__matrix]
    available_backup = self.__available.copy()
    for _ in range(patience):
        if all(self.place_selected_boat(size, patience) for size in sizes):
            return
        else:
            self.__matrix = [column.copy() for column in matrix_backup]
            self.__available = available_backup.copy()

    raise UnplaceableBoatException('could not place the requested boats')

def place_selected_boat(self, size, patience):
    for _ in range(patience):
        point = random.choice(tuple(self.__available))
        method = random.choice(tuple(Orientation))
        with suppress(UnplaceableBoatException):
            self.make_boat(point, size, method)
            return True

On using a matrix in your algorithm at all

Instead of storing both the state of your board as a grid and the available positions in a set, why don't you drop the grid? It's purpose is only for representation and the "real work" only necessitate the available set.

In the same vein, you could simplify the whole algorithm by removing positions from self.available and only maintaining an second set of removed positions for backup purposes:

import enum
import random
from contextlib import suppress
from collections import namedtuple


Point = namedtuple('Point', 'x y')


class BaseBoatPlacerException(Exception):
    pass


class IncorrectDirectionException(BaseBoatPlacerException, ValueError):
    pass


class UnplaceableBoatException(BaseBoatPlacerException):
    pass


class Orientation(enum.Enum):
    HORIZONTAL = 1
    VERTICAL = 2


class Board:
    def __init__(self, width, height):
        self.__width = width
        self.__height = height
        self.__available = {
                Point(x, y)
                for x in range(width)
                for y in range(height)
        }

    def place_boats(self, sizes, patience=10):
        for _ in range(patience):
            removed_positions = set()
            if all(self.place_selected_boat(size, patience, removed_positions) for size in sizes):
                return
            else:
                self.__available.update(removed_positions)

        raise UnplaceableBoatException('could not place the requested boats')

    def place_selected_boat(self, size, patience, removed):
        for _ in range(patience):
            point = random.choice(tuple(self.__available))
            method = random.choice(tuple(Orientation))
            with suppress(UnplaceableBoatException):
                self.make_boat(point, size, method, removed)
                return True

    def make_boat(self, point, size, method, removed):
        x_offset, y_offset = 1, 1
        if method is Orientation.HORIZONTAL:
            x_offset = size
        elif method is Orientation.VERTICAL:
            y_offset = size
        else:
            raise IncorrectDirectionException('method was not understood')

        positions = {
            Point(point.x + x, point.y + y)
            for x in range(x_offset)
            for y in range(y_offset)
        }
        # Make sure no boat touch each other
        surroundings = {
            Point(point.x + x, point.y + y)
            for point in positions
            for x, y in ((1, 0), (-1, 0), (0, 1), (0, -1))
        }
        if not ((positions + surroundings) <= self.__available):
            raise UnplaceableBoatException('boat cannot be placed')

        self.__available -= positions
        removed.update(positions)

    def __str__(self):
        inter_line = '+'.join('-' * self.__width)
        line_separator = '\n{}\n'.format(inter_line)
        return line_separator.join(
                '|'.join(
                    ' ' if Point(x, y) in self.__available else '#'
                    for x in range(self.__width)
                ) for y in range(self.__height)
        )
\$\endgroup\$
  • \$\begingroup\$ Thank you for providing such a detailed review! I will probably wait a few days before accepting any answer in case others want to provide their own critiques. Seeing the mess of for, else, and break keywords removed is great. Would you mind commenting about whether or not you see any elegance to Python's use of those keywords in the context of a for loop? \$\endgroup\$ – Noctis Skytower Nov 22 '17 at 14:20
  • \$\begingroup\$ Also, I just noticed a bug in the final version of your code that probably stems from a misunderstanding of what self.__available is meant to track. As was mentioned in the first paragraph and second sentence of the question, boats are not allowed to be adjacent to each other. If you look at the mark_cell method, you will notice that it returns a 3x3 block of points around the target cell on success. When a boat is successfully placed, the union of all those blocks is no longer available for boat placement. This prevents boats from ever touching each other. \$\endgroup\$ – Noctis Skytower Nov 22 '17 at 14:30
  • \$\begingroup\$ @NoctisSkytower Oh, right, my bad, didn't pay enough attention. I will think about it and check wether it's worth keeping this part in or not. And about the for ... else construct, I already gave my views in the first part of the answer, I don't really understand what you are asking then. \$\endgroup\$ – Mathias Ettinger Nov 22 '17 at 17:31
  • \$\begingroup\$ In other words, do you think that a newly designed language would benefit enough from a concept similar to Python's for/else to warrant inclusion in its design? \$\endgroup\$ – Noctis Skytower Nov 22 '17 at 17:48
  • \$\begingroup\$ @NoctisSkytower sorry for the late reply. I'd say it completely depends of the aims of the language. It kinda fits in Python as it can help reduce clutter and extra variables (e.g. I'd rather use for..if..break..else than next(..for..if..) or next(filter(..))). But its usage should be very rare and most of the time can be avoided with a more beautiful code layout. \$\endgroup\$ – Mathias Ettinger Nov 27 '17 at 8:44

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.