PS4 problem 4 solution

def find_best_shifts(wordlist, text):

    return find_best_shifts_rec(wordlist, text, 0)


def find_spaces(text, start):
    """
    given a text and start position, find all the spaces
    returns a list of all the indices. empty list if none
    """
    tally = []
    tmptext = text[start:]
    counter = 0
    for i in tmptext:
        if i == " ":
            tally.append(counter+start)
        counter+=1
    return tally


def is_tupleorlist(arg1):
    """
    checks if something is a list or a tuple
    """
    if type(arg1) == tuple or type(arg1) == list:
        return True
    else:
        return 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.
    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)
    """

    """for every possible shift from 0 to 27"""
    for n in range (0,27):

        answer = []
        curr_shift_tuple = start,-n

        """set s to be the text up to the start parameter concatenated with the text
        after the start parameter that has been shifted by n"""
        s = text[:start] + apply_coder(text[start:], build_decoder(n))

        """look for the spaces beginning at the start location"""
        spaceslist = find_spaces(s, start)

        """if we find a space and the point from start to first space are a valid word then we
        recurse the function starting at the point of the space
        There's only 2 possible outcomes from doing our shift. Either there's a space in the shifted
        chunk or there isn't, which means we should test of that chunk is a word or not (we're at the
        end of the sentence possibly)
        """
        if spaceslist != []:
            j = s[start:spaceslist[0]] #j is the first word from start
            if is_word(wordlist, j): #check if j is a word
                foo = find_best_shifts_rec(wordlist, s, spaceslist[0]+1)
                if is_tupleorlist(foo): #if the recursive call returns a tuple then we've found an answer
                    answer.append(curr_shift_tuple)
                    answer += foo
                    return answer
                    #if foo is not a tuple then do nothing and continue checking range
        elif spaceslist == []:
            j = s[start:len(s)] #j is the string from start to the end of s
            if is_word(wordlist, j): #check if j is a word
                answer.append(curr_shift_tuple)
                return answer

    return None


foo2 = "dnbxivmcmzuwzmhuebgsfdhsnyhepvwumpikzlydi p aivl hfgesffsfnglqqc eyryofdeiziqjz xk"
bar = find_best_shifts(wordlist, foo2)
print bar
print apply_shifts(foo2, bar)