Question

I need some more help with theory (ps5_ghost). I don't quite understand why the statement:
if newCombination in wordlist == True: return True
in 'is_word' doesn't return True. Doesn't it do the check right then? It seems when I assign 'newCombination in wordlist' to a variable (as in is_word2) it works fine. http://codepad.org/SmwSlHzt

Answer 1

Also, any clues as to how to check that the fragment being inputted by the user(s) is/is not forming a non-existent (non-existent in 'wordlist') word? Binary search for each combination being inputted?

Answer 2

About your first question: there should be parenthesis in the statement, i.e.: if (newCombination in wordlist) == True: //code. A better way to write this, at least a more pythonic way, is to write: if newCombination in wordlist: //code. This will remove the ambiguity that existed in your original statement.
About your second question: I think you can do something similar to problem set 3 (the MatchStringOneExactSub), plus binary search, but I don't know how to check for the input without the user actually hitting return.

Answer 3

you need to search through the word list to see if there is a word that begins with the fragment. you can just start at the beginning of the list or try a binary search.

http://docs.python.org/library/stdtypes.html#string-methods

'Strings are compared lexicographically...'
http://docs.python.org/reference/expressions.html#notin
http://codepad.org/mwjnS5eq

Answer 4

All good info. Those string comparison's are interesting. Gonna try and work them into the code.

Answer 5

got it working. Ended up searching word by word and comparing the input fragment with comparable indices in 'words in wordlist.' As I learn more about speed it will be interesting to understand exactly how expensive that kind of search is...

Answer 6

well - the binary search works by repeatedly cutting the size of the problem in half. if you have N things to search through, the number of times you half to cut it in half to get down to just two items is:
\[2^{y} = N\] or \[y = \ln N \div \ln 2\]
our list is about 80000 words so a binary search makes about 16 cuts before it is down to two items

Answer 7

As bmp says, don't compare a boolean to True or False. The boolean is already the condition. Also, if you have code like this

if a:
return True
return False

just do this

return a

If it's the opposite then just return not a.

But your question asked if "word in wordlist" was True then why is "word in wordlist == True" False. That's a very good question. I was writing a long response about why it doesn't make sense, but then I realized what is going on, and it seems unexpected in this situation, which makes it a little dangerous.

http://docs.python.org/reference/expressions.html#notin

The docs say comparisons can be chained arbitrarily, like

x < y <= z

which is equivalent to

x < y and y <= z.

in is a comparison operator, with the same precedence as ==, so your code

newCombination in wordlist == True

is equivalent to

newCombination in wordlist and wordlist == True

which is certainly always False, because wordlist is a sequence, not a boolean. Putting the parens around the in test forces Python to interpret the statement the way it makes sense.

So this was an interesting learning example. You learned not to compare booleans to True and False, and we all learned that Python has some interesting syntax that will keep us all on our toes.