В написанной на днях статье Вернулся невод с тиной морскою я дал ссылку на частотный словарь Википедии. Колличество скачиваний на порядки превзошло все мои ожидания. Я почувствавал огромное духовное родство с читателями Хабра. Одна часть скачавших (как и я!) любит всячески возиться со словами и словарями, а вторая часть (как и я!), увидев на просторах сети интересный артефакт, тут же хватает его и тащит к себе в гнездо, а что с ним делать — потом разберёмся!
К первой части у меня просьба. Если Вы нашли интересное применение словарю или у вас есть идея такого применения и это всё не коммерческая тайна, поделитесь, пожалуйста, в комментариях.
А для второй части, для тех, кто скачал словарь, а теперь мучительно думает, что делать со свалившимся счастьем, я хочу написать несколько статей. Собственно с этой и начну.
Криптарифм — разновидность математических головоломок. В арифметическом тождестве каждая цифра заменена буквой (одинаковые цифры — одинаковыми буквами, разные — разными). Решением криптарифма является такая подстановка, при которой тождество становится верным. Как правило, криптарифм имеет только одно решение.
Самым известным криптарифмом является «SEND+MORE=MONEY», опубликованный в 1924ом году английским математиком Генри Дудени. Его (единственное) решение 9567+1085=10652.
Решить криптарифм вручную может быть довольно сложно, зависит от конкретной головоломки. Но ещё сложнее придумать криптарифм так, чтобы он представлял из себя несколько связанных между собой слов или даже осмысленную фразу. Придумать головоломку на умножение хотя бы трёхзначных чисел, задача для человека крайне сложная.
Об автоматических решателях криптарифмов написано много, впрочем, с современными машинами, тупой брутфорс-решатель пишется в несколько строчек и решает за вполне приемлемое время.
В этой статье я покажу, как, имея под рукой большой словарь, написать программу-ассистент для сочинения красивых криптарифмов.
Работать программа будет так:
функция получает начало криптарифма, до знака равенства, например «SEND+MORE», и печатает список полных криптарифмов имеющих одно решение.
Перебираем все возможные подстановки для полученного начала криптарифма. Подстановки, в которых одно или несколько чисел начинаются с нуля отбрасываем за ненадобностью. Для каждой подстановки вычисляем результат получившегося в результате её применения арифметического выражения. Если в этом результате есть цифры из подстановки, заменяем их соответствующими буквами и помним о том, что те цифры, которых в подстановке не было нельзя заменять буквами из подстановки. Ищем в словаре слова, подходящие под получившийся шаблон, по ходу дела заполняем словарь, в котором каждому найденному слову соответствует список подстановок, в результате которых это слово может получиться. В конце отбираем только те слова, которые могут получиться в результате только одной подстановки (криптарифм имеет одно решение) и их выводим. Выводить можно отсортировав по частотности в порядке убывания, чтобы всякий мусор (а его в википедии немало) оказался внизу получившегося списка.
Рассмотрим один шаг работы алгоритма:
пользователь ввёл — хабр*хабр
алгоритм пробует очередную подстановку, например — х=7, а=6, б=1, р=8
сначала вычисление — 7618*7618=58033924
в получившемся числе присутствует 8, которой соответствует буква р, таким образом нам надо найти в словаре все слова, подходящие под шаблон 5р033924 (или проще говоря слова, в которых вторая буква «р», а четвёртая и пятая буквы совпадают), причём ещё надо учесть, что цифры 5, 0, 3, 9, 2, 4 не могут соответствовать буквам х, а и б, т.к. эти буквы уже заняты цифрами 7, 6 и 1 соответственно.
Когда алгоритм отработает, оставляем только те, слова, которые можно получить только одной подстановкой и выводим соответствующие строчки, в частности хабр*хабр=троллинг,7618*7618=58033924 (ВНИМАНИЕ! Мнение автора программы может не совпадать с содержанием получившихся в результате её выполнения крифтарифмов).
Единственная нетривиальная часть алгоритма — поиск слов, обладающих определёнными свойствами, в огромном словаре. Для этого, при загрузке словаря, программа заполняет несколько индексов.
0) word_list — список всех слов словаря
1) pattern_index — индекс структур. Структура слова определяется вот такой функцией:
def pattern(st):
d={}
rv=[]
for l in st:
if not(l in d):
d[l]=len(d)
rv.append(d[l])
return tuple(rv)
Индексом в словаре служит структура, а значением — сет всех слов (точнее не самих слов, а их индексов в списке word_list), обладающих подобной струтурой. При помощи этого словаря можно моментально найти все слова, в которых кол-во и расположение букв совпадает с заданым словом или шаблоном:
for i in signature_dict.get(signature_key(u'барабан'),set()):
print words_list[i],
каракас кабаках казакам балабан заказал билибин галаган доходов барабан барабаш заказан перепел потопом доходом роторов каракал казаках киликия киликию заказах заказав заказам белебей ротором доводом
2) letters_order_index — индекс расположения букв. Ключ — буква и её порядковый номер в слове. Значение — сет всех слов (точнее… ну вы поняли) в которых эта буква стоит на заданной позиции.
for i in letters_order_index.get((1,u'ы'),set()):
print words_list[i],
быкова высказываниями дык был рысак выказать выглядели лыжного была были было быстров дыховичный дымке сыпь лыжа вытеснив выпуском выслушав выигран выводил рысистой выступающими лыжника сычёва выкуплены выразили высылку высочайшими…
3) letters_existance_index — индекс нахождения букв в словах. Ключ — буква. Значение — сет всех слов (точнее… итд.) в которых есть эта буква.
for i in letters_existance_index.get((1,u'ъ'), set()):
print words_list[i],
объявленные объявленной объединила конъюгации предъявило объединённая разъезжал съездить несъедобен грузоподъемностью подъехали подъемные подъездах объёмными объезд объединяется необъяснимые въезда объявит объёмом объявился объединяющие объединенные съёмочная предъявлении въезд изъято подъездных объективы…
Т.к. перечисленные индексы содержат сеты (множества), с ними можно легко проделывать операции над множествами — объединение, пересечение, разницу и пр.
Теперь становится полностью понятно, как искать слова в примере с подстановкой.
сначала находим множество всех слов, у которых структура такая же, как у 58033924, затем получаем его пересечение с множеством слов, у которых вторая буква «р», от того что получилось отнимаем по очереди множества слов, в которых есть буквы «х», «а» и «б». то, что получается в итоге и есть множество слов для подстановки х=7, а=6, б=1, р=8.
Вот собственно програмный код.
import re, itertools
import codecs
from collections import defaultdict
from copy import copy
def signature_key(st):
d={}
rv=[]
for l in st:
if not(l in d):
d[l]=len(d)
rv.append(d[l])
return tuple(rv)
def substitutions_generator(st):
words = re.split('[-*+]',st)
letters = list(set(''.join(words)))
first_letters = set([w[0] for w in words])
for comb in itertools.combinations(range(10),len(letters)):
d = dict(zip(letters,comb))
if not any(d[k] == 0 for k in first_letters):
yield d
def eval_substitution(st,substitution):
reverse_substitution = {}
for k in substitution:
reverse_substitution[str(substitution[k])] = k
st = st.replace(k,str(substitution[k]))
result = str(eval(st))
tojd = st + "=" + result
forbidden = set([]) #цифры, которые нельзя заменять буквами из substitution
for k in reverse_substitution:
if not(k in result):
forbidden.add(reverse_substitution[k])
else:
result = result.replace(k,reverse_substitution[k])
return result,tojd,forbidden
def gen_indexes(path, limit = None):
freq_dict = {}
pattern_index = defaultdict(set)
letters_order_index = defaultdict(set)
words_list=[]
letters_existance_index = defaultdict(set)
for i,l in enumerate(codecs.open(path,"r","utf-8-sig")):
if limit and i>limit:break
w,n=l.split()
words_list.append(w)
index = len(words_list)-1
freq_dict[index]=int(n)
pattern_index[signature_key(w)].add(index)
for k in list(enumerate(w)):
letters_order_index[k].add(index)
for l in w:
letters_existance_index[l].add(index)
return words_list, pattern_index, letters_order_index, letters_existance_index, freq_dict
def generate_cryptarithm(st, indexes):
words_list, pattern_index, letters_order_index, letters_existance_index, freq_dict = indexes
d=defaultdict(list)
for sub in substitutions_generator(st):
res,tojd,forbidden = eval_substitution(st,sub)
cur_indexes=copy(pattern_index.get(signature_key(res),set([])))
if not cur_indexes:
continue
for lk in list(enumerate(res)):
if not(lk[1] in '0123456789'):
cur_indexes&=letters_order_index.get(lk,set([]))
for l in forbidden:
cur_indexes-=letters_existance_index[l]
if cur_indexes:
for w in cur_indexes:
d[w].append((sub,tojd))
for k in sorted(d.keys(), key = lambda x:freq_dict[x], reverse = True):
if len(d[k]) ==1:
tojd=d[k][0][1]
print "%s=%s,%s"%(st,words_list[k],tojd)
Для того, чтобы пользоваться этим модулем можно импортировать из него две функции — gen_indexes и generate_cryptarithm.
Сгенерируем достойный ответ на send+more=money:
# -*- coding: utf-8 -*-
from cryptarithm import generate_cryptarithm,gen_indexes
indexes = gen_indexes("wiki_freq.txt", 400000)
l1=[u'пошли',u'пришли',u'вышли',u'отправь']
l2=[u'еще',u'больше',u'мне',u'много', u'срочно']
for w1 in l1:
for w2 in l2:
generate_cryptarithm(w1+u'+'+w2,indexes)
generate_cryptarithm(w1+u'*'+w2,indexes)
generate_cryptarithm(w1+u'-'+w2,indexes)
Получим много вариантов, остаётся только просмотреть и выбрать.
Лично мне наиболее симпатичен вышли-еще=воблы,43198-505=42693
Код распространяется по лицензии!
Лицензия.
Берите кто хочет. Делайте что хотите — меняйте, распространяйте, продавайте. Указывать моё авторство не обязательно. Но если сделайте с программой что-нибудь интересное или получите интересные результаты в результате её использования — напишите, пожалуйста, комментарий.
Автор: gromozeka1980
