Checking within a range of field of fields

Question

I wasn't quite sure how to word the title, sorry if it doesn't make sense/is misleading.

Note - a "boat" is 3 O's next to each other in an array, so

_|O|_  _|_|_
_|O|_  O|O|O
 |O|    | |

are boats.

So I have an a list of lists (n x n) (working with lists) in which I generate n boats at random spaces. I don't want the boats to be next to each other, touch by corners, or be on top of each other.

A tried checking if a boat would end up on top of another boat in the vein of this:

if board[y - 2][x] == 'O' or board[y + 2][x] == 'O' ...

and so on, which ended up being unsurprisingly long.

I also got index out of range errors, since I was sometimes checking for coordinates not in the field.

So, is there a way I can check for boats in every direction without going out of index range?

Better yet, any ideas on how to make the boats not generate next to each other?

The code for boat generation is here:

from random import *

side = int(input())
game_state = []

def generate_initial_state():

    for i in range(side):
        game_state.append([])
        for j in range(side):
            game_state[i].append('.')

    for i in range(side):
        # Generate boat origin on random coordinates within the game board,
        # if there's a boat already, generate new ones
        y_cor = randint(0, side-1)
        x_cor = randint(0, side-1)
        while game_state[y_cor][x_cor] == 'O':
            y_cor = randint(0, side - 1)
            x_cor = randint(0, side - 1)
        # Direct chooses if the boat will be generated up, down, or sideways
        direct = randint(1, 4)
        cycle = 0

        while cycle < 3:
        # Generates a boat going from origin in one direction,
        # if the boat would end outside the board, chooses a different direction
            if direct == 1:
                if y_cor + 2 >= side:
                    direct = randint(1, 4)
                else:
                    game_state[y_cor + cycle][x_cor] = 'O'
                    cycle += 1
            elif direct == 2:
                if x_cor + 2 >= side:
                    direct = randint(1, 4)
                else:
                    game_state[y_cor][x_cor + cycle] = 'O'
                    cycle += 1
            elif direct == 3:
                if y_cor - 2 < 0:
                    direct = randint(1, 4)
                else:
                    game_state[y_cor - cycle][x_cor] = 'O'
                    cycle += 1
            elif direct == 4:
                if x_cor - 2 < 0:
                    direct = randint(1, 4)
                else:
                    game_state[y_cor][x_cor - cycle] = 'O'
                    cycle += 1

for i in range(side):
    print(*game_state[i])

Answer 1

First I would only use two directions (horizontal and vertical), which shouldn't change the probabilities (with your model, a boat can be generated in two ways).

This allows index overflow to only occur by exceeding the allowable indices, which provokes an IndexError that can be intercepted (using a negative index doesn't and that could mess up your generator).

Secondly, using a flag could help you do the trick.

I added a few other modifications :

EDIT : I just realized that my code was rejecting perfectly valid boats if they were on the border, so here is a version that doesn't.

Update : some explanations

We use a boolean flag boat_built to track the suitability of a randomly chosen position of the boat: once all tests are made, this variable decides if the choice was suitable (True) or if obstructions were encountered while tests were carried out (False).

Using

boat_built &= (game_state[x_cor + k*dx][y_cor + k*dy] != "0")

we update the flag for every test : if boat_built was False before the test, it will remain False regardless of the test's result (False & a = False): this is intended, because it means that an obstruction has already been encountered and the boat is invalid.

On the other hand, if boat_built was True before the test, it will contain the result of the test afterwards (True & a = a): this is also intended, since failing the new test means we now have found an obstruction.

Note that all 15 tests are carried out for every boat, even if an obstruction is encountered early on.

from random import *

side = int(input())

game_state = [['.' for i in range(side)] for j in range(side)]

l_dir = [(1, 0), (0, 1)]

def generate_initial_state():

    for i in range(side):
        boat_built = False
        while not boat_built:
            boat_built = True

            y_cor = randrange(side)
            x_cor = randrange(side)

            dx, dy = l_dir[randrange(2)]

            try:
                # check that the three required cells are empty
                for k in range(3):
                    boat_built &= (game_state[x_cor + k*dx][y_cor + k*dy] != "0")
            except IndexError:
                # if any is out of range, choice is invalid
                boat_built = False

            for k in range(5):
                for l in [-1, 1]:
                    try:
                        # check if neighbours on the long sides are empty
                        boat_built &= (game_state[x_cor + (k-1)*dx + l*dy][y_cor + l*dx + (k-1)*dy] != "0")
                    except IndexError:
                        # if we're out of range, no obstruction
                        pass

            for k in [-1, 3]:
                try:
                    # check if neighbours on the short sides are empty
                    boat_built &= (game_state[x_cor + k*dx][y_cor + k*dy] != "0")
                except IndexError:
                    # again, if we're out of range, no obstruction
                    pass


        # if we reach this point, a valid position has been found
        for k in range(3):
            game_state[x_cor + k*dx][y_cor + k*dy] = "0"


generate_initial_state()

for i in range(side):
    print(*game_state[i])

Answer 2

You can try the following class and see if it solves your problem:

#! /usr/bin/env python3
import collections
import enum
import random


def main():
    board = Board(10, 10)
    print(board)
    board.place_boats([2, 3, 3, 4, 5])
    print('\n' + '=' * 21 + '\n')
    print(board)


Point = collections.namedtuple('Point', 'x, y')
# noinspection PyArgumentList
Orientation = enum.Enum('Orientation', 'HORIZONTAL, VERTICAL')


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


if __name__ == '__main__':
    main()

Answer 3

Your code has, as you complain, too much tedious repeated logic to inspect a point's neighbors. You could turn four tests into one with something like this:

    offset = [
        (0, -1),
        (-1, 0), (1, 0),
        (0, 1),
    ]
    for xoff, yoff in offset:
        if game_state[x + xoff * cycle][y + yoff * cycle] == 'O':
            report_collision(x, y)

Additionally, you could mark the grid with both 'O' for "boat" and 'o' for "bordering a boat", to simplify detecting adjacent boats.