Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

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

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

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

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

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

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

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

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB