Lab 4: Lists and Data Abstraction

Due at 11:59pm on 09/24/2015.

Starter Files

Download lab04.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

• To receive credit for this lab, you must complete Questions 2-11 in lab04.py and submit through OK.
• Questions 12-13 are extra practice. It can be found in the lab04_extra.py file. It is recommended that you complete this problem on your own time.

Lists warm-up!

Question 1: Fill in the blanks

In each of following, what does the list indexing look like to get the number 7? Think about each one and then check your solution with the toggle button.

def get_seven_a(x):
    """
    >>> x = [1, 3, [5, 7], 9]
    >>> get_seven_a(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[2][1]

def get_seven_a(x):
    return x[2][1]

def get_seven_b(x):
    """
    >>> x = [[7]]
    >>> get_seven_b(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[0][0]

def get_seven_b(x):
    return x[0][0]

def get_seven_c(x):
    """
    >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    >>> get_seven_c(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[1][1][1][1][1][1][0]

def get_seven_c(x):
    return x[1][1][1][1][1][1][0]

Question 2: If this not that

Define if_this_not_that, which takes a list of integers i_list, and an integer this, and for each element in i_list if the element is larger than this then print the element, otherwise print that.

def if_this_not_that(i_list, this):
    """
    >>> original_list = [1, 2, 3, 4, 5]
    >>> if_this_not_that(original_list, 3)
    that
    that
    that
    4
    5
    """
    "*** YOUR CODE HERE ***"
    for elem in i_list:
        if elem <= this:
            print("that")
        else:
            print(elem)

Use OK to test your code:

python3 ok -q if_this_not_that

Question 3: Reverse (iteratively)

Write a function reverse_iter that takes a list and returns a new list that is the reverse of the original. Use iteration! You may also use slicing notation. Do not use lst[::-1]!

def reverse_iter(lst):
    """Returns the reverse of the given list.

    >>> reverse_iter([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    new, i = [], 0
    while i < len(lst):
        new = [lst[i]] + new
        i += 1
    return new

Use OK to test your code:

python3 ok -q reverse_iter

Data Abstraction

Data abstraction is a powerful concept in computer science that allows programmers to treat code as objects --- for example, car objects, chair objects, people objects, etc. That way, programmers don't have to worry about how code is implemented --- they just have to know what it does.

Data abstraction mimics how we think about the world. For example, when you want to drive a car, you don't need to know how the engine was built or what kind of material the tires are made of. You just have to know how to turn the wheel and press the gas pedal.

An abstract data type consists of two types of functions:

• Constructors: functions that build the abstract data type.
• Selectors: functions that retrieve information from the data type.

For example, say we have an abstract data type called city. This city object will hold the city's name, and its latitude and longitude. To create a city object, you'd use a constructor like

city = make_city(name, lat, lon)

To extract the information of a city object, you would use the selectors like

get_name(city)
get_lat(city)
get_lon(city)

For example, here is how we would use the make_city constructor to create a city object to represent Berkeley and the selectors to access its information.

>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
'Berkeley'
>>> get_lat(berkeley)
122
>>> get_lon(berkeley)
37

The following code will compute the distance between two city objects:

from math import sqrt
def distance(city_1, city_2):
    lat_1, lon_1 = get_lat(city_1), get_lon(city_1)
    lat_2, lon_2 = get_lat(city_2), get_lon(city_2)
    return sqrt((lat_1 - lat_2)**2 + (lon_1 - lon_2)**2)

Notice that we don't need to know how these functions were implemented. We are assuming that someone else has defined them for us.

It's okay if the end user doesn't know how functions were implemented. However, the functions still have to be defined by someone. We'll look into defining the constructors and selectors later in this discussion.

Question 4: Closer city

Implement closer_city, a function that takes a latitude, longitude, and two cities, and returns the name of the city that is relatively closer to the provided latitude and longitude.

You may only use selectors and constructors (introduced above) for this question. You may also use the distance function defined above. All of these functions can be found in utils.py, if you are curious how they are implemented. However, the point of data abstraction, as we've said, is that we do not need to know how an abstract data type is implemented, but rather just how we can interact with and use the data type.

def closer_city(lat, lon, city1, city2):
    """ Returns the name of either city1 or city2, whichever is closest
        to coordinate (lat, lon).

        >>> berkeley = make_city('Berkeley', 37.87, 112.26)
        >>> stanford = make_city('Stanford', 34.05, 118.25)
        >>> closer_city(38.33, 121.44, berkeley, stanford)
        'Stanford'
        >>> bucharest = make_city('Bucharest', 44.43, 26.10)
        >>> vienna = make_city('Vienna', 48.20, 16.37)
        >>> closer_city(41.29, 174.78, bucharest, vienna)
        'Bucharest'
    """
    "*** YOUR CODE HERE ***"
    new_city = make_city('arb', lat, lon)
    dist1 = distance(city1, new_city)
    dist2 = distance(city2, new_city)
    if dist1 < dist2:
         return get_name(city1)
    return get_name(city2)

Use OK to test your code:

python3 ok -q closer_city

Connect N

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 5: Creating an empty board

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 _______
    return ["-" for i in range(size)]

Use OK to test your code:

python3 ok -q create_row

def create_board(rows, columns):
    """Returns a board with the given dimensions.

    >>> create_board(3, 5)
    [['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-']]
    """
    "*** YOUR CODE HERE ***"
    return _______
    return [create_row(columns) for i in range(rows)]

Use OK to test your code:

python3 ok -q create_board

Question 6: 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 _______
    return lst[:index] + [elem] + lst[(index + 1):]

Use OK to test your code:

python3 ok -q replace_elem

Question 7: 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 _______
    return board[row][column]

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 ***"
    curr_row_index = max_rows - 1
    while curr_row_index >= 0 and get_piece(board, curr_row_index, column) != "-":
        curr_row_index -= 1
    if curr_row_index >= 0:
        new_row = replace_elem(board[curr_row_index], column, player)
        new_board = replace_elem(board, curr_row_index, new_row)
        board = new_board
    return curr_row_index, board

Use OK to test your code:

python3 ok -q get_piece
python3 ok -q put_piece

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 8: Making a move

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 ***"
    if col < 0 or col >= max_cols:
        return -1, board
    return put_piece(board, max_rows, col, player)

Use OK to test your code:

python3 ok -q make_move

Question 9: Printing and viewing the board

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 ***"
    for row in range(max_rows):
        row_str = ''
        for col in range(max_cols):
            piece = get_piece(board, row, col)
            row_str += piece + " "
        print(row_str.strip())

Use OK to test your code:

python3 ok -q print_board

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 10: Checking for victory

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 ***"
    adjacent = 0
    for col in range(max_cols):
        piece = get_piece(board, row, col)
        if piece == player:
            adjacent += 1
        else:
            adjacent = 0
        if adjacent >= num_connect:
            return True
    return False

Use OK to test your code:

python3 ok -q check_win_row

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 ***"
    adjacent = 0
    for row in range(max_rows):
        piece = get_piece(board, row, col)
        if piece == player:
            adjacent += 1
        else:
            adjacent = 0
        if adjacent >= num_connect:
            return True
    return False

Use OK to test your code:

python3 ok -q check_win_column

Question 11: Winning!

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 _______
    return check_win_row(board, max_rows, max_cols, num_connect, row, player) or \
             check_win_column(board, max_rows, max_cols, num_connect, col, player) or \
               diagonal_win

Use OK to test your code:

python3 ok -q check_win

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:

$ python3 -i lab04.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.

Extra Questions

Questions in this section are not required for submission. However, we encourage you to try them out on your own time for extra practice.

Question 12: Flatten

Write a function flatten that takes a (possibly deep) list and "flattens" it. For example:

>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]

Hint: you can check if something is a list by using the built-in type function. For example,

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

def flatten(lst):
    """Returns a flattened version of lst.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]      # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    """
    "*** YOUR CODE HERE ***"
    if not lst:
        return []
    elif type(lst[0]) == list:
        return flatten(lst[0]) + flatten(lst[1:])
    else:
        return [lst[0]] + flatten(lst[1:])

Use OK to test your code:

python3 ok -q flatten

Question 13: Merge

Write a function merge that takes 2 sorted lists lst1 and lst2, and returns a new list that contains all the elements in the two lists in sorted order.

def merge(lst1, lst2):
    """Merges two sorted lists.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
    # recursive
    if not lst1 or not lst2:
        return lst1 + lst2
    elif lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])

# Iterative solution 
def merge_iter(lst1, lst2):
    """Merges two sorted lists.

    >>> merge_iter([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge_iter([], [2, 4, 6])
    [2, 4, 6]
    >>> merge_iter([1, 2, 3], [])
    [1, 2, 3]
    >>> merge_iter([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    new = []
    while lst1 and lst2:
        if lst1[0] < lst2[0]:
            new += [lst1[0]]
            lst1 = lst1[1:]
        else:
            new += [lst2[0]]
            lst2 = lst2[1:]
    if lst1:
        return new + lst1
    else:
        return new + lst2

Use OK to test your code:

python3 ok -q merge