All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General > Word Problems
Word Meld 7 (Posted on 2005-01-22) Difficulty: 4 of 5
Previous "Word Meld" puzzles consisted of a pair of words for which to find the shortest sequence of common words, each differing from the previous by only one letter, which began with one word of the pair and ended with the other.

For this problem, find the pair of words that has a shortest solution of maximum possible length.

See The Solution Submitted by David Shin    
Rating: 2.6667 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts thoughts | Comment 1 of 11

This seems a problem that's best approached through a computer solution.

It probably goes without saying this is really several problems: one for 4-letter words, one for 5-letter words, etc.  Then the best solutions for all the cases would be compared to get the best (maximum length) of all of these.

A given word can be connected, through change of one letter, to various other words, giving rise to a tree structure.  However, the branches of the tree may loop back to some prior point in a given sequence, leading to a closed loop.

It would seem a good start to create an index for each word, to all the words to which it can be connected.  Then the branches can be traversed more easily (quickly).

But then what does one look for?  At first thought, you'd look for words that could be a dead end on a meld, or by its traditional name, ladder. (For example, the word BOOK is not a dead end, as it can connect COOK and BOOT.) Then, for each such dead end found, traverse the branches leading from it until another dead end is reached or a loop back to a prior point in the word ladder.  However, the longest required chain might not end in a dead end, but rather in a loop at either end (topologically looking like a dog bone--a linear string in the middle, with a loop at either end).  Of course it would have loops and branches leading out from the middle also, to be investigated to see if they are longer.  So we can't just look for strict dead ends as starting places.

And once we find such a sequence, it has to be verified as the shortest sequence (meld, ladder, chain, whatever you want to call it) connecting the two end words.

An example of a loop, for example, would be: book, bock, back, bank, bonk, conk, cook ... and then back to book.  But if, say, BANK's connection to BAND (not in this loop) started a string that led to another such loop, it could be part of the answer, for either the word cook or book, as either would take three steps to get to BANK, and from there continue on to the other end.

 

Edited on January 22, 2005, 4:06 pm
  Posted by Charlie on 2005-01-22 15:53:45

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information