import sys

def get_targs():
    ''' Read words from console '''
    start_word = ''
    finish_word = ''
    key = False
    depth = 0
    if len(sys.argv) == 3:
        start_word = sys.argv[1]
        finish_word = sys.argv[2]
    elif len(sys.argv) == 5 and sys.argv[3] == '--all':
        start_word = sys.argv[1]
        finish_word = sys.argv[2]
        key = True
        depth = sys.argv[4]
    elif (len(sys.argv) != 3 and len(sys.argv) != 5) or sys.argv[1] == 'help':
        print ('Run the program again and write 2 words with a space and key "--all" and number, if you want to have all of the chain length number')
        sys.exit()
    return start_word, finish_word, key, depth


def correct_length(start_word, finish_word):
    ''' Check that the words were the same length '''
    return len(start_word) == len(finish_word)


def get_similar(word, words):
    ''' Looking in the dictionary words that are different from the previous
    one by one letter'''
    same_words = set()
    for dictionary_word in words:
        is_prefix_eq = False
        for ch in range(len(word)):
            if dictionary_word[ch] != word[ch]:
                if is_prefix_eq:
                    break
                is_prefix_eq = True
        else:
            same_words.add(dictionary_word)
    return same_words


def get_good_words(start_word, words):
    ''' Select all the words from the dictionary, which length is equal
    to the original word'''
    good_words = {i.strip() for i in words if len(i.strip()) == len(start_word)}
    return good_words


def build_tree(start_word, finish_word, dictionary, words):
    ''' Building "a tree" of words and words like them '''
    queue = [start_word]
    while len(queue) != 0:
        current = queue.pop(0)
        similar_words = get_similar(current, words)
        for word in similar_words:
            if word not in dictionary:
                queue.append(word)
                dictionary[word] = current
            if word == finish_word:
                return word
    return None

def print_result(word, finish_word, dictionary):
    '''Print results for situation without keys'''
    if word is None:
        print('Our dictionary have no this words, sorry :(')
        return
    path = [finish_word]
    while dictionary[word] is not None:
        path.append(dictionary[word])
        word = dictionary[word]
    for word in path[::-1]:
        print(word)

def equal_words(start_word, finish_word):
    '''Check words for equality'''
    if start_word == finish_word:
        print(start_word)
        return True
    return False

def DFS(current_word, finish_word, trace, words, depth):
    '''Depth-first search for searching all chains that length is depth'''
    if len(trace) > depth:
        return
    if current_word == finish_word:
        yield trace
        return
    for word in get_similar(current_word, words):
        if word in trace:
            continue
        for i in DFS(word, finish_word, trace + [word], words, depth):
            yield i

def main():
    start_word, finish_word, key, depth = get_targs()
    if equal_words(start_word, finish_word):
        sys.exit()

    if not correct_length(start_word, finish_word):
        print('Your words have differnt length')
        sys.exit()

    words = get_good_words(start_word, open('runouns.txt', encoding='utf-8'))

    dictionary = {start_word: None}
    if key == False:
        tree = build_tree(start_word, finish_word, dictionary, words)
        print_result(tree, finish_word, dictionary)
    if key == True:
        traces = DFS(start_word, finish_word, [start_word], words, int(depth))
        list_of_traces = list(traces)
        if len(list_of_traces) == 0:
            print('We have not chains, that have this depth. Run programm again and enter a number that is greater than the previous depth')
        else:
            for i in list_of_traces:
                for j in i:
                   print(j)
                print()

if __name__ == "__main__":
    main()