Cryptic Kicker

Powszechną, ale niepewną metodą szyfrowania tekstu jest permutacja liter alfabetu. Innymi słowy, każda litera alfabetu jest konsekwentnie zastępowana w tekście inną literą. Aby zapewnić odwracalność szyfrowania, dwie litery nie są zastępowane tą samą literą. Twoim zadaniem jest odszyfrowanie kilku zakodowanych wierszy tekstu, przy założeniu, że każda linia używa innego zestawu zamienników i że wszystkie słowa w odszyfrowanym tekście pochodzą ze słownika znanych słów.

Wejście

Dane wejściowe składają się z małych liter w kolejności alfabetycznej. Te słowa składają się na słownik słów, które mogą pojawić się w odszyfrowanym tekście. Po słowniku znajduje się kilka wierszy wprowadzania. Każda linia jest szyfrowana zgodnie z powyższym opisem.

Słownik nie zawiera więcej niż 1000 słów. Żadne słowo nie przekracza 16 liter. Zaszyfrowane linie zawierają tylko małe litery i spacje i nie przekraczają 80 znaków.

Wynik

Odszyfruj każdą linię i wydrukuj ją na standardowe wyjście. Jeśli istnieje wiele rozwiązań, każde z nich zrobi. Jeśli nie ma rozwiązania, zastąp każdą literę alfabetu gwiazdką.

Przykładowe dane wejściowe

and dick jane puff spot yertle

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

Przykładowe dane wyjściowe

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

Oto rozwiązanie. Należy pamiętać, że nie jestem koniem biegnącym w wyścigu o najkrótsze bajty / programista konkurencyjny. Po prostu lubię puzzle!

( Źródło )

Python 3, 423 bajty

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))

Odczytuje dane wejściowe ze STDIN i zapisuje dane wyjściowe do STDOUT, używając tego samego formatu, co przykładowe dane wejściowe / wyjściowe.

Wyjaśnienie

Dla każdej linii tekstu zaszyfrowanego wykonujemy następującą procedurę:

Trzymamy mapę M wszystkich transformacji liter, które już ustaliliśmy (która początkowo jest pusta). Robimy to w taki sposób, aby wszystkie litery źródłowe były pisane małymi literami, a litery docelowe - dużymi.

Przetwarzamy słowa w tekście zaszyfrowanym w kolejności. Dla każdego słowa znajdujemy wszystkie słowa w słowniku, które mogą być dopasowane, w następujący sposób:

Załóżmy, że nasze słowo, w , jest glpplppljjli że M zawiera regułę j -> P. Najpierw przekształcamy w używając istniejących reguł w M , otrzymując glpplpplPPl. Następnie przekształcamy w w następujący regex o smaku Pythona:

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

Zasady transformacji są następujące:

• Pierwsze wystąpienie każdej małej litery x, jest zastępowane przez . Definiuje nazwaną grupę przechwytywania, o nazwie , która pasuje do jednego znaku.(?P<x>.)x
• Każde kolejne wystąpienie każdej małej litery xjest zastępowane przez . Jest to odniesienie do postaci wcześniej schwytanej przez wskazaną grupę .(?P=x)x

Wykonujemy tę transformację poprzez odwrócenie w , a następnie zastosowanie dwóch następujących podstawień wyrażeń regularnych:

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

a następnie odwrócenie wyniku. Zauważ, że znaki wcześniej przekształcone przez M pojawiają się jako wielkie litery, a zatem pozostają niezmienione.

Dopasowujemy wynikowe wyrażenie regularne do każdego słowa w słowniku, przy czym słowa w słowniku pojawiają się jako wielkie litery. Na przykład powyższe wyrażenie regularne pasuje do słowa MISSISSIPPI. Jeśli znajdziemy mecz, możemy wyodrębnić nowe zasady transformacji od niego, i dodać je do M . Nowe reguły transformacji to po prostu znaki przechwycone przez każdą z grup przechwytywania. W powyższym wyrażeniu regularnym gdopasowania Mgrupowe, ldopasowania grupowe Ii pdopasowania grupowe Sdają nam reguły g -> M, l -> I, p -> S. Musimy upewnić się, że wynikające reguły są spójne, to znaczy, że żadne dwie litery źródłowe nie są odwzorowane na tę samą literę docelową; w przeciwnym razie odrzucamy dopasowanie.

Następnie przechodzimy do następnego słowa, korzystając z rozszerzonych reguł transformacji. Jeśli możemy dopasować wszystkie słowa zaszyfrowane za pomocą tego procesu, odszyfrowaliśmy tekst. Jeśli nie możemy dopasować słowa do któregokolwiek ze słów ze słownika, cofamy się i próbujemy dopasować poprzednie słowa do różnych słów ze słownika. Jeśli ten proces się nie powiedzie, nie ma rozwiązania i drukujemy rząd gwiazdek.

CJam, 62 56 bajtów

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

Dość powolny i wymagający pamięci, ale działa w przypadku testowym z interpreterem Java.

Przykładowy przebieg

$ 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