From: Fedor Labounko <fedor.labounko@...>
Date: 2007-01-10T06:42:50+09:00
Subject: Re: [QUIZ] Word Blender (#108)

------=_Part_35092_20974607.1168378966974
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 1/9/07, Bob Showalter <showaltb@gmail.com> wrote:
>
> On 1/7/07, Fedor Labounko <fedor.labounko@gmail.com> wrote:
> > On 1/7/07, Daniel Finnie <danfinnie@optonline.net> wrote:
> >
> > > # Find words that use the same letters
> > > selectedWords = dict.scan(/^[#{baseWord}]{3,6}$/)
> >
> >
> > I was really impressed when I first saw this. It doesn't quite work if
> you
> > want to exclude reusing the same letter more than once
> > ("hhh".scan(/^[hello]{3,6}$/) => ["hhh"]) but it comes so close to
> something
> > I've only ever thought about implementing as a recursive method.
> > Unfortunately I don't know much about this but now I wonder if it's
> possible
> > to find all partial permutations of a word with a regexp.
> >
> >
>
> Here's a revision to Daniel's approach that seems to work well:
>
> # Open and read the dictionary.
> dict = IO.read("/usr/share/dict/words").scan(/^[a-z]{3,6}$/)
>
> # Pick a random word with 6 letters.
> baseWord = dict.grep(/^[a-z]{6}$/).rand_elem
>
> # Find words that use the same letters
> sortWord = baseWord.scan(/./).sort.to_s
> selectedWords = dict.select {|w|
> Regexp.new(w.scan(/./).sort.join('.*')).match(sortWord) }
>
> I started by just extracting only the 3-6 letter words.
>
> Then I sort the base word so the letters are in order. Let's say the
> baseWord is "parlor". Then sortWord would be "aloprr".
>
> Now for each word in the dictionary, sort it in letter order and
> create a regex. Suppose the word is "roar". The sorted version is
> "aorr" and the regex is "a.*o.*r.*r". If that regex matches the
> sortWord, we found a valid subword.
>
> This could be sped up by precompiling the regexes I would guess.
>
> Bob
>
>
Very interesting, you create a matching in the opposite direction, matching
against the picked word vs against the dictionary of words, very nice. I
like this more than Daniel's approach since it doesn't involve creating
Regexps which grow as n^2 compared to the length of our word. This ends up
going through all the words (length 3 to 6 anyhow) in the dictionary to find
the matches. Finding all permutations would go through the dictionary
roughly the number of subwords times, taking log of the length of the
dictionary number of steps each time. For all but the largest of words with
lots of subwords would the latter be slower, but the Regexp approach is very
nice and simple, and I can't decide what I like more.

It does bother me a bit though that I don't know how long each regexp takes
to run to get its match as I know that some Regexps do take quite a while to
match or exclude some words, just not sure if this one would be one of them.

------=_Part_35092_20974607.1168378966974--