5
\$\begingroup\$

The problem is described in full here - Aaah!.

Input

The input consists of two lines. The first line is the “aaah” Jon Marius is able to say that day. The second line is the “aah” the doctor wants to hear. Only lowercase ’a’ and ’h’ will be used in the input, and each line will contain between 0 and 999 ’a’s, inclusive, followed by a single ’h’.

Output

Output “go” if Jon Marius can go to that doctor, and output “no” otherwise.

Sample Input 1
aaah
aaaaah

Sample Output1
no

Sample Input 2
aaah ah

Sample Output 2
go

My source code for the problem is below. I wrote one of the fast running implementations, but not the best. What changes can I make so as to improve the efficiency of the code?

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

#define MAX_LEN 1000
#define MAX_INP 2000

//Checks whether the input is in the required format
int isValidInput(char*);

int main(int __argc, char* __argv[]) {
    char strJon[MAX_INP], strDoc[MAX_INP];
    int resJon, resDoc;

    gets(strJon);
    gets(strDoc);

    resJon = isValidInput(strJon);

    if(resJon <= 0) {
            printf("no\n");
            return 0;
    }

    resDoc = isValidInput(strDoc);
    if(resDoc <= 0) {
            printf("no\n");
            return 0;
    }

    if(resDoc > resJon) { 
            printf("no\n");
            return 0;
    }

    printf("go\n");

    return 0;
}

//Checks valid input & returns len
int isValidInput(char* strInp) {
    char *str = strInp;
    int len = 0;

    if(str == NULL) return -1;

    //Check if the string either starts with 'a' or 'h' 
    if(!(str[0] == 'h' || str[0] == 'H') && !(str[0] == 'a' || str[0] == 'A')) return -1; 

    len = strlen(str);
    if((str[0] == 'h' || str[0] == 'H') &&  len > 1) return -1;

    if(str[len - 1] != 'h' && str[len - 1] != 'H') return -1;

    if(len > MAX_LEN) return -1;

    while(*(str + 1) != NULL) {
            if(*str != 'a' && *str != 'A') return -1;
            ++str;
    }

    str = NULL;

    return len;
}
\$\endgroup\$

migrated from programmers.stackexchange.com Jun 27 '14 at 8:52

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • 1
    \$\begingroup\$ Get rid of those gets calls. Those are buffer overflows by definition. \$\endgroup\$ – CodesInChaos Jun 27 '14 at 10:48
  • \$\begingroup\$ I'd expect your code to take negligible time compared to launching the process. \$\endgroup\$ – CodesInChaos Jun 27 '14 at 10:53
  • 1
    \$\begingroup\$ isnt this a simple return (strlen(doc)>strlen(jon)?"no":"go")? \$\endgroup\$ – Hugo Delsing Jun 27 '14 at 12:20
5
\$\begingroup\$

I don't see any requirements about actually valuating the input. This gives that the problem to be a simple length calculation of two strings. It's possible that you can get even fast behaviour if you can get the strings into two c-strings and do pointer arithmetic to calc i instead of the expensive i++ and i--.

#include<stdlib.h>
#include<stdio.h>
int main(int argc, char ** argv)
{
        char c;
        int i = 0;
        while (getc(stdin) != '\n')
                i++;
        while (getc(stdin) != '\n')
                i--;
        if (i < 0)
                printf("no\n");
        else
                printf("go\n");
        return 0;
}
\$\endgroup\$
  • \$\begingroup\$ In the problem description the last line say - Only lowercase ’a’ and ’h’ will be used in the input, and each line will contain between 0 and 999 ’a’s, inclusive, followed by a single ’h’. Doesn't that mean an input validation? \$\endgroup\$ – Kunal B. Jun 27 '14 at 5:46
  • \$\begingroup\$ @KunalB.: No it does not. They only explain what inputs you will get. There is no explanation what to do when the input does not reflect the given pattern so you can do what you want in this case. \$\endgroup\$ – Nobody Jun 27 '14 at 9:22
  • \$\begingroup\$ @KunalB. please mark this as accepted if you're happy with my answer. \$\endgroup\$ – iveqy Aug 9 '14 at 12:15
4
\$\begingroup\$

The obvious performance enhancement is to stop using malloc and instead use the stack. Stack allocation is much faster than heap allocation. Change your string declarations to:

char strJon[MAX_INP], strDoc[MAX_INP];

Then get rid of the calls to malloc and free.

In general, it is silly to use malloc to allocate on the heap if you are allocating a fixed amount and not returning the result outside the current scope.

Though in such a trivial program, I can't imagine it actually mattering much as IO costs will trump these enhancements.

\$\endgroup\$
  • \$\begingroup\$ N.B. Since MAX_INP is a #defined constant, you can do this in any version of C. If you are using C99, you can do this even if the size of the array is not constant. If you are using C11, you may or may not be able to use a variable-sized array (it depends on the compiler). \$\endgroup\$ – Snowbody Jun 27 '14 at 18:17
3
\$\begingroup\$

Another likely improvement is to recognise that the string must contain repetitions of "aaaa" and "aaaaaaaa" and deal with 4 or 8 bytes (uint32_t or uint64_t) at once. 32-bit or 64-bit arithmetic will be much faster (unless you're still using a Z-80!)

Only when the string fails to match this pattern do you need to deal with individual bytes.

\$\endgroup\$
  • \$\begingroup\$ However, this approach gets you into trouble with strings like "h" where you read 4 bytes and thereby two bytes behind the null-termination which invokes UB. \$\endgroup\$ – Nobody Jun 27 '14 at 10:17
  • 2
    \$\begingroup\$ Indeed so, I should probably have added such a warning. But combine this with the stack allocation answer, and you know the storage is there, and yours to use. So the test fails immediately and hands over to the bytewide part. \$\endgroup\$ – Brian Drummond Jun 27 '14 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.