Question

Just out of curiosity, How do you solve PS4 Question 4 the Recursive way? I figured out the iterative way (which it says is harder, but I found easier)

Answer 1

Here is the code that I used for it:

# Helper Code
def is_word(wordlist, word):
word = word.lower()
word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
return word in wordlist
# My Code
def build_coder(shift):
assert type(shift) == int, "You need to enter a whole number"
letterLookup = {' ': 52,'A': 26, 'C': 28, 'B': 27, 'E': 30, 'D': 29, 'G': 32, 'F': 31, 'I': 34, 'H': 33, 'K': 36, 'J': 35, 'M': 38, 'L': 37, 'O': 40, 'N': 39, 'Q': 42, 'P': 41, 'S': 44, 'R': 43, 'U': 46, 'T': 45, 'W': 48, 'V': 47, 'Y': 50, 'X': 49, 'Z': 51, 'a': 0, 'c': 2, 'b': 1, 'e': 4, 'd': 3, 'g': 6, 'f': 5, 'i': 8, 'h': 7, 'k': 10, 'j': 9, 'm': 12, 'l': 11, 'o': 14, 'n': 13, 'q': 16, 'p': 15, 's': 18, 'r': 17, 'u': 20, 't': 19, 'w': 22, 'v': 21, 'y': 24, 'x': 23, 'z': 25}
numberLookup = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g', 7: 'h', 8: 'i', 9: 'j', 10: 'k', 11: 'l', 12: 'm', 13: 'n', 14: 'o', 15: 'p', 16: 'q', 17: 'r', 18: 's', 19: 't', 20: 'u', 21: 'v', 22: 'w', 23: 'x', 24: 'y', 25: 'z', 26: 'A', 27: 'B', 28: 'C', 29: 'D', 30: 'E', 31: 'F', 32: 'G', 33: 'H', 34: 'I', 35: 'J', 36: 'K', 37: 'L', 38: 'M', 39: 'N', 40: 'O', 41: 'P', 42: 'Q', 43: 'R', 44: 'S', 45: 'T', 46: 'U', 47: 'V', 48: 'W', 49: 'X', 50: 'Y', 51: 'Z', 52: ' '}
result = {}
for key, val in letterLookup.items():
number = (val + shift) % 53
newLetter = numberLookup[number]
result[key] = newLetter
return result

def apply_coder(text, coder):
string = text
result = ""
for c in string:
if c not in coder:
result += c
else:
result += coder[c]
return result

def apply_shift(text, shift):
coder = None
try:
coder = build_coder(shift)
## return coder
return apply_coder(text,coder)
except Exception, e:
print e

def apply_shifts(text, shifts):
result = text
for (key, val) in shifts:
result = result[:key] + apply_shift(result[key:],val)
return result

Answer 2

and here is the iterative way:

def find_best_shifts(wordlist, text):
index_shift_tuples = []
scramble = text[:]
unscrambled = ""
are_letters = True
letterLookup = {' ': 52,'A': 26, 'C': 28, 'B': 27, 'E': 30, 'D': 29, 'G': 32, 'F': 31, 'I': 34, 'H': 33, 'K': 36, 'J': 35, 'M': 38, 'L': 37, 'O': 40, 'N': 39, 'Q': 42, 'P': 41, 'S': 44, 'R': 43, 'U': 46, 'T': 45, 'W': 48, 'V': 47, 'Y': 50, 'X': 49, 'Z': 51, 'a': 0, 'c': 2, 'b': 1, 'e': 4, 'd': 3, 'g': 6, 'f': 5, 'i': 8, 'h': 7, 'k': 10, 'j': 9, 'm': 12, 'l': 11, 'o': 14, 'n': 13, 'q': 16, 'p': 15, 's': 18, 'r': 17, 'u': 20, 't': 19, 'w': 22, 'v': 21, 'y': 24, 'x': 23, 'z': 25}

while len(scramble) > 0:
## print unscrambled, index_shift_tuples
## print scramble
if scramble[0] not in letterLookup:
are_letters = False
unscrambled = unscrambled[:-1] + scramble[0] + " "
for letter in scramble:
if letter in letterLookup:
are_letters = True
break
if are_letters == False:
break

for iterate in range(53):
encoded = apply_shift(scramble,iterate)
## print encoded
split = string.split(encoded)
## print split[0]
if is_word(wordlist,split[0]):
## print split[0]
if iterate == 0:
unscrambled = unscrambled + split[0] + " "
split.remove(split[0])
scramble = " ".join(split)
break
index_shift_tuples.append((len(unscrambled),iterate))
unscrambled = unscrambled + split[0] + " "
split.remove(split[0])
scramble = " ".join(split)
break
print unscrambled[:-1]
return index_shift_tuples

Answer 3

What was the actual question? Some of use aren't familiar with them.

Answer 4

The caesar cipher.
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-2/lecture-10-hashing-and-classes/MIT6_00SCS11_ps4.pdf

Problem 4. The idea is the alphabet is 'shifted' x amount of characters in order to create an unreadable cipher. In a previous problem you need to be able to solve a single shift. This problem requires you to solve a multi shift. As in, all characters in the string are shifted and then at particular index of the string till the end of the string it is shifted (leaving the part prior to the current index shifted at least once).

A shift can only occur between words.

It gives you a 'is_word()' helper function that produces either True or False.

The outline goes on to say that you should try to solve it recursively (twice) as recursion is easier. Yet I personally find iteration easier - my guess is due to not fully understanding recursion.

Answer 5

Is your overall solution that you shift the entire word by 1 until you hit a correct word?

Answer 6

I think in this case, the optimal solution is the solution that uses the least number of shifts, rather than any particular solution which allows for a shift between every word.

Answer 7

Suppose it took me \(n\) shifts by the time I got to the \(i^{th}\) word. Suppose we know this is optimal based upon recursion.

If the \((i+1)^{th}\) word fits my current shift, I can stick with it.

If it doesn't fit then there could be a more optimal solution. The cost of accepting a shift change just means we have \(n+1\) instead of \(n\) shifts. However it might be possible that by changing our last shift, we would be able to keep it down to \(n\) shifts.

Answer 8

So it is not just a matter of finding a correct shift but knowing where it is best to put the shifts.

Answer 9

Our base case is that the string is one word long with one shift I think.

Answer 10

By the way, there is a better way to do letter/number look-up.
```
def numberLookup(letter):
if 'a' <= letter and letter <= 'z':
return ord(letter) - ord('a')
elif 'A' <= letter and letter <= 'Z':
return ord(letter) - ord('A') + 26
return 52

def letterLookup(number):
if 0 <= number and number <= 25:
return chr(number + ord('a'))
if 26 <= number and number <= 51:
return chr(number + ord('A') - 26)
return ' '
```