Question

I coded the following solution for problem set 4 in 6.00. It works 100x faster than the one proposed by the course solution, but I am not sure if its a good idea to use globals and if I can do anything to get rid of them.

Answer 1

record = []
solved = False

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)
"""
global record
global solved
while (start < len(text)) and (solved == False):
for i in range(0,28):
if solved == False:
cipher = apply_shift(text[start:], i)
split = cipher.split()
if is_word(wordlist,split[0]):
record.append((start,i))
find_best_shifts_rec(wordlist, text[:start]+cipher, start+len(split[0])+1)
if solved == False:
record.pop()
return []
solved = True
return record

Answer 2

Can you just make "record" and "solved" parameters to the function? I might give them default values (see http://effbot.org/zone/default-values.htm if you're unfamiliar), making the code like this:

def find_best_shifts_rec(wordlist, text, start, record=[], solved=False):
"""
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)
"""

while (start < len(text)) and (solved == False):
for i in range(0,28):
if solved == False:
cipher = apply_shift(text[start:], i)
split = cipher.split()
if is_word(wordlist,split[0]):
record.append((start,i))
find_best_shifts_rec(wordlist, text[:start]+cipher, start+len(split[0])+1, record, solved)
if solved == False:
record.pop()
return []
solved = True
return record


The nice thing about using default parameters is that the call to this function (when you are outside of the function) can remain the same - users do not need to know that you've added in additional parameters.

Hope this helps!

Answer 3

def find_best_shifts_rec(wordlist, text, start, record=[], solved=False):
while (start < len(text)) and (solved == False):
for i in range(0,28):
if solved == False:
cipher = apply_shift(text[start:], i)
split = cipher.split()
if is_word(wordlist,split[0]):
print "Before call:", text
record.append((start,i))
find_best_shifts_rec(wordlist, text[:start]+cipher, start+len(split[0])+1, record, solved)
print "After call:", text
if solved == False:
record.pop()
print "Popping last record."
return []
solved = True
print "Shifts", record
return record

***
Loading word list from file...
55909 words loaded.
Before call: eqorqukvqtbmultiform wyy ion
Before call: compositor ksjrgdmpkyuwwygml
Before call: compositor multiform wyy ion
Shifts [(0, 25), (11, 2), (21, 5)]
After call: compositor multiform wyy ion
Popping last record.
After call: compositor ksjrgdmpkyuwwygml
Popping last record.
After call: eqorqukvqtbmultiform wyy ion
Popping last record.

FINAL SHIFTS []
eqorqukvqtbmultiform wyy ion
***

The answer I get in "Shifts" is right. But the function does not stop there and starts popping records after the problem is solved.

Answer 4

To be honest, globals are fine in this context. If you were really worried about it, you could use a closure to hide the variables; something like:

def best_shift_finder(record = [], solved = False):
def find_best_shifts_rec(wordlist, text):
# same code as your first post

best_shift_finder()(wordlist, text)

*Should* do the trick. The trouble above is that when you pass record and solved recursively, you don't modify the original values. If you wanted to work it properly, you'd have to return the values of record and solved from the function and update the values when you call it recursively. It can be a bit of a pain.