import time
import random
#Прочитаем данные словаря
dictionary_list = set()
for i in open("E:/Project/List(2-10).txt").readlines():
    dictionary_list.add(i[:len(i)-1])   
    
#Сформируем список для дальнейшего использования
letters = [[0 for i in range(7)] for j in range(7)]
def prepare_words(i, j, word, words_list, used_cells):
    
    if letters[i][j] == 0 or len(word) == 7 or used_cells.get(letters[i][j] + str(i) + str(j)) == True:
        return
    
    word = word + letters[i][j]
    words_list.append(word)
        
    for x in 1,0,-1:
        for y in 1,0,-1:
            #used_cells - список уже использованых ячеек
            #перед рекурсивным вызовом добавляем текущее значение в ячейку, после - удаляем
            used_cells[letters[i][j] + str(i) + str(j)] = True
            prepare_words(i-x, j-y, word, words_list, used_cells)
            del used_cells[letters[i][j] + str(i) + str(j)]
                    
def filling_words_list():
    words_list = []
    for i in range(1,6):
        for j in range(1,6):
            used_cells = {}
            prepare_words(i, j, "", words_list, used_cells)   
    return words_list
def find_words():
    #Отметим время начала выполнения функции
    start_time = time.time()
    
    #Вводим строку для анализа, если строка будет пустая, то сгенерируем её
    string = input()
    if string == "":
        alphabet = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя"
        for i in range(0,25):
            mark = random.randint(0, 32)
            string += alphabet[mark]
    if len(string) != 25:
        print("Вы ввели не верное количество букв, повторите ввод еще раз.\nКоличество введенных знаков -", len(string))   
        find_words()
        return
    #Заполним ранее сформированную таблицу буквами из строки
    #крайние значения таблицы будут равны 0
    global letters
    n = 0
    for i in range(1,6):
        for j in range(1,6):
            letters[i][j] = string[n]
            n +=1
    #Сформируем и заполним таблицу возможных комбинаций из букв строки
    words_list = filling_words_list()
    #Найдем пересечения данных словаря комбинаций букв, полученный список сортируем по длине слова
    n = 0
    for i in sorted(set(words_list) & dictionary_list, key=len, reverse = True):   
        print(i)
        n +=1
        
    print("Найдено слов -", n, ", за", int((time.time() - start_time)), "секунд(ы)")    
  
    #Перезапустим функцию?
    anser = int(input("Хотите сыграть еще раз? (0 - нет, 1 - да)"))
    print("\n")
    if anser > 0:
        find_words()
    else:
        print("Game over")
        
find_words()