magic_for_stackoverflow.c

// https://stackoverflow.com/questions/59149018/finding-majority-of-boolean-array-using-only-4-elements-query#59149018
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <limits.h>
#include <stdbool.h>
#include <time.h>
#include <stdarg.h>

typedef struct magic_s {
    bool *val;
    size_t size;
} magic;

magic *magic_alloc(size_t size) {
    magic *ret = malloc(sizeof(*ret));
    if (ret == NULL) abort();
    ret->size = size;
    ret->val = malloc(sizeof(*ret->val) * size);
    if (ret->val == NULL) abort();
    return ret;
}

magic *magic_new_rand(size_t size) {
    magic *ret = magic_alloc(size);

    unsigned bits_entropy = 0;
    for (unsigned j = (int)RAND_MAX; j; j >>= 1) {
        bits_entropy++;
    }
    
    unsigned r = 0;
    for (size_t i = 0; i < size; ++i) {
        if (i % bits_entropy == 0) {
            r = rand();
        }
        ret->val[i] = r & 1;
        r >>= 1;
    }

    return ret;
}

magic *magic_new_set(size_t size, ...) {
    magic *ret = magic_alloc(size);
    va_list va;
    va_start(va, size);
    for (size_t i = 0; i < size; ++i) {
        ret->val[i] = va_arg(va, int);
    }
    va_end(va);
    return ret;
}

enum magic_res {
    // point a)
    FOUR_ZERO = 0,
    // point b)
    THREE_ONE = 2,
    // point c)
    TWO_TWO = 4,
};

enum magic_res magic_query(magic *t, size_t a, size_t b, size_t c, size_t d) {
    assert(t != NULL);
    assert(a < t->size);
    assert(b < t->size);
    assert(c < t->size);
    assert(d < t->size);
    const bool * const val = t->val;
    const bool r[4] = { val[a], val[b], val[c], val[d], };
    // like in first grade
    if (r[0] == r[1] && r[1] == r[2] && r[2] == r[3]) return FOUR_ZERO;
    if (r[0] == r[1] && r[1] != r[2] && r[2] == r[3]) return THREE_ONE;
    if (r[0] != r[1] && r[1] == r[2] && r[2] == r[3]) return THREE_ONE;
    if (r[0] == r[1] && r[1] == r[2] && r[2] != r[3]) return THREE_ONE;
    return TWO_TWO;
}

void magic_println(magic *t) {
    printf("%p = {", (void*)t);
    if (t->size) {
        printf("%d", t->val[0]);
    }
    for (size_t i = 1; i < t->size; ++i) {
        printf(",%d", t->val[i]);
    }
    printf("}\n");
}

void magic_free(magic *t) {
    free(t->val);
    free(t);
}

/**
 * return any of the indeces of the majority element
 * in the magic container
 */ 
size_t magic_find(magic *t) {
    // TODO
    return -1;
}

int main() {
    srand(time(0));
    magic *t = magic_new_set(7, 0,1,1,0,0,0,1);
    magic_println(t);
    size_t idx = magic_find(t);
    magic_free(t);
    return 0;
}