"""A longest snake in the 4-cube, drawn on the cube-in-a-cube picture of Q_4. Every snake (induced path) in Q_4 is found by depth-first search; the longest have 7 edges. The one drawn is the longest snake whose edges cross the fewest other edges in the drawing. Checked here with the same test as checks/judge/snake.py: distinct vertices, consecutive ones adjacent, and no chord. The record snakes for d = 13 to 16 are in constructions/; at 8192 or more corners they do not draw at card size, so the card shows the 4-cube, the largest that still reads at that size.""" from pathlib import Path import kit D = 4 def snakes(d): found = [] def grow(path, used): found.append(list(path)) v = path[-1] for c in range(d): w = v ^ 1 << c if w not in used and not any(w ^ 1 << k in used and w ^ 1 << k != v for k in range(d)): used.add(w) grow(path + [w], used) used.discard(w) for s in range(2 ** d): grow([s], {s}) m = max(map(len, found)) return [p for p in found if len(p) == m] def is_snake(path, d): where = {v: i for i, v in enumerate(path)} return (len(where) == len(path) and all(bin(a ^ b).count('1') == 1 for a, b in zip(path, path[1:])) and all(abs(i - where[v ^ 1 << c]) == 1 for i, v in enumerate(path) for c in range(d) if v ^ 1 << c in where)) longest = snakes(D) assert len(longest[0]) - 1 == 7 and all(is_snake(p, D) for p in longest) # bits 0-2: a cube in oblique view; bit 3: the same cube at half size, inside it U, SCALE = [(176, 0), (0, -176), (-82, -60)], (1.0, 0.5) def at(v): x = sum((v >> k & 1) * U[k][0] for k in range(3)) - sum(u[0] for u in U) / 2 y = sum((v >> k & 1) * U[k][1] for k in range(3)) - sum(u[1] for u in U) / 2 s = SCALE[v >> 3 & 1] return kit.W / 2 + x * s, 130 + y * s EDGES = [(v, v ^ 1 << k) for v in range(16) for k in range(D) if v < v ^ 1 << k] def crosses(p, q, r, t): def o(a, b, c): return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) return o(p, q, r) * o(p, q, t) < 0 and o(r, t, p) * o(r, t, q) < 0 def clutter(path): E = list(zip(path, path[1:])) return sum(crosses(at(a), at(b), at(c), at(d)) for a, b in E for c, d in EDGES), path snake = min(longest, key=clutter) on = set(snake) body = [kit.line(*at(a), *at(b), 'faint-s', 2) for a, b in EDGES] body.append(kit.polyline([at(v) for v in snake], 'f-s', 5)) body += [kit.dot(*at(v), 8) if v in on else kit.circle(*at(v), 4, 'faint') for v in range(16)] kit.write(__file__, 'mathematics', ''.join(body), label='a longest snake in the 4-cube ยท 7 edges')