This must be in Python and can't use print(). It must be return.

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).

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().

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!