othello_problem_session.py

# Reversi (https://en.wikipedia.org/wiki/Reversi), also called Othello, is a game where each piece has two sides, black and white, and after being placed, further moves cause other pieces to flip tiles. Specifically, a line of pieces of one color gets flipped when they become surrounded by pieces of the opposite color on both ends.

# In this problem, we will be given a 2-dimensional array representing the board. Each position will contain a value of “B”, “W”, or “*” representing empty. Additionally, we get a position that is currently empty. Update the board to the new state after that play, including any flips if it is black’s turn to play. You can modify the existing array, but either way, return the board (2d array) with the new state.

# Follow-up:
# 1. Update this code to take a parameter of a “B” or “W,” indicating which player is making a move.
 

# EXAMPLE(S)
# For example, consider the row:

# 1 2 3 4 5 6 7 8
# * B W W W W * *

# If black places a piece at position 7, the white pieces in between get flipped, so the result is:

# 1 2 3 4 5 6 7 8
# * B B B B B B *

# This can happen on a row, column, or diagonal and even at the same time. In the following example, if white place on position (5, 5), then all of the black pieces flip to white!

#   1 2 3 4 5 6 7 8
# 1 * * * * * * * *
# 2 * W * * * * * *
# 3 * * B * * * * *
# 4 * * * B * * * *
# 5 W B W B ! * * *
# 6 * * * * B * * *
# 7 * * * * B * * *
# 8 * * * * B * * *

#direction = [[-1, 1], [0, 1], [1, 1], [-1, 0], [1, 0], [-1,-1], [0,-1], [1,-1]]
#    for dx,dy in direction:

# if not OOB
# flip after popping back up the stack

# approaches:

'''
example = [
    [*,*,*,*,*,*,*,*],
    [*,*,W,*,*,*,*,*],
    [*,*,B,*,*,*,*,*],
    [*,*,B,*,*,*,*,*],
    [W,W,W,W,W,*,*,*],
    [*,*,*,*,B,*,*,*],
    [*,*,*,*,B,*,*,*],
    [*,*,*,*,W,*,*,*]
    ]

example = [
    [*,*,*,*,*,*,*,*],
    [*,W,*,*,*,*,*,*],
    [*,*,B,*,*,*,*,*],
    [*,*,*,B,*,*,*,*],
    [W,B,W,B,*,*,*,*],
    [*,*,*,*,B,*,*,*],
    [*,*,*,*,B,*,*,*],
    [*,*,*,*,W,*,*,*]
    ]

example = [
    [*,*,*,*,*,*,*,*],
    [*,W,*,*,*,*,*,*],
    [*,*,B,*,*,*,*,*],
    [*,*,*,B,*,*,*,*],
    [W,B,W,B,*,*,*,*],
    [*,*,*,*,B,*,*,*],
    [*,*,*,*,B,*,*,*],
    [*,*,*,*,B,*,*,*]
    ]

example = [
    [*,*,*,*,*,*,*,*],
    [*,W,*,*,*,*,*,*],
    [*,*,B,*,*,*,*,*],
    [*,*,*,W,*,*,*,*],
    [W,B,W,B,*,*,*,*],
    [*,*,*,*,W,*,*,*],
    [*,*,*,*,W,*,*,*],
    [*,*,*,*,W,*,*,*]
    ]
'''

# FUNCTION SIGNATURE
# function reversi(board, x, y)

def recur(board, possX, possY, dx, dy):
    if possX < 0 or possX >= len(board): return False
    if possY < 0 or possY >= len(board): return False

    if board[possX][possY] == "*": return False
    if board[possX][possY] == "W": return True

    res = recur(board, possX + dx, possY + dy, dx, dy)
    if res == True:
        board[possX][possY] = "W"
    return res
    


def reversi(board, x, y):
    length = len(board)
    direction = [[-1, 1], [0, 1], [1, 1], [-1, 0], [1, 0], [-1,-1], [0,-1], [1,-1]]

    board[x][y] = "W"

    for dx, dy in direction:
        recur(board, x + dx, y + dy, dx, dy)

    for r in range(len(board)):
        print(' '.join(board[r]))
 


# 0,2
# 0,1

board = [
    ['*','*','*','*','*','*','*','*'],
    ['*','W','*','*','*','*','*','*'],
    ['*','*','B','*','*','*','*','*'],
    ['*','*','*','B','*','*','*','*'],
    ['W','B','B','B','*','*','*','*'],
    ['*','*','*','*','B','*','*','*'],
    ['*','*','*','*','B','*','*','*'],
    ['*','*','*','*','W','*','*','*']
]

reversi(board, 4, 4)