Thread: What is an appropriate data structure?

  1. #1
    Registered User
    Join Date
    Jan 2004
    Posts
    13

    Question What is an appropriate data structure?

    Hi,

    I am working on a program that accepts a string of 7 letters and then tries to find every word in a dictionary that contains those 7 letters.

    Basically it is an anagram program that finds valid scrabble words with given letters.

    Anyway, my dictionary file is a word list of over 200,000 words stored in a text file. My queston is, should i find all possible letter combinations of my 7 letters then compare each combination against each word in the list then return all matches?

    I'm not to concerned with the algorithm at present as it will evolve as i go, but i am trying to figure out the best way to store the word list.

    Should i just keep them in a file or should i try load them into an array or some other kind of structure? I did try loading them all into a sql database but people have told me that sql is quite inefficient for what i am trying to do.

    Any advice would be great.

    Thanks

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Anyway, my dictionary file is a word list of over 200,000 words stored in a text file. My queston is, should i find all possible letter combinations of my 7 letters then compare each combination against each word in the list then return all matches?
    That's a whole lot of CPU cycles. To make things more efficient I would probably use a hash table.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    There is a much faster way. Here's an example.

    Word list:
    Code:
    alloc
    free
    locale
    main
    program
    Scrabble letters
    Code:
    locamle
    What do you do? First, sort and enumerate the letters of each word in the word list, and your letter rack itself:

    Code:
    program
    1 'a'
    0 'b'
    0 'c'
    ...
    1 'g'
    ...
    1 'm'
    0 'n'
    1 'o'
    1 'p'
    0 'q'
    2 'r'
    ...
    Then you check if each word can be formed using the given letters in the rack. Figure that out yourself.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Since programmers learn best by example, here's one for you...
    Code:
    #include<stdio.h>
    int main( void ) { printf("Programmers learn best by example.\n"); return 0; }
    You also don't need a ; at the end of your main function...

    (Note for posterity: This refers to the above poster's sig.)

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Daggnabbit, that hurt. I'm scarred for life
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  6. #6
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    You can read the text file word by word, transform it as stated in my post above, check if it can be formed using the tiles, keep/discard and read the next one in. That way, you won't be using much RAM at all. That is, if memory is an issue. If it isn't, I have ways to speed things up
    Last edited by jafet; 07-01-2006 at 06:52 AM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Include GTK+ just for a data structure?
    By Jesdisciple in forum C Programming
    Replies: 0
    Last Post: 04-12-2009, 07:19 PM
  2. pthread question how would I init this data structure?
    By mr_coffee in forum C Programming
    Replies: 2
    Last Post: 02-23-2009, 12:42 PM
  3. Data structure implementation
    By fkheng in forum C Programming
    Replies: 3
    Last Post: 07-31-2003, 07:44 AM
  4. can't insert data into my B-Tree class structure
    By daluu in forum C++ Programming
    Replies: 0
    Last Post: 12-05-2002, 06:03 PM
  5. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM