Skip to content

Instantly share code, notes, and snippets.

@timmontague timmontague/puzzle.c
Last active Aug 29, 2015

Embed
What would you like to do?
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.