# Connect Four – get all diagonal and anti-diagonal rows

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

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:
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!

Using generator is a good way to implement this.

Let's see what can be improved.

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:
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:
if 0 <= move < self.width:
return move
print('Choose a row between 1 and ', self.width, '!', sep='')

def move(self, player):
while True:
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).