Pretende-se desenvolver um programa para descodificar mensagens cifradas de acordo com uma cifra de substituição: cada letra da mensagem original foi substituida por outra letra (existindo uma bijecção entre as letras do alfabeto original e as letras do alfabeto do código). Por exemplo, podemos substituir a letra 'e' pela letra 'r', a letra 'h' pela letra 'x', a letra 'l' pela letra 'v' e a letra 'o' pela letra 'p' e a mensagem 'hello' será codificada como 'xrvvp'.
O processo de descodificação de um código deste não pode ser cego (no sentido de se tentarem todas as combinações pois existem 26! combinações possíveis). Uma solução passa por tirar partido do facto de nem todas as letras aparecerem com a mesma frequência. De facto, as letras em Inglês surgem pela seguinte ordem (da mais frequente para a menos frequente): E, T, A, O, I, N, S, H, R, D, L, C, U, M, W, F, G, Y, P, B, V, K, J, X, Q, Z. Então, a primeira etapa passa por contar o número de vezes que cada letra surge na mensagem, e ordená-las por ordem descrescente de ocorrência. Com esta informação, podemos tentar quebrar o código: basta associar a letra mais frequente à letra 'E', a segunda frequente à letra 'T' e assim sucessivamente (para não surgirem confusões entre as letras já foram substituidas e as que ainda não foram, assume-se que as letras na mensagem original (codificada) são minúsculas e que as letras que já foram descodificadas são maiúsculas). Este método mesmo assim não é muito eficiente. Imagine-se que se chegou a uma situação ÄOEET wTrEd". Obviamente, este caminho não irá conduzir à solução pois AOEET, que já resulta da substituição, não é uma palavra inglesa. Por isso, uma optimização passa por, sempre que se tiver uma palavra completa já instanciada, testar se esta existe, recorrendo a um dicionário. Se existir, continuar a descodificação, senão, voltar atrás e procurar outra substituição, modificando a última substituição feita. Por exemplo, se a última substituição foi 'x' por 'O' então, em vez de se considerar 'O' deve considerar-se a letra seguinte na lista, ou seja, 'I'.
Assume-se que os espaços estão no sítio certo.
Escrever em Prolog um programa para descodificar mensagens codificadas de acordo com o método anterior.
O programa deverá receber como argumentos uma string correspondendo à mensagem codificada. Está disponível um ficheiro dicionario.pl com um pequeno dicionário de palavras inglesas (através do predicado word/1).
O programa deverá ser chamado através do predicado decode/1 e mostrará no ecrã a mensagem descodificada, tal como nos exemplos seguintes:
?- decode('uaof of l uxfu uv uax cxmvcxg').
A mensagem e:
THIS IS A TEST TO THE DECODER
?- decode('rxpp cvqx tve alzx hlqlnxc uv cxmvcx uax hxfflnx').
...