Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

double_o_seven

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

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    which function?

    • 2 years ago
  2. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    choose_best_word

    • 2 years ago
  3. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  4. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  5. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  6. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  7. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  8. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  9. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  10. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    cool, we'd like to see it

    • 2 years ago
  11. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  12. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    http://dpaste.com/hold/558231/

    • 2 years ago
  13. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  14. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    sorry

    • 2 years ago
  15. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  16. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

    • 2 years ago
  17. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  18. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  19. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  20. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  21. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    If ba cannot become*

    • 2 years ago
  22. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  23. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  24. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  25. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  26. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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......

    • 2 years ago
  27. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  28. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  29. Arbiter
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  30. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  31. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

    • 2 years ago
  32. Arbiter
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  33. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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".

    • 2 years ago
  34. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  35. Arbiter
    Best Response
    You've already chosen the best response.
    Medals 0

    That's exactly what I mean.

    • 2 years ago
  36. double_o_seven
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  37. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
    • Attachments:

See more questions >>>

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.