hamcycle.py

[W:=10,H:=10,find:=lambda x:x if x==uf[x]else(uf.__setitem__(x,x:=find(uf[x]))or x),union:=lambda a,b:uf.__setitem__(find(a),find(b)),c2i:=lambda x,y:y*W+x,i2c:=lambda i:(i%W,i//W),uf:=[*range(W*H)],E:=[(c2i(x,y),c2i(x+1-z,y+z))for x in range(W-1)for y in range(H-1)for z in range(2)]+[(c2i(x,H-1),c2i(x+1,H-1))for x in range(W-1)]+[(c2i(W-1,y),c2i(W-1,y+1))for y in range(H-1)],__import__("random").shuffle(E),PE:=[],N:=[[[]for _ in'*'*W]for _ in'*'*H],[[union(a,b),c1:=i2c(a),c2:=i2c(b),N[c1[1]][c1[0]].append(c2),N[c2[1]][c2[0]].append(c1),PE.extend([((2*c1[0]+1,2*c1[1]),(2*c1[0]+2,2*c1[1])),((2*c1[0]+1,2*c1[1]+1),(2*c1[0]+2,2*c1[1]+1))]if c1[1]==c2[1]else[((2*c1[0],2*c1[1]+1),(2*c1[0],2*c1[1]+2)),((2*c1[0]+1,2*c1[1]+1),(2*c1[0]+1,2*c1[1]+2))])]for a,b in E if find(a)!=find(b)],[[[0 if(x-1,y)in N[y][x]else PE.append(((2*x,2*y),(2*x,2*y+1))),0 if(x+1,y)in N[y][x]else PE.append(((2*x+1,2*y),(2*x+1,2*y+1))),0 if(x,y-1)in N[y][x]else PE.append(((2*x,2*y),(2*x+1,2*y))),0 if(x,y+1)in N[y][x]else PE.append(((2*x,2*y+1),(2*x+1,2*y+1)))]for x in range(W)]for y in range(H)],PN:=[[[]for _ in'*'*W*2]for _ in'*'*H*2],[[PN[y1][x1].append((x2,y2)),PN[y2][x2].append((x1,y1))]for(x1,y1),(x2,y2)in PE],C:=" ╴╷┐╶─┌┬╵┘│┤└┴├┼",[[l:="",[[f:=0,[(f:=f|(ny==y-1)<<3|(nx==x+1)<<2|(ny==y+1)<<1|(nx==x-1)<<0)for nx,ny in PN[y][x]],l:=l+C[f]]for x in range(W*2)],nl:=l[0],[(nl:=nl+C[5*(C.index(c)&1)]+c)for c in l[1:]],print(nl)]for y in range(H*2)]]

hamiltonian_cycle.py

import random
import sys

width, height = map(int, sys.argv[1:])
assert width > 0 and height > 0 and width % 2 == height % 2 == 0

width //= 2
height //= 2

class UnionFind:
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        self.parents[a] = b

c2i = lambda x, y: y * width + x
i2c = lambda i: (i % width, i // width)

uf = UnionFind(width * height)
edges = [(c2i(x, y), c2i(x+1-z, y+z)) for x in range(width-1) for y in range(height-1) for z in range(2)]
edges += [(c2i(x, height-1), c2i(x+1, height-1)) for x in range(width-1)]
edges += [(c2i(width-1, y), c2i(width-1, y+1)) for y in range(height-1)]
random.shuffle(edges)

path_edges = []

nodes = [[[] for _ in range(width)] for _ in range(height)]
for a, b in edges:
    if uf.find(a) != uf.find(b):
        uf.union(a, b)
        (x1, y1), (x2, y2) = map(i2c, [a, b])
        nodes[y1][x1].append((x2, y2))
        nodes[y2][x2].append((x1, y1))
        if y1 == y2:
            path_edges += [((2*x1+1, 2*y1), (2*x1+2, 2*y1)), ((2*x1+1, 2*y1+1), (2*x1+2, 2*y1+1))]
        else:
            path_edges += [((2*x1, 2*y1+1), (2*x1, 2*y1+2)), ((2*x1+1, 2*y1+1), (2*x1+1, 2*y1+2))]

for y in range(height):
    for x in range(width):
        if (x-1,y) not in nodes[y][x]:
            path_edges.append(((2*x, 2*y), (2*x, 2*y+1)))
        if (x+1,y) not in nodes[y][x]:
            path_edges.append(((2*x+1, 2*y), (2*x+1, 2*y+1)))
        if (x,y-1) not in nodes[y][x]:
            path_edges.append(((2*x, 2*y), (2*x+1, 2*y)))
        if (x,y+1) not in nodes[y][x]:
            path_edges.append(((2*x, 2*y+1), (2*x+1, 2*y+1)))

path_nodes = [[[] for _ in range(width*2)] for _ in range(height*2)]
for (x1, y1), (x2, y2) in path_edges:
    path_nodes[y1][x1].append((x2, y2))
    path_nodes[y2][x2].append((x1, y1))

CHARS = " ╴╷┐╶─┌┬╵┘│┤└┴├┼"
for y in range(height*2):
    line = ""
    for x in range(width*2):
        flags = 0
        for nx, ny in path_nodes[y][x]:
            flags |= (ny==y-1) << 3
            flags |= (nx==x+1) << 2
            flags |= (ny==y+1) << 1
            flags |= (nx==x-1) << 0
        line += CHARS[flags]
    new_line = line[0]
    for c in line[1:]:
        new_line += CHARS[5 * (CHARS.index(c) & 1)] + c
    print(new_line)