COP4342 - 2017 Spring

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 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

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