Definitions
Call two words “adjacent” if you can change one word into the other by adding, deleting, or changing a single letter.
A “word list” is an ordered list of unique words where successive words are adjacent.
Program
Using the computer language of your choice, write a program which takes two words as inputs and walks through the dictionary and creates a list of words between them.
Use the official Scrabble word list as your dictionary of valid words.
If you know Perl, a Perl solution is preferred.
Examples
Some examples:
- hate → love: hate, have, hove, love
- dogs → wolves: dogs, does, doles, soles, solves, wolves
- man → woman: man, ran, roan, roman, woman
- flour → flower: flour, lour, dour, doer, dower, lower, flower
Questions
- What is the shortest list between “crawl” and “run”?
- What is the shortest list between “mouse” and “elephant”?
- Does your program necessarily return the shortest list?
- What assumptions did you make in your program?
- How did you test your program?
- What is the Big-O complexity of your program?
More Questions
- Suppose each letter had a point value (for example, as in Scrabble). Discuss (but don’t code) how your algorithm would change if you wanted to find the the list with the lowest possible point total.
- Sometimes the shortest list isn’t unique. Discuss (but don’t code) how your algorithm would change if you needed to return all of the shortest list between two words.
- Discuss (don’t code) how you might change your program if your concern was minimizing memory usage.
- Discuss (don’t code) how you might change your program if your concern was minimizing CPU time.
- Discuss (don’t code) how you might change your program if your concern was minimizing programmer time.
- Discuss (but don’t code) how your algorithm would change if you wanted to find the longest list between two words.
