Due by 4pm on Wednesday, 2/22
You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers (the dot is significant: it denotes the current directory)
cp ~cs61a/lib/hw/hw5.py .
Readings. Chapter 2.4
Destructive and Nondestructive Operations. The terms "destructive" and "nondestructive" describe the effects of an operation on the states of the objects that provide input. An operation is nondestructive if the state of the input objects is unchanged, and the operation creates entirely new objects to represent its result. With a nondestructive operation, the original input values generally remain intact. An operation is destructive if it sometimes changes the state of some of the input objects, so that a client can't count on the original input values remaining around except by maintaining copies. An operation may be destructive for speed or simply because its abstract purpose is to make a permanent change in the state of some object.
Q1. Write two functions that reverse the contents of a list as a side effect. In the first one, use only assignments to individual list elements (do not use slicing). In the second, do everything in one statement with slicing. In both cases, do not create any new lists (no list displays, generators, applications of list, etc. These are destructive operations.:
def reverse_list1(L):
"""Reverse the contents of L and return None. (Use a loop)"""
def reverse_list2(L):
"""Reverse the contents of L and return None. (One assignment)"""
______________________________
Q2. In pre-Python 3 days, there was no nonlocal statement. Show how to implement make_account from lecture (using a mutable data structure). The answer has nothing to do with global: there can be any number of independent accounts. As in lecture, an account will be represented as a function:
def make_account(balance):
"""A new bank account with initial balance `balance`.
If acc is an account returned by make_account, then
acc('balance') returns the current balance.
acc('deposit', d) deposits d cents into the account
acc('withdraw', w) withdraws w cents from the account, if
possible.
'deposit' and 'withdraw' return acc itself."""
Q3. Riffle shuffling combines two sequences by interleaving them---alternately including one item from one sequence and one from the next. Using ordinary Python lists, implement a nondestructive shuffle. The answer is short, and doesn't even need a loop.:
def shuffle(r):
"""Return a list that interleaves the first half of sequence R
with the second half. The resulting list starts with the first item
of R, then the middle item, then the second item, then the item after
the middle, etc. If R contains an odd number of items, the extra
one is in the first half and goes on the end of the resulting list.
Nondestructive: does not disturb the original list.
>>> L = [0, 1, 2, 3, 4, 5, 6, 7]
>>> R = shuffle(L)
>>> L
[0, 1, 2, 3, 4, 5, 6, 7]
>>> R
[0, 4, 1, 5, 2, 6, 3, 7]
"""
Q4. J. H. Conway's "game" of Life (briefly presented in class) is a simulation run on a rectangular grid of squares, each of which is, at any given time, either empty or occupied by a single organism. At the beginning of each turn, organisms in occupied cells die and organisms are born into unoccupied cells according to the following rules:
Variations of the game treat the edges of the board in various ways: the board can be treated as infinite in all directions, as surrounded by "desert" cells in which organisms are never born, wrapped around so as to be doughnut shaped, etc. We will go with the surrounded-by-desert option.
The Python class Life in the hw5.py file represents Life boards, providing operations for initializing their contents, advancing by one turn, and producing printable versions of their contents. Fill in the advance operation to make it work. (While you're at it, make sure you understand how the parts we've already implemented work!).:
class Life(object):
"""A representation of a position in J.H. Conway's Game of Life."""
def __init__(self, starting_board):
"""Initialize SELF to the position depicted in the string
STARTING_BOARD, which has the form "xxxxx\nxxxxx\nxxxxx..." where
each x is either '.' or '*', and the newlines separate rows.
The number of x's in each row must be equal. Leading
and trailing whitespace is ignored."""
def advance(self):
"""Advance SELF's board to the next turn."""
# YOUR SOLUTION HERE
def printable(self, empty=" ", occupied="*"):
"""A printable representation of SELF, using EMPTY for unoccupied
squares and OCCUPIED for occupied ones."""
def __str__(self):
"""String representation returned by str(SELF)."""
Mutable Rlists Rlists as presented so far are immutable. Consider now an extension of rlist to make it mutable:
empty_rlist = None
def make_rlist(first, last = None):
return [first, last]
def first(r):
return r[0]
def rest(r):
return r[1]
def set_first(r, new_first):
r[0] = new_first
def set_rest(r, new_rest):
r[1] = new_rest
def rlist(*items):
"""A new rlist consisting of ITEMS."""
result = empty_rlist
for i in range(1, len(items)+1):
result = make_rlist(items[-i], result)
return result
def rlist_to_list(r):
"""The standard Python list containing the same items as R."""
result = []
while r != empty_rlist:
result.append(first(r))
r = rest(r)
return result
Functions that make use of set_first and set_rest are called destructive, since they typically destroy existing data.
Q5. Using the mutable rlist abstraction, implement a destructive filter function:
def dfilter_rlist(pred, r):
"""Remove all items in R for which PRED returns a false value, returning
the rlist of the remaining items. Destructive: does not use
make_rlist (or create new lists by other means either).
>>> L = rlist(0, 1, 2, 4, 5, 7)
>>> R = dfilter_rlist(lambda x: x%2 == 0, L)
>>> R
[0, [2, [4, None]]]
>>> L
[0, [2, [4, None]]]
"""
Q6. [Extra for experts] Using mutable rlists, implement a destructive shuffle operation that does not create new list objects:
def dshuffle_rlist(r):
"""Interleave the first half of rlist R with the second half.
The resulting list starts with the first item of the original R,
then the middle item, then the second item, then the item after
the middle, etc. If R contains an odd number of items, the extra
one is in the first half and goes on the end of the resulting list.
Destructive: does not use make_rlist (or create new lists by
other means either). Returns the modified list.
>>> L = rlist(0, 1, 2, 3, 4, 5, 6, 7)
>>> R = dshuffle_rlist(L)
>>> rlist_to_list(L)
[0, 4, 1, 5, 2, 6, 3, 7]
>>> rlist_to_list(R)
[0, 4, 1, 5, 2, 6, 3, 7]
>>> L = rlist(0, 1, 2, 3, 4, 5, 6)
>>> R = dshuffle_rlist(L)
>>> rlist_to_list(L)
[0, 4, 1, 5, 2, 6, 3]
>>> rlist_to_list(R)
[0, 4, 1, 5, 2, 6, 3]
"""