Question

PS#6, problem 4: I am having a hard time understanding what it is asking me to do. Is it asking me to find all possible permutations in a hand and call it rearrange_dict, then passing each key through is_valid_word?

I was able to do problem 3 fine code is below just in case I approached it wrong (which may be the reason I don't understand what is asked in problem 4). Please help!
http://codepad.org/1RSxtXDm

Answer 1

alwahsh posted some code below. So did I.

Answer 2

rearrange dictionary keys are the sorted words and the values are the words
{sorted(word) : word}
'alpha' --> {'aahlp' : 'alpha'}

then you can say something like
find the highest scoring key in the rearranged dictionary that is a sorted(subset) of hand
or
for every sorted(subset) of hand which corresponding rearranged dictionary key has the highest value

Answer 3

not entirely sure what is going on or why sorting each word first makes it faster.... Will go struggle a little longer and read through the older posts. Thanks!

Answer 4

it's faster because the dictionary is accessed in constant time (I believe).

so here are the steps (and example with 'hunt'):


-sort the word: e.g. hntu
-create all the subsets of the sorted word: e.g. h, n, hn, t, th, tn, thn, u, uh, un, uhn,ut,uth,utn,uthn
-now you have a list with 15 elements (2**4 -1)
-iterate over the 15 elements to find the highest score. since you already have the rearranged_dict, you're just plugging in the subsets as the keys.

iterating through 15 elements is faster than iterating through the whole dictionary every time.

Answer 5

in the previous problem you should have had to test all the (subset) permutations of hand to find the best word. you have to look for 'aac' and 'aca' and 'caa'

with the rearranged dictionary the keys are sorted so a word that contains the letters a, a, and you only have to use (sorted) combinations of hand ('aac' only) and there are a lot less combinations than permutations.

hope that made sense

Answer 6

I didn't use permutations on the previous problem which is probably why I was having difficulty grasping how sorting it like the pset suggested was going to make it faster as I didn't see how I was going to avoid looping through the whole wordfile at least once. But between the both of you, I think it is crystal clear what is being asked. Thanks!

Answer 7

you shouldn't have to loop. you can use the in or not in operators
http://docs.python.org/reference/expressions.html#in

Answer 8

nope didn't need to loop after all the help I got from you guys - so thanks for that!. Only looped once through the list of combinations rather than the whole dictionary