## double_o_seven 4 years ago ps6 #3. here's my code: http://dpaste.com/hold/557734/ here is the thought behind the code: http://dpaste.com/hold/557740/ my problem is that it is skipping some searches when the first few letters can become a word, but are not.... i have modified the code so that 'hand' will be {"a":1, "h":2, "n":1, "d":1} every time

1. bwCA

which function?

2. double_o_seven

choose_best_word

3. double_o_seven

I think that my problem is when a word is potentially a word, but not one and the loop goes through the remaining letters. The second letter isn't moving up one because there's potential and it doesn't get removed after all latter possibilities are checked.

4. double_o_seven

I've been trying to think up a fix but can't seem to come up with one

5. bwCA

you are correct. some searches are being missed. I tried out your choose_best_word function with 3 letter hands and just printed out the 'words' that are being tested: http://dpaste.com/558210/ you need to test all the 1, 2 and 3 letter permutations of a three letter hand -- permutations of 3 letters taken: 3 at a time, 2 at a time, 1 at a time this yields a maximum of 15 unique sequences for 3 letters there are probably a lot of ways to generate those sequences there was a cool one posted here earlier that was found on the net: the powerset function http://openstudy.com/groups/mit+6.0+intro+computer+science+%28ocw%29/updates/4dfb168b0b8b370c28be9ee7# http://dpaste.com/555751/ I cheated, i searched the python docs on my computer for permutations and found this (python 2.6+): http://docs.python.org/library/itertools.html#itertools.permutations remember you have to find all the permutations taken: 1 at a time, 2 at a time .... (lengthofhand) at a time

6. bwCA

spoiler: http://dpaste.com/558228/

7. bwCA

whoops, sorry - i think the powerset function mentioned above makes combinations, NOT permutations - they aren't the same. You need permutations fo problem 3.

8. bwCA

you can search for permutation algorithms - not many ppl have posted their solutions here. my spoiler above works.

9. double_o_seven

i might have fixed my problem without it.... let me check

10. bwCA

cool, we'd like to see it

11. double_o_seven

its kinda messy with a bunch of comments in it but I'll have it up in a minute or two

12. double_o_seven
13. double_o_seven

there's a bug in it. needs repair....

14. double_o_seven

sorry

15. bwCA

don't be sorry. if you uncomment just the print statement at line 181 you can see the sequences you are generating. you are close - for a 3 letter hand you get all the 2 letter sequences and 2/6 of the three letter sequences. I'm using this, http://dpaste.com/558246/ along with the print statement at line 181 to see the sequences you are generating.

16. double_o_seven

I don't quite understand what you mean by "remember you have to find all the permutations taken: 1 at a time, 2 at a time .... (lengthofhand) at a time ". Are you trying to say that I have to check all combinations?

17. double_o_seven

I know that My code is not going through EVERY possible combination. Thats why I check to see if the word can become a word or not. For example, if the hand is [q, u, e, e, n] if the combination of letters is qn then we automatically know that any combination of letters added to that will not be a word (qne, qnu, qnee, etc.) because qn cannot begin any possible word. That is why some searches are skipped. However, in this process, I seem to be skipping some of the necessary searches, which is what I wish to fix.

18. bwCA

well for this problem and a three letter hand, i think you need to check: 1 letter, 2 letter, and three letter permutations of the hand. e.g. ------------------ hand: abc ------------------ a b c ab ac ba bc ca cb abc acb bac bca cab cba

19. double_o_seven

That is going through every possible combination. I don't want to do that. If the first few letters can't produce a word, then any letters after that, no matter how arranged, will never produce word.

20. double_o_seven

If ba doesn't cannot become a word in the future then there is no need to check bca

21. double_o_seven

If ba cannot become*

22. bwCA

ok. i imagine that would be right if the dictionary had every single word in it. the one we are using is missing lots of words. but maybe you are right. if you are generating the sequences you want to, you should be able to look up the points and keep track of the highest scoring one. maybe put the code that generates the sequences into a seperate function then you can call it with the function that is validating and keeping track of the score. that might make it easier to see where things are going wrong.

23. double_o_seven

So your saying to just walk through every single possible combination of hand and check to see if it is a word or not?

24. bwCA

that is what i did. I don't remember anyone else posting their solution. if you can get yours to work that would be great - i have seen some pretty novel solutions here, and that is very cool. if you can generate every permutation of the hand in 1, 2, 3, 4 ... letter sequences then it is fairly easy to write code that will check each of those and keep track of the one with the highest score. and it will find the answer - every time. what you are trying to do is an optimization of that - you are trying to eliminate checking some of those sequences. that will complicate the program but it might be worthwhile to do. a hand with 10 letters starts having a lot of permutations - something like 6235300. a hand with 20 letters takes a while crunch. one of the things i have read over and over (from different sources) since i have started this class is to: 1) try and keep it simple 2) don't try to optimize till you get something that works 3) if you have something that works, if it is fast enough there is no need to optimize. 4) if it does turn out to be too slow,, then try optimizing. sometimes optimizing isn't necessarily changing your algorithm but maybe the data structures you are using. but just my \$.02 (or maybe \$0.59 - i guess i do get long winded) besides writing a program i think one purpose of this problem set is giving us some experience in being able to look at a problem and seeing how long it might take to compute an answer. getting a feel for the complexity of problems and solutions.

25. double_o_seven

The route I'm taking seems to be too complex for the moment so I have decided to take an alternate route. The thinking is to create a list with all possible combinations of the letters in then check to see if any of those combinations are actually words. If one is a word calculate compare etc.

26. double_o_seven

ok, so here's what a put together: http://dpaste.com/hold/558666/ however,there seems to be a bug in it since it's giving me over 15000 combinations and mathematically, there should be less than that in a 7 letter hand. I tried running it with smaller hands and it seemed to do pretty well up to 6. Smaller hand sizes seemed to be missing. I think the reason behind the slowness is that its cubic and growing extremely fast......

27. bwCA

13699 for 7 letters - http://dpaste.com/558675/

28. double_o_seven

fix'd: http://dpaste.com/hold/559437/ it takes a while though....

29. Arbiter

An easier way to do it is just walk through every word in word_list and see which ones can be made with your current hand. Just keep track of which one yielded the highest score.

30. bwCA

all_permutations - that's pretty cool. i couldn't figure out how to do that... i'm stealing and saving it... :) yep, try it with a 20 letter hand, I can;t remember but i think i just let it run overnight.

31. bwCA

thnx for chiming in arbiter, i was wondering if someone found a different way to solve this. what did you do for problem 4?? supposedly the sorted (rearranged) dictionary is supposed to make the process faster. is it faster with your method?

32. Arbiter

In problem 4 I pretty much just followed the pseudocode in the problem set description. I find all possible subsets of letters in the hand, check which ones are present in the rearrange_dict, and for those that are I compute their score. At the end I of course return the word that had the highest score. For hands of size 7, my problem 4 solution is significantly faster. However, for larger hands my solution for problem 3 will be faster. This is because the time that it takes to walk through word_list is linear in the size of word_list. My solution to problem 4 takes time that is exponential in the size of the hand. This is because there are 2^n possible subsets for a hand containing n letters. So, if we have a hand of size 7, the problem 4 solution will have to walk through 83677 words in the word_list, but the problem 4 solution will only have to walk through 128 subsets.

33. double_o_seven

bwCA: My all permutations code doesn't give ALL possible permutations. It skips the single letter ones because, if I remember correctly, the program doesn't accept single letter words like "a" or "i".

34. double_o_seven

Arbiter: by going through every word in word_list, do you mean something like currentscore = 0 wordToReturn = "." for word in word_list: if is_valid_word(word, hand, points_dict) and get_word_score(word, HAND_SIZE) > currentScore: wordToReturn = word currentScore = get_word_score(word, HAND_SIZE) return wordToReturn

35. Arbiter

That's exactly what I mean.

36. double_o_seven

never would have thought of that... thats nice!

37. bwCA

so up to about a 15-16 letter hand the problem 4 solution is faster than searching through the entire word_list method. yeay!!