puzzle.c

// http://puzzling.stackexchange.com/questions/4453/a-first-choice-die

#include <stdio.h>
#include <stdlib.h>
#include <error.h>
#include <assert.h>

typedef struct die_t {
    char face[6];
    size_t n_wins;
    struct die_t **wins;
} die;

/* returns:
 * zero     if d1 ties  d2
 * positive if d1 beats d2
 * negative if d2 beats d1 */
int play(die *d1, die *d2) {
    int i, j;
    int ret = 0;
    for (i = 0; i < 6; i++) {
	for (j = 0; j < 6; j++) {
	    if (d1->face[i] > d2->face[j]) {
		ret++;
	    } else if (d1->face[i] < d2->face[j]) {
		ret--;
	    }
	}
    }
    return ret;
}

void printd(die *d1, die *d2, die *d3) {
    int i;
    printf("Solution:\ndie 1: ");
    for (i = 0; i < 6; i++)
	printf("%d ", d1->face[i]);
    printf("\ndie 2: ");
    for (i = 0; i < 6; i++)
	printf("%d ", d2->face[i]);
    printf("\ndie 3: ");
    for (i = 0; i < 6; i++)
	printf("%d ", d3->face[i]);
    printf("\n");
}

int main(void) {
    size_t n_dice = 0;
    size_t i, j, k, l, m, n;
    die *d1, *d2, *d3;
    die die_list[462];
    /* generate all 462 possible dice */
    for (i = 1; i <= 6; i++)
	for (j = i; j <= 6; j++)
	    for (k = j; k <= 6; k++)
		for (l = k; l <= 6; l++)
		    for (m = l; m <= 6; m++)
			for (n = m; n <= 6; n++) {
			    assert(n_dice < 462);
			    die_list[n_dice].face[0] = i;
			    die_list[n_dice].face[1] = j;
			    die_list[n_dice].face[2] = k;
			    die_list[n_dice].face[3] = l;
			    die_list[n_dice].face[4] = m;
			    die_list[n_dice].face[5] = n;
			    die_list[n_dice].n_wins = 0;
			    die_list[n_dice].wins = NULL;
			    n_dice++;
			}
    
    /* play every die against every other die */
    for (i = 0; i < n_dice-1; i++) {
	d1 = &die_list[i];
	for (j = i+1; j < n_dice; j++) {
	    d2 = &die_list[j];
	    int result = play(d1, d2);
	    if (result > 0) {
		d1->n_wins++;
		d1->wins = realloc(d1->wins, d1->n_wins*sizeof(die*));
		if (!d1->wins) {
		    perror("wins realloc");
		    return -1;
		}
		d1->wins[d1->n_wins-1] = d2;
	    } else if (result < 0) {
		d2->n_wins++;
		d2->wins = realloc(d2->wins, d2->n_wins*sizeof(die*));
		if (!d2->wins) {
		    perror("wins realloc");
		    return -1;
		}
		d2->wins[d2->n_wins-1] = d1;
	    }
	}
    }

    /* look for cycles of length 3 */
    for (i = 0; i < n_dice; i++) {
	d1 = &die_list[i];
	for (j = 0; j < d1->n_wins; j++) {
	    d2 = d1->wins[j];
	    for (k = 0; k < d2->n_wins; k++) {
		d3 = d2->wins[k];
		for (l = 0; l < d3->n_wins; l++) {
		   if (d3->wins[l] == d1)
		       printd(d1, d2, d3);
		}
	    }
	}
    }
    return 0;
}