import sys
import time
import arguments


def get_words(dictionary, encoding):
    words = {}
    try:
        with open(dictionary, encoding=encoding) as f:
            for line in f:
                line = line.strip()
                n = len(line)
                if n not in words.keys():
                    words[n] = set()
                words[n].add(line)
        return words
    except TypeError:
        report(2, dictionary)
    except FileNotFoundError:
        report(2, dictionary)
    except LookupError:
        report(3, encoding)


def node(word1, word2):
    cur_pos = 0
    diff = 0
    while cur_pos < len(word1) and diff < 2:
        diff += int(word1[cur_pos] != word2[cur_pos])
        cur_pos += 1
    return True if diff == 1 else False


def find_adjacent(vertex):
    adj = set()
    n = len(vertex)
    for word in words[n]:
        if node(word, vertex):
            adj.add(word)
    return adj


def make_graph(n, words):
    graph = {}
    flag = False
    for word1 in words[n]:
        for word2 in words[n]:
            print(word1, " ", word2)
            if not flag:
                graph[word2] = set()
            if node(word1, word2):
                graph[word1].add(word2)
                graph[word2].add(word1)
        flag = True
    return graph


def check(first, last):
    n = len(first)
    if n != len(last):
        report(0)
        return False
    if first not in words[n]:
        report(1, first)
        return False
    if last not in words[n]:
        report(1, last)
        return False
    return True


def search(first, last, words, quick):
    if check(first, last):
        parent = {}
        n = len(first)
        container = [first]
        used = {word: False for word in words[n]}
        used[first] = True
        while container:
            cur = container[-1] if quick else container[0]
            container = container[:-1] if quick else container[1:]
            for word in find_adjacent(cur):
                if not used[word]:
                    container.append(word)
                    used[word] = True
                    parent[word] = cur
                if word == last:
                    return (True, parent)
        return (used[last], parent)


def way(first, last, parent):
    temp = [last]
    cur = last
    while cur != first:
        cur = parent[cur]
        temp.append(cur)
    return temp


def show_answer(first, last, words):
    if search(first, last, words, arguments.args.q)[0]:
        parent = search(first, last, words, arguments.args.q)[1]
        ans = way(first, last, parent)
        steps = len(ans)
        print("________________________________________________")
        kind = "random" if arguments.args.q else "optimal"
        print("The {} way takes {} steps to get \
from '{}' to '{}'".format(kind, steps, first, last))
        for i in range(steps):
            print(ans[steps - i - 1])
    else:
        print("________________________________________________")
        print("Sorry! I tried hard but I haven't found no way")


def report(error_code, param=""):
    messages = []
    messages.append("Your words have different lengths! \
How do you imagine me to do that?")
    messages.append("Sorry, I'm not poliglot. \
I haven't found the word '{}' in your dictionary.".format(param))
    messages.append("Sorry, I can't find \
'{}' in current directory".format(param))
    messages.append("Sorry, I don't know \
anything about encoding '{}'".format(param))
    print (messages[error_code])
    sys.exit()


words = get_words(arguments.args.d, arguments.args.e)
start = time.time()
show_answer(arguments.args.first, arguments.args.last, words)
finish = time.time()
print("________________________________________________")
print("It took me {:2.3f} seconds to solve this \
problem".format(finish - start))
print("Hope, it didn't seem too long")