All submissions for this problem are available.
A common word puzzle found in the XXX College magazine is the word metamorphism. By taking a starting word and successively altering a single letter to make a new word, one can build a sequence of words which changes the original word to a given end word. For instance, the word ``spice'' can be transformed in four steps to the word ``stock'' according to the following sequence: spice, slice, slick, stick, stock. Each successive word differs from the previous word in only a single character position while the word length remains the same.
Given a dictionary of words from which to make transformations, plus a list of starting and ending words, your team is to write a program to determine the number of steps in the shortest possible transformation.
The input will be a single file in two sections. The first section will be the dictionary of available words with one word per line, terminated by a line containing an # rather than a word. There can be up to 200 words in the dictionary; all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.
Following the dictionary are pairs of words, one pair per line, with the words in the pair separated by a single space. These pairs represent the starting and ending words in a transformation. The pairs are terminated by the end-of-file. All pairs are guaranteed to have a transformation using the dictionary given. The starting and ending words will appear in the dictionary.
The output should contain one line per word pair, and must include the starting word, the ending word, and the number of steps in the shortest possible transformation, separated by single spaces.
Sample Input dip lip mad map maple may pad pip pod pop sap sip slice slick spice stick stock # spice stock may pod Sample Output spice stock 4 may pod 3
|Time Limit:||15 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.