Daniel Finnie
1/9/2007 11:11:00 PM
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
>
>