Home > Back-end >  i have been on this question for quaring the document for two days straight, and it is not working.
i have been on this question for quaring the document for two days straight, and it is not working.

Time:01-30

I am not able to debug what is going on. The code seems correct yet I am new to pointers to pointers, and here there are 4 in series.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAX_CHARACTERS 1005
#define MAX_PARAGRAPHS 5

char *kth_word_in_mth_sentence_of_nth_paragraph(char ****document, int k, int m, int n) {
    return *(*(*(document   n - 1)   m - 1)   k - 1);
}

char **kth_sentence_in_mth_paragraph(char ****document, int k, int m) { 
    return (*(*(document   m - 1)   k - 1));
}

char ***kth_paragraph(char ****document, int k) {
    return *(document   k - 1);
}

char ****get_document(char *text) {
    /* allocating memory */
    int len = strlen(text);
    /* allocate memory for each component first */
    char ****document = malloc(sizeof(char ***));
    char ***paragraph = malloc(sizeof(char **));
    char **sentence = malloc(sizeof(char *));
    char *word = malloc(sizeof(char) * 1024);
    /* connect all the components to point in the sequence that is required */
    *document = paragraph;
    *paragraph = sentence;
    *sentence = word;
    /* declare some numbers as iterators for the words, sentences,etc. */
    int parano = 0;
    int sentno = 0;
    int wordno = 0;
    int charno = 0;
    /* now iterate over the text filling and expanding the document at the same time */
    /*----------------------------------------------------------------------------------------------------*/
    /* feeding data in those spaces */
    for (int i = 0; i < len; i  ) {
        if (text[i] == ' ') {
            /* wrapping the current word, that is, resizing to len   1 */
            char *current_word = *(*(*(document   parano)   sentno)   wordno);
            current_word = realloc(current_word, strlen(current_word)   1);
            /*  resizing the current sentence to add another word*/
            char **current_sentence = (*(*(document   parano)   sentno));
            current_sentence = realloc(current_sentence, sizeof(char *) * (wordno   2));
            
            wordno  ;
            charno = 0;
            /* allocating space to that new char * / word that has been created in the same sentence */
            *(*(*(document   parano)   sentno)   wordno) = malloc(sizeof(char) * 1000);
        }
        else if (text[i] == '.') {
            /* wrapping of the current word has to be done anyways */
            char *current_word1 = *(*(*(document   parano)   sentno)   wordno);
            current_word1 = realloc(current_word1, strlen(current_word1)   1);
            charno = 0;
            
            if (text[i   1] != '\n') {
                /* the paragraph does not change, and the sentence ends */
                /* resize that paragraph for adding another sentence */
                char ***current_para = *(document   parano);
                current_para = realloc(current_para, sizeof(char **) * (sentno   2));
                sentno  ;
                wordno = 0;
                /* allocating word to that sentence */
                *(*(document   parano)   sentno) = malloc(sizeof(char *));
                /* allocating space for that word */
                *(*(*(document   parano)   sentno)   wordno) = malloc(sizeof(char) * 1000);
            } else {
                /*  if this is the last sentence of this paragraph*/
                wordno = 0;
                charno = 0;
                sentno = 0;
            }
        }
        else if (text[i] == '\n') {
            /* paragraph has changed */
            /* add another paragraph to the document */
            document = realloc(document, sizeof(char ***) * (parano   2));
            parano  ;
            /* add sentence to that paragraph */
            (*(document   parano) ) = malloc(sizeof(char **));
            /* add a word to that paragrapgh */
            (*(*(document   parano)   sentno)) = malloc(sizeof(char *));
            /* allocate space for that word */
            *(*(*(document   parano)   sentno)   wordno) = malloc(sizeof(char) * 1000);
        } else {
            scanf("%c", *(*(*(document   parano)   sentno)   wordno)   charno);
            printf("%c\n", **(*(*(document   parano)   sentno)   wordno)   charno);
            charno  ;
        }
    }
    return document;
}

char *get_input_text() {    
    int paragraph_count;
    scanf("%d", &paragraph_count);

    char p[MAX_PARAGRAPHS][MAX_CHARACTERS], doc[MAX_CHARACTERS];
    memset(doc, 0, sizeof(doc));
    getchar();
    for (int i = 0; i < paragraph_count; i  ) {
        scanf("%[^\n]%*c", p[i]);
        strcat(doc, p[i]);
        if (i != paragraph_count - 1)
            strcat(doc, "\n");
    }

    char *returnDoc = (char *)malloc((strlen(doc) 1) * (sizeof(char)));
    strcpy(returnDoc, doc);
    return returnDoc;
}

void print_word(char *word) {
    printf("%s", word);
}

void print_sentence(char **sentence) {
    int word_count;
    scanf("%d", &word_count);
    for (int i = 0; i < word_count; i  ) {
        printf("%s", sentence[i]);
        if (i != word_count - 1)
            printf(" ");
    }
} 

void print_paragraph(char ***paragraph) {
    int sentence_count;
    scanf("%d", &sentence_count);
    for (int i = 0; i < sentence_count; i  ) {
        print_sentence(*(paragraph   i));
        printf(".");
    }
}

int main() {
    char *text = get_input_text();
    char ****document = get_document(text);

    int q;
    scanf("%d", &q);

    while (q--) {
        int type;
        scanf("%d", &type);

        if (type == 3) {
            int k, m, n;
            scanf("%d %d %d", &k, &m, &n);
            char *word = kth_word_in_mth_sentence_of_nth_paragraph(document, k, m, n);
            print_word(word);
        }
        else if (type == 2) {
            int k, m;
            scanf("%d %d", &k, &m);
            char **sentence = kth_sentence_in_mth_paragraph(document, k, m);
            print_sentence(sentence);
        } else {
            int k;
            scanf("%d", &k);
            char ***paragraph = kth_paragraph(document, k);
            print_paragraph(paragraph);
        }
        printf("\n");
    }     
}

this is one of the questions on Hackerrank for the C language. link to the question hacker rank question my profile

shows aborted, realloc invalid size. I couldn't find anything for the last 2 days.

inputs for the problem

2
Learning C is fun.
Learning pointers is more fun.It is good to have pointers.
3
1 2
2
5
6
2 1 1
4
3 1 1 1

expected output

Learning pointers is more fun.It is good to have pointers.
Learning C is fun
Learning

CodePudding user response:

  1. When processing regular characters (final else clause) you read additional input instead of operating over text, i.e. instead of:
                scanf("%c", &document[parano][sentno][wordno][charno]);
                printf("%c\n", document[parano][sentno][wordno][charno]);
                charno  ;

you want to do:

                document[parano][sentno][wordno][charno  ] = text[i];

By the time we hit text[i] == ' ' for the first time the value of ***document is "3\n1 2\n2\n" but you wanted it to be "Learning".

  1. (not fixed) When processing a word (`text[i] == ' ') you expand current word, yet, you hard-code 1000 when you allocate it initially so this doesn't make sense. Be consistent.

  2. parano, sentno, wordno, charno is indices but same suggest they are counts. It's not wrong just confusing and why you have to wordno 2 when relloc'ing.

  3. Terminate words with `\0'.

  4. When you process ' ' you add another word which you may or may not need which is fine. But when process a '.' you look ahead to the following letter is a \n or not. Be consistent. If you look ahead then you need to check that i 1 < len, and it's fragile, say, there is a stray space before the \n.

  5. (not fixed) Memory leaks. As the size of the sub-elements (paragraph, sentences and words) are private implementation details of get_document() you will have refactor the code to make those available. I suggest:

struct document {
   char ****document;
   size_t paragraphs;
   size_t sentences;
   size_t words;
}
  1. (not fixed) Deduplicate. Similar to the print functions, create a allocation function per type.

  2. (not fixed, really) get_input_text(). You split the into paragraphs then concatenate everything again into a local variable then copy it into a dynamically allocated variable:

   char *str = malloc(BUFFER_LEN);
   for(size_t i = 0, l = 0; l < lines && i   1 < BUFFER_LEN; i  = strlen(str   i)) {
       int rv = fgets(str   i, BUFFER_LEN - i, stdin);
       if(!rv) {
          // handle error
          break;
       }
   }
   return s;
  1. (not fixed) Separate i/o from processing. This simplifies testing and it makes it easier to figure out what is going on. In main(), you read a query type then 1 to 3 numbers. scanf()` tells you how many items where read so you simply do. As you don't use the kth_ functions for anything else just combine then with print_ funci
    int n = scanf("%d %d %d %d", &type, &p, &s, &w);
    switch(type) {
        case 1:
            if(n != 2) {
              // handle error
            }
            print_paragraph(document, p);
            break;
        ...
    }
  1. (not fixed) Add error checks for the remainingmalloc(), strdup() etc.

  2. Don't hard-code magic values (1000). I introduced the constant WORD_LEN but you also have MAX_CHARACTERS which is kinda the same thing.

  3. (not fixed) Consider using char *s = strpbrk(text i, " .\n") to copy a word at a time. It will simplify \0 handling, and likely to be faster than walking the text a byte at a time, i.e. i = s - text i, just handle the s == NULL special case.

valgrind is now happy other than leaks (see above):

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHARACTERS 1005
#define MAX_PARAGRAPHS 5
#define WORD_LEN 1000

char *kth_word_in_mth_sentence_of_nth_paragraph(char ****document, int p, int s, int w) {
    return document[p - 1][s - 1][w - 1];
}

char **kth_sentence_in_mth_paragraph(char ****document, int p, int s) {
    return document[p - 1][s - 1];
}

char ***kth_paragraph(char ****document, int p) {
    return document[p - 1];
}

char ****get_document(char* text) {
    char ****document = malloc(sizeof ***document);
    *document = malloc(sizeof **document);
    **document = malloc(sizeof *document);
    ***document = malloc(WORD_LEN);

    /*  declare some numbers as iterators for the words, sentences,etc.*/
    int parano = 0;
    int sentno = 0;
    int wordno = 0;
    int charno = 0;
    /*  now iterate over the text filling and expanding the document at the same time*/
    /*----------------------------------------------------------------------------------------------------*/
    /*  feading data in those spaces*/
    size_t len = strlen(text);
    for (size_t i = 0; i < len; i  ) {
        switch(text[i]) {
            case ' ': {
                document[parano][sentno][wordno][charno] = '\0';

                wordno  ;
                char **words = realloc(
                    document[parano][sentno],
                    (wordno   1) * sizeof *document[parano][sentno]
                );
                if(!words) {
                    printf("realloc of words failed\n");
                    exit(1);
                }
                document[parano][sentno] = words;
                document[parano][sentno][wordno] = malloc(WORD_LEN);
                charno = 0;
                break;
            }
            case '.': {
                document[parano][sentno][wordno][charno] = '\0';

                sentno  ;
                char ***sentences = realloc(
                    document[parano],
                    (sentno   1) * sizeof *document[parano]
                );
                if(!sentences) {
                    printf("realloc of sentences failed\n");
                    exit(1);
                }
                document[parano] = sentences;
                document[parano][sentno] = malloc(sizeof **document);
                wordno = 0;
                document[parano][sentno][wordno] = malloc(WORD_LEN);
                charno = 0;
                break;
            }
            case '\n': {
                document[parano][sentno][wordno][charno] = '\0';

                parano  ;
                char ****paragraphs = realloc(
                    document,
                    (parano   1) * sizeof *document
                );
                if(!paragraphs) {
                    printf("realloc of paragraphs failed\n");
                    exit(1);
                }
                document = paragraphs;
                document[parano] = malloc(sizeof ***document);
                sentno = 0;
                document[parano][sentno] = malloc(sizeof **document);
                wordno = 0;
                document[parano][sentno][wordno] = malloc(WORD_LEN);
                charno = 0;
                break;
            }
            default: // character
                document[parano][sentno][wordno][charno  ] = text[i];
        }
    }
    return document;
}

char *get_input_text() {
    int paragraph_count;
    scanf("%d", &paragraph_count);
    char p[MAX_PARAGRAPHS][MAX_CHARACTERS];
    char doc[MAX_CHARACTERS];
    memset(doc, 0, sizeof doc);
    getchar();
    for (int i = 0; i < paragraph_count; i  ) {
        scanf("%[^\n]%*c", p[i]);
        strcat(doc, p[i]);
        if (i != paragraph_count - 1)
            strcat(doc, "\n");
    }
    return strdup(doc);
}

void print_word(char *word) {
    printf("%s", word);
}

void print_sentence(char **sentence) {
    int word_count;
    scanf("%d", &word_count);
    for(int i = 0; i < word_count; i  ){
        print_word(sentence[i]);
        if(i   1 != word_count)
            printf(" ");
    }
}

void print_paragraph(char ***paragraph) {
    int sentence_count;
    scanf("%d", &sentence_count);
    for (int i = 0; i < sentence_count; i  ) {
        print_sentence(paragraph[i]);
        printf(".");
    }
}

int main() {
    char *text = get_input_text();
    char ****document = get_document(text);
    int q;
    scanf("%d", &q);
    while (q--) {
        int type;
        scanf("%d", &type);
        switch(type) {
            case 1: {
                int p;
                scanf("%d", &p);
                print_paragraph(kth_paragraph(document, p));
                break;
            }
            case 2: {
                int p, s;
                scanf("%d %d", &p, &s);
                print_sentence(kth_sentence_in_mth_paragraph(document, p, s));
                break;
            }
            case 3: {
                int p, s, w;
                scanf("%d %d %d", &p, &s, &w);
                print_word(kth_word_in_mth_sentence_of_nth_paragraph(document, p, s, w));
                break;
            }
            default:
                printf("error\n");
        }
        printf("\n");
    }
    free(text);
}

Output as expected:

Learning pointers is more fun.It is good to have pointers.
Learning C is fun
Learning

Btw, a whole different way of solving this is problem is keep the original input (text) then write functions to directly extract a paragraph, sentence or word from that string. If you input is huge then create an index, say, (paragraph, sentence, word) to &text[i].

  • Related