Skip to content

Instantly share code, notes, and snippets.

@Kamilcuk
Created December 3, 2019 02:47
Show Gist options
  • Save Kamilcuk/0aed9777a9249bc636bac26b8a9c166f to your computer and use it in GitHub Desktop.
Save Kamilcuk/0aed9777a9249bc636bac26b8a9c166f to your computer and use it in GitHub Desktop.
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment