A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 4 years ago

PS5: Ghost In order to determine whether the word fragment is a fragment of a valid word, I've implemented the following steps. 1) search the wordlist to determine the closest alphabetical match (this returns an index number). 2) run a brute force search +/- 50 around the index found in step 1 to determine if the fragment matches any real words. for example, the index for 'quix' is 57415. I then run a brute force search around 57415 to determine if there are any matches. does anyone have a more elegant solution?

  • This Question is Closed
  1. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I initially thought that I might be able to simply check to see if the fragment matched a slice of the word returned by the nearest index. For example, if your fragment is 'quix', the nearest index is 57415, which is the word 'quixote'. you can then compare 'quix' with a 4 letter slice of 'quixote'. However, this breaks down in some cases. For example, 'quixoti'. Again, the index search returns 57415 as the nearest alphabetical match: 'quixote'. If I compared 'quixoti' with a 7 letter slice of 'quixote' I'd get False, which isn't what I want, because 'quixoti' is a fragment of the real word 'quixotic'.

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

    Since this is an ordered list I used adaptation of the binary search. Where the standard binary search would pick a guess halfway through the list and then compare the guess to the word you're searching (we'll call it s_word) for to see if s_word is equal to, greater than, less than the guess. The modified version would take in a word fragment (frag) and instead of comparing frag to the entire guess we can compare it just to the first len(frag) letters of the guess ( guess[:len(frag)] ). There are certainly different approaches. This is the first I considered and seemed sufficient, but in light of the ideas introduced in PS6 there may be easier and more efficient methods. Hope this helps

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

    nice. I assume there's a few intermediate steps where you set a variable equal to your guess so you can slice the variable. e.g. -determine your guess -set a variable equal to the guess: guessHolder = wordlist[mid] -slice the variable and compare to fragment: guessHolder[:len(fragment)] there's no way to pull a word out of the wordlist and slice it simultaneous is there?

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

    i used a binary search. I compared the fragment directly to the word in the list - not a slice. Python does fine for these comparisons: "Strings are compared lexicographically using the numeric equivalents (the result of the built-in function ord()) of their characters." http://docs.python.org/reference/expressions.html#not-in examples: http://pastebin.com/VGhkWvkz my function: http://dpaste.com/693392/

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

    valmont: You can pull a word out of the wordlist and take a fragment via wordlist[1240][:3] for example will take the first three characters in the 1240th word. bwCA: Great idea! You only need to compare fragments when checking for equality then.

  6. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.