The problem of “Poisonous Plants” – C Source code

There are a number of plants in a garden. Each of these plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies.

You are given the initial values of the pesticide in each of the plants. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

For example, pesticide levels p=[3,6,2,7,5] . Using a 1-indexed array, day 1 plants (2,4) die leaving p=[3,2,5] . On day 2 , plant 3 of the current array dies leaving p=[3,2]. As there is no plant with a higher concentration of pesticide than the one to its left, plants stop dying after day 2.

https://www.hackerrank.com/challenges/poisonous-plants

Solution 1 – Simple

#include <assert.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>

char* readline();
char** split_string(char*);

// Complete the poisonousPlants function below.
int poisonousPlants(int p_count, int* p)
{
    int rounds = 0;

    int* tstack = (int*)malloc(p_count * sizeof(int));
    int tstack_cnt =0;
    tstack[0] = p[0];

    for (;;)
    {    
        tstack_cnt = 1;

        for (int i = 0; i < p_count-1; i++)
            if (p[i] >= p[i + 1])
                tstack[tstack_cnt++] = p[i+1];
            
        if (tstack_cnt == p_count)
            return rounds;
        rounds++;
        memcpy(p, tstack, tstack_cnt * sizeof(int));
        p_count = tstack_cnt;
    }
}

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

    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

    char** p_temp = split_string(readline());

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

    for (int i = 0; i < n; i++) {
        char* p_item_endptr;
        char* p_item_str = *(p_temp + i);
        int p_item = strtol(p_item_str, &p_item_endptr, 10);

        if (p_item_endptr == p_item_str || *p_item_endptr != '\0') { exit(EXIT_FAILURE); }

        *(p + i) = p_item;
    }

    int p_count = n;

    int result = poisonousPlants(p_count, p);

    fprintf(fptr, "%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; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

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

    data = realloc(data, data_length);

    return data;
}

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

Solution 2 – Advance

#include <assert.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>

char* readline();
char** split_string(char*);

typedef struct {
    int value;
    int count;
} stack_item;

// Complete the poisonousPlants function below.
int poisonousPlants(int p_count, int* p)
{
    int local_max, cur_element, idx=-1,max_days =0;
    stack_item *stack = (stack_item*)calloc(p_count,sizeof(stack_item));

    for (int i=0; i<p_count; i++) 
    {
        local_max = 0;
        cur_element = p[i];

        while (idx >= 0) 
        {
            if (cur_element > stack[idx].value)
                break; 
            
            if (stack[idx].count > local_max) 
                local_max = stack[idx].count;
                
            --idx;
        }

        stack[++idx].value = cur_element;

        stack[idx].count = idx == 0 ? 0 : ++local_max;
        max_days = (idx != 0 && local_max > max_days) ? local_max : max_days;
    }
    return max_days;
}

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

    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

    char** p_temp = split_string(readline());

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

    for (int i = 0; i < n; i++) {
        char* p_item_endptr;
        char* p_item_str = *(p_temp + i);
        int p_item = strtol(p_item_str, &p_item_endptr, 10);

        if (p_item_endptr == p_item_str || *p_item_endptr != '\0') { exit(EXIT_FAILURE); }

        *(p + i) = p_item;
    }

    int p_count = n;

    int result = poisonousPlants(p_count, p);

    fprintf(fptr, "%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; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

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

    data = realloc(data, data_length);

    return data;
}

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