A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 3 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
 3 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

This Question is Closed

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0choose_best_word

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0I 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.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0I've been trying to think up a fix but can't seem to come up with one

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0you 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

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0spoiler: http://dpaste.com/558228/

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0whoops, sorry  i think the powerset function mentioned above makes combinations, NOT permutations  they aren't the same. You need permutations fo problem 3.

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0you can search for permutation algorithms  not many ppl have posted their solutions here. my spoiler above works.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0i might have fixed my problem without it.... let me check

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0its kinda messy with a bunch of comments in it but I'll have it up in a minute or two

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0there's a bug in it. needs repair....

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0don'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.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0I 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?

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0I 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.

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0well 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

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0That 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.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0If ba doesn't cannot become a word in the future then there is no need to check bca

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0If ba cannot become*

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0ok. 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.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0So your saying to just walk through every single possible combination of hand and check to see if it is a word or not?

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0that 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.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0The 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.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0ok, 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......

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.013699 for 7 letters  http://dpaste.com/558675/

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0fix'd: http://dpaste.com/hold/559437/ it takes a while though....

Arbiter
 3 years ago
Best ResponseYou've already chosen the best response.0An 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.

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0all_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.

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0thnx 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?

Arbiter
 3 years ago
Best ResponseYou've already chosen the best response.0In 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.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0bwCA: 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".

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0Arbiter: 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

Arbiter
 3 years ago
Best ResponseYou've already chosen the best response.0That's exactly what I mean.

double_o_seven
 3 years ago
Best ResponseYou've already chosen the best response.0never would have thought of that... thats nice!

bwCA
 3 years ago
Best ResponseYou've already chosen the best response.0so up to about a 1516 letter hand the problem 4 solution is faster than searching through the entire word_list method. yeay!!
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.