Google Kickstarter 2019 - Ex.1 Palindromes

palindromes.c

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

/* let's assume lines have a maximum of 200 characters */
#define BUF_SIZE 200

/* use binary AND to find if number is odd,
   if LSB is 1 (2^0 = 1 is set) then number is odd */
#define odd(n) (n & 1)

/* char to unsigned int */
#define ctou(c) (c - '0')

/* string to unsigned int, 7x faster than strtoul */
inline unsigned int strtou(char *str)
{
    unsigned int res = 0;

    while(*str)
        res = (res << 1) + (res << 3) + *(str++) - '0';

    return res;
}

/* replaces \n with \0 */
inline void normalize(char *str)
{
    while(*str)
    {
        if(*str == '\n')
            *str = '\0';

        ++str;
    }
}

/* char frequency */
inline void frequency(unsigned int freq[26], char *str, unsigned int min, unsigned int max)
{
    for(unsigned int i = min - 1; i >= min - 1 && i <= max - 1; i++)
        ++freq[str[i] - 'A'];
}

enum {
    CASES,
    CASE_INFO,
    DICTIONARY,
    TRY
};

int main(int argc, const char* argv[])
{
    unsigned int state = CASES;

    unsigned int cases_size;
    unsigned int *cases;

    unsigned int    cur_case = 0,
                    tries = 0,
                    cur_try = 1,
                    pass = 0;

    unsigned int dic_size;
    char *dic = NULL;
    char *subdic = NULL;

    char *token;

    char buf[BUF_SIZE];
    while(fgets(buf, BUF_SIZE, stdin)) /* iterate over lines */
    {
        /* we should check for \n but instead we assume buffer length */
        normalize(buf); /* remove \n */
        switch (state)
        {
            case CASES:
                //printf("# CASES (%s)\n", buf);
                cases_size = strtou(buf);
                //cases = malloc(cases_size * sizeof(unsigned int));
                state = CASE_INFO;
                break;

            case CASE_INFO:
                //printf("# CASE_INFO (%s)\n", buf);
                ++cur_case;
                /* resolve tokens (dic_size, tries)*/
                token = strtok(buf, " ");
                dic_size = strtou(token);
                dic = realloc(dic, dic_size * sizeof(char));

                token = strtok(NULL, " ");
                tries = strtou(token);
                //printf("tries = %u\n", tries);

                state = DICTIONARY;
                break;

            case DICTIONARY:
                //printf("# DICTIONARY (%s)\n", buf);
                memcpy(dic, buf, dic_size);

                state = TRY;
                break;

            case TRY:
                //printf("# TRY %u (%s)\n", cur_try, buf);
                token = strtok(buf, " ");
                const unsigned int min = strtou(token);

                token = strtok(NULL, " ");
                const unsigned int max = strtou(token);

                unsigned int freq[26] = {0};
                frequency(freq, dic, min, max);

                unsigned int odd = 0;
                for(unsigned int i = 0; i < 26; i++)
                    if(odd(freq[i]))
                        ++odd;

                const unsigned int length = max - min + 1;
                if((odd(length) && odd == 1) || (!odd(length) && odd == 0))
                    ++pass;

                if(cur_try == tries)
                {
                    printf("Case #%d: %d\n", cur_case, pass);

                    pass = 0;
                    cur_try = 1;
                    if(cur_case == cases_size)
                        goto exit;
                    else
                        state = CASE_INFO;
                } else
                    cur_try++;

                break;

            default:
                break;
        }
    }

exit:
    free(dic);
    free(subdic);
    free(cases);

    return 0;
}

palindromes_thread.c

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

/* let's assume lines have a maximum of 200 characters */
#define BUF_SIZE 200

/* use binary AND to find if number is odd,
   if LSB is 1 (2^0 = 1 is set) then number is odd */
#define odd(n) (n & 1)

/* char to unsigned int */
#define ctou(c) (c - '0')

/* string to unsigned int, 7x faster than strtoul */
inline unsigned int strtou(char *str)
{
    unsigned int res = 0;

    while(*str)
        res = (res << 1) + (res << 3) + *(str++) - '0';

    return res;
}

/* replaces \n with \0 */
inline void normalize(char *str)
{
    while(*str)
    {
        if(*str == '\n')
            *str = '\0';

        ++str;
    }
}

/* char frequency */
inline void frequency(unsigned int freq[26], char *str, unsigned int min, unsigned int max)
{
    for(unsigned int i = min - 1; i >= min - 1 && i <= max - 1; i++)
        ++freq[str[i] - 'A'];
}

enum {
    CASES,
    CASE_INFO,
    DICTIONARY,
    TRY
};

struct calculate_args {
    unsigned int cur_case;
    unsigned int *cases;
    unsigned int tries_size;
    char **tries;
    char *dic;
};

void *calculate(void *args)
{
    struct calculate_args *a = (struct calculate_args*) args;

    unsigned int pass = 0;
    char *token;

    for(unsigned int i = 0; i < a->tries_size; i++)
    {
        token = strtok(a->tries[i], " ");
        const unsigned int min = strtou(token);

        token = strtok(NULL, " ");
        const unsigned int max = strtou(token);

        unsigned int freq[26] = {0};
        frequency(freq, a->dic, min, max);

        unsigned int odd = 0;
        for(unsigned int i = 0; i < 26; i++)
            if(odd(freq[i]))
                ++odd;

        const unsigned int length = max - min + 1;
        if((odd(length) && odd == 1) || (!odd(length) && odd == 0))
            ++pass;
    }

    a->cases[a->cur_case] = pass;

    free(a->dic);
}

int main(int argc, const char* argv[])
{
    unsigned int state = CASES;

    unsigned int cases_size;
    unsigned int *cases;
    pthread_t *pth;

    unsigned int    cur_case = 0,
                    cur_try = 0,
                    pass = 0;

    unsigned int dic_size;
    char *dic = NULL;
    char *subdic = NULL;

    unsigned int tries_size;
    char **tries = NULL;

    char *token;

    char buf[BUF_SIZE];
    while(fgets(buf, BUF_SIZE, stdin)) /* iterate over lines */
    {
        /* we should check for \n but instead we assume buffer length */
        normalize(buf); /* remove \n */
        switch (state)
        {
            case CASES:
                //printf("# CASES (%s)\n", buf);
                cases_size = strtou(buf);
                cases = malloc(cases_size * sizeof(unsigned int));
                pth = malloc(cases_size * sizeof(pthread_t));
                state = CASE_INFO;
                break;

            case CASE_INFO:
                //printf("# CASE_INFO (%s)\n", buf);
                ++cur_case;
                /* resolve tokens (dic_size, tries)*/
                token = strtok(buf, " ");
                dic_size = strtou(token);
                dic = realloc(dic, dic_size * sizeof(char));

                token = strtok(NULL, " ");
                tries_size = strtou(token);
                tries = realloc(tries, tries_size * sizeof(char*));

                state = DICTIONARY;
                break;

            case DICTIONARY:
                //printf("# DICTIONARY (%s)\n", buf);
                memcpy(dic, buf, dic_size);

                state = TRY;
                break;

            case TRY:
                //printf("# TRY %u (%s)\n", cur_try, buf);

                tries[cur_try] = malloc(BUF_SIZE * sizeof(char));
                strncpy(tries[cur_try], buf, BUF_SIZE);

                if(cur_try + 1 == tries_size)
                {
                    char *dicc = malloc(BUF_SIZE * sizeof(char));
                    strncpy(dicc, dic, BUF_SIZE);

                    struct calculate_args args = {cur_case, cases, tries_size, tries, dicc};
                    pthread_create(pth + cur_case, NULL, calculate, &args);
                    pthread_join(pth[cur_case], NULL);

                    printf("Case #%d: %d\n", cur_case, cases[cur_case]);

                    pass = 0;
                    cur_try = 0;
                    if(cur_case == cases_size)
                        goto exit;
                    else
                        state = CASE_INFO;
                } else
                    cur_try++;

                break;

            default:
                break;
        }
    }

exit:
    for(unsigned int i = 0; i < tries_size; i++)
        free(tries[i]);

    free(dic);
    free(subdic);
    free(cases);
    free(pth);

    return 0;
}