Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re: Challenge: Mystery Word Puzzle

by dragonchild (Archbishop)
on Jan 12, 2005 at 20:04 UTC ( [id://421740]=note: print w/replies, xml ) Need Help??


in reply to Challenge: Mystery Word Puzzle

The problem is intractable unless you can satisfy at least one of the following conditions:
  1. You have a list of words that is guaranteed to contain the mystery word
  2. The mystery word cannot have duplicate letters (violates assumption #2 above)
  3. The number of letters in common is the exact number of letters, duplicates included. (violates assumption #3 above)

Either you have a list and you brute force it like jdporter's solution or you have to be able to generate words. To generate those words, you have to know how many of each letter there are and you cannot know that without either conditions #2 or #3 satisfied.

Once you give me one of those, then I can solve your puzzle. :-)

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.

Replies are listed 'Best First'.
Re^2: Challenge: Mystery Word Puzzle
by Limbic~Region (Chancellor) on Jan 12, 2005 at 20:13 UTC
    dragonchild,

    You have a list of words that is guaranteed to contain the mystery word
    As I indicated, the mystery word(s) should be able to be found in most any english dictionary

    I am not sure I agree with you on 2 and 3 with regards to the problem being intractable otherwise. If you strip each hint word to the unique set of letters first, you can still end up with a candidate list of letters. You then only need to allow the possibility that each letter in your candidate list be allowed to repeat one or more times when matching against the dictionary. The number of letters allowed to repeat and up to how many times is dictated by how many less candidate letters you have then your mystery word's length.

    I fully admit that may be flawed reasoning. I also freely admit that my assumptions were not "rules" written in stone - remember my code was unfinished. If you would like to redefine the assumptions and move forward, be my guest. It is a fun problem regardless.

    Cheers - L~R

      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...)

        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.
        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.

Re^2: Challenge: Mystery Word Puzzle
by jdporter (Paladin) on Jan 12, 2005 at 20:11 UTC
    The problem (as stated) is not intractable. It may be super-polynomial, but I don't think so. (Just intuition; could be wrong.)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://421740]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others musing on the Monastery: (8)
As of 2024-03-28 10:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found