Question

PS5: Ghost

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?

Answer 1

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'.

Answer 2

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

Answer 3

nice.

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?

Answer 4

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."
http://docs.python.org/reference/expressions.html#not-in

examples: http://pastebin.com/VGhkWvkz
my function: http://dpaste.com/693392/

Answer 5

valmont:
You can pull a word out of the wordlist and take a fragment via
wordlist[1240][:3] for example will take the first three characters in
the 1240th word.

bwCA:
Great idea! You only need to compare fragments when checking for equality then.