Problem set 4: the Caesar Cipher

Part b: Python code 

To do this, implement the following function according to the specification. 

def find_best_shifts(wordlist, text): 

    """ 

    Given a scrambled string, returns a shift key that will decode the text 

to 

    words in wordlist, or None if there is no such key. 

 

    ***HINT: Make use of the recursive function 

    find_best_shifts_rec(wordlist, text, start)*** 

 

    wordlist: list of words 

    text: scambled text to try to find the words for 

    returns: list of tuples.  each tuple is (position in text, amount of 

shift) 

 

    Examples: 

    >>> s = random_scrambled(wordlist, 3) 

    >>> s 

    'eqorqukvqtbmultiform wyy ion' 

    >>> shifts = find_best_shifts(wordlist, s) 

    >>> shifts 

    [(0, 25), (11, 2), (21, 5)] 

    >>> apply_shifts(s, shifts) 

    'compositor multiform accents' 

    >>> s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 

18), (12, 16)]) 

    >>> s 

    'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?' 

    >>> shifts = find_best_shifts(wordlist, s) 

    >>> print apply_shifts(s, shifts) 

    Do Androids Dream of Electric Sheep? 

    """ 

To solve this problem successfully, we highly recommend that you use recursion (did we say use 

recursion again?). The non-recursive version of this function is much more difficult to 

understand and code. The key to getting the recursion correct is in understanding the seemingly 

---

unnecessary parameter “start”. As always with recursion, you should begin by thinking about 

your base case, the simplest possible sub-problem you will need to solve. What value of start 

would make a good base case? (Hint: the answer is NOT zero.) 

To help you test your code, we’ve given you two simple helper functions: 

random_string(wordlist, n) generates n random words from wordlist and returns them in a string. 

random_scrambled(wordlist, n) generates n random words from wordlist and returns them in a 

string after encrypting them with a random multi-level Caesar shift. You can start by making 

sure your code decrypts a single word correctly, then move up to 2 and higher. 

NOTE: This function depends on your implementation of apply_shifts, so it will not work 

correctly until you have completed Problem 3. 

def find_best_shifts_rec(wordlist, text, start): 

    """ 

    Given a scrambled string and a starting position from which 

    to decode, returns a shift key that will decode the text to 

    words in wordlist, or None if there is no such key. 

    Hint: You will find this function much easier to implement 

    if you use recursion. 

 

    wordlist: list of words 

    text: scambled text to try to find the words for 

    start: where to start looking at shifts 

    returns: list of tuples.  each tuple is (position in text, amount of 

shift) 

    """ 

    ### TODO.