Phase 3 - Autocorrect

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/proj/typing_test/#phase-3-autocorrect

Problem 04: Autocorrect Skeleton

Specs: https://inst.eecs.berkeley.edu/~cs61a/su19/proj/typing_test/#problem-04-autocorrect-skeleton-2-pts

def autocorrect(user_input, words_list, score_function):
    if user_input in words_list:
        return user_input
    
    score_log = {}
    
    for word in words_list:
        score_key = score_function(user_input, word)
        
        if score_key not in score_log:
            score_log[score_key] = word
    return score_log[min(score_log)]

Problem 05: First Score Function

Specs: https://inst.eecs.berkeley.edu/~cs61a/su19/proj/typing_test/#problem-05-first-score-function-2-pts

def swap_score(word1, word2):
    if len(word1) <= 0 or len(word2) <= 0:
        return 0
    else:
        return (0 if word1[0] == word2[0] else 1) + swap_score(word1[1:], word2[1:])

Problem 06: Second Score Function

Specs: https://inst.eecs.berkeley.edu/~cs61a/su19/proj/typing_test/#problem-06-second-score-function-3-pts

add_char = lambda word1, char: char + word1
rem_char = lambda word1: word1[1:]
sub_char = lambda word1, char: char + word1[1:]
def score_function(word1, word2):
    """A score_function that computes the edit distance between word1 and word2."""
    #words match
    if word1 == word2:
        return 0
    elif len(word2) == 0:
        return len(word1)
    elif len(word1) == 0:
        return 1 + score_function(add_char(word1, word2[0]), word2)
    elif word1[0] == word2[0]:
        return 0 + score_function(word1[1:], word2[1:])
    elif len(word1) > len(word2):
        return 1 + min(
            score_function(sub_char(word1, word2[0]), word2),
            score_function(rem_char(word1), word2)
        )
    else:
        return 1 + min(
            score_function(sub_char(word1, word2[0]), word2),
            score_function(rem_char(word1), word2),
            score_function(add_char(word1, word2[0]), word2)
        )

Problem 07: Accuracy

Specs: https://inst.eecs.berkeley.edu/~cs61a/su19/proj/typing_test/#problem-07-accuracy-1-pts

def score_function_accurate(word1, word2):
    #words match
    if word1 == word2:
        return 0
    #if len(word2) is 0 return len(word1)
    elif len(word2) == 0:
        return len(word1)
    elif len(word1) == 0:
        return 1 + score_function_accurate(add_char(word1, word2[0]), word2)
    elif word1[0] == word2[0]:
        return 0 + score_function_accurate(word1[1:], word2[1:])
    elif len(word1) > len(word2):
        return min(
            KEY_DISTANCES[word1[0], word2[0]] + score_function_accurate(sub_char(word1, word2[0]), word2),
            1 + score_function_accurate(rem_char(word1), word2)
        )
    else:
        return min(
            KEY_DISTANCES[word1[0], word2[0]] + score_function_accurate(sub_char(word1, word2[0]), word2),
            1 + score_function_accurate(rem_char(word1), word2),
            1 + score_function_accurate(add_char(word1, word2[0]), word2)
        )

Problem 08: Efficiency

Specs: https://inst.eecs.berkeley.edu/~cs61a/su19/proj/typing_test/#problem-08-efficiency-2-pts

def score_function_final(word1, word2):
    cache = {}
    
    def save_in_cache(word1, word2, score):
        cache[word1+word2] = score
        cache[word2+word1] = score

    def score_function(word1, word2):
        #words match
        if word1 == word2:
            return 0
        #if len(word2) is 0 return len(word1)
        elif len(word2) == 0:
            return len(word1)
        elif len(word1) == 0:
            return 1 + score_function_memo(add_char(word1, word2[0]), word2)
        elif word1[0] == word2[0]:
            return 0 + score_function_memo(word1[1:], word2[1:])
        elif len(word1) > len(word2):
            return min(
                KEY_DISTANCES[word1[0], word2[0]] + score_function_memo(sub_char(word1, word2[0]), word2),
                1 + score_function_memo(rem_char(word1), word2)
            )
        else:
            return min(
                KEY_DISTANCES[word1[0], word2[0]] + score_function_memo(sub_char(word1, word2[0]), word2),
                1 + score_function_memo(rem_char(word1), word2),
                1 + score_function_memo(add_char(word1, word2[0]), word2)
            )

    def score_function_memo(word1, word2):
        if word1+word2 not in cache:
            save_in_cache(word1, word2, score_function(word1, word2)) 
        return cache[word1+word2]

    return score_function_memo(word1, word2)