Cryptic Kicker

Распространенным, но небезопасным методом шифрования текста является перестановка букв алфавита. Другими словами, каждая буква алфавита последовательно заменяется в тексте другой буквой. Чтобы обеспечить обратимость шифрования, никакие две буквы не заменяются одной и той же буквой. Ваша задача - расшифровать несколько закодированных строк текста, предполагая, что каждая строка использует различный набор замен, и что все слова в расшифрованном тексте взяты из словаря известных слов.

вход

Ввод состоит из строчных слов в алфавитном порядке. Эти слова составляют словарь слов, которые могут появиться в расшифрованном тексте. За словарем следуют несколько строк ввода. Каждая строка зашифрована, как описано выше.

В словаре не более 1000 слов. Ни одно слово не превышает 16 букв. Зашифрованные строки содержат только строчные буквы и пробелы и не превышают 80 символов в длину.

Выход

Расшифруйте каждую строку и распечатайте ее на стандартный вывод. Если есть несколько решений, подойдет любое. Если решения не существует, замените каждую букву алфавита звездочкой.

Пример ввода

and dick jane puff spot yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

Пример вывода

dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

Вот решение. Обратите внимание, что я не лошадь, участвующая в гонке на самые короткие байты / Конкурсный программист. Я просто люблю головоломки!

( Источник )

Python 3, 423 байта

import sys,re
S=re.sub
D,*L=sys.stdin.read().split('\n')
def f(W,M=[],V="",r=0):
 if len({d for(s,d)in M})==len(M):
  if[]==W:return V.lower()
  for d in D.split():p='([a-z])(?%s.*\\1)';m=re.match(S(p%'=',')\\1=P?(',S(p%'!',').>\\1<P?(',W[0].translate(dict(M))[::-1]))[::-1]+'$',d.upper());r=r or m and f(W[1:],M+[(ord(s),m.group(s))for s in m.groupdict()],V+d+" ")
  return r
for l in L:print(f(l.split())or S('\w','*',l))

Считывает ввод из STDIN и записывает вывод в STDOUT, используя тот же формат, что и образец ввода / вывода.

объяснение

Для каждой строки зашифрованного текста мы выполняем следующую процедуру:

Мы сохраняем карту M всех преобразований букв, которые мы уже установили (которая изначально пуста). Мы делаем это таким образом, чтобы все исходные буквы были строчными, а буквы назначения - заглавными.

Мы обрабатываем слова в зашифрованном виде по порядку. Для каждого слова мы находим все слова в словаре, которым оно может соответствовать, следующим образом:

Предположим, что наше слово w есть glpplppljjlи что M содержит правило j -> P. Сначала мы преобразуем w, используя существующие правила в M , получая glpplpplPPl. Затем мы преобразовываем w в следующее регулярное выражение со вкусом Python:

(?P<g>.)(?P<l>.)(?P<p>.)(?P=p)(?P=l)(?P=p)(?P=p)(?P=l)PP(?P=l)

Правила трансформации следующие:

• Первое вхождение каждой строчной буквы, xзаменяется на . Это определяет именованную группу захвата named , которая соответствует одному символу.(?P<x>.)x
• Каждое последующее вхождение каждой строчной буквы, xзаменяется на . Это обратная ссылка на персонажа, ранее захваченного именованной группой .(?P=x)x

Мы выполняем это преобразование, обращая w , затем применяя две следующие замены регулярных выражений:

s/([a-z])(?!.*\1)/)>\1<P?(/
s/([a-z])(?=.*\1)/)\1=P?(/

и затем полностью изменяет результат. Обратите внимание, что символы, ранее преобразованные с помощью M, отображаются в верхнем регистре и поэтому остаются без изменений.

Мы сопоставляем полученное регулярное выражение с каждым из словарных слов, где словарные слова отображаются в верхнем регистре. Например, приведенное выше регулярное выражение будет соответствовать слову MISSISSIPPI. Если мы находим матч, мы извлекаем новые правила преобразования из него, и добавить их в M . Новые правила преобразования - это просто символы, захваченные каждой из групп захвата. В приведенном выше регулярном выражении групповые gсовпадения M, групповые lсовпадения Iи групповые pсовпадения Sдают нам правила g -> M, l -> I, p -> S. Мы должны убедиться, что результирующие правила согласованы, то есть, что никакие две исходные буквы не отображаются на одну и ту же букву назначения; в противном случае мы отклоняем матч.

Затем мы переходим к следующему слову, используя расширенные правила преобразования. Если мы можем сопоставить все слова зашифрованного текста, используя этот процесс, мы расшифровали текст. Если мы не можем сопоставить слово с каким-либо из словарных слов, мы возвращаемся назад и пытаемся сопоставить предыдущие слова с разными словарными словами. Если этот процесс не удался, решения не существует, и мы печатаем ряд звездочек.

CJam, 62 56 байт

qN%Sf/(f{\:C,m*{C..+`Sa`m2/Q|z_''f-Qf|=},C:,'*f*a+0=S*N}

Довольно медленный и требует много памяти, но работает для тестового примера с интерпретатором Java.

Пример запуска

$ cat input; echo
and dick jane puff spot yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
$ time cjam kicker.cjam < input
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

real    5m19.817s
user    6m41.740s
sys     0m1.611s