0

I've implemented my load and check functions using tries. The program works fine and produces the output, but when I compared it against the output from staff's implementation, I found out that there were some discrepancies. For example, let's say we load the "large" dictionary and check "tolstoy.txt". I expected my program to write out the words that were exclusive to tolstoy.txt, but instead, it's the other way around.

My program returns words that are exclusive to "large" dictionary and cannot be found on tolstoy.txt. Have a look at my program.

#define Alphabet 27    

struct node
{    
    bool end;
    struct node* children[Alphabet];    
}; 


/**
 * Returns true if word is in dictionary else false.
 */

bool check(const char* word)
{
    struct node* move = head;
    int index = 0;
    int j = 0;

    while (word[j] != '\0')
    {
        if(word[j] == '\'')
        {
             index = Alphabet - 1;
        }
        else
        {
            index = toupper(word[j]) - 'A';
        }
        if(move->children[index] != NULL)
        {
            move = move->children[index];
            j++;
        }
        else
        {
            move->end = false;
            //printf("Not Found\n");
            break;
        }
    }
    if(word[j] == '\0' && move->end == true)
    {
        return true;
    }
    else
    {
        return false;
    }

}

[edit: unrelated code removed for Honor Code compliance.]

I've been solving this problem non-stop for a week now and I'm thoroughly exhausted. Any help would mean the world to me. Thanks!

2
  • When pasting massive amounts of code, try using 3 backticks at the start and end of the code to make the block. I'm not sure if you are allowed to post all that code, so I'll leave it up to the other reviewers to help direct you with that. – i_am_david Jul 26 '15 at 20:17
  • I noticed that you created a prototype for the Create() function, located just before the actual function itself. Doing this doesn't cause any problems, but it serves no purpose here. A prototype is only necessary if the function were called before the function itself appears in the sequence of code. For instance, if you had put Create() at the bottom of the file, you would have needed a prototype early on because it is called by load(). Since Create() precedes load() in the file, you don't need the prototype. – Cliff B Jul 26 '15 at 21:33
0

Interesting problem. It's actually showing a mix of words from both files as a side effect of the problem. Your check() code is actually altering the dictionary trie instead of just reading it. My guess is that you put some kind of a notation in and it became code (or it was the middle of the night...).

Here's the problem.

else
    {
        move->end = false;
        //printf("Not Found\n");
        break;
    }

This one is hard to explain, so follow closely. When there is a word in the check file that doesn't exist in the dictionary, but the leading letters do appear as a word, AND the dictionary word is the longest in the trie that also appears in the word being checked, the code will change the node->end marker to false in the dictionary.

For example, let's say that your word being checked is caterpillar. The dictionary contains the words cat and cater, but not caterpillar. When you check caterpillar, it will change the end of word marker for cater to false. After that, if cater is in the check text, it will show up as not a word.

Simple solution, which I think you were really intending to do:

    else
    {
        return false;
    }

Also, a couple of little details. You use a LOT of blank lines in your code. It would be more readable if you cut back. Try running your code through style50. I think you'd benefit a lot from it. Finally, for future questions, please explore the help tab at the top of this page for info on how to post code. It will help you here, and make it a lot easier for those that try to help you.

If this answers your question, please accept this answer to close the question. Let's keep up on forum maintenance. ;-)

3
  • Thanks, man! Your're a life saver! If we ever meet, I'm obliged to buy you a beer :D I had been stuck on it for quite some time, and the code got so complicated in this pset that I became frustrated very easily. I have already implemented load and check, so the other two functions would be a cakewalk, I guess. Are the other two functions (size and unload) less time consuming than load and check? – Aditya Sharma Jul 27 '15 at 18:16
  • If you had planned ahead, size would have taken all of 5 minutes. ;-) Unload will depend on how well you understand what you did with load and how well you understand how to traverse a trie. In any case, they should take less time to develop than load. – Cliff B Jul 27 '15 at 19:06
  • Are you done with the course? What was your average grade point in all the psets and final project? I didn't plan size ahead. Let's see how that pans out :) As you can infer from my code, I'm a pretty indolent coder. I haven't submitted a single Pset because there's some finishing stuff to be done. You know, documenting the code, removing unnecessary comments, checking if the input is within the bounds, et cetera et cetera :D – Aditya Sharma Jul 27 '15 at 20:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .