Code of Duty challenge

code of duty.c

/* ---------- Code of duty 1 - Frank DENIS <f@orbus.fr> @jedisct1 ---------- */

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

#define MIN_ITEM_VALUE 0U
#define MAX_ITEM_VALUE 99U
#define INPUT_FILE     "input.txt"
#define OUTPUT_FILE    "output.txt"

/* ---------- Memoization of function calls ---------- */

#define MEMOIZED_SLOTS (MAX_ITEM_VALUE - MIN_ITEM_VALUE + 1U) \
                     * (MAX_ITEM_VALUE - MIN_ITEM_VALUE + 1U)

typedef struct MemoizedCall_ {
    size_t a_size;
    unsigned char *a_items;
    size_t ret_size;
    unsigned char ret_items[]; /* includes a_items[] */
} MemoizedCall;

MemoizedCall *memoized_calls[MEMOIZED_SLOTS];

static unsigned int slot_for_memoized(const unsigned char * const a_items,
                                      const size_t a_size)
{
    if (a_size == 0U) {
        return 0;
    }
    assert(a_items[0] <= MAX_ITEM_VALUE);
    if (a_size == 1U) {
        return a_items[0];
    }
    assert(a_items[1] <= MAX_ITEM_VALUE);
    const unsigned int slot =
        (a_items[0] * (MAX_ITEM_VALUE - MIN_ITEM_VALUE + 1U) + a_items[1] +
            ~a_size) % MEMOIZED_SLOTS;
    assert(slot < MEMOIZED_SLOTS);
    return slot;
}

static int memoize(const unsigned char * const a_items, const size_t a_size,
                   const unsigned char * const ret_items,
                   const size_t ret_size)
{
    const unsigned int slot = slot_for_memoized(a_items, a_size);
    MemoizedCall *memoized_call = memoized_calls[slot];
    if (memoized_call == NULL ||
        memoized_call->a_size + memoized_call->ret_size < a_size + ret_size) {
        MemoizedCall * const new_memoized_call =
            realloc(memoized_call, sizeof *memoized_call + a_size + ret_size);
        if (new_memoized_call == NULL) {
            return -1;
        }
        memoized_call = new_memoized_call;
        memoized_calls[slot] = memoized_call;
    }
    memoized_call->a_size = a_size;
    memoized_call->ret_size = ret_size;
    memoized_call->a_items = memoized_call->ret_items + ret_size;
    memcpy(memoized_call->a_items, a_items, a_size);
    memcpy(memoized_call->ret_items, ret_items, ret_size);
    
    return 0;
}

static int fetch_memoized(const unsigned char * const a_items,
                          const size_t a_size,
                          const unsigned char * * const ret_items_p,
                          size_t * const ret_size_p)
{
    const unsigned int slot = slot_for_memoized(a_items, a_size);
    MemoizedCall *memoized_call = memoized_calls[slot];
    if (memoized_call == NULL || memoized_call->a_size != a_size ||
        memcmp(memoized_call->a_items, a_items, a_size) != 0) {
        return -1;
    }
    *ret_items_p = memoized_call->ret_items;
    *ret_size_p = memoized_call->ret_size;
    
    return 0;
}

/* ------- Compute sum, median and distance from the final vector ------- */

static unsigned int get_sum(const unsigned char * const a_items,
                            const size_t a_size)
{
    unsigned int sum = 0U;
    size_t i = 0U;
    assert(a_size > (size_t) 0U);
    do {
        sum += a_items[i];
    } while (++i < a_size);
    
    return sum;
}

static int get_median(unsigned int * const median,
                      const unsigned char * const a_items, const size_t a_size)
{
    const unsigned int sum = get_sum(a_items, a_size);
    if (sum % a_size != 0U) {
        return -1;
    }
    *median = sum / a_size;
    
    return 0;
}

static unsigned int get_score(const unsigned char * const a_items,
                              const size_t a_size, const unsigned int median)
{
    unsigned int score = 0U;
    unsigned int item;
    size_t i = 0U;
    assert(a_size > (size_t) 0U);
    do {
        item = (unsigned int) a_items[i];
        if (item < median) {
            score += median - item;
        } else {
            score += item - median;
        }
    } while (++i < a_size);

    return score;    
}

/* ---------- Explore possible vectors, with memoization ---------- */

static size_t explore(unsigned char * const ret_items,
                      const unsigned char * const a_items,
                      const size_t a_size, const unsigned int median,
                      const int can_give)
{
    if (a_size == 0U) {
        *ret_items = 0;
        return 0U;
    }
    size_t ret_size = 0U;
    const unsigned char head = a_items[0];
    if (a_size == 1U) {
        ret_items[0] = head;
        return 1U;
    }    
    const unsigned char *memoized_ret_items;
    size_t memoized_ret_size;
    if (fetch_memoized(a_items, a_size,
                       &memoized_ret_items, &memoized_ret_size) == 0) {
        memcpy(ret_items, memoized_ret_items, memoized_ret_size);
        return memoized_ret_size;
    }    
    const unsigned char * const tail_items = &a_items[1];
    const size_t tail_size = a_size - 1U;    
    const unsigned char head2 = tail_items[0];    
    const unsigned char * const tail2_items = &tail_items[1];
    const size_t tail2_size = tail_size - 1U;    
    unsigned char ftail_items[tail_size];
    const size_t ftail_size = explore(ftail_items, tail_items, tail_size,
                                      median, 1);
    unsigned char prop_items[1U + ftail_size];
    prop_items[0] = head;
    memcpy(&prop_items[1], ftail_items, ftail_size);
    const size_t prop_size = 1U + ftail_size;    
    unsigned int best_score = get_score(a_items, a_size, median);    
    const unsigned int score = get_score(prop_items, prop_size, median);
    if (score <= best_score) {
        best_score = score;
        memcpy(ret_items, prop_items, prop_size);
        ret_size = prop_size;
    }    
    unsigned char pscan_items[1U + tail2_size];
    if (head2 > MIN_ITEM_VALUE) {
        pscan_items[0] = head2 - 1;
        memcpy(&pscan_items[1], tail2_items, tail2_size);
        const size_t pscan_size = 1U + tail2_size;
        assert(pscan_size <= ftail_size);        
        const size_t ftail_size = explore(ftail_items, pscan_items, pscan_size,
                                          median, 0);
        if (head < MAX_ITEM_VALUE) {
            assert(1U + ftail_size <= prop_size);
            prop_items[0] = head + 1;
            memcpy(&prop_items[1], ftail_items, ftail_size);
            const size_t prop_size = 1U + ftail_size;
            const unsigned int score =
                get_score(prop_items, prop_size, median);
            if (score <= best_score) {
                best_score = score;
                memcpy(ret_items, prop_items, prop_size);
                ret_size = prop_size;
            }
        }                
    }
    if (head2 < MAX_ITEM_VALUE && can_give == 1) {
        pscan_items[0] = head2 + 1;
        memcpy(&pscan_items[1], tail2_items, tail2_size);
        const size_t pscan_size = 1U + tail2_size;

        assert(pscan_size <= ftail_size);
        const size_t ftail_size = explore(ftail_items, pscan_items, pscan_size,
                                          median, 1);
        if (head > MIN_ITEM_VALUE) {
            assert(1U + ftail_size <= prop_size);
            prop_items[0] = head - 1;
            memcpy(&prop_items[1], ftail_items, ftail_size);
            const size_t prop_size = 1U + ftail_size;
            const unsigned int score =
                get_score(prop_items, prop_size, median);
            if (score <= best_score) {
                memcpy(ret_items, prop_items, prop_size);
                ret_size = prop_size;
            }
        }
    }
    memoize(a_items, a_size, ret_items, ret_size);
    
    return ret_size;
}

/* ---------- Chained list, for results ---------- */

typedef struct Step_ {
    struct Step_ *next;
    size_t size;
    unsigned char items[];
} Step;

static int push_to_list(Step * * const steps, Step * * const step,
                        Step * * const previous_step, const size_t a_size)
{
    *previous_step = *step;
    Step * const step_ = malloc(sizeof *step_ + a_size);
    if (step_ == NULL) {
        return -1;
    }
    step_->next = NULL;
    if (*previous_step == NULL) {
        *steps = step_;
    } else {
        (*previous_step)->next = step_;
    }
    *step = step_;
    
    return 0;
}

static void free_list(Step * const steps)
{
    Step * step = steps;
    Step * next_step;
    while (step != NULL) {
        next_step = step->next;
        free(step);
        step = next_step;
    }
}

/* ---------- Read and parse data, solve and output file ---------- */

static void print_array(FILE * const fp, const unsigned int line,
                        const unsigned char *a_items, const size_t a_size)
{
    size_t i = 0U;
    fprintf(fp, "%u : (", line);
    do {
        fprintf(fp, "%s%u", i != 0U ? ", ": "", a_items[i]);
    } while (++i < a_size);
    fputs(")\n", fp);
}

static int solve(FILE * const fp, const unsigned char *a_items,
                 const size_t a_size)
{
    unsigned int median;
    if (get_median(&median, a_items, a_size) != 0) {
        fputs("-1\n", fp);
        return -1;
    }
    Step *steps = NULL, *previous_step, *step = NULL;
    unsigned int last_line = 0U;
    if (push_to_list(&steps, &step, &previous_step, a_size) != 0) {
        perror("push_to_list");
        exit(1);
    }
    step->size = a_size;
    memcpy(step->items, a_items, a_size);
    for (;;) {
        if (get_score(step->items, step->size, median) == 0U) {
            break;
        }
        if (push_to_list(&steps, &step, &previous_step, a_size) != 0) {
            perror("push_to_list");
            exit(1);
        }
        last_line++;        
        step->size = explore(step->items, previous_step->items,
                             previous_step->size, median, 1);
    }
    fprintf(fp, "%u\n", last_line);
    
    unsigned int line = 0U;
    const Step *scanned_step = steps;
    while (scanned_step != NULL) {
        print_array(fp, line++, scanned_step->items, scanned_step->size);
        scanned_step = scanned_step->next;
    }
    free_list(steps);
    
    return 0;
}

int main(void)
{
    FILE * const ifp = fopen(INPUT_FILE, "r");
    if (ifp == NULL) {
        fputs("Impossible d'ouvrir le fichier [" INPUT_FILE "].\n", stderr);
        return 1;
    }
    FILE * const ofp = fopen(OUTPUT_FILE, "w");
    if (ofp == NULL) {
        fputs("Impossible d'ouvrir le fichier [" INPUT_FILE "].\n", stderr);
        return 1;
    }    
    int already_solved_one = 0;    
    unsigned char *a_items = NULL;
    size_t a_size = 0U;
    unsigned int nb;    
    while (!feof(ifp)) {
        if (fscanf(ifp, "%u", &nb) != 1 || nb <= 0U) {
            break;
        }
        if ((size_t) nb > a_size || a_items == NULL) {
            unsigned char *new_a_items = realloc(a_items, (size_t) nb);
            if (new_a_items == NULL) {
                perror("realloc");
                exit(1);
            }
            a_items = new_a_items;
        }
        a_size = (size_t) nb;
        size_t i = 0U;
        unsigned int item;
        do {
            if (fscanf(ifp, "%u", &item) != 1 ||
#if MIN_ITEM_VALUE > 0
                item < MIN_ITEM_VALUE ||
#endif
                item > MAX_ITEM_VALUE) {
                fprintf(stderr, "Membre invalide: [%u]\n", item);
                exit(1);
            }
            a_items[i] = (unsigned char) item;            
        } while (++i < a_size);
        if (already_solved_one != 0) {
            fputc('\n', ofp);
        } else {
            already_solved_one = 1;
        }        
        solve(ofp, a_items, a_size);        
    }
    fclose(ofp);
    fclose(ifp);    
        
    return 0;
}