Форум сайта python.su
Добрый день.
Недавно начал изучать Python, написал первую программу.
Суть:
Есть игра “Слова”, дается таблица 5*5, в каждой ячейке таблицы занесена буква, нужно из этих букв составить как можно больше слов.
Можно ходить по горизонтали, вертикали и диагонали, использовать ячейку в одном и том же слове повторно нельзя.
Приведенный код, ищет слова длиной в семь букв, примерно за 5 секунд, если увеличить длину слова, то и время затраченное на поиск значительно вырастает, для 10-и букв, примерно 140 секунд, но и возможных вариантов в этом случае примерно 19 млн.
Подскажите пожалуйста, может для такого рода задач уже есть алгоритмы, а я тут огород горожу, ну или если не затруднит, укажите на не оптимальные части кода. Вариант, что всё отстой, не принимается
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()
Офлайн