In order to determine whether the word fragment is a fragment of a valid word, I've implemented the following steps.
1) search the wordlist to determine the closest alphabetical match (this returns an index number).
2) run a brute force search +/- 50 around the index found in step 1 to determine if the fragment matches any real words.
for example, the index for 'quix' is 57415. I then run a brute force search around 57415 to determine if there are any matches.
does anyone have a more elegant solution?
MIT 6.00 Intro Computer Science (OCW)
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
I initially thought that I might be able to simply check to see if the fragment matched a slice of the word returned by the nearest index. For example, if your fragment is 'quix', the nearest index is 57415, which is the word 'quixote'. you can then compare 'quix' with a 4 letter slice of 'quixote'.
However, this breaks down in some cases. For example, 'quixoti'. Again, the index search returns 57415 as the nearest alphabetical match: 'quixote'. If I compared 'quixoti' with a 7 letter slice of 'quixote' I'd get False, which isn't what I want, because 'quixoti' is a fragment of the real word 'quixotic'.
Since this is an ordered list I used adaptation of the binary search. Where the standard binary search would pick a guess halfway through the list and then compare the guess to the word you're searching (we'll call it s_word) for to see if s_word is equal to, greater than, less than the guess. The modified version would take in a word fragment (frag) and instead of comparing frag to the entire guess we can compare it just to the first len(frag) letters of the guess ( guess[:len(frag)] ).
There are certainly different approaches. This is the first I considered and seemed sufficient, but in light of the ideas introduced in PS6 there may be easier and more efficient methods.
Hope this helps
I assume there's a few intermediate steps where you set a variable equal to your guess so you can slice the variable. e.g.
-determine your guess
-set a variable equal to the guess: guessHolder = wordlist[mid]
-slice the variable and compare to fragment: guessHolder[:len(fragment)]
there's no way to pull a word out of the wordlist and slice it simultaneous is there?
Not the answer you are looking for? Search for more explanations.
i used a binary search. I compared the fragment directly to the word in the list - not a slice. Python does fine for these comparisons:
"Strings are compared lexicographically using the numeric equivalents (the result of the built-in function ord()) of their characters."
my function: http://dpaste.com/693392/
You can pull a word out of the wordlist and take a fragment via
wordlist[:3] for example will take the first three characters in
the 1240th word.
Great idea! You only need to compare fragments when checking for equality then.