Bill Atkins
12/8/2005 9:02:00 AM
I went ahead and implemented my own suggestions, and just to give you
an idea of how fast you can get this, my version can find all valid
anagrams of a five-letter word ("truck") given a 274,000 word
dictionary in 0.231 seconds....real-time.
:D
batkins57@gmail.com wrote:
> One thing you could try is inverting your algorithm. My dict/words
> file has 234,000+ entries in it. Since you're looping through the dict
> file and then calling rodolfo on each iteration, you have to pay the
> cost of calling rodolfo 234,000 times, even though in general only a
> couple of entries in the words file are relevant.
>
> So what you could do is first find all the possible permuations of the
> letters in your given word. Then loop through the word file once. If
> a word matches one of the permutations in your list, remove it from the
> list of words to be checked and push it onto a separate list. This
> should be significantly faster, since you calculate the combinations up
> front, and then do one scan through the list.
>
> You could also call out to a program like aspell or ispell to check
> your words for you. Those programs will do something at least as fast
> as a binary search, which will take much, much less time than scanning
> through the whole thing - even in the worst case, a 234,000 entry file
> will be checked in 18 string comparisons, instead of 234,000.
>
> hth,
> Bill
>
> travis laduke wrote:
> > it seems to me, with computers these days, this should finish
> > instantly, not take like 20 seconds.
> > also, please help me make my ruby more ruby-like. i'm new to ruby,
> > not that i know any other language.
> >
> >
> > ##these are here from when i was first testing
> > secret_word = "spine"
> > rack = "spine"
> >
> > secret_word = secret_word.split(//)
> > rack = rack.split(//)
> > test_rack = rack.to_s
> >
> > ##are there enough of the right letters in the rack to spell the word
> > from the dictionary?
> > ##i think i'm going to use funny spanish names for my methods instead
> > of descriptive names.
> > def rodolfo(secret_word, rack)
> > secret_word.each do |x|
> > rack = rack.to_s
> > if rack.include? x
> > rack = rack.sub(x, '')
> > ##p rack, x
> > else
> > ##puts x, ' rack don\'t work'
> > break
> > end
> > end
> > end
> >
> >
> > puts "reading dictionary"
> > dict = IO.readlines('/usr/share/dict/words')
> >
> > while rack
> > puts "enter rack"
> > rack = gets.chomp.split(//)
> >
> > dict.each do |secret_word|
> >
> > if rodolfo(secret_word.chomp.split(//), rack)
> > puts secret_word.to_s
> > end
> > end
> > end