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.)
re(2): 3-letters with a better list (spoiler) | Comment 10 of 12 |
(In reply to re: 3-letters with a better list (spoiler) by Charlie)

Absolutely, Charlie, if you want to see Mathematica code. I know this isn't particularly useful to super coders. For Mathematica users, I could just send the notebook to anyone interested (do we have email capability via this site?)

A description might be better; I created a graph from the Scrabble list using the one-letter change as the edge rule (built-in function). I took the largest connected component (which eliminated only a few isolated words). Then I created the adjacency matrix (about a million entries for the 3-letter words problem, but awfully sparse) and computed all the diameter paths watching for the entries that stay zero the longest in each row under powers of the matrix.

Mathematica is good at handling sets and has gotten better at sparse matrices (still doesn't hold a candle to Matlab), but at the 4-letter word problem, none of this is going to work since we move from almost 1000 words to over 5000 words. The number of edges in the largest component is over 32,000. However, I do have code that can compute the shortest path spanning tree rooted from a given word. It takes three minutes to do this, so if I let a PC run for about 11 days, I can tell you the longest 4-letter minimal meld paths.

Does anybody have any thoughts on upper and lower bounds? What do we expect to find for the 4-letter case? Any guesses??? I have found a path of 16 words in the 4-letter group, if that helps (assuming Scrabble words).

Edited on January 25, 2005, 9:26 pm
  Posted by owl on 2005-01-25 21:22:49

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 (15)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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