def rot( c, n ):
    """ rotates the single letter, c, by n spots in the alphabet
    """
    if 'a' <= c <= 'z':
        if ord(c) + n <= ord('z'):
            return chr( ord(c) + n )
        else:
            return chr( ord(c)+n-26)
    elif 'A' <= c <= 'Z':
        if ord(c) + n <= ord('Z'):
            return chr( ord(c) + n)
        else:
            return chr( ord(c) + n - 26)
    else:
        return c

def list_to_str( L ):
    """ L must be a list of characters; then,
        this returns a single string from them
    """
    if len(L) == 0: return ''
    return L[0] + list_to_str( L[1:] )
#Here's how to test list_to_str:    list_to_str( ['c','s','5','!'] ) should return 'cs5!'

def encipher( S, n ):
    """Takes in a string, S, and rotates that string through the alphabet by
        n letters. Upper case letters stay upper case, same for lower case.
        non-alphabetic characters do not change.
    """
    return list_to_str([rot(c,n) for c in S])

def letterScore( let ):
	""" output: value of character as scrabble tile
		input: single - character string
	"""
	if let in 'anorsteil':
		return 1
	elif let in 'dg':
		return 2
	elif let in 'bcpm':
		return 3
	elif let in 'fhvwy':
		return 4
	elif let in 'k':
		return 5
	elif let in 'jx':
		return 8
	elif let in 'qz':
		return 10
	else:
		return 0
def scrabbleScore( S ):
	""" output: scrabble score of string
		input: a string S
	"""
	if len(S)==0:
		return 0
	else:
		return scrabbleScore( S[1:] ) + letterScore(S[0])
def decipher( S ):
	""" returns the original english
    """
    E_all = [encipher( S, n) for n in range(26)]
    print (E_all)
	LoL = [ [scrabbleScore(w), w] for w in E_all]
	print[LoL]
	bestWord = min(LoL)
	return bestWord[1]

def remZero( L ):
    """removes 0's from the list L"""
    if len(L) == 0:
        return L
    elif L[0] != 0:
        return L[0:1] + remZero(L[1:])
    else:
        return remZero(L[1:])

def remOne( L ):
    """removes 1's from the list L
    """
    if len( L ) == 0:
        return L
    elif L[0] != 1:
        return L[0:1] + remOne(L[1:])
    else:
        return remOne(L[1:])

def blsort( L ):
    """sorts the list L in asceding order
        note: should be assumed that L contains only binary digits
    """
    if len(L) == 0:
        return ''
    else:
        return remOne(L) + remZero(L)

def removeone(e,L):
	if len(L) == 0:
		return L
	elif L[0] != e:
		return L[0:1] + removeone(e,L[1:])
	else:
		return L[1:]

def gensort( L ):
	""" returns the list L in ascending order
	"""
	if len(L) == 0:
		return L
	else:
		return [(min(L))] + gensort(removeone(min(L),L))

def jscore( S, T ):
    """returns the Jotto score of S compared with T
    """
    if len(S) == 0:
	    return 0
    else:
	    if S[0] in T:
		    return 1 + jscore(S[1:],removeone(S[0],T))
	    else:
		    return jscore(S[1:],T)

def count( e, L ):
    """ returns the # of e's in L """
    LC = [ e==x for x in L ]
    return sum( LC )

def exact_change( target_amount, L ):
    """ returns true or false according to if the contents of L can be summed up
        to reach the target_amount
    """
    if target_amount == 0:
	    return True
    elif target_amount<0:
	    return False
    elif len(L) == 0:
	    return False
    else:
	    result1 = exact_change(target_amount,L[1:])
	    result2 = exact_change(target_amount-L[0], L[1:])
	    if result1 == True or result2 == True:
		    return True
	    else:
		    return False

def LCS( S, T ):
    """returns the longest shared sequence b/t S and T
    """
    if len(S) == 0 or len(T) == 0:
	    return ''
    elif S[0] == T[0]:
	    return str(S[0]) + str(LCS(S[1:],T[1:]))
    else:
	    result1 = LCS(S[1:],T)
	    result2 = LCS(S,T[1:])
	    if len(result1) > len(result2):
		    return result1
	    else:
		    return result2