Due by 11:59pm on Friday, 3/24

Instructions

Download hw06.zip.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using OK: If you have any questions about using OK, please refer to this guide.

Homework Questions

Exceptions

Question 1: No KeyErrors Allowed

If we try to look up a key that does not exist in a dictionary, then Python will raise a KeyError. Write the function avoid_keyerror which returns the value mapped to key in the dictionary. If key does not exist, print 'Avoid Exception' and map key to the string 'no value'. Use exception handling as opposed to Python's built-in .get("no_value") method on dictionaries, which is the official way to solve this problem.

def avoid_keyerror(dictionary, key):
    """ Returns the value associated with key in dictionary. If key 
    does not exist in the dictionary, print out 'Avoid Exception',
    insert KEY in the dictionary with value 'no value' and also return
    'no value'.

    >>> d = {1: 'one', 3: 'three', 5: 'five'}
    >>> avoid_keyerror(d, 3)
    'three'
    >>> avoid_keyerror(d, 4)
    Avoid Exception
    'no value'
    >>> d[4]
    'no value'
    >>> avoid_keyerror(d, 4)
    'no value'
    >>> avoid_keyerror(d, 3)
    'three'
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q avoid_keyerror

Question 2: Replace a Value

Consider a program that is intended to find the first occurrence of a certain label, target in a linked list and replace it with another, replacement, non-destructively. An obvious implementation looks like this:

def lst_replace_first_obvious(L, target, replacement):
    """Return the result of replacing the first occurrence of TARGET
    in linked-list L with REPLACEMENT.  Returns the original L unchanged
    if TARGET does not occur.  Non-destructive."""
    if L is Link.empty:
        return Link.empty
    elif L.first == target:
        return Link(replacement, L.rest)
    else:
        return Link(L.first, lst_replace_first_obvious(L.rest, target, replacement))

However, this solution creates an entirely new list even when the target does not appear. Suppose we'd like to avoid creating new list elements when that happens, and instead simply return the original input list. Show how to do so by using a try statement to handle the case that target does not appear in the list.

Use OK to test your code:

python3 ok -q lst_replace_first

Extra questions

Extra questions are not worth extra credit and are entirely optional.

[From a contest in St. Petersburg, courtesy of M. Dynin] Given a rectangle of letters (such as

AB
BC

), a starting position within that rectangle (such as the character in the upper-left corner), and a string (such as "ABBC", consider the question of finding the number of paths through the letters that

• match the given string,
• begin at the starting position, and
• at each step move one square in one of the eight compass directions (north, south, east, west, northeast, northwest, southeast, southwest).

For the given example, there are two such paths. They are E-SW-E and S-NE-S---that is, "one step east, one step southwest, one step east" and "one step south, one step northeast, and one step south." For the rectangle

CBB
BBA

and the string "BBCBBA", starting at the square in the middle of the top row, there are 12 paths. Paths are allowed to visit the same position any number of times.

Implement the function num_paths to return these values. The array will be represented as an array of same-length strings (the two examples above are

{ "AB", "BC" }  and  { "CBB", "BBA" }

). There is an obvious recursive solution, but it will take too long on some doctests. Use the idea of memoizing or dynamic programming to get a solution that completes in reasonable time.

Use OK to test your code:

python3 ok -q num_paths