15-112 Fall 2013 Quiz 5b
* 25 Minutes.  No calculators, no notes, no books, no computers.  * Show your work. Circle your answers.

1.       Code Tracing [10 pts]  Indicate what this will print.
For this question only:  you may use T for True and F for False, and you may omit all brackets [ ] in your answers.
Also, to receive any credit, you must use arrow diagrams to show your work.

a = [[1, 2],[3, 4]]

(b,c,d) = (a, copy.copy(a), copy.deepcopy(a))

try:

    a[0][0] += 10

except:

    b[0][1] += 20

try:

    c[1][0] += 30

    d[1][1] += 40

    b[0] = range(5,7)

    a[2][1] = b[1][2]

except:

    a = c
for L in [a,b,c,d]: print L

 

2.       Reasoning Over Code [15 pts; 7.5 pts each]
Find arguments for the following functions that make each return True.

def f(L):

    # Assume L is a ragged (non-rectangular!) 2d list

    return (max(L[-1]) == 2) and L == [range(n+1) for n in xrange(len(L))]

def f(s1, s2):

    d = dict()

    for val in s1: d[val] = 1

    for val in s2: d[val] = 2 + d.get(val,0)

    for x in range(4): assert(d.get(x,0) == x)
    return True

 

3.        Free Response:  Word Search with wraparound and multi-letter cells [75 pts]
Here we will modify wordSearch in two ways.  First, we will allow wraparound (as in the Othello hw).  For example:
    board = [ [ 'a', 'b', 'c' ],
              [ 'd', 'e', 'f' ],
              [ 'h', 'i', 'j' ] ]
This board contains 'ah' heading up from (0,0), 'ca' heading right from (0,2), and 'ic' heading down-right from (2,1).   Second, we will allow multiple letters in a single cell, which must be matched in order and in their entirety (no partial matches).  For example:
    board = [ [ 'a', 'bcd', 'e' ],
This board contains 'abcd' and 'abcde' but not 'abc'.  Heading left, it also contains 'ebcd' and 'ebcda' but not 'ebc' and also not 'edcb'.  And since we also support wraparound, this board contains 'bcdea'.  To make this work, rewrite the innermost function of wordsearch accordingly.  Among other parameters, your function should take a direction as a non-negative int (not a tuple), and return True if the word is in the wordSearch and False otherwise.