import re

def find_word(message):
    wordDict = {}
    scoreDict = {}
    # Remove punctuation
    message = re.sub('[^A-Za-z0-9\s+]+', '', message)
    # Lowercase the sentence
    message = message.lower()
    # Put it into a list
    messageList = message.split(" ")
    # Compile my dictionary of pairs
    index1 = 0
    while index1 < (len(messageList)-1):
        for index2 in range(index1+1,len(messageList)):
            wordDict[messageList[index1],messageList[index2]] = 0
        index1 += 1
    # Add up the values
    for pair in wordDict:
        # Check first letters
        if pair[0][0] == pair[1][0]:
            wordDict[pair] += 10
        # Check end letters
        if pair[0][-1] == pair[1][-1]:
            wordDict[pair] += 10
        # Check lengths
        if len(pair[0]) <= len(pair[1]):
            wordDict[pair] += 30 * (len(pair[0]) / len(pair[1]))
        else:
            wordDict[pair] += 30 * (len(pair[1]) / len(pair[0]))
        # Check unique letters
        uniCount = 0
        sameCount = 0
        usedLetters = ""
        for letter in pair[0]:
            if letter not in usedLetters:
                uniCount += 1
                usedLetters += letter
        for letter in pair[1]:
            if letter not in pair[0]:
                uniCount += 1
                usedLetters += letter
        if len(pair[0]) <= len(pair[1]):
            for letter in pair[0]:
                if letter in pair[1]:
                    sameCount += 1
        else:
            for letter in pair[1]:
                if letter in pair[0]:
                    sameCount += 1
        if uniCount > 0:
            wordDict[pair] += 50 * (sameCount / uniCount)
    print("Paired scores:",wordDict,"\n")

    # Find the sum score of each word
    for pair in wordDict:
        if pair[0] not in scoreDict:
            scoreDict[pair[0]] = wordDict[pair]
        else:
            scoreDict[pair[0]] += wordDict[pair]
        if pair[1] not in scoreDict:
            scoreDict[pair[1]] = wordDict[pair]
        else:
            scoreDict[pair[1]] += wordDict[pair]
    print ("Sum of scores:",scoreDict,"\n")

    # Find the average score of each word
    for pair in scoreDict:
        scoreDict[pair] = scoreDict[pair] / len(scoreDict)
    highestScore = 0
    highestWord = None
    for word in scoreDict:
        if scoreDict[word] > highestScore:
            highestScore = scoreDict[word]
            highestWord = word
    print ("Average scores:",scoreDict,"\n")
    print ("My Answer",highestWord)
    return highestWord



find_word("Friend Fred and friend Ted.")