Farmer John is playing a word game against his cows. It starts like this:
* Farmer John chooses a word, such as 'cat'
* The cows then choose their own word, perhaps 'dog'
Farmer John then must morph his word to the cows' word by performing a number of steps, each one of which changes one single letter at a time to make a new, valid word.
Your program should read a dictionary of valid words from file dict.txt. The file has no more than 25,000 words, each with length in the range 1..20. These 'words' contain only letters in the range 'a'..'z'. The same dictionary is used for all tests.
For this example, Farmer John could make the following sequence of four words:
'cat' -> 'cot' -> 'cog' -> 'dog'
to morph words from the first word 'cat' to the final word 'dog' in just three moves. The cows will never give Farmer John an impossible task. Farmer John must get from his word to the cows' word in as few moves as possible.
You will be given a starting word and an ending word. Determine and output a number which is the least number of legal letter changes required to morph the starting word to the ending word.