def rot(string):
	caesard = {}	

	capitals = [i for i, char in enumerate(string) if char.isupper()]

	for rot in range(26):
		lower, modified = string.lower(), ""
		newString = []
		for char in lower:
			newString.append(ascii_lowercase[((ascii_lowercase.index(char) + rot) % len(ascii_lowercase))])

		for i in capitals:
			char = ascii_lowercase.index(newString[i])
			newString[i] = ascii_lowercase[char].upper()
		caesard["".join(newString)] = str(26-rot)
	return caesard

def decrypt(key, ciphertext):
    # decrypt ciphertext using key, by way of a Vigenre cipher

    key = key.lower()
    ciphertext = ciphertext.lower().replace('\n','').replace(' ','')
    out = ''

    # print(ciphertext)
    for i in range(len(ciphertext)):
        # for each symbol in the ciphertext


        # get the symbol's index in the alphabet
        symbol_index = ascii_lowercase.index(ciphertext[i])

        # get the key_symbol
        key_symbol = key[i % len(key)]

        # get the key_symbol's index in the alphabet
        key_symbol_index = ascii_lowercase.index(key_symbol)

        # decrypt the cipher symbol and append to out
        out += ascii_lowercase[(symbol_index - key_symbol_index + \
               len(ascii_lowercase)) % len(ascii_lowercase)]

    return out

 def _letter_generator(self, current_index, letter, encode=True):
     current_key = self.key[current_index % len(self.key)]
     if encode:
         current_key = (ascii_lowercase.index(current_key) + ascii_lowercase.index(letter)) % 26
     else:
         current_key = (ascii_lowercase.index(letter) - ascii_lowercase.index(current_key)) % 26
     return ascii_lowercase[current_key]

def rot13(message, action="encode"):
    """Write a function called rot13 that uses the Caesar cipher to encrypt a
    message. The Caesar cipher works like a substitution cipher but each character
    is replaced by the character 13 characters to ‘its right’ in the alphabet.
    So for example the letter a becomes the letter n. If a letter is past the
    middle of the alphabet then the counting wraps around to the letter a again,
    so n becomes a, o becomes b and so on."""
    from string import ascii_lowercase as lc
    new_message = ""
    message = message.lower()
    if action == "decode":
        for char in message:
            if char in lc:
                idx = (lc.index(char)-13) % 26
                new_message += lc[idx]
            else:
                new_message += char
        return new_message
    for char in message:
        if char in lc:
            idx = (lc.index(char)+13) % 26
            new_message += lc[idx]
        else:
            new_message += char
    return new_message

def getIndexFromA(letter, shiftAmount):
    '''Returns if the letter's index is in the next alphabet over, or in the
    same alphabet, in addition to the index of the relative alphabet cycle.'''
    realShift = getRealShift(inputShiftAmount)
    letter = letter.lower()
    letterIndexFromEnd = 25 - ascii_lowercase.index(letter)
    if letterIndexFromEnd < realShift:
        shiftedLetterIndex = realShift - (letterIndexFromEnd + 1)
        return shiftedLetterIndex
    else:
        return realShift + ascii_lowercase.index(letter)

def main():
	text, new_text, key = "", "", "qwcpwnuht"

	with open("krypton5") as f:
		text = f.read().lower().rstrip("\n")

	for i, c in enumerate(text):
		index_of_key = al.index(key[i % len(key)])
	
		new_text += al[(index_of_key + al.index(c)) % 26]

	print new_text

 def code(self, text, shift_sign):
    # pad the end of the key with 'a' (basically no substitution)
    self.key = self.key + 'a' * len(text)
    # make text lowercase, strip out non letters, convert to list
    text = list(re.sub(r'[^a-z]','',text.lower()))
    # return result using character substitution based on key
    result = ''   
    for i in range(len(text)):
        char_value = letters.index(text[i])
        key_shift = shift_sign * letters.index(self.key[i])
        result += letters[(char_value + key_shift) % 26]
    return result

def main():
	reverse_key = []
	key = "enc"
	string = "rwfwcvttw ufriifyg dws jjbhwooqm ezu iwsh".replace(" ","")
	new_string = ""

	for i, char in enumerate(string):
		key_char = key[ i % len(key) ]
		key_char_index = al.index( key_char ) + 1
		char_index = al.index( char) + 1

		new_index = char_index - key_char_index
		reverse_key.append(al[new_index-1])

	print "".join(reverse_key)

 def name_value(name):
     result = 0
     name = name.lower().strip()
     for char in name:
         if char != '"':
             result += lowercase.index(char) 
     return result

def caeser(sourcetext, offset=None, reverse=False):
    # caeser(string) -> string
    # offset - integer value for cipher offset
    # reverse - bool to reverse the offset (useful for decryption)
    # Apply an offset to ascii characters.
    
    # Trivial case, return sourcetext unchanged and avoid
    # translating character by character.
    if offset == None:
        return sourcetext
    # reverse flag undoes the cipher offset. This is the same
    # as making the offset negative. Conditional merely changes
    # the sign of offset. The same effect can be achieved by
    # manually adjusting the sign of offset in the caller.
    if reverse:
        offset = -offset
    
    # build enciphered string character by character
    # For each character, if it is an ascii letter apply
    # the offset and append the new character to the cipher. 
    # Otherwise, simply append nonletters to the cipher.
    cipher = []
    for char in sourcetext:
        if char in ascii_letters:
            if char in ascii_lowercase:
                i = ascii_lowercase.index(char) + offset
                i = modulate_index(ascii_lowercase, i)
                cipher.append(ascii_lowercase[i])
            else:
                i = ascii_uppercase.index(char) + offset
                i = modulate_index(ascii_uppercase, i)
                cipher.append(ascii_uppercase[i])
        else: cipher.append(char)
    ciphertext = ''.join(cipher)
    return ciphertext

def encrypt():
	messagelist = []
	rando = []
	
	message = input('Please enter your message : ').replace(' ', '').lower()
	while not message.isalpha(): # message can only be letters
		print('Please input only letters!')
		message = input('Please enter your message: ').replace(' ', '').lower()
	publickey = int(input('Please enter the public key: '))

	for i in range(len(message)): # change letters to respective numbers
		messagelist.append(ascii_lowercase.index(message[i])) 
	
	seed = randint(100,10000)
	while seed ** 4 < publickey: # seed squared > square root of n
		seed = randint(100,10000)
		if gcd(seed, publickey) != 1: # coprime if gcd = 1
			continue
	print('Your seed is :', seed)
	
	initno = seed * seed
	for i in range(len(messagelist)): # number of int based on length of message
		if i == 0:
			rando.append(initno % publickey)
		else:
			rando.append((initno ** 2 ** i) % publickey) # xi = x0 ** i mod N
		
	for i in range(len(messagelist)): # C = (M + x) mod 26
		messagelist[i] = ascii_lowercase[(messagelist[i] + rando[i]) % 26]
	print('Ciphertext :', ''.join(messagelist))
	print('x-value :',rando[len(rando)-1]) # last random int produced

def generate_graph(words,alt):
    from string import ascii_lowercase as lowercase
    from itertools import permutations
    
    G = nx.Graph(name="words")
    lookup = dict((c,lowercase.index(c)) for c in lowercase)
    if alt:
        def scramble(word):
            perms = [''.join(p) for p in permutations(word)]
            return set(perms)
        def edit_distance_one(word):
            for i in range(len(word)):
                left, c, right = word[0:i], word[i], word[i+1:]
                j = lookup[c] # lowercase.index(c)
                for cc in lowercase[j+1:]:
                    for i in scramble(left + cc + right):
                        yield i
    else:
        def edit_distance_one(word):
            for i in range(len(word)):
                left, c, right = word[0:i], word[i], word[i+1:]
                j = lookup[c] # lowercase.index(c)
                for cc in lowercase[j+1:]:
                    yield left + cc + right
    candgen = ((word, cand) for word in sorted(words)
               for cand in edit_distance_one(word) if cand in words)
    G.add_nodes_from(words)
    for word, cand in candgen:
        G.add_edge(word, cand)
    return G

def decrypt():
	rando = []
	cipherlist = []
	
	privatep = int(input('Please enter the first private key : '))
	privateq = int(input('Please enter the second private key : '))
	ciphertext = input('Please enter the ciphertext : ').replace(' ', '')
	x = int(input('Please enter the x-value: '))
	publickey = privatep * privateq
	
	for i in range(len(ciphertext)):
		cipherlist.append(ascii_lowercase.index(ciphertext[i]))
	
	p = pow(x, int((privatep + 1)/4)** (len(ciphertext)-1), privatep) # formula
	q = pow(x, int((privateq + 1)/4)** (len(ciphertext)-1), privateq) # formula
	initno = (privatep * q * pow(privatep,privateq-2,privateq) + privateq * p * pow(privateq,privatep-2,privatep)) % publickey
	
	for i in range(len(cipherlist)):
		if i == 0:
			rando.append(initno % publickey) 
		else:
			rando.append((initno ** 2 ** i) % publickey) # xi = x0 ** i mod N

	for i in range(len(cipherlist)): # M = (C - x) mod N
		cipherlist[i] = ascii_lowercase[(cipherlist[i] - rando[i]) % 26]
	print('This is your plaintext : ' + ''.join(cipherlist))

def moving_shift(string, shift):
    words = string
    lens = len(words)
    m, n = divmod(lens, 5)
    if n > 0:
        m +=1
    res = ['', '', '', '' ,'']
    chars = -1

    for idx, char in enumerate(words):
        chars += 1
        change=None
        if char in ascii_lowercase + ascii_uppercase:
            if char in ascii_lowercase:
                pos = ascii_lowercase.index(char)
                np = (pos + shift + chars) % 26
                change = ascii_lowercase[np]
            elif char in ascii_uppercase:
                pos = ascii_uppercase.index(char)
                np = (pos + shift + chars) % 26
                change = ascii_uppercase[np]
        else:
            change = char
        res[chars//m] += change
    return res

def generate_graph(words):
    from string import ascii_lowercase as lowercase
    G = nx.Graph(name="words")
    lookup = dict((c,lowercase.index(c)) for c in lowercase)
    def edit_distance_one(word):
        for i in range(len(word)):
            left, c, right = word[0:i], word[i], word[i+1:]
            j = lookup[c] # lowercase.index(c)
            for cc in lowercase[j+1:]:
                # yield left + cc + right
                for x in range(6):
                    if x == 0:
                        yield cc + left + right
                    elif x == 1:
                        yield cc + right + left
                    elif x == 2:
                        yield right + cc + left
                    elif x == 3:
                        yield left + cc + right
                    elif x == 4:
                        yield right + left + cc
                    else:
                        yield left + right + cc
    candgen = ((word, cand) for word in sorted(words)
               for cand in edit_distance_one(word) if cand in words)
    G.add_nodes_from(words)
    for word, cand in candgen:
        G.add_edge(word, cand)
    return G

def get_searchTerms():
  searchTerm=get_var('previous_searchTerm')
  if searchTerm==None:
    i=0
  else:
    i=ascii_lowercase.index(searchTerm)+1
  return ascii_lowercase[i:]

def generate_graph(words):
    #Import lowercase ASCII characters
    from string import ascii_lowercase as lowercase
    #Initialize G as Graph from networkx
    G = nx.Graph(name="words")
    #Dictionary of each char in lowercase mapped to it's index
    lookup = dict((c,lowercase.index(c)) for c in lowercase)
    def edit_distance_one(word):
        for i in range(len(word)):
            left, c, right = word[0:i], word[i], word[i+1:]
            j = lookup[c] # lowercase.index(c)
            dist_one_anagrams = set()
            for cc in lowercase:
                if cc!=c:
                    dist_one_anagrams.add(left + cc + right)
            for w in dist_one_anagrams:
                dist_one_anagrams_2 = {"".join(perm) for perm in itertools.permutations(w)}
                dist_one_anagrams = dist_one_anagrams|dist_one_anagrams_2
            for w in dist_one_anagrams:
                yield w    
    #Generator for words and their neighbors that exist in input data
    candgen = ((word, cand) for word in sorted(words) 
               for cand in edit_distance_one(word) if cand in words)
    #Add each word in words as a node into G
    G.add_nodes_from(words)
    #Add edge between a word and it's neighbor
    for word, cand in candgen:
        G.add_edge(word, cand)
    #Return generated graph
    return G

def generate_graph(words):
    from string import ascii_lowercase as lowercase
    G = nx.Graph(name="words")
    lookup = dict((c,lowercase.index(c)) for c in lowercase)
    def edit_distance_two(word):
        s_word = ''.join(sorted(word))
        for i in range(len(s_word)):
            left, c, right = s_word[0:i], s_word[i], s_word[i+1:]
            j = lookup[c] # lowercase.index(c)
            for cc in lowercase[j+1:]:
                yield left + cc + right
    G.add_nodes_from(words)
    swords=[]
    awords=[]
    for word in sorted(words):
        awords.append(word)
        swords.append(''.join(sorted(word)))
    for word in awords:
        for cand in edit_distance_two(word):
            i = 0
            for sword in swords:
                if cand == sword:
                    G.add_edge(word, awords[i])
                i+=1
    return G

def generate_graph(words):
    from string import ascii_lowercase as lowercase
    G = nx.Graph(name="words")
    lookup = dict((c,lowercase.index(c)) for c in lowercase)
    def edit_distance_one(word):
        word1="".join(sorted(word))
        for i in reversed(range(len(word))):
            left, c, right = word1[0:i], word1[i], word1[i+1:]
            j = lookup[c] # lowercase.index(c)
            bound=25
            for cc in lowercase[0:bound]:
                if (cc !=c):
                    yield left + cc + right
##    candgen = ((word, cand) for word in sorted(words)
##  for cand1 in edit_distance_one(word) if ((cand1 in wordsd.values()) and (cand==wordsd.keys()[words.values.index(cand1)]))
    candgen=[]
    for word in sorted(words):
        for cand2 in edit_distance_one(word):
            cand1 = ''.join(sorted(cand2))
            if (cand1 in wordsd.values()):
                cand=wordsd.keys()[wordsd.values().index(cand1)]
                candgen.append([word,cand])
                                  
    G.add_nodes_from(words)
    for word, cand in candgen:
        G.add_edge(word, cand)
    return G

def write_seq(fh, ending_letter):
    ending_index = ascii_lowercase.index(ending_letter.lower())
    ending_index += 1

    for letter in ascii_lowercase[:ending_index]:
        fh = add_letter(fh, letter)

    return fh