keypad path enumeration

keypad.py

#!/usr/bin/env python3
# https://twitter.com/cwillmore/status/1192927454429511680

neighbors1 = [[0, 1], [0, 1, 2], [1, 2]]
def neighbors(i, j):
    """Enumerate all the buttons that are adjacent to button (i, j)."""
    for ii in neighbors1[i]:
        for jj in neighbors1[j]:
            if i != ii or j != jj:
                yield (ii, jj)

def paths(n):
    """
    Enumerate all non-repeating paths with n + 1 vertices. Does not
    perform canonicalization.
    """
    visited = [[False] * 3 for i in range(3)]
    path_buf = [None] * (n + 1)
    def aux(n, i, j):
        if visited[i][j]:
            return
        visited[i][j] = True
        path_buf[n] = (i, j)
        if n == 0:
            yield list(path_buf)
        else:
            for ii, jj in neighbors(i, j):
                for path in aux(n - 1, ii, jj):
                    yield path
        visited[i][j] = False
    for i in range(3):
        for j in range(3):
            for path in aux(n, i, j):
                yield path

def canonical_transform(path):
    """
    Canonicalize a button path by considering all rotations, reflections,
    and reversals of the path and returning the one that comes first
    lexicographically.
    """
    def reflect(path):
        return [(j, i) for (i, j) in path]
    def reverse(path):
        return list(reversed(path))
    def rotate(path):
        return [(j, 2 - i) for (i, j) in path]
    bases = [path, reflect(path), reverse(path), reverse(reflect(path))]
    best = path
    for p in bases:
        for i in range(4):
            best = min(p, best)
            p = rotate(p)
    return best

def uniq(l):
    """Given a sorted list 'l', remove all duplicate elements in 'l'."""
    i = 0
    while i < len(l) - 1:
        if l[i] == l[i + 1]:
            del l[i + 1]
        else:
            i += 1

import pyx
import random
import os
c = pyx.canvas.canvas()

# calculate the set of canonical paths
long_paths = list(paths(8))
long_paths = [canonical_transform(path) for path in long_paths]
long_paths.sort()
uniq(long_paths)
print(len(long_paths))

cell_size = 4
for path_i, path in enumerate(long_paths):
    # place the path
    path_row, path_col = divmod(path_i, 13)
    path_row *= 2
    if path_col > 6:
        path_col -= 6
        path_row += 1
    path_base_x = cell_size * path_col
    path_base_y = cell_size * (7 - path_row - 1)
    if path_row % 2 == 1:
        path_base_x -= cell_size / 2.0
    if path_row == 7:
        path_base_x += cell_size / 2.0

    # draw bg rect (to give the pdf a little bit of margin)
    c.fill(pyx.path.rect(path_base_x - 0.5, path_base_y - 0.5, 4, 4), [pyx.color.rgb.white])

    # draw dots
    for i in range(3):
        for j in range(3):
            c.fill(pyx.path.circle(path_base_x + 0.5 + i, path_base_y + 0.5 + j, 0.40), [pyx.color.gray(0.8)])
    # draw path
    transformed_path = [(path_base_x + 0.5 + x, path_base_y + 0.5 + y) for x, y in path]
    pyx_path = pyx.path.path(pyx.path.moveto(*transformed_path[0]), *[pyx.path.lineto(*p) for p in transformed_path[1:]])
    c.stroke(pyx_path, [pyx.color.rgb.red, pyx.style.linewidth.THICK, pyx.style.linejoin.round, pyx.style.linecap.round])

c.writePDFfile("foo.pdf")
os.system("open foo.pdf")