Go Aaaaaaaaaaah

Question

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;
}

Answer 1

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;
}

Answer 2

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.

Answer 3

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.