Long version of the problem.
Back to the list of problems.
======================================================================== 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