Word Metamorphism

Problem code: AXR1P4

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.

Input

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.

Output

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

Author: admin
Date Added: 13-08-2009
Time Limit: 15 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

@admin: This problem has a

goharshady @ 15 Oct 2010 07:08 PM

@admin:

This problem has a wrong test case.

The words in the test are not in the list.

Please check.

HOW MANY TEST CASES?

coded_gsn @ 12 Feb 2012 12:43 AM
HOW MANY TEST CASES?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions