Question
What can I use? You may only use the following things. You may ask about adding things to a list, but we are unlikely to
What can I use?
You may only use the following things. You may ask about adding things to a list, but we are unlikely to add
anything. If you use something disallowed, it's not an honor code violation, you just won't get points.
Restrictions
no modules may be imported.
Allowed
basic statements, variables, operators, del, indexing, slicing, in, are all allowed
any form of control flow we've covered is allowed (if/else, loops, etc)
only these built-in functions: range(), len(), int(), str(), list(), abs()
only these built-in methods: s.split(), s.join(), s.pop(), xs.append(), xs.extend(),
xs.insert(), s.format()
calling other functions of the project (and your own helper functions). Please do this! J
Hint In our solution, we only used range, len, in, abs, .append(), .join(), .split(), and list().
Remember: your grade is significantly based on passing test cases try to completely finish individual functions
before moving on. The easiest way to implement many functions is to call the earlier/easier functions, so it'll pay off
to complete functions before moving on. Don't let yourself be "almost done" with a function, but miss all the tests!
Connect Four!
Connect Four is a game where players win by placing four of their pieces in a row,
either horizontally, vertically, or diagonally. The board is a vertical plane with a
limited number of columns; playing a piece in a column will drop to the lowest
available space. Players take turns dropping pieces into columns, trying to get four in
a row before their opponent does.
Representations
We will represent the board as a list of lists of values; the overall list is really a list of rows, and each row is a
list of the items in the row. We represent each space with a single-character string. Look at the example below
for both the picture and the corresponding grid representation.
empty spaces are represented by a period "."
player pieces are represented by upper-case letters.
a board is of any finite rectangular size. Always indicate the number of rows before number of columns.
o in this spec, we use board as convenient shorthand for a list of lists of length-one strings.
o only non-negative indexes are allowed (Python doesn't enforce it but our program should).
o only length-one strings are allowed in the inner lists.
o a board is "valid" when it is rectangular, has at most two colors in it, no floating pieces, and no
more that one extra move for some player. Otherwise it's a least a list of lists of length-1 strings.
a coord is a pair of row- and col- indexes, e.g. (0,0), (2,3), (5,1). Only non-negative indexes allowed.
a color is a single upper-case letter.
a run is our terminology for four pieces of the same color in a line. We don't care which direction it goes.
Indexing into the Board
When we have a grid, we have two dimensions. The first dimension
indicates the row (top row to bottom row), and the second dimension
indicates the column (left column to right column). Thus with N rows
and M columns, we have a grid with indexes as shown to the right.
Here we define some sample boards, which are used (by name) in
examples through the definitions below. The direct board definitions are given, as well as the
print(show_board(ex)) outputs to the right (which is easier to understand). The final page of this document
shows usage of many of the functions by calling them on these examples.
ex1 = [['.', '.', '.', 'R', '.', '.', '.'],
['.', '.', 'Y', 'R', 'R', '.', '.'],
['.', 'R', 'Y', 'R', 'Y', 'R', '.'],
['Y', 'Y', 'Y', 'R', 'Y', 'Y', 'R']]
ex2 = [['.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', 'Y', '.', '.', '.'],
['.', '.', 'Y', 'B', 'Y', '.', '.'],
['.', 'Y', 'B', 'B', 'B', 'Y', '.'],
['Y', 'B', 'B', 'B', 'Y', 'B', 'Y']]
ex3 = [['.', '.', '.', '.'],
['.', '.', '.', '.'],
['.', 'B', 'B', '.'],
['.', 'B', 'S', '.'],
['S', 'S', 'B', 'S']]
ex4 = [['.', '.', '.'],
['.', 'A', '.'],
['.', '.', '.'],
['B', 'A', 'B']]
ex5 = [['.', '.', '.', '.'],
['X', 'O', '.', '.'],
['O', 'O', '.', 'O'],
['X', 'X', 'X', 'X'],
['X', 'O', 'O', 'O']]
ex6 = [['.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', 'O', 'X', '.', '.', '.'],
['.', '.', '.', 'O', 'O', 'X', '.', '.', '.'],
['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!
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!'
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!
please use python language
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started