Placing boats on a game board by intelligent trial and error

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?

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)
)

• 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? – Noctis Skytower Nov 22 '17 at 14:20
• 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. – Noctis Skytower Nov 22 '17 at 14:30
• @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. – Mathias Ettinger Nov 22 '17 at 17:31
• 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? – Noctis Skytower Nov 22 '17 at 17:48
• @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. – Mathias Ettinger Nov 27 '17 at 8:44