html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Генератор криптарифмов

В написанной на днях статье Вернулся невод с тиной морскою, я дал ссылку на частотный словарь Википедии. Количество скачиваний на порядки превзошло все мои ожидания. Я почувствавал огромное духовное родство с читателями Хабра. Одна часть скачавших (как и я!) любит всячески возиться со словами и словарями, а вторая часть (как и я!), увидев на просторах сети интересный артефакт, тут же хватает его и тащит к себе в гнездо, а что с ним делать — потом разберёмся!

К первой части у меня просьба. Если Вы нашли интересное применение словарю или у вас есть идея такого применения и это всё не коммерческая тайна, поделитесь, пожалуйста, в комментариях.

А для второй части, для тех, кто скачал словарь, а теперь мучительно думает, что делать со свалившимся счастьем, я хочу написать несколько статей. Собственно с этой и начну.

Криптарифм — разновидность математических головоломок. В арифметическом тождестве каждая цифра заменена буквой (одинаковые цифры — одинаковыми буквами, разные — разными). Решением криптарифма является такая подстановка, при которой тождество становится верным. Как правило, криптарифм имеет только одно решение.

Самым известным криптарифмом является «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

Код распространяется по лицензии!

Лицензия.
Берите кто хочет. Делайте что хотите — меняйте, распространяйте, продавайте. Указывать моё авторство не обязательно. Но если сделаете с программой что-нибудь интересное или получите интересные результаты в результате её использования — напишите, пожалуйста, комментарий.
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

7

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • habrahabr.ru
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции