Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Unscrambling word Program help

  1. Dec 20, 2005 #1
    Hello Guys.

    I was wondering how would you go around making an application that unjumbles words. It uses a wordlist and extracts the unjumbled word like.

    jumbled: ial

    I hope somone got an idea. Thanx
  2. jcsd
  3. Dec 21, 2005 #2

    jim mcnamara

    User Avatar

    Staff: Mentor

    Here is a start in C:

    word list:
    Code (Text):

    char wordlist[4][8]={"all", "some", "small", "sine"};
    char alpha[4][10]={0x0};

    wordlist has four elements: each word we know how to unscramble
    alpha is an alphabetically arranged set of characters from wordlist:
    wordlist alpha
    all all
    some emos
    small allms
    sine eins

    The algorithm is:
    Code (Text):

    input a scrambled word
    lowercase all the letters in the word
    alphabetize the letters in the scrambled (just like we did for "alpha" above)
    search thru each element of alpha to find an exact match
    print the corresponding element in wordlist -
      i.e., if you find an exact match with "emos" print "some"
      else printf "not found in list"
  4. Dec 21, 2005 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    mcnamara's onto a good start, but don't try to store all those words in memory!

    First, sort the letters in the target word. Read the words from the word list (a text file) one at a time, sort the characters, and compare with the sorted target word.

    - Warren
  5. Dec 21, 2005 #4


    User Avatar

    Staff: Mentor

    An even faster way would be to count the letters in the word and add up the ordinal of all the letters (1=a, 2=b, etc.). Then match the number of letters and total ordinal sum against your word list (where you've already computed these two numbers for each word, and sorted numerically), and then try permutations of your test word against the matched words from your word list. Should take the search from order(N) down to order(log[N]) or less, I would think....
  6. Dec 21, 2005 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member


    There are a ton of different ways one could optimize this for run-time performance, particularly by storing pre-computations like the one you described.

    - Warren
  7. Dec 22, 2005 #6
    Thanx guys. I got a start
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook