We use cookies. You have options. Cookies help us keep the site running smoothly and inform some of our advertising, but if you’d like to make adjustments, you can visit our Cookie Notice page for more information.
We’d like to use cookies on your device. Cookies help us keep the site running smoothly and inform some of our advertising, but how we use them is entirely up to you. Accept our recommended settings or customise them to your wishes.
×

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.
In Our Company