Como resolvo o exercício de "kicker de cripta" proposto em "desafios de programação (o manual de treinamento do concurso de programação)"?

StackOverflow https://stackoverflow.com/questions/2175356

  •  24-09-2019
  •  | 
  •  

Pergunta

"Os desafios de programação (o manual de treinamento do concurso de programação)" é provavelmente um dos melhores exercícios sobre algoritmos. Eu resolvi os 11 primeiros exercícios, mas agora estou preso ao problema do "kicker de cripta":

Kicker de cripta
Um método comum, mas inseguro, de criptografar o texto é permitir as letras do alfabeto. Em outras palavras, cada letra do alfabeto é consistentemente substituída no texto por outra letra. Para garantir que a criptografia seja reversível, não há duas letras são substituídas pela mesma letra.

Sua tarefa é descriptografar várias linhas de texto codificadas, assumindo que cada linha use um conjunto diferente de substituições e que todas as palavras no texto descriptografadas são de um dicionário de palavras conhecidas.

Entrada
A entrada consiste em uma linha contendo um número inteiro n, seguido por n palavras minúsculas, uma por linha, em ordem alfabética. Essas n palavras compõem o dicionário de palavras que podem aparecer no texto descriptografado.
Após o dicionário, existem várias linhas de entrada. Cada linha é criptografada como descrito acima.

Não há mais de 1.000 palavras no dicionário. Nenhuma palavra excede 16 letras. As linhas criptografadas contêm apenas letras e espaços minúsculos e não excedem 80 caracteres de comprimento.

Resultado
Descriptografar cada linha e imprimi -la para saída padrão. Se houver várias soluções, alguém fará.
Se não houver solução, substitua todas as letras do alfabeto por um asterisco.

Entrada de amostra 6
e
Dick
Jane
sopro
ver
yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxxaaaaaaaaaaaaaaaaaaaaaaaa

Saída de amostra
Dick e Jane e Puff and Spot e Yertle ...

o que estratégia Devo levar para resolver este exercício? Eu estava pensando em uma solução clássica e brutal de retrocesso, mas estou tentando evitar isso até encontrar algo mais inteligente.

PS: Isso não está relacionado à lição de casa, estou apenas tentando melhorar minhas habilidades gerais.

Foi útil?

Solução

KeyArray manterá a tabela de substituição.

  • Comece com um keyArray vazio, esta é a versão 0

  • Combine a palavra criptografada mais longa com a palavra de dicionário mais longa e adicione ao keyArray (se houver dois mais longos, escolha algum), esta é a versão 1.

  • Descriptografar algumas cartas da próxima palavra mais longa.

  • Verifique se as letras descriptografadas correspondem à letra na mesma posição em qualquer palavra do dicionário do mesmo comprimento.
  • Se ninguém corresponder, volte à versão 0 e tente outra palavra.

  • Se algumas letras corresponderem, adicione o restante das letras ao KeyArray, esta é a versão 2.

  • Descriptografar algumas cartas da próxima palavra mais longa.

  • Verifique se as letras descriptografadas correspondem à letra na mesma posição em qualquer palavra do dicionário.
  • Se nenhum corresponde, volte à versão 1 e tente outra palavra
  • Se algumas letras corresponderem, adicione o restante das letras ao KeyArray, esta é a versão 3.

Repita até que todas as palavras sejam descriptografadas.

Se na versão 0 nenhuma das palavras mais longas criar uma descriptografar parcial em palavras mais curtas, muito provavelmente não há solução.

Outras dicas

Uma pequena otimização pode ser feita enumiando possibilidades antes da execução de retrocesso. Em 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))

Resultado:

{'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 você tiver algumas possibilidades de elemento único, poderá eliminá-las da entrada e executar novamente o algoritmo.

EDITAR: Mudou para definir em vez de listar e adicionar código de impressão.

Na verdade, tentei uma abordagem bastante diferente. Eu construí um trie das palavras do dicionário. Então eu ando pelo trie e a frase juntos recursivamente (atravessando o trie em um DFS).

Em cada espaço, certifico -me de acertar o fim de uma palavra no trie e, se assim for, volto à raiz. Ao longo do caminho, acompanho as atribuições de letras que fiz até agora. Se alguma vez eu tiver uma tarefa que contradiz uma tarefa anterior, falhei e desvendo a recursão ao ponto, posso fazer o próximo possível Assigment.

Parece complicado, mas parece funcionar muito bem. E realmente não é tão difícil de codificar!

Outra otimização possível, se você tiver texto "suficiente" para lidar e conhece o idioma do texto, pode usar frequências de letras (consulte: http://en.wikipedia.org/wiki/Letter_frequency). É claro que essa é uma abordagem muito aproximada ao lidar com 6/7 palavras, mas será a maneira mais rápida se você tiver algumas páginas para decodificar.

Editar: Sobre a solução de Max, você pode tentar extrair algumas características da palavra também, como repetir letras. Obviamente, a observação desse sopro no dicionário e no QYMM no texto criptografado são as únicas palavras de quatro letras que terminam com uma letra dupla fornecem uma resposta direta para 3 das letras. Em cenários mais complexos, você poderá restringir as possibilidades para cada casal de letras.

Aqui está uma implementação de Java com mais refinamentos para o algoritmo proposto por @carlos gutiérrez.

Algoritmo e solução de kicker de cripta, o que deu errado?

  • O refinamento é adicionar um padrão de palavras para reduzir o espaço de pesquisa para obter palavras. Por exemplo, as palavras "abc" e "ela" têm o mesmo padrão enquanto "aac" e "ela" não como uma palavra de três letras distintas não corresponderia a uma palavra distinta de letras de reboque.

  • Além disso, o algoritmo pode ser implementado recursivamente, o que é mais intuitivo e sensato.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top