Spaces:
Sleeping
Sleeping
File size: 3,991 Bytes
605ae26 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | import collections
import random
import itertools
class FSORouter:
def __init__(self, m, k=3, r=None):
self.m = m
self.k = k
if r:
self.r = r
elif k == 3:
self.r = [1, m - 2, 1]
if m == 3: self.r = [1, 1, 1]
elif k == 2:
self.r = [1, m - 1]
elif k == 4:
# Law I Escape: k=4 resolves even-grid parity obstructions
self.r = [1] * 4
else:
self.r = [1] * k
self.perms = {}
for s in range(m):
if k == 3:
if s < m - 2: p = [0, 1, 2]
elif s == m - 2: p = [0, 2, 1]
else: p = [1, 0, 2]
elif k == 2:
if s == 0: p = [0, 1]
else: p = [1, 0]
elif k == 4:
# Balanced distribution for k=4
p = [0, 1, 2, 3]
if s % 2 == 1: p = [2, 3, 0, 1]
else:
p = list(range(k))
self.perms[s] = p
self.anomalies = {}
def get_permutation(self, x):
s = sum(x) % self.m
if (tuple(x), s) in self.anomalies:
return self.anomalies[(tuple(x), s)]
p = list(self.perms.get(s, list(range(self.k))))
if self.k == 3 and self.m % 2 != 0:
if x[1] == 0 and s != self.m - 2:
d0_idx = p.index(0); d2_idx = p.index(2)
p[d0_idx], p[d2_idx] = 2, 0
return p
def step(self, x, color):
p = self.get_permutation(x)
dim = p[color % len(p)]
nx = list(x)
nx[dim] = (nx[dim] + self.r[dim]) % self.m
return tuple(nx), dim
def trace_cycle(self, color, start_node=None):
if start_node is None:
start_node = tuple([0] * self.k)
visited = []
visited_set = set()
edges = set()
curr = start_node
for _ in range(self.m ** self.k + 1):
if curr in visited_set:
break
visited.append(curr)
visited_set.add(curr)
next_node, dim = self.step(curr, color)
edges.add((curr, dim))
curr = next_node
return visited, edges, curr
def verify_fso_routing(m, k=3, router=None, silent=False):
if router is None:
router = FSORouter(m, k)
all_edges = set(); total_nodes = m ** k; success = True
results = []
for color in range(k):
nodes, edges, final_node = router.trace_cycle(color)
is_ham = len(nodes) == total_nodes and final_node == nodes[0]
results.append(is_ham)
if not is_ham: success = False
all_edges.update(edges)
final_success = success and (len(all_edges) == k * total_nodes)
if not silent:
print(f"Verification (m={m}, k={k}): Hamiltonian={results}, Success={final_success}")
return final_success
def repair_manifold(m, k, max_iterations=2000):
router = FSORouter(m, k)
if verify_fso_routing(m, k, router, silent=True):
return router
for attempt in range(max_iterations):
color = random.randint(0, k - 1)
nodes, edges, final_node = router.trace_cycle(color)
if len(nodes) < m**k:
tail = nodes[-1]
s = sum(tail) % m
p = list(router.get_permutation(tail))
i, j = random.sample(range(k), 2)
p[i], p[j] = p[j], p[i]
router.anomalies[(tail, s)] = p
if verify_fso_routing(m, k, router, silent=True):
print(f"Repair successful for G_{m}^{k} at attempt {attempt}!")
verify_fso_routing(m, k, router)
return router
print(f"Repair failed for G_{m}^{k}.")
return None
if __name__ == "__main__":
print("\n--- Standard Verifications ---")
verify_fso_routing(3, 3)
print("\n--- Law I Escape: Testing k=4 for even grids ---")
# m=2, k=3 is obstructed
verify_fso_routing(2, 3)
# m=2, k=4
repair_manifold(2, 4)
|