presents.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

#define ABC_DRAW 0
#define ABC_A_WINS 1
#define ABC_B_WINS 2
#define ABC_C_WINS 3
#define ABC_AB_DRAW 4
#define ABC_AC_DRAW 5
#define ABC_BC_DRAW 6

int run(int *boxes, int nboxes, int npresents, int ncontestants) {
     if (ncontestants < 2 || ncontestants > 3)
          return 0;
     for (int i = 0; i < nboxes; ++i) {
          boxes[i] = 0;
     }
     for (int p = 0; p < npresents; ++p) {
          while (1) {
               int j;
               while (1) {
                    j = rand();
                    if (j < ((RAND_MAX / nboxes) * nboxes)) {
                         j %= nboxes;
                         break;
                    }
               }
               if (!boxes[j]) {
                    boxes[j] = 1;
                    break;
               }
          }
     }
     int a, b, c;
     int a_iter = 0;
     int b_iter = 0;
     int c_iter = 0;
     int a_count = 0;
     int b_count = 0;
     int c_count = 0;
     for (a = 0; a_count < npresents && a < nboxes; a += 1) { /* 0, 1, 2, 3, ... */
          ++a_iter;
          if (boxes[a]) {
               ++a_count;
          }
     }
     for (b = 0; b_count < npresents && b < nboxes; b += 2) { /* 0, 2, 4, ... */
          ++b_iter;
          if (boxes[b]) {
               ++b_count;
          }
     }
     for (b = 1; b_count < npresents && b < nboxes; b += 2) { /* 1, 3, 5, ... */
          ++b_iter;
          if (boxes[b]) {
               ++b_count;
          }
     }

     if (ncontestants == 2) {
          if (a_iter < b_iter)
               return 1;
          if (a_iter > b_iter)
               return 2;
          return 0;
     }

     for (c = 0; c_count < npresents && c < nboxes; c += 3) { /* 0, 3, 6, ... */
          ++c_iter;
          if (boxes[c]) {
               ++c_count;
          }
     }
     for (c = 1; c_count < npresents && c < nboxes; c += 3) { /* 1, 4, 7, ... */
          ++c_iter;
          if (boxes[c]) {
               ++c_count;
          }
     }
     for (c = 2; c_count < npresents && c < nboxes; c += 3) { /* 2, 5, 8, ... */
          ++c_iter;
          if (boxes[c]) {
               ++c_count;
          }
     }

     if (a_iter < b_iter) {
          if (b_iter <= c_iter)
               return ABC_A_WINS;
          if (a_iter < c_iter)
               return ABC_A_WINS;
          if (c_iter < a_iter)
               return ABC_C_WINS;
          return ABC_AC_DRAW;
     } else if (b_iter < a_iter) {
          if (a_iter <= c_iter)
               return ABC_B_WINS;
          if (b_iter < c_iter)
               return ABC_B_WINS;
          if (c_iter < b_iter)
               return ABC_C_WINS;
          return ABC_BC_DRAW;
     } else {
          if (c_iter < a_iter)
               return ABC_C_WINS;
          if (a_iter < c_iter)
               return ABC_AB_DRAW;
          return ABC_DRAW;
     }
}

int main(int argc, char **argv) {
     srand(time(NULL) + getpid() * 23);

     int nboxes = argc < 2 ? 100 : atoi(argv[1]);
     int npresents = argc < 3 ? 26 : atoi(argv[2]);
     if (nboxes <= npresents) {
          return 0;
     }

     int ncontestants = argc < 4 ? 2 : atoi(argv[3]);
     if (ncontestants < 2)
          ncontestants = 2;
     else if (ncontestants > 3)
          ncontestants = 3;

     int *boxes = calloc(nboxes, sizeof(int));
     if (ncontestants == 2) {
          int a = 0, b = 0, d = 0;
          for (int i = 0;; ++i) {
               int result = run(boxes, nboxes, npresents, 2);
               if (result == 0) {
                    a++;
               } else if (result == 1) {
                    b++;
               } else {
                    d++;
               }
               if (i % 10000 == 0) {
                    printf("  %6.2f a  %6.2f b  %6.2f ab\n", 100.0 * a / i, 100.0 * b / i, 100.0 * d / i);
               }
          }
     } else {
          int a = 0, b = 0, c = 0, ab = 0, ac = 0, bc = 0, abc = 0;
          for (int i = 0;; ++i) {
               int result = run(boxes, nboxes, npresents, 3);
               if (result == 0) {
                    abc++;
               } else if (result == 1) {
                    a++;
               } else if (result == 2) {
                    b++;
               } else if (result == 3) {
                    c++;
               } else if (result == 4) {
                    ab++;
               } else if (result == 5) {
                    ac++;
               } else if (result == 6) {
                    bc++;
               }
               if (i % 10000 == 0) {
                    printf("  %6.2f a  %6.2f b  %6.2f c  %6.2f ab  %6.2f ac  %6.2f bc  %6.2f abc\n",
                           100.0 * a / i,
                           100.0 * b / i,
                           100.0 * c / i,
                           100.0 * ab / i,
                           100.0 * ac / i,
                           100.0 * bc / i,
                           100.0 * abc / i);
               }
          }
     }
}