Уведомления

Группа в Telegram: присоединиться | Jabber-конференция сообщества: pythonua@conference.jabber.ru

#1 Июнь 14, 2018 13:38:58

ivan_ivanov
Зарегистрирован: 2018-06-14
Сообщения: 1
Репутация: +  0  -
Профиль   Отправить e-mail  

Подскажите пожалуйста, как лучше реализовать алгоритм

Добрый день.
Недавно начал изучать 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()

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version