Fallos de Morse *

* Este es el tercer programa de los planteados en la fase final del Concurso ACM de Programación para Estudiantes 1997.

Traducción: Angel Alvarez (DIT, UPM)

A Samuel F. B. Morse se le conoce por el sistema de codificación que lleva su nombre. El código Morse aún se usa en la comunicación internacional por radio y su codificación de texto es muy simple: Cada carácter, con independencia de que sea minúscula o mayúscula, se traduce en una secuencia de "puntos" y "rayas", que son los elementos del código Morse (y que se representan por "." y "-", respectivamente). Cada elemento se transmite enviando una señal durante un determinado intervalo de tiempo. El punto es bastante corto, y la raya, cuando la codificación es perfecta, dura tres veces más que un punto. Entre dos elementos consecutivos hay un breve intervalo de silencio, y un silencio más largo entre caracteres consecutivos. Entre palabras consecutivas, el intervalo de silencio es aún más largo. Es esta dependencia de intervalos de tiempo, tanto para los elementos como para los silencios intermedios, lo que hace que los operadores de Morse emitan con frecuencia código con fallos, lo cuál se traduce en problemas de interpretación para los operadores que lo reciben, si bien es usual que esos errores se puedan corregir apelando al contexto.

En este problema se considera la recepción de palabras en código Morse, pero sin intervalos de silencio entre los caracteres. Sin ellos, puede ocurrir que distintas palabras se codifiquen igual. Por ejemplo, si se recibe el código "punto punto punto", éste puede interpretarse bien como "EEE", o "EI", o "IE" o "S", de acuerdo al esquema de codificación que se muestra más adelante en "Datos de entrada de ejemplo". Para decidir entre distintas interpretaciones, se supone que tenemos un contexto determinado, en el sentido de que toda palabra recibida ha de pertenecer a un conjunto dado de ellas.

En este problema el programa ha de leer primero una tabla que define la codificación de las letras y las cifras decimales en el código Morse, luego una lista de palabras esperadas (el contexto), y por fin una secuencia de palabras codificadas en código Morse, que han de descodificarse. Las palabras codificadas pueden tener errores y, para cada una de ellas, el programa ha de encontrar aquella palabra del contexto que le corresponda perfectamente, si es que hay alguna, o, en su defecto, aquélla que mejor se le aproxime, junto con una indicación de aproximación.

Si hay una sola palabra del contexto que corresponde exactamente al código Morse leído, se imprimirá ésta por sí misma en una línea. Si hay más de una palabra del contexto que corresponde exactamente al código Morse leído, se imprimirá aquélla que sea más corta en número de caracteres. Y si hay aún más de una que cumpla esta última restricción, se imprimirá cualquiera de ellas. Adicionalmente, en los casos en los que haya más de una palabra del contexto que corresponda exactamente con el código Morse leído, ésta se imprimirá seguida por un símbolo de exclamación ("!").

Se supone que los únicos errores de transmisión posibles son debidos a elementos que se añaden al (o truncan del) final del código Morse de una palabra. Por ello, cuando no se encuentre ninguna palabra en el contexto que corresponda exactamente al código Morse leído, se imprimirá la palabra del contexto que, bien corresponda al prefijo más largo del código, o bien tenga el mínimo número de elementos adicionales a continuación de los del código Morse leído. Si hay más de una palabra del contexto que cumpla estas reglas, se imprimirá cualquiera de ellas. Y en cualquier caso, todas las palabras que no correspondan de manera exacta al código Morse leído, irán seguidas de un carácter de interrogación ("?").

Se supone que los datos de entrada contendrán solamente casos de los descritos mediante las reglas anteriores.

Viene primero la tabla de códigos Morse como una secuencia de líneas en cada una de las cuales hay una letra mayúscula o una cifra, seguida de cero o más espacios en blanco, y una secuencia de como máximo seis puntos y rayas, que será el código Morse correspondiente. Puede haber espacios en blanco adicionales tanto al principio como al final de las líneas. La tabla de códigos Morse se acaba mediante una línea que solo tiene un asterisco (con cualquier número de espacios en blanco antes y después de él). Se supone que la tabla de códigos Morse incluye todos los caracteres que aparecen en las palabras dadas en el apartado de contexto.

El apartado de contexto viene a continuación, y está formado por una secuencia de líneas, cada una de las cuales tiene una palabra (de no más de diez caracteres) y cualquier número de espacios en blanco antes y después de la misma. Las palabras sólo contendrán letras mayúsculas y cifras, y no habrá más de 100 de ellas. El fin de este apartado de contexto se significa de nuevo mediante una línea con un asterisco, al igual que en el apartado anterior.

El resto de los datos de entrada lo constituyen palabras codificadas en Morse, cada una con un máximo de ochenta elementos, separadas entre sí por uno o más espacios en blanco, o caracteres de fin de línea. Otra vez, y al igual que en los dos apartados anteriores, el mismo tipo de línea con un único asterisco finaliza este apartado también.

Para cada palabra codificada en Morse, escribir aquella palabra del contexto que mejor corresponda según la reglas dadas, escribiendo también después de ella un signo de exclamación ("!") o de interrogación ("?"), si es el caso.

A .- WHAT

B -... HATH

C -.-. GOD

D -.. WROTH?

E . WHAT

F ..-. AN

G --. EARTHQUAKE

H .... IM!

I .. READY

J .--- TO

K -.- IM!

L .-..

M --

N -.

O ---

P .--.

Q --.-

R .-.

S ...

T -

U ..-

V ...-

W .--

X -..-

Y -.--

Z --..

0 ------

1 .-----

2 ..---

3 ---..

4 ....-

5 .....

6 -....

7 --...

8 ---..

9 ----.

*

AN

EARTHQUAKE

EAT

GOD

HATH

IM

READY

TO

WHAT

WROTH

*

.--.....-- .....--....

--.----.. .--.-.----..

.--.....-- .--.

..-.-.-....--.-..-.--.-.

..-- .-...--..-.--

---- ..--

*