Usamos cookies. Tienes opciones. Las cookies nos ayudan a mantener el sitio funcionando sin problemas e informar sobre nuestra publicidad, pero si deseas realizar ajustes, puedes visitar nuestro Aviso de cookies para más información.
Uso de cookies en su dispositivo. Las cookies nos ayudan a mantener esta página web funcionando correctamente y a personalizar nuestra publicidad, pero el uso que hacemos de las cookies depende de usted. Acepte nuestra configuración o personalícela.
×

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.
En nuestra compañía