Re^3: Challenge: Mystery Word Puzzle

I fully concur with dragonchild that solving this problem requires either a dictionary containing all valid "words", or an ability to generate words. The latter would probably require having a machine that could answer the question "Is this a valid word?" for any given candidate. (This is sometimes called an "oracle".)

An oracle could simply check for the existence of a word in a dictionary. This might lead to a better (i.e. more efficient) solution than a brute force search, if the dictionary is huge and well indexed for fast lookups. What would be really cool, though, would be an oracle that encodes all kinds of heuristics about what constitutes a valid English word. :-)

I have written a script which determines the exact set of letters that a valid solution must contain, given a hint set. Actually, there could be more than one such sets. For example, given the hint set

	dealt - 2 in common
	solid - 2 in common
	rooky - 1 in common
	cedar - 1 in common
	edict - 0 in common
	flare - 3 in common
	shout - 1 in common

it produces the following list:

	afkls
	aflo
	aflsy

This means that any words which can be composed of exactly the set of letters 'a','f','k','l','s' (duplicates allowed) are solutions to the puzzle. And similarly for the other two letter sets.

Of course, that still leaves the final, hardest, step: generating actual real words from the letters. Again, this could be brute-forced, but where's the fun in that? ;-)

(Btw, my code also supports generation of puzzles — since you asked...)

Comment on Re^3: Challenge: Mystery Word Puzzle

Replies are listed 'Best First'.
Re^4: Challenge: Mystery Word Puzzle by BrowserUk (Patriarch) on Jan 13, 2005 at 23:33 UTC
I get 6 words that match those hints. Three 4-character and three 5-character. Anything like your results? Examine what is said, not who speaks. Silence betokens consent. Love the truth but pardon error.	[reply]
Re^4: Challenge: Mystery Word Puzzle by dragonchild (Archbishop) on Jan 14, 2005 at 01:17 UTC
Of course, that still leaves the final, hardest, step: generating actual real words from the letters. Again, this could be brute-forced, but where's the fun in that? ;-) Actually, anagramming is extremely easy, to the point of being golf'ed on at least one occasion. I think the point of programmatically solving the puzzle is to get to the valid letter sets as elegantly as possible and leave the anagramming as "an exercise for the reader". At least, if I was grading this, that's the solution that would get the A. :-) Being right, does not endow the right to be rude; politeness costs nothing. Being unknowing, is not the same as being stupid. Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence. Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.	[reply]
Re^5: Challenge: Mystery Word Puzzle by jdporter (Paladin) on Jan 17, 2005 at 18:54 UTC
Taking a set of letters and rearranging them is easy. Determining whether the resulting combination is valid word is not, except to look for it in a dictionary. Unless you know something I don't...	[reply]
Re^6: Challenge: Mystery Word Puzzle by dragonchild (Archbishop) on Jan 17, 2005 at 19:08 UTC
No, you're right. The point is that the number of dictionary lookups is orders of magnitude less than the other dictionary-based solutions that have been proposed. Instead of looking through all the N-letter words and seeing if they meet the rules, you generate the set of letters that meets the rules and figure out which orderings are valid words. So, you go from "All N-letter words" to "N! dictionary lookups". Being right, does not endow the right to be rude; politeness costs nothing. Being unknowing, is not the same as being stupid. Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence. Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.	[reply]