Homework 4
Due by 11:59pm on Sunday, 10/16/2016
Instructions
Download hw04.zip. Inside the archive, you will find a file called hw04.py, along with a copy of the OK autograder. Upload the zip file to Jupyter to complete the assignment. See Lab 0 for instructions on using Jupyter to complete assignments.
Submission: When you are done, submit the assignment by uploading the .py file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored. See Lab 0 for instructions on submitting assignments.
Readings: This homework relies on following references:
Required Questions
Rules
By the end of this game, you will have implemented your own Connect N game (most commonly connect 4). As you might already know, Connect N is a two-player game where the players take turns dropping a piece from the top of a column in a grid. The piece ends at the last empty spot in this column - that is, as close to the bottom as possible. A player can only put pieces in columns with open spaces.
The winner is the first player who gets N of their pieces next to each other - either horizontally, vertically or diagonally. The game ends at this point, or as soon as the board is full.
Building Connect N
Let's build the combat field for players 'X'
and 'O'
.
In this lab, we will represent the playing board as a list of lists. We call such a list two-dimensional
because we can visualize it as a rectangle. For instance, the list [['-', '-', '-', '-'], ['O', 'O', 'O', 'X'], ['X', 'X', 'X', 'O']]
would represent the following board:
- - - -
O O O X
X X X O
What does the number of nested lists represent? What about the number of elements in each nested list? When you have made up your mind, you are ready to build the board!
Notice that just like lists are zero-indexed, our board is zero-indexed. This means that the columns and rows in the above board would be numbered like this:
0 - - - -
1 O O O X
2 X X X O
0 1 2 3
Question 1: Creating an empty board
We are going to use data abstraction as we build our game, so let's start by making the constructors. We will represent an empty spot by the string'-'
. In lab04.py
, fill out the constructors. Remember to use your abstraction. How should we make a new row inside create_board
? By using the create_row
function that you write first. Each function should consist of only a single line, so you might find list comprehensions handy - though not necessary.
def create_row(size):
"""Returns a single, empty row with the given size. Each empty spot is
represented by the string '-'.
>>> create_row(5)
['-', '-', '-', '-', '-']
"""
"*** YOUR CODE HERE ***"
return _______
Use OK to test your code:
python ok -q create_row --local
def create_board(rows, columns):
"""Returns a board with the given dimensions.
>>> create_board(3, 5)
[['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-']]
"""
"*** YOUR CODE HERE ***"
return _______
Use OK to test your code:
python ok -q create_board --local
Question 2: Updating the board
Over the course of a game, the board will change and we will need to keep our representation of the
board up-to-date. To do so, we will be creating a new board that represents the new state of the
game every time a piece is played. Implement replace_elem
, which takes a list, an index, and an
element to be placed at that index in the returned new list.
This function should consist of a one-line return statement.
def replace_elem(lst, index, elem):
"""Create and return a new list whose elements are the same as those in
LST except at index INDEX, which should contain element ELEM instead.
>>> old = [1, 2, 3, 4, 5, 6, 7]
>>> new = replace_elem(old, 2, 8)
>>> new
[1, 2, 8, 4, 5, 6, 7]
>>> new is old # check that replace_elem outputs a new list
False
"""
assert index >= 0 and index < len(lst), 'Index is out of bounds'
"*** YOUR CODE HERE ***"
return _______
Use OK to test your code:
python ok -q replace_elem --local
Question 3: Manipulating pieces
Now that we have the board ready, let's make a way to find out which
piece ('-'
, 'X'
or 'O'
) is at a given position. Implement get_piece
so it does this.
Note: The get_piece
function is what we call a selector, which is
allowed to break through the data abstraction barrier in order to abstract away
the inner implementation for all of the other functions that both the programmer
and other users will use.
This function should consist of a one-line return statement.
def get_piece(board, row, column):
"""Returns the piece at location (row, column) in the board.
>>> rows, columns = 2, 2
>>> board = create_board(rows, columns)
>>> board = put_piece(board, rows, 0, 'X')[1]
>>> board = put_piece(board, rows, 0, 'O')[1]
>>> get_piece(board, 1, 0)
'X'
>>> get_piece(board, 1, 1)
'-'
"""
"*** YOUR CODE HERE ***"
return _______
Right now, all spots in our board are empty, so the output of get_piece
won't
be very interesting - and neither will the game. Let's change that! Go ahead and
implement put_piece
which places the given player's piece in the given
column. put_piece
should return the 2-element tuple that contains (row
index
, new_board
) where row index
is the index of the row the piece ends up
in, or -1 if the column is already full. The new_board
is the new board after
the piece has been placed.
Assume that the given column is on the board. Remember that you can get pieces
in the board by using get_piece
. The argument max_rows
may be helpful in
determining which rows you should check for an empty slot to put the piece in.
Note: You will probably need to use the
replace_elem
function you wrote above twice to create the new board.
Note: You should not be indexing into the board directly. Instead, use the
get_piece
selector you just wrote.
def put_piece(board, max_rows, column, player):
"""Puts PLAYER's piece in the bottommost empty spot in the given column of
the board. Returns a tuple of two elements:
1. The index of the row the piece ends up in, or -1 if the column
is full.
2. The new board
>>> rows, columns = 2, 2
>>> board = create_board(rows, columns)
>>> row, new_board = put_piece(board, rows, 0, 'X')
>>> row
1
>>> row, new_board = put_piece(new_board, rows, 0, 'O')
>>> row
0
>>> row, new_board = put_piece(new_board, rows, 0, 'X')
>>> row
-1
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python ok -q get_piece --local
python ok -q put_piece --local
You are now crossing the abstraction barrier!!!
You have now implemented the constructor and selectors as well as ways to modify the attributes of your abstract data type, the board. From now on, you should never need to treat the board as if it were a list. Instead, trust your abstraction barrier and use the functions you have written so far.
Question 4: Making a move
In ourput_piece
function, we assumed that the player gives a valid column number. This won't always be
the case though. Implement make_move
which checks that the given column is valid, and that the
column isn't full. make_move
returns a 2-element tuple (row index, board). If the move is valid,
put a piece in the column and return the index of the row the piece ends up in (do you have a function
that will help you do this?) as well as the new board. If the move is invalid, make_move
should return
-1 and the original board, unchanged.
The arguments max_rows
and max_cols
describe the dimensions of the board and may be useful in determining whether or not a move is valid.
def make_move(board, max_rows, max_cols, col, player):
"""Put player's piece in column COL of the board, if it is a valid move.
Return a tuple of two values:
1. If the move is valid, make_move returns the index of the row the
piece is placed in. Otherwise, it returns -1.
2. The updated board
>>> rows, columns = 2, 2
>>> board = create_board(rows, columns)
>>> row, board = make_move(board, rows, columns, 0, 'X')
>>> row
1
>>> get_piece(board, 1, 0)
'X'
>>> row, board = make_move(board, rows, columns, 0, 'O')
>>> row
0
>>> row, board = make_move(board, rows, columns, 0, 'X')
>>> row
-1
>>> row, board = make_move(board, rows, columns, -4, '0')
>>> row
-1
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python ok -q make_move --local
Question 5: Printing and viewing the board
Wouldn't it be great if we could actually see the board and the pieces on it? That is exactly whatprint_board
is for.
In questions 1 and 2, we implemented the constructors and selectors, so let's use some of them now.
Let's implement print_board
as if we didn't know the board is a list of lists. This is called
respecting the data abstraction barrier. You can do this by using your above functions (not necessarily all
of them). The arguments max_rows
and max_cols
describe the dimensions of the board.
We would like our board to look good, and for this, strings do a better job than lists. Thus, we would
like the row ['X', 'X', 'O', '-']
to be printed as 'X X O -'
where the pieces are separated by a
single blank space. Remember that 'hel' + 'lo' = 'hello'
.
Hint: You might find that you're failing doctests that seem to be correct. Chances are that you have an extra space character at the end of your rows in your board. A function that might come in handy is strip()
, which removes leading and trailing whitespace from a string. For example:
>>> s = ' hello '
>>> s = s.strip()
>>> s
'hello'
def print_board(board, max_rows, max_cols):
"""Prints the board. Row 0 is at the top, and column 0 at the far left.
>>> rows, columns = 2, 2
>>> board = create_board(rows, columns)
>>> print_board(board, rows, columns)
- -
- -
>>> new_board = make_move(board, rows, columns, 0, 'X')[1]
>>> print_board(new_board, rows, columns)
- -
X -
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python ok -q print_board --local
Now we can actually play the game! To try it out, run the following command in the terminal from your lab04
directory:
$ python3 -i lab04.py
>>> start_game()
Question 6: Checking for victory
Fun, right? At least if you don't care about winning...The last thing we need for our Connect N game to be fully functioning is the ability to detect a win.
Let's implement check_win_row
and check_win_col
that check for horizontal and vertical wins for the given
player. Since we check for wins after each turn, and only the player who made the most recent move can have a
win, check_win_row
and check_win_col
should only check for a win for the player that is passed as an
argument. Also remember that num_connect
tells you how many adjacent pieces are needed for a win. The
arguments max_rows
and max_cols
describe the dimensions of the game board.
As in print_board
, use the data abstractions you just built.
def check_win_row(board, max_rows, max_cols, num_connect, row, player):
""" Returns True if the given player has a horizontal win
in the given row, and otherwise False.
>>> rows, columns, num_connect = 4, 4, 2
>>> board = create_board(rows, columns)
>>> board = make_move(board, rows, columns, 0, 'X')[1]
>>> board = make_move(board, rows, columns, 0, 'O')[1]
>>> check_win_row(board, rows, columns, num_connect, 3, 'O')
False
>>> board = make_move(board, rows, columns, 2, 'X')[1]
>>> board = make_move(board, rows, columns, 0, 'O')[1]
>>> check_win_row(board, rows, columns, num_connect, 3, 'X')
False
>>> board = make_move(board, rows, columns, 1, 'X')[1]
>>> check_win_row(board, rows, columns, num_connect, 3, 'X')
True
>>> check_win_row(board, rows, columns, 4, 3, 'X') # A win depends on the value of num_connect
False
>>> check_win_row(board, rows, columns, num_connect, 3, 'O') # We only detect wins for the given player
False
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python ok -q check_win_row --local
def check_win_column(board, max_rows, max_cols, num_connect, col, player):
""" Returns True if the given player has a vertical win in the given column,
and otherwise False.
>>> rows, columns, num_connect = 5, 5, 2
>>> board = create_board(rows, columns)
>>> board = make_move(board, rows, columns, 0, 'X')[1]
>>> board = make_move(board, rows, columns, 1, 'O')[1]
>>> check_win_column(board, rows, columns, num_connect, 0, 'X')
False
>>> board = make_move(board, rows, columns, 1, 'X')[1]
>>> board = make_move(board, rows, columns, 1, 'O')[1]
>>> check_win_column(board, rows, columns, num_connect, 1, 'O')
False
>>> board = make_move(board, rows, columns, 2, 'X')[1]
>>> board = make_move(board, rows, columns, 1, 'O')[1]
>>> check_win_column(board, rows, columns, num_connect, 1, 'O')
True
>>> check_win_column(board, rows, columns, 4, 1, 'O')
False
>>> check_win_column(board, rows, columns, num_connect, 1, 'X')
False
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python ok -q check_win_column --local
Question 7: Winning!
We're almost done with our Connect N game! The last thing we should do is to implementcheck_win
.
This function should return True if there is any win - that is, horizontally, vertically or diagonally.
We have provided the function check_win_diagonal(board, max_rows, max_cols, num_connect, row, col, player)
which returns True, if the given player has a diagonal win passing the spot (row, column), and otherwise False.
Try to write check_win
in one line.
def check_win(board, max_rows, max_cols, num_connect, row, col, player):
"""Returns True if the given player has any kind of win after placing a
piece at (row, col), and False otherwise.
>>> rows, columns, num_connect = 2, 2, 2
>>> board = create_board(rows, columns)
>>> board = make_move(board, rows, columns, 0, 'X')[1]
>>> board = make_move(board, rows, columns, 1, 'O')[1]
>>> board = make_move(board, rows, columns, 0, 'X')[1]
>>> check_win(board, rows, columns, num_connect, 0, 0, 'O')
False
>>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
True
>>> board = create_board(rows, columns)
>>> board = make_move(board, rows, columns, 0, 'X')[1]
>>> board = make_move(board, rows, columns, 0, 'O')[1]
>>> board = make_move(board, rows, columns, 1, 'X')[1]
>>> check_win(board, rows, columns, num_connect, 1, 0, 'X')
True
>>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
False
>>> board = create_board(rows, columns)
>>> board = make_move(board, rows, columns, 0, 'X')[1]
>>> board = make_move(board, rows, columns, 1, 'O')[1]
>>> board = make_move(board, rows, columns, 1, 'X')[1]
>>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
False
>>> check_win(board, rows, columns, num_connect, 1, 0, 'X')
True
"""
diagonal_win = check_win_diagonal(board, max_rows, max_cols, num_connect,
row, col, player)
"*** YOUR CODE HERE ***"
return _______
Use OK to test your code:
python ok -q check_win --local
Congratulations, you just built your own Connect N game! Don't you think the person next to you would be down for a game? As before, run the game by running the following command in your terminal:
python -i hw04.py
>>> start_game()
We implemented the play
function for you, but if you are curious, you should take a look at it.
As you will see, thanks to the layers of data abstraction, the play
function is actually very simple.
Notice how we use your make_move
, print_board
, and check_win
to play the game without even knowing
how the board and pieces are implemented.