From: Daniel Finnie <danfinnie@...>
Date: 2007-01-10T08:10:39+09:00
Subject: Re: [QUIZ] Word Blender (#108)

The regexes for me are fairly fast.  For my regex that weeds out words 
with repeated characters (I posted it before and it is fairly lengthy, 
so I won't post it again unless by request), a 10,000 word dictionary 
(the one in my /usr/share/dict/words) takes less than .5 seconds to pick 
the baseword and all related words.  Under .2 seconds if it doesn't weed 
out words with repeated characters.

One thing I can see to optimize in your method is all the sorting.  I 
haven't tested the performance yet, but sets might be the answer.

require 'set'

class String
	def letters
		split(//).to_set
	end
end

baseWordSet = baseWord.letters
dict.select {|x| x.letters.subset?(baseWordSet)}

It's more readable, IMHO, at least.

Dan

Bob Showalter 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
> 
>