3
\$\begingroup\$

I started learning python with the connect four game. Now I'm searching for the best way to get all diagonal and anti-diagonal rows of a matrix. It should work with any 2-dimensional matrix.

My code works, but there are certainly better ways to do the task. I get those rows with this generator:

def get_rows(self, width, height):
    # get horizontal rows
    for row in self.board:
        yield row
    # get vertical rows
    for col in range(width):
        yield [self.board[row][col] for row in range(height)]
    # get diagonal and anti-diagonal rows
    for num in range(width + height - 1):
        row = min(num, height - 1)
        col = max(0, num + 1 - height)
        yield [self.board[row-i][col+i]
               for i in range(min(height, width))
               if row-i >= 0 and col+i < width]
        row = max(0, num + 1 - width)
        col = max(0, width - 1 - num)
        yield [self.board[row+i][col+i]
               for i in range(min(height, width))
               if row+i < height and col+i < width]
    0   1   2   3   4   5

0  0,0 0,1 0,2 0,3 0,4 0,5
1  1,0 1,1 1,2 1,3 1,4 1,5
2  2,0 2,1 2,2 2,3 2,4 2,5
3  3,0 3,1 3,2 3,3 3,4 3,5

In this example board we need following rows:

diagonal:

[0,0]
[1,0] [0,1]
[2,0] [1,1] [0,2]
[3,0] [2,1] [1,2] [0,3]
[3,1] [2,2] [1,3] [0,4]
...
[3,4] [2,5]
[3,5]

anti-diagonal:

[0,5]
[0,4] [1,5]
...
[0,0] [1,1] [2,2] [3,3]
...
[3,0]

My generator creates the starting points of these rows and then adds respectively subtracts from them to get the next element. What do you think about it. How could it be improved (without using numpy)?

This is the whole code:

class ConnectFour:
    def __init__(self, width=7, height=6, win_amount=4):
        self.width, self.height = width, height
        self.win_amount = win_amount
        red, green, black = ('\x1b[1;31m', '\x1b[1;32m', '\x1b[0;0m')
        self.players = (green + ' O ' + black, red + ' O ' + black)
        self.board = [[''] * width for _ in range(height)]

    def print_board(self):
        print()
        for row in self.board:
            print('|'.join(elem.center(3) for elem in row))
            print('-' * (self.width * 4 - 1))
        print(*(str(x).center(3) for x in range(1, self.width+1)))
        print()

    def ask_number(self, player):
        while True:
            try:
                move = int(input('Choose a row,' + self.players[player] + ':')) - 1
                break
            except ValueError:
                print("That's not a number. Try again!")
        return move

    def move(self, player):
        while True:
            move = self.ask_number(player)
            if 0 <= move < self.width: break
            print('Choose a row between 1 and ', self.width, '!', sep='')
        for row in reversed(self.board):
            if row[move] == '':
                row[move] = self.players[player]
                return True
        print('This row is full. Try again!')
        self.move(player)

    def get_rows(self, width, height):
        # get horizontal rows
        for row in self.board:
            yield row
        # get vertical rows
        for col in range(width):
            yield [self.board[row][col] for row in range(height)]
        # get diagonal and anti-diagonal rows
        for num in range(width + height - 1):
            row = min(num, height - 1)
            col = max(0, num + 1 - height)
            yield [self.board[row-i][col+i]
                   for i in range(min(height, width))
                   if row-i >= 0 and col+i < width]
            row = max(0, num + 1 - width)
            col = max(0, width - 1 - num)
            yield [self.board[row+i][col+i]
                   for i in range(min(height, width))
                   if row+i < height and col+i < width]

    def check_won(self, player):
        for row in self.get_rows(self.width, self.height):
            for i in range(len(row) + 1 - self.win_amount):
                if all(x == self.players[player]
                       for x in row[i:i+self.win_amount]):
                    return True
        return False

def play():
    game = ConnectFour(7, 6, 4)
    game.print_board()
    player = 0
    for _ in range(game.width * game.height):
        game.move(player)
        game.print_board()
        if game.check_won(player):
            print(game.players[player], 'wins!')
            break
        player = (player + 1) % 2
    else:
        print("It's a draw!")
    if input('Play again? (yes or no): ').lower().startswith('y'):
        play()

play()

I would be really glad if somebody would comment on it! Comments on the whole thing are welcome as well!

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

Using generator is a good way to implement this.

Let's see what can be improved.

Additional variable

The expression min(height, width) is computed multiple times. It would be easier to store in a variable:

min_dim = min(height, width)

Dimensions as parameters (and other signature changes)

Having the dimensions are parameters for the method is a bit unexpected.

You could rewrite the method by relying on the attribute of the instance:

def get_rows(self):
    width, height = self.width, self.height
    ... # code unchanged

An alternative could be to write a standalone function (not a method) that does take 2 dimensions as parameters and return indices (instead of values from board).

def get_lines_in_rectangle(width, height):
    # get horizontal rows
    for row in range(height):
        yield [(row, col) for col in range(width)]
    # get vertical rows
    for col in range(width):
        yield [(row, col) for row in range(height)]
     # get diagonal and anti-diagonal rows
    min_dim = min(height, width)
    for num in range(width + height - 1):
        row = min(num, height - 1)
        col = max(0, num + 1 - height)
        yield [(row-i, col+i)
               for i in range(min_dim)
               if row-i >= 0 and col+i < width]
        row = max(0, num + 1 - width)
        col = max(0, width - 1 - num)
        yield [(row+i, col+i)
               for i in range(min_dim)
               if row+i < height and col+i < width]

...

    def get_rows(self):
        for l in get_lines_in_rectangle(self.width, self.height):
            yield [self.board[row][col] for row, col in l]

Both solutions have pros and cons - I have no perfect solution to suggest.

This function may be slightly less efficient but it is much easier to unit-test as the results depends on 2 integers instead of a full game state.

Also, this could be computed once and for all and re-applied to the game state easily on demand.

Going further, we could also write a function computing lines of length l:

def get_lines_of_len_in_rectangle(length, width, height):
    for l in get_lines_in_rectangle(width, height):
        for i in range(len(l) + 1 - length):
            yield l[i:i+length]

This can also: - be unit-tested more easily - be computed once and stored for future reuse

And then used easily in check_won (we don't need the get_rows method anymore):

    def check_won(self, player):
        for l in get_lines_of_len_in_rectangle(self.win_amount, self.width, self.height):
            if all(self.board[row][col] == self.players[player] for row, col in l):
                return True
        return False

Another idea

All the ideas above don't really matter if we try to see how humans would handle that task: only once a new move is completed, we check if there is a matching line from that new position. Thus, we do not need to consider all lines but a very minimal subset of it (a single row, a single column and two diagonals).


Recursion

Recursion is a great tool (especially to handle data structure with a definition which is itself based on recursion).

However, it is not always the best tool especially in Python as it does not optimise tail recursion.

Here, it can lead to situations in play or move where the call stack gets arbitrarily big and:

  • stacktraces becomes impossible to use
  • we may get an exception when maximum recursion depth is exceeded.

For play, my suggestion is to introduce a new function:

def play():
    game = ConnectFour(7, 6, 4)
    game.print_board()
    player = 0
    for _ in range(game.width * game.height):
        game.move(player)
        game.print_board()
        if game.check_won(player):
            print(game.players[player], 'wins!')
            break
        player = (player + 1) % 2
    else:
        print("It's a draw!")

def play_games():
    while True:
        play()
        if not input('Play again? (yes or no): ').lower().startswith('y'):
            break

For move, we can just wrap the whole logic in a while loop even tough readability suffers a bit of it:

   def move(self, player):
        while True:
            while True:
                move = self.ask_number(player)
                if 0 <= move < self.width:
                    break
                print('Choose a row between 1 and ', self.width, '!', sep='')
            for row in reversed(self.board):
                if row[move] == '':
                    row[move] = self.players[player]
                    return
            print('This row is full. Try again!')

We could split it with another method:

    def ask_move(self, player):
        while True:
            move = self.ask_number(player)
            if 0 <= move < self.width:
                return move
            print('Choose a row between 1 and ', self.width, '!', sep='')

    def move(self, player):
        while True:
            move = self.ask_move(player)
            for row in reversed(self.board):
                if row[move] == '':
                    row[move] = self.players[player]
                    return
            print('This row is full. Try again!')

The play function

It seems like it could make sense for play to be a method rather than a function.

We'd have:

    def play(self):
        self.print_board()
        player = 0
        for _ in range(self.width * self.height):
            self.move(player)
            self.print_board()
            if self.check_won(player):
                print(self.players[player], 'wins!')
                break
            player = (player + 1) % 2
        else:
            print("It's a draw!")

def play_games():
    while True:
        ConnectFour(7, 6, 4).play()
        if not input('Play again? (yes or no): ').lower().startswith('y'):
            break

A lying UX ?

The line if not input('Play again? (yes or no): ').lower().startswith('y') shows something which can be confusing: we lie to the user.

We tell the user that the valid options are "yes" and "no" but "Yankee" would start the game all the same.

There are various ways to handle it (changing the message, changing the validation code).


| improve this answer | |
\$\endgroup\$

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.