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

python
  1. import re, itertools
  2. import codecs
  3. from collections import defaultdict
  4. from copy import copy
  5.  
  6. def pattern(st):
  7.     d={}  
  8.     rv=[]
  9.     for l in st:
  10.         if not(l in d):
  11.             d[l]=len(d)
  12.         rv.append(d[l])
  13.     return tuple(rv)
  14.  
  15. def substitutions_generator(st):
  16.     words = re.split('[-*+]',st)
  17.     letters = list(set(''.join(words)))
  18.     first_letters = set([w[0] for w in words])
  19.     for comb in itertools.combinations(range(10),len(letters)):
  20.         d = dict(zip(letters,comb))
  21.         if not any(d[k] == 0 for k in first_letters):
  22.             yield d
  23.  
  24. def eval_substitution(st,substitution):
  25.     reverse_substitution = {}
  26.     for k in substitution:
  27.         reverse_substitution[str(substitution[k])] = k
  28.         st = st.replace(k,str(substitution[k]))
  29.     result = str(eval(st))
  30.     tojd = st + "=" + result
  31.     forbidden = set([]) #цифры, которые нельзя заменять буквами из substitution
  32.     for k in reverse_substitution:
  33.         if not(k in result):
  34.             forbidden.add(reverse_substitution[k])          
  35.         else:
  36.             result = result.replace(k,reverse_substitution[k])
  37.     return result,tojd,forbidden
  38.  
  39.  
  40. def gen_indexes(path, limit = None):  
  41.     freq_dict = {}
  42.     pattern_index = defaultdict(set)
  43.     letters_order_index = defaultdict(set)
  44.     words_list=[]
  45.     letters_existance_index = defaultdict(set)
  46.  
  47.     for i,l in enumerate(codecs.open(path,"r","utf-8-sig")):
  48.         if limit and i>limit:break
  49.         w,n=l.split()
  50.         words_list.append(w)
  51.         index = len(words_list)-1
  52.         freq_dict[index]=int(n)
  53.         pattern_index[pattern(w)].add(index)
  54.         for k in list(enumerate(w)):
  55.             letters_order_index[k].add(index)
  56.         for l in w:
  57.             letters_existance_index[l].add(index)
  58.     return words_list, pattern_index, letters_order_index, letters_existance_index, freq_dict
  59.  
  60. def generate_cryptarithm(st, indexes):
  61.     words_list, pattern_index, letters_order_index, letters_existance_index, freq_dict = indexes
  62.     d=defaultdict(list)
  63.     for sub in substitutions_generator(st):      
  64.         res,tojd,forbidden = eval_substitution(st,sub)
  65.         cur_indexes=copy(pattern_index.get(pattern(res),set([])))
  66.         if not cur_indexes:
  67.             continue
  68.         for lk in list(enumerate(res)):
  69.             if not(lk[1] in '0123456789'):
  70.                 cur_indexes&=letters_order_index.get(lk,set([]))
  71.         for l in forbidden:
  72.             cur_indexes-=letters_existance_index[l]
  73.         if cur_indexes:
  74.             for w in cur_indexes:
  75.                 d[w].append((sub,tojd))
  76.     for k in sorted(d.keys(), key = lambda x:freq_dict[x], reverse = True):
  77.         if len(d[k]) ==1:
  78.             tojd=d[k][0][1]
  79.             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)
Назад

Реклама

Мы в соцсетях

tw tg yt gt