First time posting here, newbie to python but really enjoying what I'm doing with it. Working through the MIT Open courseware problems at the moment. Any suggestions of other similar resources?
My problem is with returning a recursive function that's meant to build a list of multi layer shifts as tuples where each tuple is (start location of shift,magnitude of shift). A shift of 5 would change a to f, a-b-c-d-e-f.
Code below for reference but you shouldn't need to read through it all.
text is the multi layered scrambled input, eg: 'grrkxmdffi jwyxechants idchdgyqapufeulij'
def find_best_shifts_rec(wordlist, text, start):
### TODO.
"""Shifts stay in place at least until a space, so shift can only start
with a new word
Base case? all remaining words are real
Need to find the base case which goes at the start of the function to
ensure it's all cleanly returned
Base case could be empty string if true words are removed?
Base case when start = end
take recursive out of loop
use other functions to simplify
"""
shifts = []
shift = 0
for a in range(27):
shift += 1
#creates a string and only shifts from the start point
"""text[:start] + optional add in not sure how it'd help"""
testtext = apply_shift(text[start:],-shift)
testlist = testtext.split()
#counts how many real words were made by the current shift
realwords = 0
for word in testlist:
if word in wordlist:
realwords += 1
else:
#as soon as a non valid word is found i know the shift is not valid
break
if a == 27 and realwords == 0:
print 'here\'s the prob'
#if one or more words are real
if realwords > 0:
#add the location and magnitude of shift
shifts = [(start,shift)]
#recursive call - start needs to be the end of the last valid word
start += testtext.find(testlist[realwords - 1]) + len(testlist[realwords - 1]) + 1
if start >= len(text):
#Base case
return shifts
else:
return shifts + find_best_shifts_rec(wordlist,text,start)
This frequently returns the correct list of tuples, but sometimes, with this text input for example, I get the error:
return shifts + find_best_shifts_rec(wordlist,text,start)
TypeError: can only concatenate list (not "NoneType") to list
this error is for the following at the very bottom of my code
else:
return shifts + find_best_shifts_rec(wordlist,text,start)
From what I gather, one of the recursive calls returns the None value, and then trying to conc this with the list throws up the error. How can I get around this?
EDIT:
By adding to the end:
elif a == 26: return [()]
I can prevent the type error when it can't find a correct shift. How can I get the entire function to return none?
Below is my attempt at reworking your code to do what you want. Specific changes: dropped the range from 27 to 26 to let the loop exit naturally and return the empty shifts array; combined a and shift and started them at zero so an unencoded text will return [(0, 0)]; the .find() logic will mess up if the same word appears in the list twice, changed it to rindex() as a bandaid (i.e. the last correctly decoded one is where you want to start, not the first).
def find_best_shifts_rec(wordlist, text, start=0):
shifts = []
for shift in range(26):
# creates a string and only shifts from the start point
testtext = apply_shift(text[start:], -shift)
testlist = testtext.split()
# words made by the current shift
realwords = []
for word in testlist:
if word in wordlist:
realwords.append(word)
else: # as soon as an invalid word is found I know the shift is invalid
break
if realwords: # if one or more words are real
# add the location and magnitude of shift
shifts = [(start, shift)]
# recursive call - start needs to be the end of the last valid word
realword = realwords[-1]
start += testtext.rindex(realword) + len(realword) + 1
if start >= len(text):
return shifts # base case
return shifts + find_best_shifts_rec(wordlist, text, start)
return shifts
'lbh fwj hlzkv tbizljb'