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