Kicker samar

Metode enkripsi teks yang umum tetapi tidak aman adalah dengan mengubah huruf alfabet. Dengan kata lain, setiap huruf alfabet secara konsisten diganti dalam teks dengan beberapa huruf lainnya. Untuk memastikan bahwa enkripsi dapat dibalik, tidak ada dua huruf yang diganti dengan huruf yang sama. Tugas Anda adalah mendekripsi beberapa baris teks yang disandikan, dengan asumsi bahwa setiap baris menggunakan serangkaian penggantian yang berbeda, dan bahwa semua kata dalam teks yang didekripsi tersebut berasal dari kamus kata-kata yang dikenal.

Memasukkan

Input terdiri dari kata-kata kecil, dalam urutan abjad. Kata-kata ini menyusun kamus kata-kata yang mungkin muncul dalam teks yang didekripsi. Mengikuti kamus adalah beberapa baris input. Setiap baris dienkripsi seperti dijelaskan di atas.

Tidak ada lebih dari 1.000 kata dalam kamus. Tidak ada kata yang melebihi 16 huruf. Baris terenkripsi hanya berisi huruf kecil dan spasi dan panjangnya tidak lebih dari 80 karakter.

Keluaran

Dekripsi setiap baris dan cetak ke output standar. Jika ada beberapa solusi, ada yang akan melakukannya. Jika tidak ada solusi, ganti setiap huruf dari alfabet dengan tanda bintang.

Input Sampel

and dick jane puff spot yertle

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

Output Sampel

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

Inilah solusinya. Harap dicatat bahwa saya bukan kuda yang berlari dalam perlombaan untuk byte / programmer Kompetitif terpendek . Saya suka puzzle!

( Sumber )

Python 3, 423 byte

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

Membaca input dari STDIN dan menulis output ke STDOUT, menggunakan format yang sama dengan input / output sampel.

Penjelasan

Untuk setiap baris ciphertext, kami melakukan prosedur berikut:

Kami menyimpan peta, M , dari semua transformasi huruf yang telah kami buat (yang awalnya kosong). Kami melakukannya sedemikian rupa sehingga huruf sumber semuanya huruf kecil dan huruf tujuan semua huruf besar.

Kami memproses kata-kata dalam ciphertext secara berurutan. Untuk setiap kata, kami menemukan semua kata dalam kamus yang cocok, sebagai berikut:

Misalkan kata kita, w , adalah glpplppljjldan bahwa M mengandung aturan j -> P. Kami pertama-tama mengubah w menggunakan aturan yang ada di M , dapatkan glpplpplPPl. Kami kemudian mengubah w menjadi regex rasa python berikut:

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

Aturan transformasi adalah sebagai berikut:

• Kemunculan pertama setiap huruf kecil x,, diganti dengan . Ini mendefinisikan kelompok tangkapan bernama, yang disebut , yang cocok dengan cahracter tunggal.(?P<x>.)x
• Setiap kemunculan selanjutnya setiap huruf kecil x,, diganti dengan . Ini adalah referensi kembali ke karakter yang sebelumnya ditangkap oleh grup yang disebutkan .(?P=x)x

Kami melakukan transformasi ini dengan membalikkan w , lalu menerapkan dua pergantian regex berikut:

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

dan kemudian membalikkan hasilnya. Perhatikan bahwa karakter yang sebelumnya diubah oleh M muncul sebagai huruf besar, dan oleh karena itu tetap tidak berubah.

Kami mencocokkan regex yang dihasilkan dengan masing-masing kata kamus, di mana kata-kata kamus muncul sebagai huruf besar. Misalnya, regex di atas akan cocok dengan kata MISSISSIPPI. Jika kita menemukan kecocokan, kita mengekstrak aturan transformasi baru dari itu, dan menambahkannya ke M . Aturan transformasi baru hanyalah karakter yang ditangkap oleh masing-masing kelompok tangkapan. Di regex di atas, grup gcocok M, grup lcocok I, dan grup pcocok S, memberi kami aturan g -> M, l -> I, p -> S. Kita harus memastikan bahwa aturan yang dihasilkan konsisten, yaitu, bahwa tidak ada dua huruf sumber yang dipetakan ke surat tujuan yang sama; jika tidak, kami menolak pertandingan.

Kami kemudian melanjutkan ke kata berikutnya, menggunakan aturan transformasi augmented. Jika kami dapat mencocokkan semua kata ciphertext menggunakan proses ini, kami telah mendekripsi teksnya. Jika kami tidak dapat mencocokkan kata dengan kata-kata kamus, kami mundur dan mencoba untuk mencocokkan kata-kata sebelumnya dengan kata-kata kamus yang berbeda. Jika proses ini gagal, tidak ada solusi, dan kami mencetak deretan tanda bintang.

CJam, 62 56 byte

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

Cukup lambat dan memori haus, tetapi bekerja untuk test case dengan Java interpreter.

Contoh dijalankan

$ 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