# CloseWordsSol_alt.py
# CS 1110 Professors and Alex Parkhurst
# March 2016

""" Illustrates various ideas about what it means
for two strings to be close.
"""

### note re: grading rubric: need to check that docstrings have listed all preconditions
### and mentioned all parameters.

import string # gives us ascii_lowercase
from GetData import fileToStringList


def offByOne(s1,s2):
    """ Returns True if s1 and s2 have the same
    length and there is exactly one integer k for
    which s1[k]!=s2[k] is True. In other words,
    s1 and s2 differ in exactly one position.

    PreC: s1 and s2 are nonempty strings.
    """
    if len(s1)!=len(s2) or s1==s2:
        return False
    n = 0
    for k in range(len(s1)):
        if s1[k] != s2[k]:
            n+=1
        if n==2:
            return False
    return True # since we checked for case of s1==s2, n must be 1 here.


# Alternate implementation
def offByOne2(s1, s2):
    """Same as offByOne."""
    if len(s1) != len(s2):
        return False

    #assert: s1 and s2 have equal length
    diffs = 0 # number of differences found so far
    i = 0 # next position to check for a difference
    while i < len(s1) and diffs < 2:
        if s1[i] != s2[i]:
            diffs += 1
        i+=1

    return diffs == 1


# Another alternate implementation - less complex
# condition in the while (but therefore always
# goes through the entire string even if it could
# have stopped early.)
def offByOne3(s1, s2):
    """Same spec as above."""
    if len(s1) != len(s2):
        return False

    #assert: s1 and s2 have equal length
    diffs = 0 # number of differences found so far
    i = 0 # next position to check for a difference
    while i < len(s1):
        if s1[i] != s2[i]:
            diffs += 1
        i+=1

    return diffs == 1



def offBySwap(s1,s2):
    """ Returns True if s1 and s2 are different strings, and s2 can be
    obtained from s1 by swapping two adjacent characters.

    PreC: s1 and s2 are non-empty strings.
    """
    if s1 == s2 or len(s1)!=len(s2):
        return False
    for k in range(len(s1)-1): # k is potential swap location, so note the "-1"!
                               # Also note: range(0) is [], so the loop
                               # is not entered if len(s1) is 1!
        swap_in_s1 = s1[:k] + s1[k+1] + s1[k] + s1[k+2:]
        if swap_in_s1==s2:
            return True
    return False


# Alternate, much more complicated implementation that explicitly checks each
# string position.
def offBySwap_alt_1pass(s1,s2):
    """Same as offBySwap."""
    # Main idea: count "observable swaps" ('aa' vs 'aa' not counted)

    # Deal with obvious False cases
    if s1 == s2 or len(s1) != len(s2):
        return False

    # If we got here, we have same-length strings with at least 2 characters

    num_swaps = 0 # number of observable swaps found so far
    i = 0 # next place to check
    # Find first observable swap beginning, if any.
    while i < len(s1)-1 and num_swaps < 1:
        # Note that if len(s1) is 1, this loop is never entered, which makes
        # sense because then an i of 0 can't be the start of a swap.
        if s1[i] == s2[i+1] and s1[i+1] == s2[i] and s1[i] != s1[i+1]:
            num_swaps +=1
            i+= 2  # Once you have a swap, everything *after* the swap must be checked
                   # for equality.
        elif s1[i] != s2[i]: # not a swap, so shouldn't be unequal
            return False
        else:
            i += 1

    # debug stmt: print "out of swap search: s1, s2, i, num_swaps are", s1, s2, i, num_swaps

    if i >= len(s1)-1: # got to end of string
        return num_swaps == 1
    else:
        # Assertion: i is before the last character, and num_swaps is 1
        # Now, we check that the rest of the strings starting from i is the same
        for j in range(i, len(s1)):
            if s1[j] != s2[j]:
                return False

    # Did not find an unequal character
    return True

# Alternate implementation that, like offBySwap_alt_1pass, counts differences,
# but implements the checking of whether the differences are swaps
# in a different manner.
def offBySwap_alt_2passes(s1,s2):
    """Same as offBySwap."""

    if s1 == s2 or len(s1) != len(s2):
        return False

    num_wrong = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            num_wrong += 1
    if num_wrong != 2:
        return False

    #now we know there are only 2 errors in the string
    for j in range(len(s1) - 1):
        if s1[j] != s2[j] and s1[j] == s2[j+1] and s1[j+1] == s2[j]:
            return True
    return False

# An incorrect "solution"!
# This "solution" never checks that the parts of the strings after the swap are the same,
# or notices if the stuff before the swap is not the same.
def offBySwap_wrong(s1,s2):
    """Same as offBySwap."""

    # Deal with obvious False cases
    if s1 == s2 or len(s1) != len(s2) or len(s1) == 1: # To get to 3rd clause, lengths
                                                       # must be equal.
        return False

    # If we got here, we have same-length unequal strings with at least 2 characters

    num_swaps = 0 # number of swaps found so far
    i = 0 # next place to check for a swap
    # Find 1st swap beginning, if any.  Everything before i should have the
    # same characters in s1 and s2.
    while i < len(s1)-1 and num_swaps < 2:
        if s1[i] == s2[i+1] and s1[i+1] == s2[i]:
            num_swaps +=1
        i += 1

    if i == len(s1)-1: # got to end of string
        return num_swaps == 1
    else:
        # i is before the last character, but num_swaps >= 2
        return False

def offByExtra(s1,s2):
    """ Returns True if removing one character from s1 gives s2
    or if removing one character from s2 gives s1. Otherwise returns
    False.

    PreC: s1 and s2 are nonempty strings.
    """
    if len(s1)==len(s2)+1:
        return s2 in ListOfDeleteOnes(s1)
    elif len(s2)==len(s1)+1:
        return s1 in ListOfDeleteOnes(s2)
    else:
        return False


# Alternate implementation
def offByExtra2(s1, s2):
    """Same as offByExtra."""
    if abs(len(s1) - len(s2)) != 1:
        return False

    # Assertion: string lengths off by one
    if len(s1) < len(s2):
        shorter = s1; longer = s2
    else:
        shorter = s2; longer = s1
    return shorter in ListOfDeleteOnes(longer)


def ListOfDeleteOnes(s):
    """ Returns a list of all the strings that can be obtained
    by deleting a single character in s.

    PreC: s is a nonempty string.
    """
    n = len(s)
    t = []
    for k in range(n):
        x = s[:k]+s[k+1:]
        t.append(x)
    return t


def ListOfNeighbors(s,L):
    """ Returns a list of all entries in L that are
    neighbors of s.

    PreC: s is a nonempty string and L is a list of nonempty strings.
    """
    T = []
    for w in L:
        B1 = offByOne(s,w)
        B2 = offByExtra(s,w)
        B3 = offBySwap(s,w)
        if (B1 or B2 or B3) and s!=w:
            T.append(w)
    return T


# Alternate implementation
def ListOfNeighbors_alt(s, L):
    """same as ListOfNeighbors"""
    mylist = []
    for s2 in L:
        if offByOne(s, s2) or offByExtra(s, s2) or (s2 != s and offBySwap(s, s2)):
            mylist.append(s2)
    return mylist



def ListOfNeighbors2(s,L):
    """ Returns a sorted list of all entries in L that are
    neighbors of neighbors of s. The returned list has no
    duplicate entries.

    PreC: s is a string and L is a list of strings.
    """
    T = list(set(ListOfNeighbors(s,L)))
    U = []
    for t in T:
       U.extend(ListOfNeighbors(t,L))
    # Remove duplicates and sort
    U = list(set(U))
    U.sort()
    return U


def ScrabbleScore(s):
    """ Returns the Scrabble value of the upper-case version of s.

    PreC: s is a nonempty string comprised of letters.
    """
    Letters = string.ascii_uppercase
            #A B C D  E F G H I J K L M N O P  Q R S T U V W X Y  Z
    Supply= [9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2, 1,6,4,6,4,2,2,1,2, 1]
    Value = [1,3,3,2, 1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10]

    runningSum = 0
    s = s.upper()
    for c in s:
        i = Letters.find(c)
        if s.count(c)>Supply[i]:
            return 0
        runningSum += Value[i]
    return runningSum


def main():
    """Showcases the code in this module."""

    L = fileToStringList('EnglishWords.txt')

    # Solicit a string of lowercase letters
    while True:
        s = raw_input('Enter a string of lower case letters: ')
        k=0
        for c in s:
            if c in string.ascii_lowercase:
                k+=1
        if k==len(s):
            break

    # Print all the neighbors of s and their Scrabble scores...
    print '\nNeighbors...\n'
    T = ListOfNeighbors(s,L)
    for t in T:
        print t,ScrabbleScore(t)

    # Print all the neighbors of the neighbors of s and their Scrabble scores...
    print '\nNeighbors of the Neighbors...\n'
    U = ListOfNeighbors2(s,L)
    for u in U:
        print u,ScrabbleScore(u)


# helper for alternate implementation. Uses string.ascii_lowercase.
def verify_lower(s):
    """Returns True if s is made of lowercase letters.  Otherwise,
    throw a ValueError exception"""
    for c in s:
        if c not in string.ascii_lowercase:
            raise ValueError
    return True


# alternate implementation - try/except
def main2():
    L = fileToStringList('EnglishWords.txt')

    # Solicit a string of lower case letters
    goodinput = False # have we received a valid s yet?
    while not goodinput:
        try:
            s = raw_input('Enter a string of lowercase letters: ')
            goodinput = verify_lower(s)
        except ValueError:
            print "No, your input has to be all lowercase letters."


    # Print all the neighbors of s and their Scrabble scores...
    print '\nNeighbors...\n'
    nbrs = ListOfNeighbors(s,L)
    for nbr in nbrs:
        print nbr,ScrabbleScore(nbr)

    # Print all the neighbors of the neighbors of s and their Scrabble scores...
    print '\nNeighbors of the Neighbors...\n'
    nbrnbrs = ListOfNeighbors2(s,L)
    for nn in nbrnbrs:
        print nn,ScrabbleScore(nn)


def testem():

    # test offByOne
    for answer in [ ['read', 'rexd', True],
                    ['read', 'xexd', False],
                    ['read', 'readx', False],
                    ['read', 'eadx', False],
                    ['a','x', True],
                    ['a', 'a', False],
                    ['a', 'A', True]]:
        for fn in [offByOne, offByOne2, offByOne3]:
            response = fn(answer[0], answer[1])
            right = answer[2]
            if response != right:
                print str(fn)+":", "problem with", answer
    print "done testing off-by-one"

    # test offBySwap
    for answer in [ ['read', 'raed', True],
                    ['read', 'read', False],
                    ['read', 'erad', True],
                    ['Read', 'Erad', False],
                    ['read', 'erbx', False],
                    ['read', 'bxda', False],
                    ['read', 'reda', True],
                    ['reaxd', 'read', False],
                    ['read', 'rexd', False],
                    ['x', 'Y', False],
                    ['ae','a', False],
                    ['a', 'a', False],
                    ['read', 'erda', False], # two swaps
                    ['read', 'ared', False],
                    ['read', 'eard', False],
                    ['aa', 'aa', False],
                    ['aab', 'aab', False],
                    ['aaa', 'aaa', False],
                    ['aacd', 'aadc', True],
                    ['aardvark', 'aadrvark', True]]:
        for fn in [offBySwap, offBySwap_alt_1pass, offBySwap_alt_2passes, offBySwap_wrong]:
            response = fn(answer[0], answer[1])
            right = answer[2]
            if response != right:
                print str(fn)+":", "problem with", answer
    print "done testing off-by-swap"

    # test ListOfDeleteOnes
    s = "abcd"; right = ["bcd", "acd", "abd", "abc"]
    response = ListOfDeleteOnes(s)
    if len(response) != len(right):
        print "problem with", right
    else:
        for item in right:
            if item not in response:
                print "problem with", right
    print "done testing ListOfDeleteOnes"

    # test offByExtra
    for answer in [["abcd", "abcxd", True],
                    ["abcda", "abcd", True],
                    ["abcd", "bcda", False],
                    ["abcd", "abcdef", False],
                    ["abcd", "abcd", False],
                    ["xabcd", "abcd", True],
                    ["xabcd", "abce", False]]:
        for fn in [offByExtra, offByExtra]:
            response1 = fn(answer[0], answer[1])
            response2 = fn(answer[1], answer[0])
            right = answer[2]
            if response1 != right or response2 != right:
                print str(fn) + ":", "problem with", answer
    print "done testing offByExtra"

    # test ListOfNeighbors:
    smallList = ["abc", "abcd", "abcde", "aba", "aab"]
    for answer in [["abc", ["abcd", "aba"]],
                    ["aba", ["abc", "aab"]]]:
        for fn in [ListOfNeighbors, ListOfNeighbors_alt]:
            response = set(fn(answer[0], smallList)) # don't worry about order
            right = set(answer[1])
            if response != right:
                print str(fn)+":", "problem with", answer
                print "\t response was", response
    L = fileToStringList('EnglishWords.txt')
    for answer in [["transform", ["transforms"]],
                    ["largest", ["larges", "largess"]]]:
        for fn in [ListOfNeighbors, ListOfNeighbors_alt]:
            response = set(fn(answer[0], L))
            right = set(answer[1])
            if response != right:
                print str(fn)+":", "problem with transform, result was", response

    print "done with mini-test of ListOfNeighbors"

    for answer in [["zoology", 20], ["zology", 19], ["zyzzyva",0], ["piKacHu", 18]]:
        response = ScrabbleScore(answer[0])
        right = answer[1]
        if response != right:
            print "problem with", answer
    print "done with mini-test of ScrabbleScore"



if __name__ == "__main__":
    testem()  # When submitting, this should be removed and the below uncommented,
              # but leaving this in for students to see how this kind of testing
              # might be done.
    #main()