1use std::collections::{BTreeSet, HashMap};
24
25fn gf2_rank(mut rows: Vec<u128>) -> usize {
27 let mut rank = 0;
28 let mut col = 0;
29 while col < 128 && rank < rows.len() {
30 let bit = 1u128 << col;
31 if let Some(pivot) = (rank..rows.len()).find(|&r| rows[r] & bit != 0) {
32 rows.swap(rank, pivot);
33 let pr = rows[rank];
34 for r in 0..rows.len() {
35 if r != rank && rows[r] & bit != 0 {
36 rows[r] ^= pr;
37 }
38 }
39 rank += 1;
40 }
41 col += 1;
42 }
43 rank
44}
45
46pub(crate) fn gf2_rank_wide(mut rows: Vec<Vec<u64>>, ncols: usize) -> usize {
48 let words = ncols.div_ceil(64);
49 for r in &mut rows {
50 r.resize(words, 0);
51 }
52 let mut rank = 0;
53 for col in 0..ncols {
54 let (w, bit) = (col / 64, 1u64 << (col % 64));
55 if let Some(pivot) = (rank..rows.len()).find(|&r| rows[r][w] & bit != 0) {
56 rows.swap(rank, pivot);
57 let pr = rows[rank].clone();
58 for r in 0..rows.len() {
59 if r != rank && rows[r][w] & bit != 0 {
60 for t in 0..words {
61 rows[r][t] ^= pr[t];
62 }
63 }
64 }
65 rank += 1;
66 if rank == rows.len() {
67 break;
68 }
69 }
70 }
71 rank
72}
73
74pub struct ProgressComplex {
77 pub n: usize,
78 pub m: usize,
79 forbidden: BTreeSet<(usize, usize)>,
80}
81
82impl ProgressComplex {
83 pub fn new(n: usize, m: usize, forbidden: &[(usize, usize)]) -> Self {
84 ProgressComplex {
85 n,
86 m,
87 forbidden: forbidden.iter().copied().collect(),
88 }
89 }
90
91 fn vid(&self, i: usize, j: usize) -> usize {
92 i * (self.m + 1) + j
93 }
94
95 fn cell_edges(&self, i: usize, j: usize) -> [(usize, usize); 4] {
97 let v = |a: usize, b: usize| self.vid(a, b);
98 let order = |a: usize, b: usize| (a.min(b), a.max(b));
99 [
100 order(v(i, j), v(i + 1, j)), order(v(i, j + 1), v(i + 1, j + 1)), order(v(i, j), v(i, j + 1)), order(v(i + 1, j), v(i + 1, j + 1)), ]
105 }
106
107 fn allowed_cells(&self) -> Vec<(usize, usize)> {
108 let mut cells = Vec::new();
109 for i in 0..self.n {
110 for j in 0..self.m {
111 if !self.forbidden.contains(&(i, j)) {
112 cells.push((i, j));
113 }
114 }
115 }
116 cells
117 }
118
119 pub fn betti(&self) -> (usize, usize, usize) {
123 let cells = self.allowed_cells();
124
125 let mut edge_set: BTreeSet<(usize, usize)> = BTreeSet::new();
126 let mut vert_set: BTreeSet<usize> = BTreeSet::new();
127 for &(i, j) in &cells {
128 for e in self.cell_edges(i, j) {
129 edge_set.insert(e);
130 vert_set.insert(e.0);
131 vert_set.insert(e.1);
132 }
133 }
134
135 let edges: Vec<(usize, usize)> = edge_set.into_iter().collect();
136 let edge_index: HashMap<(usize, usize), usize> =
137 edges.iter().enumerate().map(|(k, &e)| (e, k)).collect();
138 let verts: Vec<usize> = vert_set.into_iter().collect();
139 let vert_index: HashMap<usize, usize> =
140 verts.iter().enumerate().map(|(k, &v)| (v, k)).collect();
141 let (nv, ne, nc) = (verts.len(), edges.len(), cells.len());
142 assert!(
143 ne <= 128,
144 "GF(2) rows are u128 — keep grids small (#edges = {ne})"
145 );
146
147 let mut parent: Vec<usize> = (0..nv).collect();
149 fn find(parent: &mut [usize], x: usize) -> usize {
150 let mut r = x;
151 while parent[r] != r {
152 r = parent[r];
153 }
154 let mut c = x;
155 while parent[c] != r {
156 let nx = parent[c];
157 parent[c] = r;
158 c = nx;
159 }
160 r
161 }
162 for &(a, b) in &edges {
163 let (ra, rb) = (
164 find(&mut parent, vert_index[&a]),
165 find(&mut parent, vert_index[&b]),
166 );
167 if ra != rb {
168 parent[ra] = rb;
169 }
170 }
171 let b0 = (0..nv).filter(|&x| find(&mut parent, x) == x).count();
172
173 let d2: Vec<u128> = cells
175 .iter()
176 .map(|&(i, j)| {
177 self.cell_edges(i, j)
178 .iter()
179 .fold(0u128, |row, e| row ^ (1u128 << edge_index[e]))
180 })
181 .collect();
182 let rank2 = gf2_rank(d2);
183
184 let b2 = nc - rank2;
185 let b1 = ne + b0 - nv - rank2;
187 (b0, b1, b2)
188 }
189
190 pub fn euler(&self) -> i64 {
192 let cells = self.allowed_cells();
193 let mut edge_set: BTreeSet<(usize, usize)> = BTreeSet::new();
194 let mut vert_set: BTreeSet<usize> = BTreeSet::new();
195 for &(i, j) in &cells {
196 for e in self.cell_edges(i, j) {
197 edge_set.insert(e);
198 vert_set.insert(e.0);
199 vert_set.insert(e.1);
200 }
201 }
202 vert_set.len() as i64 - edge_set.len() as i64 + cells.len() as i64
203 }
204}
205
206type V3 = (usize, usize, usize);
208
209pub struct ProgressComplex3 {
215 pub n: usize,
216 pub m: usize,
217 pub p: usize,
218 forbidden: BTreeSet<V3>,
219}
220
221impl ProgressComplex3 {
222 pub fn new(n: usize, m: usize, p: usize, forbidden: &[V3]) -> Self {
223 ProgressComplex3 {
224 n,
225 m,
226 p,
227 forbidden: forbidden.iter().copied().collect(),
228 }
229 }
230
231 fn corners(i: usize, j: usize, l: usize) -> [V3; 8] {
233 let mut c = [(0, 0, 0); 8];
234 for (b, slot) in c.iter_mut().enumerate() {
235 *slot = (i + (b & 1), j + ((b >> 1) & 1), l + ((b >> 2) & 1));
236 }
237 c
238 }
239
240 fn differ_in_one(a: V3, b: V3) -> bool {
241 let d = (a.0 != b.0) as u8 + (a.1 != b.1) as u8 + (a.2 != b.2) as u8;
242 d == 1
243 }
244
245 fn cell_edges(i: usize, j: usize, l: usize) -> Vec<[V3; 2]> {
247 let cs = Self::corners(i, j, l);
248 let mut es = Vec::new();
249 for a in 0..8 {
250 for b in (a + 1)..8 {
251 if Self::differ_in_one(cs[a], cs[b]) {
252 let (mut u, mut v) = (cs[a], cs[b]);
253 if v < u {
254 std::mem::swap(&mut u, &mut v);
255 }
256 es.push([u, v]);
257 }
258 }
259 }
260 es
261 }
262
263 fn cell_faces(i: usize, j: usize, l: usize) -> Vec<[V3; 4]> {
265 let cs = Self::corners(i, j, l);
266 let mut fs = Vec::new();
267 for axis in 0..3 {
268 for val in 0..2 {
269 let mut quad: Vec<V3> = cs
270 .iter()
271 .copied()
272 .filter(|&c| [c.0, c.1, c.2][axis] == [i, j, l][axis] + val)
273 .collect();
274 quad.sort_unstable();
275 fs.push([quad[0], quad[1], quad[2], quad[3]]);
276 }
277 }
278 fs
279 }
280
281 fn face_edges(face: &[V3; 4]) -> Vec<[V3; 2]> {
283 let mut es = Vec::new();
284 for a in 0..4 {
285 for b in (a + 1)..4 {
286 if Self::differ_in_one(face[a], face[b]) {
287 let (mut u, mut v) = (face[a], face[b]);
288 if v < u {
289 std::mem::swap(&mut u, &mut v);
290 }
291 es.push([u, v]);
292 }
293 }
294 }
295 es
296 }
297
298 fn allowed_cells(&self) -> Vec<V3> {
299 let mut cells = Vec::new();
300 for i in 0..self.n {
301 for j in 0..self.m {
302 for l in 0..self.p {
303 if !self.forbidden.contains(&(i, j, l)) {
304 cells.push((i, j, l));
305 }
306 }
307 }
308 }
309 cells
310 }
311
312 pub fn betti(&self) -> (usize, usize, usize, usize) {
315 let cells = self.allowed_cells();
316
317 let mut verts: BTreeSet<V3> = BTreeSet::new();
319 let mut edges: BTreeSet<[V3; 2]> = BTreeSet::new();
320 let mut faces: BTreeSet<[V3; 4]> = BTreeSet::new();
321 for &(i, j, l) in &cells {
322 for c in Self::corners(i, j, l) {
323 verts.insert(c);
324 }
325 for e in Self::cell_edges(i, j, l) {
326 edges.insert(e);
327 }
328 for f in Self::cell_faces(i, j, l) {
329 faces.insert(f);
330 }
331 }
332 let verts: Vec<V3> = verts.into_iter().collect();
333 let edges: Vec<[V3; 2]> = edges.into_iter().collect();
334 let faces: Vec<[V3; 4]> = faces.into_iter().collect();
335 let vidx: HashMap<V3, usize> = verts.iter().enumerate().map(|(k, &v)| (v, k)).collect();
336 let eidx: HashMap<[V3; 2], usize> =
337 edges.iter().enumerate().map(|(k, &e)| (e, k)).collect();
338 let fidx: HashMap<[V3; 4], usize> =
339 faces.iter().enumerate().map(|(k, &f)| (f, k)).collect();
340 let (nv, ne, nf, nc) = (verts.len(), edges.len(), faces.len(), cells.len());
341
342 let mut parent: Vec<usize> = (0..nv).collect();
344 fn find(parent: &mut [usize], x: usize) -> usize {
345 let mut r = x;
346 while parent[r] != r {
347 r = parent[r];
348 }
349 let mut c = x;
350 while parent[c] != r {
351 let nx = parent[c];
352 parent[c] = r;
353 c = nx;
354 }
355 r
356 }
357 for e in &edges {
358 let (ra, rb) = (
359 find(&mut parent, vidx[&e[0]]),
360 find(&mut parent, vidx[&e[1]]),
361 );
362 if ra != rb {
363 parent[ra] = rb;
364 }
365 }
366 let b0 = (0..nv).filter(|&x| find(&mut parent, x) == x).count();
367
368 let d2: Vec<Vec<u64>> = faces
370 .iter()
371 .map(|f| {
372 let mut row = vec![0u64; ne.div_ceil(64)];
373 for e in Self::face_edges(f) {
374 let idx = eidx[&e];
375 row[idx / 64] ^= 1u64 << (idx % 64);
376 }
377 row
378 })
379 .collect();
380 let d3: Vec<Vec<u64>> = cells
381 .iter()
382 .map(|&(i, j, l)| {
383 let mut row = vec![0u64; nf.div_ceil(64)];
384 for f in Self::cell_faces(i, j, l) {
385 let idx = fidx[&f];
386 row[idx / 64] ^= 1u64 << (idx % 64);
387 }
388 row
389 })
390 .collect();
391 let rank2 = gf2_rank_wide(d2, ne);
392 let rank3 = gf2_rank_wide(d3, nf);
393
394 let b1 = ne + b0 - nv - rank2;
395 let b2 = nf - rank2 - rank3;
396 let b3 = nc - rank3;
397 (b0, b1, b2, b3)
398 }
399}
400
401#[cfg(test)]
402#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/progress_complex/tests.rs"]
403mod tests;