Игра в слова

Программирование
У моего любимого производителя табака появилась игра в слова (http://www.richmond-tobacco.com/game_slova/), победителям, разумеется приз.

Суть игры, выпадают случайные буквы, из которых нужно собрать слово. Например, буквы ПИВЕРТ,
из них можно собрать слово ПРИВЕТ.

Все бы ничего, но надо собрать 11 слов, да еще и на время. Причем каждое следующее слово длиннее предыдущего на одну букву. Для слов из 4-6 букв в общем-то проблем не возникало, но дальше все трудней и трудней.

Но впереди ждут сигареты, и поэтому надо что-то придумать.


Первое, что пришло в голову — это подбор по словарю. После недолгих поисков в Интернете, был найден словарь (http://www.hackzone.ru/files/get/id/309/Slovar_+iz+180000+russkih+slov.html)

Чуток задержимся, как будем искать по словарю. Нам нужны слова, в которых есть все нужные, и надо как можно быстрей их найти. Первое, что приходит в голову — завести индекс по длине слова — это ускорит процесс. Но по одной длине слова — результат будет все-равно очень внушительный. Поэтому прибегнем к такому фокусу: если в слове отсортировать буквы по алфавиту — то как раз, все слова с таким набором букв и будут ответом. Для примера, есть слова:
КОМАР
КОРМА
МАКРО

Отсортируем их по алфавиту, получится:
КОМАР -> АКМОР
КОРМА -> АКМОР
МАКРО -> АКМОР

Т.е. — если нам выпали 5 букв А, К, М, О, Р — то будет как минимум 3 слова, которые могут претендовать на ответ.
Получается, у нас словать будет иметь вид:
dict(word, length, hash)
word - само слово
length - длина слова
hash - хэш для этого слово. (в нашем случае хэш будет - слово, в котором буквы отсортированы по алфавиту).


Список слов у нас есть, создаем БД и заполняем наш словарь. В качестве БД был выбран sqlite.

Создаем нашу базу:
[dk@kote ~]$ sqlite3 dict.db
SQLite version 3.6.23.1
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> create table dict(word varchar(30), length int, hash varchar(30));
sqlite> create index ix_dict_length on dict(length);
sqlite> create index ix_dict_hash on dict(hash);
sqlite> .exit
[dk@kote ~]$

Так же были созданы индексы для полей length и hash — именно по ним будет идти поиск. Да-да, можно меня попинать — что хэш можно было бы сделать хотя бы на CRC — но банально лень, не те длины :)

Заполняем наш словарь:
#!/usr/local/bin/python
# -*- coding: utf-8 -*-
import string
import sqlite3

def hashWord(word):
    # sorting
    result = ''
    for c in sorted(word):
        result = result + c
    # return
    return result


file = open('./words.txt', 'r')
conn = sqlite3.connect('./dict.db')
c = conn.cursor()
for line in file:
    word = line.decode('cp866').rstrip().upper()
    length = len(word)
    hash = hashWord(word)
    sql = u"""insert into dict (word, length, hash) values ("{0}", {1}, "{2}")""".format(word, length, hash)
    c.execute(sql)
conn.commit()
c.close()


Словарь заполнили, теперь пишем функцию поиска по словарю — она до неприличия простая:
def findWords(text):
    text = text.upper()
    length = len(text)
    hash = hashWord(text)
    sql = u'select word from app_words_word where length = {0} and hash = "{1}"'.format(length, hash)
    conn = sqlite3.connect('./dict.db')
    c = conn.cursor()
    rows = c.execute(sql)
    result = []
    for row in rows:
        result.append(row[0])
    c.close()
    conn.close()
    return result


Ну и пишем простенькое приложение для тестирования:
[dk@kote ~]$ cat test.py
#!/usr/local/bin/python
# -*- coding: utf-8 -*-
import string
import sqlite3

def hashWord(word):
    # sorting
    result = ''
    for c in sorted(word):
        result = result + c
    # return
    return result

def findWords(text):
    text = text.upper()
    length = len(text)
    hash = hashWord(text)
    sql = u'select word from app_words_word where length = {0} and hash = "{1}"'.format(length, hash)
    conn = sqlite3.connect('./dict.db')
    c = conn.cursor()
    rows = c.execute(sql)
    result = []
    for row in rows:
        result.append(row[0])
    c.close()
    conn.close()
    return result


for text in [u'алтикаб', u'алантт', u'марко']:
    print 'Ask: ' + text
    for word in findWords(text):
        print '\tAnswer:' + word
[dk@kote ~]$ ./test.py
Ask: алтикаб
        Answer:БАЛТИКА
Ask: алантт
        Answer:ТАНТАЛ
        Answer:АТЛАНТ
        Answer:ТАЛАНТ
Ask: марко
        Answer:КОМАР
        Answer:КОРМА
        Answer:МАКОР
        Answer:МАКРО
        Answer:МОКРА
[dk@kote ~]$


Может кому такой способ и пригодится :)

2 комментария

avatar
Ну так выиграл или нет, вот что больше интересно :)
avatar
Мне больше ради спортивного интереса было :) После автоматизации ответов, первые места, да, были захвачены :)
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.