CODEWITHSUNDEEP
python2d
LetMeSOThat4U
LetMeSOThat4U

Reputation: 6796

checking diagonals in 2d list (Python)

The initial problem: for a given 3x3 tic tac toe board check if one of the players has won.

The simplest solution I have come up so far is rotating the matrix and summing up each row:

board
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]

pr(board)
0 1 2
3 4 5
6 7 8

pr(zip(*board))
0 3 6
1 4 7
2 5 8

0..9 numbers above are just for showing positions on the board, normally they would be filled with 1 for player 1 and -1 for player 2 and 0 for unfilled position. Go row by row and if it sums up to 3 or -3 this is the winning block.

However, diagonals are not checked. Is there some way to extract diagonals from such matrix in elegant + highly performant way? I don't mean using trivial indexes "manually" (0, 1, 2), but rather get diagonal of n x n matrix.

P.S. pr is just a helper function for printing 2d list:

def pr(x):
    for row in x:
        print ' '.join(map(str, row))

Upvotes: 4

Views: 14049

Answers (6)

Mitya Kuznetsov
Mitya Kuznetsov

Reputation: 1

tmp_diagonals = [set(), set()]
    num = 0
    for idx in range(len(board) - 1, -1, -1):
        tmp_diagonals[0].add(board[num][num])
        tmp_diagonals[1].add(board[num][idx])
        num += 1

Upvotes: -1

martineau
martineau

Reputation: 123541

The diagonals on a square board lie either where the indices are equal, so for a 3x3 board they are board[0][0], board[1][1], and board[2][2] or where the two sum to the board size-1 (3 places in this case): such as board[0][2], board[1][1], and board[2][0] -- notice that board[1][1] is included in both sets, as it should be. These facts makes it fairly easy to write Python code to compute them:

board = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
BOARD_SIZE = len(board)

diags1 = [board[i][i] for i in xrange(BOARD_SIZE)]
diags2 = [board[i][BOARD_SIZE-1-i] for i in xrange(BOARD_SIZE)]

print diags1
print diags2

Output:

[0, 4, 8]
[2, 4, 6]

Upvotes: 2

Christian Rapp
Christian Rapp

Reputation: 1903

Number your game field with a magic square

2|9|4
7|5|3
6|1|8

Now sum up after three moves and check if the sum is 15 --> Winner. You have to check this for every player. Surely you have to recheck after 4th move and 5th move (only the player that started the game)

This is how I solved this problem in my first Java class.

Upvotes: 4

Stjepan Bakrac
Stjepan Bakrac

Reputation: 1134

This will give you a list containing the diagonal elements of one direction (top left to bottom right):

[board[i][i] for i in range(len(board))]

This will do the same for the opposite direction:

[board[i][len(board)-i-1] for i in range(len(board))]

Upvotes: 1

David Robinson
David Robinson

Reputation: 78630

You can get one diagonal with:

[r[i] for i, r in enumerate(board)]
# [0, 4, 8]

And the opposite diagonal with:

[r[-i-1] for i, r in enumerate(board)]
# [2, 4, 6]

Upvotes: 12

Gijs
Gijs

Reputation: 10891

Probably what you need is in numpy, see Get all the diagonals in a matrix/list of lists in Python. Maybe you can use this, and flip it like you did to get the other solution. 

if sum(board[i][i] for i in (0, 1, 2)) in (-3, 3):
    true

Upvotes: 2

Related Questions