Snakes in the box in dimensions 13 to 16
Find longer snakes, induced paths in the hypercube, in dimensions 13 to 16: beat 2946, 5850, 11,673 and 23,318 edges.
| 1 | """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 |
| 2 | found by depth-first search; the longest have 7 edges. The one drawn is the longest snake whose edges cross the fewest |
| 3 | other edges in the drawing. Checked here with the same test as checks/judge/snake.py: distinct vertices, consecutive |
| 4 | ones adjacent, and no chord. The record snakes for d = 13 to 16 are in constructions/; at 8192 or more corners they do |
| 5 | not draw at card size, so the card shows the 4-cube, the largest that still reads at that size.""" |
| 6 | from pathlib import Path |
| 7 | |
| 8 | import kit |
| 9 | |
| 10 | D = 4 |
| 11 | |
| 12 | |
| 13 | def snakes(d): |
| 14 | found = [] |
| 15 | |
| 16 | def grow(path, used): |
| 17 | found.append(list(path)) |
| 18 | v = path[-1] |
| 19 | for c in range(d): |
| 20 | w = v ^ 1 << c |
| 21 | if w not in used and not any(w ^ 1 << k in used and w ^ 1 << k != v for k in range(d)): |
| 22 | used.add(w) |
| 23 | grow(path + [w], used) |
| 24 | used.discard(w) |
| 25 | |
| 26 | for s in range(2 ** d): |
| 27 | grow([s], {s}) |
| 28 | m = max(map(len, found)) |
| 29 | return [p for p in found if len(p) == m] |
| 30 | |
| 31 | |
| 32 | def is_snake(path, d): |
| 33 | where = {v: i for i, v in enumerate(path)} |
| 34 | return (len(where) == len(path) and all(bin(a ^ b).count('1') == 1 for a, b in zip(path, path[1:])) |
| 35 | 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)) |
| 36 | |
| 37 | |
| 38 | longest = snakes(D) |
| 39 | assert len(longest[0]) - 1 == 7 and all(is_snake(p, D) for p in longest) |
| 40 | |
| 41 | # bits 0-2: a cube in oblique view; bit 3: the same cube at half size, inside it |
| 42 | U, SCALE = [(176, 0), (0, -176), (-82, -60)], (1.0, 0.5) |
| 43 | |
| 44 | |
| 45 | def at(v): |
| 46 | x = sum((v >> k & 1) * U[k][0] for k in range(3)) - sum(u[0] for u in U) / 2 |
| 47 | y = sum((v >> k & 1) * U[k][1] for k in range(3)) - sum(u[1] for u in U) / 2 |
| 48 | s = SCALE[v >> 3 & 1] |
| 49 | return kit.W / 2 + x * s, 130 + y * s |
| 50 | |
| 51 | |
| 52 | EDGES = [(v, v ^ 1 << k) for v in range(16) for k in range(D) if v < v ^ 1 << k] |
| 53 | |
| 54 | |
| 55 | def crosses(p, q, r, t): |
| 56 | def o(a, b, c): |
| 57 | return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) |
| 58 | return o(p, q, r) * o(p, q, t) < 0 and o(r, t, p) * o(r, t, q) < 0 |
| 59 | |
| 60 | |
| 61 | def clutter(path): |
| 62 | E = list(zip(path, path[1:])) |
| 63 | return sum(crosses(at(a), at(b), at(c), at(d)) for a, b in E for c, d in EDGES), path |
| 64 | |
| 65 | |
| 66 | snake = min(longest, key=clutter) |
| 67 | on = set(snake) |
| 68 | body = [kit.line(*at(a), *at(b), 'faint-s', 2) for a, b in EDGES] |
| 69 | body.append(kit.polyline([at(v) for v in snake], 'f-s', 5)) |
| 70 | body += [kit.dot(*at(v), 8) if v in on else kit.circle(*at(v), 4, 'faint') for v in range(16)] |
| 71 | kit.write(__file__, 'mathematics', ''.join(body), label='a longest snake in the 4-cube · 7 edges') |
