Please download wordlist.txt.

Like Sudoku and the crossword puzzle, the game of "doublets" was a popular fad. This fad was started by Lewis Carroll, who eventually published a small book on the subject (which should be available at https://archive.org/download/doubletsawordpu00dodggoog/doubletsawordpu00dodggoog.pdf). These puzzles are also known today as "word ladders" and "word chains".

The idea is to take one word and transform it, one letter at a time, to another word. Transformations are only valid iff the each word appears in a given word list.

For instance, using the wordlist.txt file, we can transform "chaos" into "order" with:

chaos --> chats --> coats --> costs --> posts --> poses --> roses --> rises --> riser --> rider --> eider --> elder --> older --> order

It is even comprehensive enough to support the shortest solution for the longest known word chain, "charge" into "comedo" (see the MathWorld article at http://blog.wolfram.com/2012/01/11/the-longest-word-ladder-puzzle-ever/):

charge --> change --> chance --> chancy --> chanty --> chants --> charts --> charms --> chasms --> chases --> ceases

       --> teases --> tenses --> tensed --> tented --> tested --> bested --> belted --> belied --> belies --> bevies

       --> levies --> levees --> levels --> revels --> ravels --> ravens --> mavens --> mavins --> matins --> mating

       --> hating --> haling --> holing --> homing --> hominy --> homily --> homely --> comely --> comedy --> comedo

Your assignment is to write a program "doublets" that creates such chains. Your program should assume that the attached "wordlist.txt" file is available in the current working directory; your program should take exactly two arguments, the initial word and the finish word:

$ ./doublets chaos order

chaos --> chats --> coats --> costs --> posts --> poses --> roses --> rises --> riser --> rider --> eider --> elder --> older --> order

$ ./doublets plant hovel

plant --> plans --> clans --> claps --> clops --> coops --> corps --> cores --> coves --> cover --> hover --> hovel

While some work has been done on trying to find better algorithms for this problem, brute force breadth-first search is the simplest and most general solution. I would recommend that your program "doublets" use breadth-first search; I strongly suggest you use loops and explicit state to keep track of your search.

As to programming languages, I would prefer that you use either Perl, Python, or C for this assignment. Please email me a tarfile of your work before midnight on May 5. Like the other assignments, I will test your program on 45.56.74.139.