CH4 Tasks

/*
 * Tuenti Contest
 * Challenge 4 - Task Durations
 * Author: Pedro Antonio Pardal Jimena
 * Email: [email protected]
 */

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

#define IN_FILENAME "in"
#define BUFFER_SIZE 0x1000

struct node
{
    unsigned int cost, child, brother;
};

struct node_search
{
    unsigned int tid, cost;
};

int total;
struct node *table;

int stack_ptr = 0;
struct node_search *stack;

#define stack_empty !stack_ptr

static inline void stack_push(struct node_search nod)
{
    stack[stack_ptr++] = nod;
}

static inline struct node_search stack_pop()
{
    return stack[--stack_ptr];
}

char buffer[BUFFER_SIZE];

static void read_table()
{
    int i, tid, cost, depends, brother;
    char *tok;
    FILE *in;

    in = fopen(IN_FILENAME, "r");

    if (in == NULL)
    {
        perror("fopen");
        exit(-1);
    }

    while (fgets(buffer, BUFFER_SIZE, in) != NULL)
    {
        if (buffer[0] != '#' && buffer[0] != '\0' && buffer[0] != '\n')
        {
            total = atoi(buffer);
            table = (struct node *) malloc(total*sizeof(struct node));
            stack = (struct node_search *) malloc(total*sizeof(struct node_search));

            break;
        }
    }

    for (i = 0; i < total; i++)
    {
        if (fgets(buffer, BUFFER_SIZE, in) == NULL)
        {
            perror("fgets");
            exit(-1);
        }

        if (buffer[0] == '#' || buffer[0] == '\0' || buffer[0] == '\n')
        {
            i--;
            continue;
        }

        tok = strtok(buffer, ",\n");
        tid = atoi(tok);
        tok = strtok(NULL, ",\n");
        cost = atoi(tok);

        table[tid].cost = cost;
        table[tid].child = -1;
        table[tid].brother = -1;
    }

    while (fgets(buffer, BUFFER_SIZE, in) != NULL)
    {
        if (buffer[0] != '#' && buffer[0] != '\0' && buffer[0] != '\n')
        {
            tok = strtok(buffer, ",\n");
            tid = atoi(tok);

            brother = -1;

            while ((tok = strtok(NULL, ",\n")) != NULL)
            {
                depends = atoi(tok);
                table[depends].brother = brother;
                brother = depends;
            }

            table[tid].child = brother;
        }
    }

    fclose(in);
}

static void print_table()
{
    int i;

    for (i = 0; i < total; i++)
    {
        printf("Task %d: Cost->%d, Child->%d, Brother->%d\n",
                i, table[i].cost, table[i].child, table[i].brother);
    }
}

static int compute_cost(int tid)
{
    struct node_search nod = {.tid = tid, .cost = table[tid].cost};
    int maxcost = -1, childcost = -1, child = -1;

    stack_push(nod);

    while (!stack_empty)
    {
        nod = stack_pop();

        childcost = nod.cost;

        if (childcost > maxcost)
            maxcost = childcost;

        child = table[nod.tid].child;

        while (child != -1)
        {
            nod.tid = child;
            nod.cost = table[child].cost + childcost;

            stack_push(nod);

            child = table[child].brother;
        }
    }

    return maxcost;
}

int main(int argc, char *argv[])
{
    char *tok;
    int tid, cost;

    read_table();

    if (fgets(buffer, BUFFER_SIZE, stdin) == NULL)
    {
        perror("fgets");
        exit(-1);
    }

    tok = strtok(buffer, ",\n");

    do
    {
        tid = atoi(tok);
        cost = compute_cost(tid);

        fprintf(stdout, "%d %d\n", tid, cost);
    }
    while ((tok = strtok(NULL, ",\n")) != NULL);

    return 0;
}