This is one of the OLD POTM problems

Long version of the problem.

Back to the list of problems.

Short Problem Description

========================================================================

FOR MAY, 1993 ... A NEW POTM CHALLENGE TO CONSIDER ... The CAT-DOG POTM!

========================================================================

There is an old word game* that asks you to take a word, say CAT,
change only one letter at a time, and eventually reach a second
word, like DOG.  With my rules, you can rearrange the letters each
time.  The major restriction is that all the steps along the way
have to be legitimate words.  Thus, one solution might be:

	START:				       CAT
	STEP 1:	change C to R to get           RAT
	STEP 2: change R to G and rearrange to TAG
	STEP 3: change A to O and rearrange to GOT
	STEP 4: change T to D and rearrange to DOG

There are, without too much thought, shorter solutions - with nothing
shorter than three steps possible in this case.

Repeated letters are changed one at a time, for example:
	BEES-BETS-BITE-NITE-VINE-HIVE	(5 moves)
	       ^   ^   ^    ^    ^
Another example might be:
	COLD-MOLD-MOLT-POTM-TOMB-MOTE-MODE-CODE-DOCK-DUCK	(9 moves)
	     ^       ^ ^       ^    ^   ^  ^       ^  ^
But wait - is "POTM" a legitimate word???  An interesting question!
So, when your program runs - I'll give it a list of legitimate words (the
 dictionary) from which to choose so there will be no confusion!  Of course,
 you'll have no idea what the dictionary contains when you write your entry!

* the game was invented by Lewis Carroll and words than can be transformed
	in this manner are called "Carrollinian Doublets