When Mr Smith finished the distances evaluation,
during their honeymoon in the Himalayas, Mrs Smith, the quite upset wife, made
up a vengeance.
She bought a puzzles book and started playing games
(crosswords, cryptograms, etc.). One of the most exciting is a very simple
crypto-game: given a list of words encrypted with numbers (positive integers)
the objective is to find the correspondence table that associates a letter ('A'
to 'Z') with each number in such a way that all the words in the list, after
replacing numbers by the corresponding letters, become valid words according to
a given dictionary. To start the game, the first word, called keyword or
seed, is given, asserting the value (the corresponding letters) of the
first numbers.
However, the puzzle is not so easy to play as it
seems at a first sight...
To save their honeymoon, we are asking once more
your assistance.
Your task is to write a program that reads the
input data (list of encrypted words, seed, and dictionary) and plays the game
in the place of Mrs Smith, printing out the solution (the mapping that applies
numbers to letters and solves the problem). Notice that every puzzle proposed
has one, and just one, solution.
The input is organized as follows:
· The first line contains the number 1 <= l <= 26 of different letters to be decode;
· The second line contains the number 1 <= n <= 100 of encrypted words;
· The next n lines contain the encrypted words to be decoded, one word per line represented by numbers, used sequentially starting in 1 (one number replacing the same letter, different numbers correspond to different letters). Numbers are separated by single spaces and the sequence ends with a 0. The length of a word is never less than 2 or greater than 15;
· The next line is the keyword or seed, i.e., the first word of the list to be decoded, formed by upper case letters;
· The remaining lines contain the words (upper case letters) of the dictionary (1 <= m <= 100 lines, m words of length not greater than 15).
The output is a list of l (1 <= l <= 26) lines,
each line containing a single letter, describing the correspondence table that
solves the problem. Notice that the first line displays the letter associated
with number 1, the second line exhibits the letter associated with number 2,
and so on, until the last line that shows the value of number l (the
last number to be decoded).
Below we list the input data and the output for a
game with 7 encrypted words and 11 numbers encoding the 11 different letters to
be discovered. The solution is the map shown as Sample Output, and the list of
valid words (existing in the given dictionary) that can be written with the correspondence
table, discovered by the player, is:
ADORNOANAAMORHORTAPORTAPAPELELMO
1171 2 3 4 5 3 01 5 1 01 6 3 4 07 3 4 8 1 09 3 4 8 1 09 1 9 10 11 010 11 6 3 0ADORNOADORNOAMORANAARLINDOANTUNESHORTAPORTAPORTAOPORTALPAPELPARVOELMOESTEESSEARMADURAHELENAERGONOMICOEVAERVACARMOCOUVE
ADORNMHTPEL
MIUP'2004: Fourth Portuguese National
Programming Contest