[\'O\', \'.\', \'O\', \'O\', \'X\', \'X\', \'.\', \'X\', \'.\']] >>> print(show_
ID: 3597981 • Letter: #
Question
['O', '.', 'O', 'O', 'X', 'X', '.', 'X', '.']] >>> print(show_board(ex1)) ...R... ..YRR.. .RYRYR. YYYRYYR >>> print(show_board(ex2)) ....... ...Y... ..YBY.. .YBBBY. YBBBYBY >>> print(show_board(ex3)) .... .... .BB. .BS. SSBS >>> print(show_board(ex4)) ... .A. ... BAB >>> print(show_board(ex5)) .... XO.. OO.O XXXX XOOO >>> print(show_board(ex6)) ......... ....OX... ...OOX... O.OOXX.X. >>> (0,0) (0,1) … (0,M-1) (1,0) … … (1,M-1) … … … … (N-1,0) (N-1,1) … (N-1,M-1) Functions These functions build up in usefulness and complexity; work through them roughly in the order presented and try to use your completed/100% correct earlier functions to help implement the later functions. When functions have direct answers, we share some examples. Others are better shown in a longer session, so their examples are included all together at the end of this document. You can also look at the test cases for further examples, as always: it shows the operations performed and the expected answers/status afterwards. def init_board(num_rows, num_cols): Given two positive ints, create an empty board. Unlike the physical game, our boards can be any positive dimensions. • Assume: num_rows and num_cols are positive integers. • init_board(2,3) [['.', '.', '.'], ['.', '.', '.']] def show_board(board): Given a board, create and return the string that, when printed, would print each row on consecutive lines, and each space in a row in consecutive characters on the line. • Assume: board is a board. • show_board(ex1) '...R... ..YRR.. .RYRYR. YYYRYYR ' • show_board([['.', '.', '.'] ,['A', 'B', 'A']]) "... ABA " • example usage: >>> print(show_board([['.', '.', '.'] ,['A', 'B', 'A']]) ) ... ABA >>> def read_board(s): Given a string containing lines of either player pieces or periods, pick apart the string and generate the corresponding board. Blank lines must be ignored, but if the non-blank lines don't create a rectangular shape (different lines have different lengths) or if other characters show up (neither periods nor upper-case letters), return None instead of a generated board. • Assume: s is a string. • Reminder: only periods and upper-case letters are in valid boards, and valid boards are always rectangular. You must check both of these! • read_board("... ABA ") [['.', '.', '.'] ,['A', 'B', 'A']] • read_board(".. .. OK ") [['.', '.'], ['.', '.'], ['O', 'K']] • read_board(".... .. NOO ") None #different-length rows def get_size(board): Given a board, find the dimensions and return as a tuple: (numrows, numcols). • Assume: board is a valid board. • get_size([['.', '.', '.'], ['.', '.', '.']]) (2,3) • get_size(ex3) (5,4) def is_valid_coord(board, r, c): Given a board and two ints, do r and c describe a valid location on the board? Negative indexes are not allowed here (as a design decision). • Assume: board is a valid board, r and c are integers. • Hint: you should be using this function all over the place in the rest of your project! • is_valid_coord([["B",".","R"],["R","R","B"]], 0, 0) True • is_valid_coord([["B",".","R"],["R","R","B"]], 2, 3) False • is_valid_coord([["B",".","R"],["R","R","B"]], -1,-1) False def get_coords_by_color(board, color): Given a board and target color, create a list of all the coordinates in that board containing that color, ordered by lowest row and then lowest column values. • Assume: board is a board, color is a color. • get_coords_by_color([['G','.'],['Y','Y']], "Y") [(1,0),(1,1)] • get_coords_by_color([['G','.'],['Y','Y']], "G") [(0,0)] • get_coords_by_color([['.','X'],['Y','X']], "X") [(0,1),(1,1)] def get_colors(board): Given a board, create a list of all the colors present in the board, in order of first appearance (earlier rows first; earlier spots in a row first). Do not sort them. We expect no more than two players on a board, but this function must find all colors present (perhaps to help check for erroneous boards). • Assume: board is a board. • get_colors([['.','Y'],['Y','X']]) ['Y','X'] • get_colors(ex1) ['R','Y'] • get_colors(ex2) ['Y','B'] • get_colors(ex3) ['B','S'] def count_pieces_by_color(board,color): Given a board & color, count #pieces of that color. • Assume: board is a board; color is a color. • count_pieces_by_color([['.','Y'],['Y','X']], 'X') 1 • count_pieces_by_color([['.','Y'],['Y','X']], 'A') 0 • count_pieces_by_color(ex1, 'R') 8 • count_pieces_by_color(ex1, 'Y') 8 def any_floating(board): Given a board, are any pieces floating? (Does any player-piece have a blank spot under it?) • Assume: board is a valid board other than the possibility of floating pieces. • any_floating([['X','Y'],['Y','X']]) False • any_floating([['X','Y'],['.','.'],['X','Y']]) True • any_floating(ex1) False • any_floating(ex4) True def is_column_full(board, c): Is the specified column entirely filled with player pieces? • Assume: board is a valid board, c is an int. • is_column_full([['.','Y'] ,['Y','X'] ,['Y','X']],0) False • is_column_full([['.','Y'] ,['Y','X'] ,['Y','X']],99) False # not a col. • is_column_full(ex1,3) True • is_column_full(ex1,4) False def place_one(board, c, color): Attempt to play that color in that column, with the piece falling to the lowest open space. If the column is full or the column doesn't exist, don't modify board, and return False. If the column exists and has space for another piece, update the board to play the piece of that color in that column, and return True. • Assume: board is a valid board; c is an int; color is a color. • see session at end of document for another example usage. def pop_out(board, c, color): Some variants of the game allow a player to remove the bottom piece in a column as their turn when that bottom piece is their color, called "popping out" the piece. Attempt to remove the bottom piece from the specified column, which will make any higher pieces drop down a spot. If the column is invalid, or there's nothing in the specified column, or it's not their color, make no changes and return False. Otherwise, perform the operation and return True. • Assume: board is a valid board; c is an int, color is a color. • example: >>> b = [['A','B'],['B','A']] >>> pop_out(b,0,'B') True >>> b [['0','B'],['A','A']] Checking for Winners The next five functions focus on finding winning four-in-a-row groups of any color (a 'run'). Four are variations on a theme (you'll probably use the same idea in each of them repetitively), building up to check_winner. Note that we are checking an individual spot for an individual direction of a run, we're not checking the entire row/column/diagonal in those first four functions. def check_horizontal(board, r, c): Does a run begin here and extend horizontally to the right? If the location is invalid or a run doesn't start here, return False. If it does, return True. • Assume: board is a valid board, r and c are ints. • Note: We aren't checking the entire row; we also don't mind if pieces to the left also match the run. • check_horizontal([['A','A','A','A','A','B','B','B']], 0, 1) True • check_horizontal([['A','A','A','A','A','B','B','B']], 0, 4) False def check_vertical(board, r, c): Does a run begin here and extend vertically down? If the location is invalid or a run doesn't start here, return False. If it does, return True. • Assume: board is a valid board, r and c are ints. • Note: We aren't checking the entire column; we also don't mind if pieces above also match the run. • check_vertical([['A'], ['A'], ['A'], ['A'], ['A']], 0, 0) True • check_vertical([['A'], ['A'], ['A'], ['A'], ['A']], 3, 0) False #not a full run • check_vertical([['A'], ['A'], ['A'], ['A'], ['A']], -1, -1) False #invalid location def check_major_diagonal(board, r, c): Does a run begin here and extend diagonally down and to the right? If the location is invalid or a run doesn't start here, return False. If it does, return True. • Assume: board is a valid board, r and c are ints. • Note: We aren't checking the full diagonal; we also don't mind if neighboring diagonal pieces also match. • check_major_diagonal(ex2,1,3) True • check_major_diagonal(ex2,4,0) False def check_minor_diagonal(board, r, c): Does a run begin here and extend diagonally up and to the right? If the location is invalid or a run doesn't start here, return False. If it does, return True. • Assume: board is a valid board, r and c are ints. • Note: We aren't checking the full diagonal; we also don't mind if neighboring diagonal pieces also match. • check_minor_diagonal(ex2,4,0) True • check_minor_diagonal(ex2,1,3) False def check_winner(board): Examine the entire board; return a color, "tie", "draw", or "pending": - If just one player has 1 (or more) runs, return that color - If both colors have runs, return the string "tie!" this shouldn't happen in valid games though… - If no runs are present and no spaces are left, return "draw" - If there are blank spaces and no runs, return "pending" • Assume: board is a valid board. • check_winner(ex1) 'R' • check_winner(ex3) 'pending' • check_winner([['A','B']]) 'draw' • check_winner(read_board("AAAABBBB ")) 'tie!' Extra Credit This last function is more challenging, but still only uses the same skills as before. def winning_move(board,color): Find a column that will win the game for color in a single move, and return that column index. When multiple columns offer a win, report the leftmost column. If no one-move win exists, return None. • Assume: board is a board. • winning_move(ex6,"X") 5 • winning_move(ex6,"O") 1 # leftmost column that wins for 'O' • winning_move(ex1,"O") None # game is already over!
Explanation / Answer
def init_board(num_rows, num_cols):
# create a new board
board = []
# add given number of rows
for i in range(num_rows):
# initialise each row with empty
row = ['.']*num_cols
board.append(row)
return board
# print(init_board(2, 3))
def show_board(board):
# create an empty string which will hold string representation of board
boardstr = ''
# for each row in board, craete its string representation
for row in board:
# string representation is just putting each cell one after another in row and then separating rows with new line
boardstr += ''.join(row) + ' '
# return string repreentation of board
return boardstr
# print(show_board([['.', '.', '.'], ['A', 'B', 'A']]))
def read_board(s):
# check if string is empty or None return None
if not s:
return None
# create an empty list which will hold all valid lines (non empty lines) in s
lines = []
# get all lines as a list by splitting lines on new line charatcer
tempLines = s.split(' ')
# for each line b=obtained by splitting keep only non empty lines
for line in tempLines:
# check if line is not None/empty
if line:
# append line to lines if it is non empty
lines.append(line)
# number of column will be entry in one line and all lines should have same length
col = len(lines[0])
row = 0
# for each lines
for i in range(len(lines)):
# check if length of line is different from other line, if yes return None
if len(lines[i]) != col:
return None
# if line is just white space don't consider it
if lines[i] == ' ':
continue
row += 1
# for each char in line
for c in lines[i]:
# check if char is in upper case letter, else its an invalid data
if not (c == '.' or c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
return None
# create an empty board as we now know exact number of rows and column
board = init_board(row, col)
# fill row and column from lines
for i in range(row):
for j in range(col):
board[i][j] = lines[i][j]
return board
# print(read_board(".... NOO "))
def get_size(board):
# check if board is not defined, if yes return None
if not board:
return None
# number of rows is length of outer list
row = len(board)
if row == 0:
return None
# length of column should be same for all column so taking out from first row
col = len(board[0])
return (row, col)
# print(get_size([['.', '.', '.'], ['A', 'B', 'A']]))
def is_valid_coord(board, r, c):
# a coordinate is valid if it is greater than equal to zero but strictl less than board size
if r < 0 or c < 0:
return False
(row, col) = get_size(board)
if r >= row or c >= col:
return False
return True
# print(is_valid_coord([["B", ".", "R"], ["R", "R", "B"]], 0, 0))
# print(is_valid_coord([["B", ".", "R"], ["R", "R", "B"]], 2, 3))
# print(is_valid_coord([["B", ".", "R"], ["R", "R", "B"]], -1, -1))
def get_coords_by_color(board, color):
# list to hold all coordinates of a given colr in board
color_coord = []
# iterate over full board
for i in range(len(board)):
for j in range(len(board[i])):
# check if color is same as given color if yes then add coordinate as tuple in list
if board[i][j] == color:
color_coord.append((i, j))
return color_coord
# print(get_coords_by_color([['G', '.'], ['Y', 'Y']], 'Y'))
# print(get_coords_by_color([['G', '.'], ['Y', 'Y']], 'G'))
# print(get_coords_by_color([['.', 'X'], ['Y', 'X']], 'X'))
def get_colors(board):
colors = []
# iterate over full board and get all color present in board
for i in range(len(board)):
for j in range(len(board[i])):
# ignore empty cell or if color is already notes, else add it to list
if board[i][j] != '.' and (not board[i][j] in colors):
colors.append(board[i][j])
return colors
# print(get_colors([['.', 'Y'], ['Y', 'X']]))
def count_pieces_by_color(board, color):
count = 0
# iterate over board
for i in range(len(board)):
for j in range(len(board[i])):
# if color in cell as asked color, increase its count
if board[i][j] == color:
count += 1
return count
# print(count_pieces_by_color([['.', 'Y'], ['Y', 'X']], 'Y'))
def any_floating(board):
(row, col) = get_size(board)
# iterate over all column
for j in range(col):
# variable to make sure that once we found a color all below column should have color
color_found = False
# iterate over row
for i in range(row):
# if cell is not empty then it has color which means now all below cell should have color
if board[i][j] != '.':
color_found = True
elif board[i][j] == '.' and color_found: # if color is empty and above cell is filled meaning above ell was floating
return True
# return false if no cell is floating
return False
def is_column_full(board, c):
(row, col) = get_size(board)
if c < 0 or c >= col:
return False
# iterate over all row for given column
for i in range(row):
# if there is free space meaning coloumn is not full
if board[i][c] == '.':
return False
return True
# print(is_column_full([['.', 'Y'], ['Y', 'X'], ['Y', 'X']], 0))
# print(is_column_full([['.', 'Y'], ['Y', 'X'], ['Y', 'X']], 99))
# print(is_column_full([['.', 'Y'], ['Y', 'X'], ['Y', 'X']], 1))
def place_one(board, c, color):
(row, col) = get_size(board)
if c < 0 or c >= col or is_column_full(board, c):
return False
# iterate over all row from last for given column and see if it is empty, if it is but color at that cell
for i in range(row-1, -1, -1):
# if cell si empty put color
if board[i][c] == '.':
board[i][c] = color
return True
# return False if no cell was free
return False
def pop_out(board, c, color):
(row, col) = get_size(board)
if c < 0 or c >= col or board[row-1][c] != color:
return False
# move all element down by removing last eleemnt of given column
for i in range(row-1, 0, -1):
board[i][c] = board[i-1][c]
board[0][c] = '.';
return True
# b = [['A', 'B'], ['B', 'A']]
# print(pop_out(b, 0, 'B'))
# print(b)
def check_horizontal(board, r, c):
(row, col) = get_size(board)
if not is_valid_coord(board, r, c):
return False
color = board[r][c]
if color == '.':
return False
count = 1
# from given position check next 3 position if they are same oclor if yes then winner else not
for j in range(c+1, col):
if count == 4:
break
if board[r][j] == color:
count += 1
else:
return False
return count == 4
# print(check_horizontal([['A', 'A', 'A', 'A', 'A', 'B', 'B', 'B']], 0, 4))
def check_vertical(board, r, c):
(row, col) = get_size(board)
if not is_valid_coord(board, r, c):
return False
color = board[r][c]
if color == '.':
return False
count = 1
# from given cell check below 3 cell, if they are same as cell color then winner else not
for i in range(r+1, row):
if count == 4:
break
if board[i][c] == color:
count += 1
else:
return False
return count == 4
# print(check_vertical([['A'], ['A'], ['A'], ['A'], ['A']], -1, -1))
def check_major_diagonal(board, r, c):
(row, col) = get_size(board)
if not is_valid_coord(board, r, c):
return False
color = board[r][c]
if color == '.':
return False
count = 1
j = c
# traverse major diagonal and see if next 3 entry is same as given cell, if yes winner, else not
for i in range(r+1, row):
j = j + 1
if j >= col:
break
if count == 4:
break
if board[i][j] == color:
count += 1
else:
return False
return count == 4
def check_minor_diagonal(board, r, c):
(row, col) = get_size(board)
if not is_valid_coord(board, r, c):
return False
color = board[r][c]
if color == '.':
return False
count = 1
j = c
# traverse minor diagonal and see if next 3 entry is same as given cell, if yes winner, else not
for i in range(r-1, -1, -1):
j = j + 1
if j >= col:
break
if count == 4:
break
if board[i][j] == color:
count += 1
else:
return False
return count == 4
# method to check if board is complete full
def is_board_full(board):
(row, col) = get_size(board)
for i in range(row):
for j in range(col):
if board[i][j] == '.':
return False
return True
def check_winner(board):
(row, col) = get_size(board)
winner_color = ''
won = False
# for each cell check if there is any horizonatl, vertcal, or diagonal winner
# if yes check if there is winner for other color as well
# if two winner are possible then tie
# if one winner then that is winner
for i in range(row):
for j in range(col):
if check_horizontal(board, i, j) or check_vertical(board, i, j) or check_major_diagonal(board, i, j) or check_minor_diagonal(board, i, j):
won = True
# check if winner is set and there is a new different winenr
if winner_color and winner_color != board[i][j]:
return "tie!"
else:
winner_color = board[i][j]
if won:
return winner_color
elif is_board_full(board): # if no winner is found and board is full then its a draw
return "draw"
else: # if board is not full and no winner then game is still pending
return "pending"
# completed
# create a copy of board
def get_copy_of_board(board):
board_copy = []
for row in board:
newRow = []
for col in row:
newRow.append(col)
board_copy.append(newRow)
return board_copy
def winning_move(board,color):
# if board is not pending then there cant be any winning move.
if check_winner(board) != "pending":
return None
(row, col) = get_size(board)
# for each column see if we add one entry and then check if we found a winner, if yes then there is winning move and hence we will return column index
for j in range(col):
board_copy = get_copy_of_board(board)
if place_one(board_copy, j, color):
if check_winner(board_copy) == color:
return j
# if no winning index return None
return None
# copy pastable code link: https://paste.ee/p/BqrF0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.