// fairness.c — ¿qué tan justa es la lotería en trabajos cortos?
//
// Uso: ./fairness [ensayos]
//
// Dos trabajos con los mismos boletos y la misma duración (en quanta).
// Injusticia U = (instante en que termina el primero) / (instante en que
// termina el segundo). U = 1 es perfectamente justo; U cercano a 0.5, muy
// injusto. Se compara la lotería (promedio de muchos ensayos) con stride.
#include <stdio.h>
#include <stdlib.h>

static unsigned int rng_state = 12345;

static unsigned int next_random(void) {
    unsigned int x = rng_state;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    rng_state = x;
    return x;
}

// Lotería con dos trabajos de 1 boleto cada uno: cada quantum es una moneda.
static double lottery_unfairness(int len) {
    int left[2] = {len, len};
    int t = 0, first_done = 0;
    while (left[0] > 0 || left[1] > 0) {
        int w;
        if (left[0] == 0)
            w = 1;  // solo queda uno: gana siempre
        else if (left[1] == 0)
            w = 0;
        else
            w = next_random() % 2;
        left[w]--;
        t++;
        if (first_done == 0 && left[w] == 0)
            first_done = t;
    }
    return (double)first_done / t;
}

// Stride con dos trabajos iguales: se alternan, A B A B ...
static double stride_unfairness(int len) {
    int pass[2] = {0, 0};
    int left[2] = {len, len};
    int t = 0, first_done = 0;
    while (left[0] > 0 || left[1] > 0) {
        int w;
        if (left[0] == 0)
            w = 1;
        else if (left[1] == 0)
            w = 0;
        else
            w = (pass[1] < pass[0]) ? 1 : 0;
        pass[w] += 100;  // mismo stride para los dos
        left[w]--;
        t++;
        if (first_done == 0 && left[w] == 0)
            first_done = t;
    }
    return (double)first_done / t;
}

int main(int argc, char *argv[]) {
    int trials = (argc > 1) ? atoi(argv[1]) : 1000;
    int lens[] = {1, 2, 5, 10, 20, 50, 100, 1000};
    int nlens = sizeof(lens) / sizeof(lens[0]);

    printf("duración   U lotería   U stride\n");
    for (int i = 0; i < nlens; i++) {
        double sum = 0;
        for (int k = 0; k < trials; k++)
            sum += lottery_unfairness(lens[i]);
        printf("%6d       %.3f       %.3f\n", lens[i], sum / trials,
               stride_unfairness(lens[i]));
    }
    return 0;
}