We use cookies to personalise content, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners. For information on how to change your cookie settings, please see our Privacy policy. Otherwise, if you agree to our use of cookies, please continue to use our website.

Dictionary Walk

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.