Jesse and Cookies v2 - HackerRank

v2 solution - got idea from comments on HackerRank to use a queue for new cookies. On each turn (2 per iteration), take either least sweet cookie from the original array not yet used or the least sweet new cookie, combine 2 least sweet cookies and put the new cookie to the end of the queue. Given that cookies are being taken in the increasing order, new cookies are also being created in the increasing order, so queue is always sorted accordingly and the least sweet cookie is at the front of the queue.

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);

int parse_int(char*);

/*
 * Complete the 'cookies' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER k
 *  2. INTEGER_ARRAY A
 */
 
// Time solution: array sorted + queue of new cookies
#define QSIZE 1000000

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int cookies(int k, int A_count, int* A) {
    clock_t t1, t2;
    t1 = clock();
    int operations = 0;
    qsort(A, A_count, sizeof(int), compare);
    int taken = 0;
    int queue[QSIZE], qstart = 0, qend = 0;
    while(true){
        int min1 = INT_MIN, min2 = INT_MIN;
        //fprintf(stderr, "taken=%d, qstart=%d, qend=%d\n", taken, qstart, qend);
        if(qstart == qend){ //empty
            // fprintf(stderr, "A[%d]=%d, q empty | ", taken, A[taken]);
            min1 = A[taken];
            taken++;
        } else if(taken == A_count){
            // fprintf(stderr, "A empty, q=%d | ", queue[qstart]);
            min1 = queue[qstart];
            qstart = (qstart + 1) % QSIZE;
        } else if(queue[qstart] <= A[taken]){
            // fprintf(stderr, "A[%d]=%d, q=%d | ", taken, A[taken], queue[qstart]);
            min1 = queue[qstart];
            qstart = (qstart + 1) % QSIZE;
        } else{
            // fprintf(stderr, "A[%d]=%d, q=%d | ", taken, A[taken], queue[qstart]);
            min1 = A[taken];
            taken++;            
        }
        if(min1 >= k){
            t2 = clock();
            fprintf(stderr, "%d time=%le", operations, (double)(t2-t1)/CLOCKS_PER_SEC);
            return operations;
        } else if(qstart == qend && taken == A_count){ //last cookie taken to min1, but smaller than k
            t2 = clock();
            fprintf(stderr, "-1 time=%le", (double)(t2-t1)/CLOCKS_PER_SEC);
            return -1;
        }

        if(qstart == qend){ //empty
            // fprintf(stderr, "A[%d]=%d, q empty\n", taken, A[taken]);
            min2 = A[taken];
            taken++;
        } else if(taken == A_count){
            // fprintf(stderr, "A empty, q=%d | ", queue[qstart]);
            min2 = queue[qstart];
            qstart = (qstart + 1) % QSIZE;
        } else if(queue[qstart] <= A[taken]){
            // fprintf(stderr, "A[%d]=%d, q=%d\n", taken, A[taken], queue[qstart]);
            min2 = queue[qstart];
            qstart = (qstart + 1) % QSIZE;
        } else{
            // fprintf(stderr, "A[%d]=%d, q=%d\n", taken, A[taken], queue[qstart]);
            min2 = A[taken];
            taken++;            
        }
        int new_cookie = min1 + min2 * 2;
        operations++;
        queue[qend] = new_cookie;
        qend = (qend + 1) % QSIZE;
        //fprintf(stderr, "%d %d\n", queue[qstart], queue[qend-1]);
    }
}

int main()
{
    //FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char** first_multiple_input = split_string(rtrim(readline()));

    int n = parse_int(*(first_multiple_input + 0));

    int k = parse_int(*(first_multiple_input + 1));

    char** A_temp = split_string(rtrim(readline()));

    int* A = malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        int A_item = parse_int(*(A_temp + i));

        *(A + i) = A_item;
    }

    int result = cookies(k, n, A);

    fprintf(stdout, "%d\n", result);

    //fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;

    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) {
            break;
        }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
            break;
        }

        alloc_length <<= 1;

        data = realloc(data, alloc_length);

        if (!data) {
            data = '\0';

            break;
        }
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';

        data = realloc(data, data_length);

        if (!data) {
            data = '\0';
        }
    } else {
        data = realloc(data, data_length + 1);

        if (!data) {
            data = '\0';
        } else {
            data[data_length] = '\0';
        }
    }

    return data;
}

char* ltrim(char* str) {
    if (!str) {
        return '\0';
    }

    if (!*str) {
        return str;
    }

    while (*str != '\0' && isspace(*str)) {
        str++;
    }

    return str;
}

char* rtrim(char* str) {
    if (!str) {
        return '\0';
    }

    if (!*str) {
        return str;
    }

    char* end = str + strlen(str) - 1;

    while (end >= str && isspace(*end)) {
        end--;
    }

    *(end + 1) = '\0';

    return str;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);

        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

int parse_int(char* str) {
    char* endptr;
    int value = strtol(str, &endptr, 10);

    if (endptr == str || *endptr != '\0') {
        exit(EXIT_FAILURE);
    }

    return value;
}