String Sort and remove Duplicates

Question

First I apologize for any mistype, for I am Brazilian and English is not my native language.

I am a freshman at my college and I got this algorithm to solve, from my teacher:

Make a program that creates a vector of n words, n being a size entered by the user (maximum 100). Your program should remove all duplicate words from the input vector and sort the words. Print the final vector without repeated and ordered words.

E.g. with 7 words to sort:

Input: 7 [enter]

hand ear leg hand hand leg foot

Output: ear foot hand leg

Note: Comment the program prints so that the output of the program is as shown in the example above (the numbers are separated by a spacebar, without space after last digit).

Note2: In case of invalid entry the program should print: "invalid entry" (all lower case).

Ok, I got it working but the I got confused with the notes and I can't find a way to fix the possible bugs, here is my code:

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

int main()
{
  char word[100][100], aux[100];
  int i, j, num;

  printf("Type how many words you want to order: ");
  do
  {
  scanf("%d", &num);
  }while (num>100 || num<=0);

  for(i=0; i<num; i++)
    scanf("%s",&word[i]);

  for (i = 0; i < num; i++) //loop to sort alphabetically
  {
    for (j = i+1; j < num; j++)
    {
      if ((strcasecmp(word[i], word[j]) > 0))  //swapping words
      {
        strcpy(aux, word[j]);
        strcpy(word[j], word[i]);
        strcpy(word[i], aux);
      }
    }
  }

  for (i = 0; i < num; i++) //loop to remove duplicates
  {
    if ((strcasecmp(word[i], word[i+1]) == 0))  //finding the duplicates
    {
      for (j = i+1; j < num; j++) //loop to delete it
        strcpy(word[j], word[j+1]);

      num--;
      i--;
    }
  }

  printf("\nWords sorted and without duplicates:\n");
  for(i=0; i<num-1; i++)
    printf("%s ", word[i]); //output with spacebar

  printf("%s", word[num-1]); //last output without spacebar

  return 0;
}

When I type a word with more than 100 characters, the Code::Blocks closes with an error, else it works fine. What do you think I should change?

The teacher uses a Online Judge (Sharif Judge) to evaluate if the code is right, and I got error in 3 of the tests (that are not specified), all of them were "Time Limit Exceeded". Maybe it has do to with the size of the matrix, or the problem with words >100.

Thanks in advance, Vinicius.

Answer 1

of course you will get an error if you use woerds more than 100 length casue you have this line: char word[100][50], aux[100];

that means that you word length limit is set to 50. use word[100][100];

also you may not delete duplicates, just skip them in output

lol of course if youre using judge , you should not output any symbols except the answer, this means you should delete all lines, like :

printf("Type how many words you want to order: ");

and check the input format, and check limitations, i mean max word length , max amounts of words

---

try smth like this:

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

#define max_word_length = 101;
#define max_amount_of_words = 101;

int main() {
    char word[max_amount_of_words][max_word_length] = {};
    char aux[max_word_length];
    int i, j, num;

    scanf("%d", &num);

    if (num < 0 || num > 100) {
        printf("invalid entry");
        return 0;
    }

    for (i = 0; i < num; i++) {
        scanf("%s", word[i]);
    }

    for (i = 0; i < num; i++) {//loop to sort alphabetically    
        for (j = i + 1; j < num; j++) {
            if ((strcasecmp(word[i], word[j]) > 0)) {  //swapping words         
                strcpy(aux, word[j]);
                strcpy(word[j], word[i]);
                strcpy(word[i], aux);
            }
        }
    }

    bool is_joint = false;
    for (i = 0; i < num; i++) { //loop to skip duplicates   
        if ((strcasecmp(word[i], word[i + 1]) != 0)) { //if there is a duplicate , we willnot output it
            if(is_joint) printf(" ");
            printf("%s ", word[i]);
            is_joint = true;
        }
    }

    return 0;
}

Answer 2

I guess you input sanity check is causing the issue.

As mentioned in the comment section. If n is always < 100. Definitely your sorting is not causing any time limit exceeded. Looks like the n is given something greater than 100 and your scanf is waiting and causing the issue. Also, make sure your input numbers are taken properly. If the input is > 100 print 'invalid entry'. Something like below should work.

scanf("%d", &num);
if (num > 100)
    printf("invalid entry");

for (i = 0; i < num; i++) {
    scanf("%s", word[i]);
    if (strlen(word[i])>100)
            printf("invalid entry");
}

Hope it helps!

Answer 3

I got 100% on Judge, I fixed the code and looks like this:

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

int main(){
  char word[101][101],aux[101]; //a number higher than the limit to comparisons
  int i,j,num;

  scanf("%d",&num);
  if(num<=0||num>100){ // if words < 0 or >100
    printf("invalid input");
    return 0;
  }

  for(i=0;i<num;i++){
    scanf("%s",&word[i]); //read n words
    if(strlen(word[i])>100){ //if word >100 caracters
      printf("invalid input");
      return 0;
    }
    for(j=0;j<strlen(word[i]);j++){
      if (word[i][j]>=65&&word[i][j]<=90){
        word[i][j]= word[i][j]+32; // if word is uppercase, make them lowcase
      }
      else if (word[i][j]>122||word[i][j]<97){// if word is different from alphabet lowercase
      printf("invalid input");
      return 0;
      }
    }
  }

  for(i=0;i<num;i++){
    for(j=i+1;j<num;j++){
      if((strcmp(word[i],word[j])>0)){ //loop to sort words
        strcpy(aux,word[j]);
        strcpy(word[j],word[i]);
        strcpy(word[i],aux);
      }
    }
  }


  for(i=0;i<num-1;i++){
    if((strcmp(word[i],word[i+1])!=0)){ // output words with spacebar, without the last one
      printf("%s ",word[i]);
    }
  }
  printf("%s",word[num-1]); // last word without spacebar

  return 0;
}

Thank you everyone who tried to help, I've learned a lot with your suggestions!

Answer 4

This project is actually pretty tough assignment for a programmer who just started in C.

Run this program in your computer. Before running against the Judge, make sure you run many times with your manual inputs. Once you are happy with the tests, try against the Judge.

Like I said, the hardest part is storing the user's inputs according to spec (accepting space or newline characters in multiple lines).

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

int
main(void)
{

   int iNumW, iIndex;
   int iWCnt = 0;
   int iC;
   char caTemp[100];
   char caWords[100][100];
   char *cpDelimeter = " \n";
   char *cpToken;
   char *cp;
   short sIsWord = 1;
   char caGarbage[100];

   scanf("%d", &iNumW );
   fgets(caGarbage, sizeof caGarbage, stdin);  //Remove newline char

   //Get word inputs
   while( iWCnt < iNumW )
   {
       fgets(caTemp, sizeof caTemp, stdin );
       for( cpToken = strtok( caTemp, cpDelimeter );   cpToken != NULL;  cpToken = strtok( NULL, cpDelimeter)){

          cp = cpToken;
          while( *cp ){
              sIsWord = 1;

              //Check if alphabet
              if( !isalpha(*cp) ){
                  sIsWord = 0;
                  break;
              }
              cp++;
          }
          if( sIsWord ){
              strcpy( caWords[iWCnt], cpToken );
             //printf( "%s\n", caWords[iWCnt]);
              iWCnt++;
              if( iWCnt >= iNumW ) break;
          } else {
              printf("invalid entry.\n");
        }
        //printf("%d\n", iWCnt);
      } 
   }
   int i,j ;
   for (i = 0; i < iWCnt; i++) {//loop to sort alphabetically    
      for (j = i + 1; j < iWCnt; j++) {
        if ((strcasecmp(caWords[i], caWords[j]) > 0)) {  //swapping words         
            strcpy(caTemp, caWords[j]);
            strcpy(caWords[j], caWords[i]);
            strcpy(caWords[i], caTemp);
          }
      }
  }

   for (i = 0; i < iWCnt; i++) { //loop to skip duplicates   
       if ((strcasecmp(caWords[i], caWords[i + 1]) != 0)) { //if there is a duplicate , we willnot output it
        printf("%s ", caWords[i]);
       }
   }

   return 0;
}