http://qs321.pair.com?node_id=421692

Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
I set out to write code that could solve the following style of word puzzle: There are a few things that about the puzzle that could be interpreted a number of ways, so for the purposes of my code I was using the following assumptions:

I had an idea in my mind of how to code it, but haven't gotten very far. You can see the unfinished code below. I don't want anyone to think that I haven't at least put forth a little effort before asking.

#!/usr/bin/perl use strict; use warnings; use Mystery::Word; my $puzzle = Mystery::Word->new( size => 5 ); $puzzle->hint( bumps => 2, seams => 2, domes => 3, shake => 3, pokes => 3, dukes => 3 ); my @solutions = $puzzle->solve(); print "$_\n" for @solutions; __END__ ################################## package Mystery::Word; use strict; use warnings; use Carp; use constant WORD => 0; use constant SIZE => 1; use constant COMMON => 2; use constant COMBOS => 3; our $VERSION = '0.01'; sub new { my $class = shift; croak "Incorrect number of parameters for 'new'" if @_ % 2; my $self = bless {}, $class; $self->_init( @_ ); return $self; } sub _init { my ($self, %opt) = @_; $opt{size} = force_numeric( $opt{size} ); $opt{size} ||= 0; croak "'size' parameter must be set to a positive whole integer" i +f ! $opt{size}; $self->{target} = $opt{size}; } sub hint { my $self = shift; croak "Incorrect number of parameters for 'hint'" if @_ % 2; my %hint = @_; for my $word ( keys %hint ) { carp "$word contains non alpha characters" if $word =~ tr/a-z/ +/c; push @{ $self->{hint} }, [ lc $word, length $word, force_numeric( $hint{ $word } ), combinations(length $word, $hint{ $word }) ]; } } sub combinations { my ($n, $k) = @_; return factorial( $n ) / ( factorial( $k ) * factorial( $n - $k ) +); } sub factorial { my $n = shift; my $factorial = 1; $factorial *= $_ for 1 .. $n; return $factorial; } sub force_numeric { my $num = shift; return 0 if ! defined $num || ! length $num; no warnings 'numeric'; return abs( int( $num ) ); } sub solve { my $self = shift; @{ $self->{hint} } = map { $_->[0] } sort { $a->[1] <=> $b->[1] || $b->[2] <=> $a->[2] } map { [ $_, $_->[COMBOS], $_->[COMMON] ] } @{ $self->{hint} } +; # Here is where I got stuck } "This statement is false";
The challenge is in two parts: I already know the answer to the example in this post, so don't feel it necessary to reply with it.

Cheers - L~R

Update: Prior to any replies
Added two more of my assumptions after a CB discussion (dragonchild & bart). I also emphasized that the code was just my failed attempt but is being provided to show that I did put forth some effort (bart). Also corrected a copy/paste error (wolfger).

Update2: 2005-01-12 15:30:00 EST
After noticing potential copyright issues with the two example puzzles, the hint words have been replaced and no longer form a valid puzzle - sorry. If trammell's solution works, you can always generate test puzzle with it.

Replies are listed 'Best First'.
Re: Challenge: Mystery Word Puzzle
by trammell (Priest) on Jan 12, 2005 at 20:40 UTC
    My module:
    # $Id: mw.pm,v 1.4 2005/01/12 20:20:06 trammell Exp $ package Mystery::Word; use strict; use warnings; sub new { my $class = shift; my %defaults = ( size => 5, dictfile => '/usr/share/dict/words', ); my %args = (%defaults, @_); return bless \%args, $class; } sub hint { my ($self, %args) = @_; $self->{hint} = \%args; } sub solve { my $self = shift; my @keep; WORD: for (@{ $self->words }) { next WORD unless length == $self->{size}; foreach my $hint (keys %{ $self->{hint} }) { next WORD unless letters_in_common($_,$hint) == $self->{hint}{ $hint }; } push @keep, $_; } return @keep; } sub words { my ($self, $random) = @_; unless ($self->{words}) { open (my $fh, $self->{dictfile}) or die "Can't open dictionary '$self->{dictfile}': $!"; while (<$fh>) { chomp; push @{$self->{words}}, $_; } } if ($random) { my $i = rand( @{ $self->{words} } ); return $self->{words}[$i]; } return $self->{words}; } sub letters_in_common { (my $p = lc $_[0]) =~ y/a-z//cd; (my $q = lc $_[1]) =~ y/a-z//cd; my %p = map { $_, 1 } split //, $p; my %q = map { $_, 1 } split //, $q; my %common = (%p, %q); return (scalar keys %p) + (scalar keys %q) - (scalar keys %common) +; } sub create { my $self = $_[0]; (my $mysteryword = lc $_[1]) =~ y/a-z//cd; $self->{size} = length($mysteryword); # algorithm is: # 1. choose a random word $r # 2. determine how many letters ($n) it has in common with $mysterywor +d # 3. solve the puzzle with candidate $r => $n # 4. if the solution has 1 answer ($mysteryword), we're done, otherwis +e # try again my %hints; my $count; { $count++; warn "Iteration $count" if $self->{debug}; my $r = $self->words('random'); my $n = letters_in_common($r,$mysteryword); $self->hint( %hints, $r, $n); my @s = $self->solve(); redo unless grep { $_ eq $mysteryword } @s; $hints{ $r } = $n; redo unless @s == 1; } return %hints; } 1;
    Sample usage:
    #!/usr/bin/perl -l use strict; use warnings; use mw; use Data::Dumper; my $puzzle = Mystery::Word->new( debug => 1 ); my %hints = $puzzle->create('camel'); print Dumper(\%hints); # test solution my $p2 = Mystery::Word->new( size => 5 ); $p2->hint(%hints); print for $p2->solve();
      I've found a few problems with my solution (failure to handle anagrams is one), but it does the right thing in many cases. Here is some test data I've generated--solutions are all animals on some nearby books.

      $length = 6; $hints = { 'blackly' => '2', 'drowsy' => '1', 'Haddad' => '1', 'desperado' => '2', 'achieving' => '2', 'cowls' => '1', 'bet' => '1', 'comprehension' => '2', 'foe' => '1', 'permeate' => '1', 'Balkanizations' => '4' };
      $length = 7; $hints = { 'shortest' => '3', 'drilling' => '0', 'locked' => '2', 'messing' => '1', 'irritated' => '1', 'glory' => '1', 'modes' => '2', 'transcribed' => '3' };
      $length = 5; $hints = { 'blocker' => '2', 'entropy' => '2', 'monotonously' => '4', 'resonant' => '3', 'blindfold' => '1', 'decrypts' => '2', 'inquiry' => '1', 'considered' => '3' };
      And a trickier one...
      $length = 5; $hints = { 'repartee' => '1', 'Kankakee' => '2', 'dewdrop' => '0', 'brushfires' => '2', 'identifiably' => '4', 'liberalizes' => '4', 'swimming' => '3', 'Geoffrey' => '0', 'dotting' => '2' };

        On of these has two solutions, and the "tricky" one has three--assuming my code is correct.

        P:\test>421692-1 6 blackly:2 drowsy:1 haddad:1 desperado:2 achieving:2 + cowls:1 bet:1 comprehension:2 foe:1 permeate:1 balkanizations:4 1 fabius P:\test>421692-1 7 shortest:3 drilling:0 locked:2 messing:1 irritated: +1 glory:1 modes:2 transcribed:3 2 cutoffs offcuts P:\test>421692-1 5 blocker:2 entropy:2 monotonously:4 resonant:3 blind +fold:1 decrypts:2 inquiry:1 considered:3 1 mouse P:\test>421692-1 5 repartee:1 kankakee:2 dewdrop:0 brushfires:2 identi +fiably:4 liberalizes:4 swimming:3 geoffrey:0 dotting:2 3 nails slain snail

        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
Re: Challenge: Mystery Word Puzzle
by jdporter (Paladin) on Jan 12, 2005 at 19:57 UTC
    So, assuming you've written a sub letters_in_common for the purpose of generating a puzzle, then a solution would be:
    my @solutions; word: while (<DICT>) { chomp; for my $hint ( keys %hints ) { letters_in_common( $_, $hint ) == $hints{$hint} or next word; } push @solutions, $_; }
    The only hitch is making sure that the DICT contains all the possible legal words. E.g. your typical /usr/dict/words isn't likely to have "seams" in it, so you'd have to generate it.
      A slightly different (still brute-force) approach would be to march through all 5-letter strings until you find one that meets all criteria. See if there are any words in the dictionary that are anagrams (you can do this by canonicalizing all the words in the dictionary, as well as your guess).

      You can take some of the brutishness out by constructing your guess from the lowest-valued letters in the hints. There's probably a recursive algorithm lurking in there, but it's not clear to me.


      Caution: Contents may have been coded under pressure.
      The only hitch is making sure that the DICT contains all the possible legal words. E.g. your typical /usr/dict/words isn't likely to have "seams" in it, so you'd have to generate it.

      False problem, I think. See the original spec:

      The mystery word(s) should be able to be found in most any english dictionary

      None of my (paper) English dictionaries has an entry for "seams" :-)

      dave
        But a word doesn't have to have an entry in a dictionary in order to be found in a dictionary. It could be used in the definition of another word, for example. :-)
      jdporter,
      assuming you've written a sub letters_in_common

      I did that yesterday. This wasn't the approach I was going for, but it will work as was discussed in the CB. In fact - you could likely improve it by skipping dictionary words that weren't already the desired length.

      It doesn't address the second part of the challenge though.

      Cheers - L~R

Re: Challenge: Mystery Word Puzzle
by BrowserUk (Patriarch) on Jan 12, 2005 at 19:05 UTC
    I already know the answer to the example in this post, so don't feel it necessary to reply with it.

    I've got a list of 71 words which appear to qualify for the posted example?


    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
      BrowserUk,
      Is one of them 'house'? If not, it may have been because I made a minor error correction while you were working on the problem. The code had the correct relationships of letters in common (2 having 2, and 4 having 3), but the commentary had all 6 having only 2 (copy/paste error).

      Cheers - L~R

        In that case, I have 8 words that match.


        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
Re: Challenge: Mystery Word Puzzle
by dragonchild (Archbishop) on Jan 12, 2005 at 20:04 UTC
    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.

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

      The problem (as stated) is not intractable. It may be super-polynomial, but I don't think so. (Just intuition; could be wrong.)
Re: Challenge: Mystery Word Puzzle
by Solo (Deacon) on Jan 12, 2005 at 22:15 UTC
    I have the start of an idea that the puzzle can be looked at as linear system simlutaneous equations where the hint words are each an equation and the length of the word is another.

    For the 'house' example, we'd get the system:

       e k ops = 3
    a  e  m  s = 2
      de  mo s = 3
    a  ehk   s = 3
      de k   su= 3
     b    m psu= 2
    abdehkmopsu <= 5

    Where each of the variables (a,b,d,e,...,u) can be 0 or 1. IF there is/are solution(s) to this system, we're done. The word(s) must contain only those letters--a very simple anagram search.

    If there isn't an exact solution, the system can be reduced, reducing the rules set for the dictionary search.

    Update: Given the OP's additional rule:

    There will be no letters in the mystery word that are not covered by the hint words. Added 2005-01-12 16:10:00 EST

    I'm more convinced this approach is sound, but I won't get to coding anything until the weekend.

    --Solo

    --
    You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.
      Where each of the variables (a,b,d,e,...,u) can be 0 or 1.

      Therein lies the problem. What if the answer was "shoes" ... you now have 2 S'es ... that's why this cannot really be solved algebraically. Now, if the requirement was that you didn't take unique letters but instead followed the rules of Jotto, then simultaneous equations would work just fine.

      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.

        Per the OP:
        The number of letters in common is the exact number of unique letters in common. A 't' would only be counted once even if it existed twice in both the mystery word and the hint word

        Update:That is why the final equation is LESS THAN or equal to. The letters may appear more than once, reducing the total number of unique letters, but no more than the number of letters in the secret word can be used.

        --Solo

        --
        You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.
      I vaguely seem to remember from math lessons long long ago, that to guarantee a unique solution, you must have at least as many "mutually independent" equations (the right mathematical name escapes me, what I mean is equations which cannot be simply transformed into each other; eg: 'A = 2' and '2 * A = 4' are not mutually independent) as there are variables.

      So for a system with 11 variables, 5 hints plus the mystery word do not guarantee you a unique solution, which seems to tally with the results reported. Of course the requirement that the word must exist, may make the solution unique but that is beyond mathematics!

      CountZero

      "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

        I would argue that the goal behind the mathematics (and you have your rules down, if not the terminology) is to come up with a set of "words" that satisfy the hints. This narrows the searchspace down dramatically. Then, it's a matter of a simple anagram-matching program (which is a lot quicker than the programs that were discussed here) to find the correct word(s).

        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.

        So for a system with 11 variables, 5 hints plus the mystery word do not guarantee you a unique solution

        Agreed, but I'm not sure my analogy carries through that far. But I'm more confident the algorithm will work now that all letters in the word must be covered by the hints.

        Let me try to expand on my thinking. Given the equations:

        e + k + o + p + s = 3 a + e + m + s = 2 d + e + m + o + s = 3 a + e + h + k + s = 3 d + e + k + s + u = 3 b + m + p + s + u = 2 a + b + d + e + h + k + m + o + p + s + u <= 5
        As a worst case, we can use brute-force substitution to find all solution sets--i.e. try (a=1,b=0,...), try (a=1,b=1,d=0,...), ... tye would quickly apply Algorithm-Loops's NestedLoops and have the solution sets.

        Now we have 'categorical' solutions, but we don't know if any of these categories contain dictionary words.

        We could use the categories as the regexes to search the dictionary with, for example if the solution categories were 'adet' and 'adev' for a 5-letter word:

        /^[adet]{5}$/ || /^[adev]{5}$/

        Yuk, because if there are many regexes, I want my code to optimize how it writes the regexes, and I know I'm not smart enough to do that correctly. I'm barely smart enough to see that doesn't work by itself :P

        So, I would prepare the dictionary according to the same categories the solutions represent (i.e. hash it with the categories). Then I can look up whether there are solution words very quickly. For example:

        'adet' => [ 'date', 'dated', ... ], 'adev' => [ 'dave', 'evade', 'evaded', ... ],

        Any words in the hash category with the correct number of letters is a solution.

        If I persist this dictionary hash, I need only create it once (for each dictionary.)

        Update: The dictionary hashing idea is used by other monks (as perhaps the whole algorithm is, sorry I haven't looked closely at anyone else's code.)

        --Solo

        --
        You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.
Re: Challenge: Mystery Word Puzzle
by CountZero (Bishop) on Jan 12, 2005 at 20:12 UTC
    No code (yet), just a try at an algorithm for a solution.

    1. for each of the "hint" words:
      1. delete all duplicate letters.
      2. make a list of all possible combinations of letters allowed (eg: for "bumps/2" -> bu bm bp bs um up us mp ms ps)
    2. for each of these lists of allowed letters, make all possible combinations of one item from each list (again discarding any duplicate letters in the result) which is not longer than the length of the mystery word (smaller is OK, in which case you can later "duplicate" one of the letters to "fill the gap"). Check the result with the requirements of each "hint" word (reason: by adding letters from different hint words, you may break the requirement of one of them). Put words which pass this test on a "results" list.
    3. Go through the results list (expanding words with too few letters by duplicating, triplicating, ... existing letters to fill the gaps), sort the letters and check against a dictionary of English words (preferably some sort of "inverted" dictionary with words with their letters already sorted). Put words which pass this test on a "final results list".
    4. Finished!

    CountZero

    "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

Re: Challenge: Mystery Word Puzzle
by runrig (Abbot) on Jan 12, 2005 at 20:40 UTC
    I ignored assumption #2, but the results of the following code do not violate that assumption (for this example anyway). I get two possible groups of five letters, for the sake of time, I'm not scanning any dictionary for these combinations. Even though it's probably easier to brute force a dictionary, I went the "let's find valid letter groups" route :)
    use strict; use warnings; my $word = "aaaaa"; my @words; { push @words, $word if $word =~ tr/bumps// == 2 and $word =~ tr/seam// == 2 and $word =~ tr/domes// == 3 and $word =~ tr/shake// == 3 and $word =~ tr/pokes// == 3 and $word =~ tr/dukes// == 3; last if $word eq "zzzzz"; $word = inc_letter($word, 4); redo; } print "$_\n" for @words; sub inc_letter { my ($word, $i) = @_; if (substr($word, $i, 1) eq "z") { $word = inc_letter($word, $i-1, 1); substr($word, $i, 1) = substr($word, $i-1, 1); } else { substr($word, $i, 1)++; } $word; }
    Update: The puzzle changed; this solution has not. If a general solution is desired, then more work would need to be done here.
      I came up with code that's a lot more complicated than yours, but gives the same result.
      my %hints = ( bumps => 2, seams => 2, domes => 3, shake => 3, pokes => 3, dukes => 3, ); my %letters; foreach my $w (keys %hints) { my %w = make_hash( $w ); while (my ($k,$v) = each %w) { $letters{$k} ||= 0; $letters{$k} = $v if $letters{$k} < $v; } } my $iter = combo( 5, sort keys %letters ); while ( my @w = $iter->() ) { next unless is_legal( @w ); print @w, $/; } sub is_legal { my %w = make_hash( join '', @_ ); keys %hints; while (my ($h, $n) = each %hints) { my %h = make_hash( $h ); my $num = 0; while (my ($l,$c) = each %h) { next unless exists $w{$l}; $num += $c < $w{$l} ? $c : $w{$l}; } return 0 if $num != $n; } return 1; } sub make_hash { my %w; $w{$_}++ for split '', $_[0]; %w } sub combo { my $by = shift; return sub { () } if ! $by || $by =~ /\D/ || @_ < $by; my @list = @_; my @position = (0 .. $by - 2, $by - 2); my @stop = @list - $by .. $#list; my $end_pos = $#position; my $done = undef; return sub { return () if $done; my $cur = $end_pos; { if ( ++$position[ $cur ] > $stop[ $cur ] ) { $position[ --$cur ]++; redo if $position[ $cur ] > $stop[ $cur ]; my $new_pos = $position[ $cur ]; @position[ $cur .. $end_pos ] = $new_pos .. $new_pos + + $by; } } $done = 1 if $position[0] == $stop[0]; return @list[ @position ]; } }

      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: Challenge: Mystery Word Puzzle
by Not_a_Number (Prior) on Jan 12, 2005 at 20:23 UTC

    Have you got any other test cases (or links to relevant puzzle pages) for part 1 of the challenge? My current (brute force) solution finds 'house' in a couple of seconds...

    And regarding part 2, should we assume that the result of the code should only allow a single solution (or anagrams thereof)?

    dave
      dave,
      I can certainly search the Internet and find more but currently the only ones I have are copyrighted. As for the second part - you are correct.

      Cheers - L~R

      Update: 2005-01-12 15:30:00 EST
      Second example puzzle removed due to potential copyright issues. If trammell's solution works, you can always generate test puzzle with it.

Re: Challenge: Mystery Word Puzzle
by Roy Johnson (Monsignor) on Jan 12, 2005 at 21:15 UTC
    Not a module, and not OO, but a working solution:
    #!perl -l use strict; use warnings; sub sort_word { return join '', sort split //, $_[0]; } my %hints = ( bumps => 2, seams => 2, domes => 3, shake => 3, pokes => 3, dukes => 3 ); my $wordlen = 5; my %dict; open(DICT, '/usr/dict/words') or die "$!: /usr/dict/words\n"; chomp, push @{$dict{sort_word($_)}}, $_ while (<DICT>); close(DICT); my $guess = 'a' x $wordlen; sub letters_in_common { my ($str1, $str2) = @_; my %u = map {$_ => $_} split //, $str1; return scalar(grep defined, delete @u{split //, $str2}); } while (length($guess) == $wordlen) { # Check criteria my $match = 1; while (my ($k,$v) = each %hints) { if (letters_in_common($guess, $k) != $v) { $match = 0; keys %hints; # Reset each last; } } # If match, check dictionary and print results. Done! # Otherwise, increment guess if ($match) { if (exists($dict{$guess})) { print "Solution(s): @{$dict{$guess +}}"; last } else { print "No words match qualifying guess $guess"; } } ++$guess; # Short-circuit: only keep guesses that are sorted # So when the last char flips to an a, flip the trailing # string of last chars to a repetition of the rightmost # non-a $guess =~ s/([^a])(a+)$/$1 x (length($2)+1)/e; }
    Update! It works, but I feel pretty stupid for all the work of going through all possible guesses when I should just go through the dictionary keys! Gee, it sure is faster that way!

    Caution: Contents may have been coded under pressure.
Re: Challenge: Mystery Word Puzzle ("Jotto!")
by Vynce (Friar) on Jan 12, 2005 at 22:11 UTC

    This is very similar to a game I learned from my father as "Jotto". There are a number of differences between this and jotto, however, and they make this difficult for me to think about well, as they are fundamental. first of all, in jotto, "TASTE" and "TESTS" would score 4 -- 2 T's, 1 E, 1 S. Not knowing about doubled letters makes it much harder, i think.

    Also, it's a game, as i learned it. so, you think of a mystery word, and i think of a mystery word, and we take turns guessing clue words and answering with the score. (So if i think of GLYPH and you ask "FIGHT" I'll respond "2.") and we continue until one of us solves the others word. that person is the winner. (Geting control over the clues makes it a lot more interesting to me.)

    As a puzzle, it presents an interesting bad assumption in the first challenge -- what if a puzzle is not solvable? for instance, LIGHT : 4 BLACK : 0 well, it could still be Eight, Fight, Might, Night, Right, Sight, Tight... even Ghoti. so, should the script produce all possible answers, even if the data give does not narrow it down much?

    as for "creating a puzzle"... well, there are all kinds of problems with trying to create a good puzzle algorithmically, but certainly you could keep adding random guesses until you had added enough that the word was obviously unique -- but then I would want to go back and weed out the guesses (or "clues") that didn't add any data.

    anyway, the upshot of all this is that the way i would approach the problem would be to set it up like the game -- i'd create a responder (which would just mindlessly compare clue & word and report the commonality -- i can't think of an efficient way to do this, but i can certainly think of ways to do it). then I'd create a guesser that, given a history of other guesses, would pick a new guess.

    (Apparently, Dad at some point wrote a program that brute-forced its way into playing the game, but I never saw the code. What I know of it was that it basically just picked a random word from the dictionary that could possibly be correct (meaning none of the clues conflicted with it). I don't know how efficiently it did this, though.)

    anyway, you could try to have a little logic in there that "thought" about the clues, but that's really hard. You can make a career out of writing software to apply first-order logic. (one letter of BLACK but none of LABEL so C xor K; one of SITES and one of KITES so not K, so C. ... this is a lot easier for me to do than to code.)

    on the other hand, for smplicity but brute force, you could jsut step alphabetically through the dictionary, toss out words that aren't the right length, and compare words that are against your list of clues. if it ever fails, throw it out. if it doesn't, add it to your list of possible solutions.

    you probably want something between the two extremes. possibly you can immediately skip words containing letters you have ruled out, where by letters you have ruled out i mean letters contained in clues for which the answer was "0" -- but if your puzle doesn't have any such clues, you have problems. Also, you could make a couple passes at simple logical comparisons and try to distill some simple tests you coudl compare words to, without trying to solve the whole thing by logic. say, maybe BLACK = 1 and LOCAL = 1 so either A, C, L, or O-and-B or O-and-K. but makign this be worthwhile sees to me like it will be hard.

    Just my thoughts,
    Vynce
    .

      I was thinking it was like the game Mastermind. But instead of 5 colors, we're playing with 26 letters. And we're not playing it ourselves. Instead, we see a partial history of someone else's game, and we're trying to figure out what the original sequence is.


      -- All code is 100% tested and functional unless otherwise noted.
Re: Challenge: Mystery Word Puzzle
by jdporter (Paladin) on Jan 12, 2005 at 19:38 UTC
    I want to make sure I'm very clear on one thing: The "letters in common" metric has absolutely nothing to do with position, right?
      jdporter,
      Not for the purposes of my challenge. I haven't seen any official rule book on mystery word puzzles. Given the answer to the example puzzle - you are safe in assuming 'letters in common' has no relationship to position.

      Cheers - L~R

Re: Challenge: Mystery Word Puzzle
by BrowserUk (Patriarch) on Jan 12, 2005 at 21:18 UTC

    There are some fairly dubious coding practices in there, and I don't yet guarentee it solves every puzzle, but it does solve the (now removed) example.

    I'll try test it a bit more and clean it up a bit.

    #! perl -slw use strict; sub uniq { my %x; @x{@_} = (); keys %x } my $len = shift @ARGV; my $re = '^'; my $c = 0; for my $i ( 0 .. $#ARGV ) { my( $word, $common ) = split ':', $ARGV[ $i ]; die "Bad arg '$ARGV[ $i ]'" unless $common >= 2 and $common <= length( $word ); my $uniq = join'', uniq( split '', $word ); $re .= "(?=(?:.*?[^$uniq]){${ \ ($len - $common) }})"; $c++; $re .= "(?=.*?([$word]).*?(?!\\$c)"; $re .= "([$word]).*?(?!" . join( '|', map{ "\\${ \ $c++ }" } 0 .. $common-2 ) . ')' and --$c if $common > 2; $re .= "[$word])"; } $re .= '.' x $len . '$'; $re = qr[$re]; my %w; open W, '<', 'words' or die $!; m[^[a-z]+$] and push @{ $w{ length() } }, $_ while chomp( $_ = <W>||'' + ); close W; my @m = grep{ $_ =~ $re } @{ $w{ $len } }; print ~~@m; print for @m; __END__ P:\test>421692-1 5 bumps:2 seams:2 domes:3 shake:3 pokes:3 dukes:3 1 house

    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.

      Updated: to comply with all the revised rules.

      Here's cleaner version of the above that also deals with (all?) of the edge cases.

      #! perl -slw use strict; sub uniq { my %x; @x{@_} = (); keys %x } my $len = shift @ARGV; my $re ; my $re_ex; my $cap = 1; my $cap_ex = 1; my $hints_uniq; for my $i ( 0 .. $#ARGV ) { my( $word, $common ) = split ':', $ARGV[ $i ]; my $uniq = join'', uniq( split '', $word ); $hints_uniq .= $uniq; if( $common <= length $word ) { $re_ex .= "\n\t(?= (?: .*? (?: [^$uniq] | (?: ([$uniq])(?= + .* \\" . $cap_ex++ . ") ) ) ){" . ( $len - $common ) . "} )" } if( $common >= 2 ) { $re .= "\n\t(?=.*?([$word]).*?(?!\\$cap)"; if( $common > 2 ) { my $base = $cap; for my $n ( 1 .. $common-2 ) { $re .= "([$word]).*?(?!" . join('|', map{ '\\' . $_ } $base .. ++$cap ) . ")"; } } $cap++; $re .= "[$word])"; } elsif( $common == 1 ) { $re .= "\n\t(?=.*[$word].*)" } } $hints_uniq = join '', uniq split'', $hints_uniq; my $re_covered = qr[^[$hints_uniq]+$]; $re = qr[^$re]x; $re_ex = qr[$re_ex]x; my %w; open W, '<', 'words' or die $!; m[^[a-z]+$] and push @{ $w{ length() } }, $_ while chomp( $_ = <W>||'' ); close W; my @m = grep{ $_ =~ $re_covered and $_ =~ $re_ex and $_ =~ $re } @{ $ +w{ $len } }; print ~~@m; print for @m;

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.
Re: Challenge: Mystery Word Puzzle
by TedPride (Priest) on Jan 12, 2005 at 20:56 UTC
    The following returns all the sets of 5 uniqe letters that agree with the rules (two and only two letters are common between the set of letters and each of the words). Note that I've also added a rule, that every set of letters must contain ONLY letters included in the input words.
    use strict; use warnings; my (%l, @a, $bad, $w); my @w = ('bumps','seams','domes','shake','pokes','dukes'); for (@w) { $l{$_} = () for (split //, $_); } permute(5, '', \@a, sort keys %l); for $w (@a) { $bad = 0; for (@w) { if (both($_, $w) != 2) { $bad = 1; last; } } if (!$bad) { print "$w\n"; } } sub permute { my ($d, $w, $a, @l) = @_; if (!--$d) { push @$a, $w.$_ for @l; } else { permute($d, $w.$l[$_], $a, @l[($_+1)..$#l]) for (0..($#l-$d +)); } } sub both { my ($w1, $w2) = @_; my %l; my $c = 0; $l{$_} = () for split //, $w1; for (split //, $w2) { $l{$_} = 1 if exists $l{$_}; } for (values %l) { $c++ if $_; } return $c; }
    Sloppy code in places probably, but it does the job. Returned values are:
    abdep abeou adkmp akmou
    Problem is, I can't see a way to arrange any of these into an english word, unless I'm missing a possibility on the first set. Obviously, some of the letters have to be used twice, or letters not in any of the original words have to be allowed. Back to the drawing board :\

    EDIT: Ohhh, you changed the puzzle. Time to see if I can get this one to work...

    Nope, doesn't work with the new puzzle either. I'd delete my post at this point, but I should leave it here in case someone can gain insight from my mistakes.

      TedPride,
      EDIT: Ohhh, you changed the puzzle. Time to see if I can get this one to work...

      The original puzzle was copyrighted. Even still, there was a copy/paste error. If trammell's solution works, you can always generate test puzzle with it.

      Cheers - L~R

Jotto ?! Re: Challenge: Mystery Word Puzzle
by spurperl (Priest) on Jan 13, 2005 at 07:36 UTC
Re: Challenge: Mystery Word Puzzle
by chb (Deacon) on Jan 13, 2005 at 07:06 UTC
    Ok, not really PC here, but this sounds to me like a problem crying for a prolog solution (or schelog, if you prefer nice scheme syntax over strange prolog syntax).
Re: Challenge: Mystery Word Puzzle
by kelan (Deacon) on Jan 13, 2005 at 15:47 UTC

    Here are my solutions to the two parts. After developing the first part's solution on my own and then reading through the comments, I found that it is pretty much what jdporter suggested, probably with more complexity than is needed. Oh well.

    My solution to the second part (generate hints for a word) is not as elegant as trammell's solution, in that it doesn't check to make sure the hints lead to only one solution. It just goes through the dictionary, limiting itself to words whose length are within 3 of the solution (to limit the number of hints), and, with some probability (again to limit the number), prints out the word with the number of common letters. I just wanted something simple that I could use to produce test cases. Note, however, that if it doesn't spit out the right kind of hints, you can get false solutions. I got around this by having it list more hints so there was a better chance of getting good hints:)

    Out of ~210,000 words, you get around 50 hints, which is usually enough to give a unique solution.

    Update: Please also note that neither of these solutions take into account the last assumption, that all letters will be accounted for by hints. This would undoubtably make the hint generator more accurate.

Re: Challenge: Mystery Word Puzzle
by BrowserUk (Patriarch) on Jan 13, 2005 at 01:06 UTC

    Here's a nice one.

    A word with eleven letters containing 5 letters from "limbic" and 6 from "region" :)


    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
Re: Challenge: Mystery Word Puzzle
by tall_man (Parson) on Jan 14, 2005 at 01:27 UTC
    It seems to me that great efficiencies could be had by applying logical reductions to the rules first. For example, in your given problem, take all the letters for "0 letters" out first:
    • The mystery word is 5 letters long
    • The mystery word has 2 letters in common with 'hls'
    • The mystery word has 3 letters in common with 'olr'

    In this case, one rule has reduced to a perfect match. The mystery word must contain 'o','l', and 'r'. I then could subtract those letters from the remaining rules, reducing the counts accordingly. Now the word has one letter in common with 'hs'.

    Now I can search for /^[rolh]{5}$/ and /^[rols]{5}$/, finding 'rolls' and 'solos'.

    (Update: Of course 'solos' must be eliminated, leaving 'rolls' as the only solution.)

    I believe this method could be generalized to a solution-space searching recursive algorithm. I will try to write it up when I have time.