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 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.
I've been trying to think up a fix but can't seem to come up with one
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
whoops, sorry - i think the powerset function mentioned above makes combinations, NOT permutations - they aren't the same. You need permutations fo problem 3.
you can search for permutation algorithms - not many ppl have posted their solutions here. my spoiler above works.
i might have fixed my problem without it.... let me check
cool, we'd like to see it
its kinda messy with a bunch of comments in it but I'll have it up in a minute or two
there's a bug in it. needs repair....
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.
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?
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.
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
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.
If ba doesn't cannot become a word in the future then there is no need to check bca
If ba cannot become*
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.
So your saying to just walk through every single possible combination of hand and check to see if it is a word or not?
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.
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.
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......
13699 for 7 letters - http://dpaste.com/558675/
fix'd: http://dpaste.com/hold/559437/ it takes a while though....
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.
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.
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?
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.
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".
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
That's exactly what I mean.
never would have thought of that... thats nice!
so up to about a 15-16 letter hand the problem 4 solution is faster than searching through the entire word_list method. yeay!!