Come posso risolvere l'esercizio “Cripta Kicker” proposto in “Le sfide di programmazione (Programming Contest Training Manual)”?

Question

"Programmazione sfide (La programmazione Contest Training Manual)" è probabilmente uno degli esercizi più belle libro su algoritmi. Ho risolto i primi 11 esercizi, ma ora mi sono bloccato con il problema di "Crypt Kicker":

  

Crypt Kicker
  Un metodo comune, ma non sicuro di crittografare il testo è quello di permutare le lettere dell'alfabeto.   In altre parole, ogni lettera dell'alfabeto è costantemente sostituito nel testo da qualche altra lettera. Per garantire che la crittografia è reversibile, non ci sono due lettere sono sostituite dalla stessa lettera.

     

Il compito è quello di decifrare più righe codificati di testo, supponendo che ciascuna riga utilizza un diverso insieme di sostituzioni, e che tutte le parole del testo decodificata sono da un dizionario di parole note.

     

ingresso   L'ingresso è costituito da una linea contenente un numero intero n, seguita da n parole minuscole, uno per riga, in ordine alfabetico. Queste parole n compongono il dizionario di parole che possono apparire nel testo decifrato.
  A seguito del dizionario sono diverse linee di ingresso. Ogni linea è crittografato come descritto sopra.

     

Non ci sono più di 1.000 parole del dizionario. Nessuna parola è superiore a 16   lettere. Le linee cifrati contengono solo minuscole e spazi e   non superare i 80 caratteri di lunghezza.

     

Output
  Decifrare ogni linea e stampare sullo standard output. Se ci sono più soluzioni, nessuno farà.
  Se non esiste una soluzione, sostituire ogni lettera dell'alfabeto da un asterisco.

     

Input Esempio 6
    e
    Dick
    jane
    puff
    individuare
    Yertle

     

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

     

Output di esempio
   Dick e Jane e sfoglia e posto e Yertle ...

Cosa strategia dovrei prendere per risolvere questo esercizio? Stavo pensando a una soluzione classica e brutale backtracking, ma sto cercando da evitare che finché non trovo qualcosa di più intelligente.

PS:. Questo non è correlato compiti a casa, sto solo cercando di migliorare le mie capacità complessive

Answer 1

KeyArray terrà la tabella di sostituzione.

• Inizia con un KeyArray vuoto, questa è la versione 0

• Partita parola più lunga cifrato a più lunga parola del dizionario e aggiungere al KeyArray (Se ce ne sono due più lunga, scegliere qualsiasi), questa è la versione 1.

• Decrypt alcune lettere della parola successiva più lunga criptato.

• Verificare se le lettere decifrati corrisponde alla lettera nella stessa posizione in ogni parola del dizionario della stessa lunghezza.
• Se nessuno le partite, risalgono alla versione 0 e provare un'altra parola.

• Se alcune lettere corrispondono, aggiungere il resto delle lettere a KeyArray, questa è la versione 2.

• Decrypt alcune lettere della parola successiva più lunga criptato.

• Verificare se le lettere decifrati corrisponde alla lettera nella stessa posizione in qualsiasi parola dizionario.
• Se nessuno le partite, risalgono alla versione 1 e provare un'altra parola
• Se alcune lettere corrispondono, aggiungere il resto delle lettere a KeyArray, questa è la versione 3.

Ripetere fino a quando tutte le parole siano decriptato.

Se in versione 0 nessuna delle parole più lunghe crea una decrypt parziale parole più brevi, molto probabilmente, non esiste una soluzione.

Answer 2

ottimizzazione minore Una potrebbe essere fatto enumerando le possibilità prima della corsa backtracking. In Python:

dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']

# ------------------------------------

import collections

words_of_length = collections.defaultdict(list)

for word in dictionary:
  words_of_length[len(word)].append(word)

possibilities = collections.defaultdict(set)
certainities = {}

for word in line:
    length = len(word)
    for i, letter in enumerate(word):
        if len(words_of_length[length]) == 1:
            match = words_of_length[length][0]
            certainities[letter] = match[i]
        else:
            for match in words_of_length[length]:
              possibilities[letter].add(match[i])

for letter in certainities.itervalues():
    for k in possibilities:
        possibilities[k].discard(letter)

for i, j in certainities.iteritems():
    possibilities[i] = set([j])

# ------------------------------------

import pprint
pprint.pprint(dict(possibilities))

Output:

{'a': set(['c', 'f', 'o']),
 'b': set(['d']),
 'e': set(['r']),
 'f': set(['l']),
 'g': set(['f', 'k']),
 'h': set(['j', 'p', 's']),
 'j': set(['i', 'p', 'u']),
 'm': set(['c', 'f', 'k', 'o']),
 'n': set(['e']),
 'p': set(['y']),
 'q': set(['i', 'j', 'p', 's', 'u']),
 'r': set(['j', 'p', 's']),
 's': set(['n']),
 't': set(['t']),
 'v': set(['c', 'f', 'o']),
 'x': set(['a']),
 'y': set(['i', 'p', 'u'])}

Se si dispone di alcune possibilità a singolo elemento, è possibile eliminare dal input e rieseguire l'algoritmo.

EDIT:. Switched alla serie invece di lista e aggiunto il codice di stampa

Answer 3

In realtà ho provato un approccio piuttosto diverso. Ho costruito un trie dalle parole del dizionario. Poi io cammino attraverso il trie e la frase insieme in modo ricorsivo (attraversamento del trie in un DFS).

In ogni spazio mi assicuro che ha colpito alla fine di una parola nel trie e se è così io loop back alla radice. Lungo la strada ho tenere traccia delle assegnazioni delle lettere che ho fatto finora. Se mai ho un incarico che contraddice un incarico prima fallisco e svelare la ricorsione al punto che possono rendere la prossima possibile assigment.

Sembra difficile, ma sembra funzionare abbastanza bene. E non è davvero così difficile da codice su!

Answer 4

Un altro possibile ottimizzazione, se hai testo "abbastanza" per affrontare e si conosce la lingua del testo, è possibile utilizzare le frequenze lettera (vedi: http://en.wikipedia.org/wiki/Letter_frequency). Si tratta naturalmente di un approccio molto approssimativo quando si tratta di 6/7 parole, ma sarà il modo più veloce se si dispone di un paio di pagine per la decodifica.

EDIT: sulla soluzione di Max, si potrebbe tentare di estrarre alcune caratteristiche della parola, anche, come le lettere che si ripetono. Ovviamente, osservando che soffio nel dizionario e qymm nel testo cifrato sono le uniche quattro parole lettera che termina con una doppia lettera dà una risposta dritto per 3 delle lettere. Negli scenari più complessi, si dovrebbe essere in grado di restringere le possibilità di ogni coppia lettera.

Answer 5

Ecco un'implementazione Java con altri filtri al algoritmo proposto da @Carlos Gutiérrez.

Crypt Kicker Algoritmo e soluzione, cosa è andato storto?

• La raffinatezza è quello di aggiungere un motivo di parola per ridurre lo spazio di ricerca per le parole. Ad esempio, le parole "abc" e "lei" hanno lo stesso modello, mentre "aac" e "lei" non come parola di tre lettere distinte non sarebbe abbinare una parola distinta lettere di traino.

• Inoltre, l'algoritmo può essere implementato in modo ricorsivo che è più intuitivo e sensibile.