dodec.py

#!/usr/bin/env python3

import re
from itertools import permutations
from collections import deque

class Dodecahedron(int):
    r'''
    dodecahedron embedded as a planar graph                     4—————0—————1
    - there are 3 rings: outer, middle, and inner               |\    |    /|
    - the outer and inner rings are pentagons                   | 9—E—5—A—6 |
    - the middle ring has 10 vertices                           | | |   | | |
      - 5 at corners and 5 at midpoints between corners         | | K———F | |
      - it can also be viewed as a 10-gon                       | | |   | | |
    - the outer ring aligns with the middle corners             | D—J   G—B |
    - the inner ring aligns with the middle midpoints           | |  \ /  | |
    - swapping the outer and inner rings preserves the graph    | |   H   | |
                                                                | |   |   | |
    this class handles edge coloring                            | 8———C———7 |
    - edges of the same color cannot share a vertex             |/         \|
    - the graph has a proper 3-edge-coloring                    3———————————2
    '''

    neighbors = [
        [ 4,  1,  5], [ 0,  2,  6], [ 1,  3,  7], [ 2,  4,  8], [ 3,  0,  9],
        [ 0, 10, 14], [ 1, 11, 10], [ 2, 12, 11], [ 3, 13, 12], [ 4, 14, 13],
        [ 5,  6, 15], [ 6,  7, 16], [ 7,  8, 17], [ 8,  9, 18], [ 9,  5, 19],
        [10, 16, 19], [11, 17, 15], [12, 18, 16], [13, 19, 17], [14, 15, 18],
    ]
    pairs = [(u,v) for u, vs in enumerate(neighbors) for v in vs if u < v]
    edges = {k: e for e, ps in enumerate(pairs) for k in [ps,ps[::-1]]}
    morphs = []

    def _edge_formatter(match):
        n = (ord(match[0]) - 65 - bool(match[0] > 'I')) % 41
        shape = next( s for s, group in { '—': 'ABFLMOPSTWY2',
                                          '|': 'CDHNQRUVXZ15',
                                          '/': 'EJ3',
                                          '\\': 'GK4', }.items()
                        if match[0] in group )
        return f'\033[{{{n}}}m{shape}\033[0m'

    structure = re.sub('[A-Z1-5]', _edge_formatter, '''
    .AAAAA.BBBBB.
    HK    C    ED
    H .T.M.L.O. D
    H U Z   V N D
    H U .222. N D
    H U 5   1 N D
    H .Y.   .W. D
    H R  4 3  Q D
    H R   .   Q D
    H R   X   Q D
    H .SSS.PPP. D
    HJ         GD
    .FFFFFFFFFFF.
    '''.strip().replace('.','o').replace('\n    ','\n'))

    # ------------------------------------------------------------------------

    def __new__(cls, data=0b_11_10_01):
        return super().__new__(cls, data)

    @property
    def data(self):
        return int(self)

    def __repr__(self):
        return f'Dodecahedron({self.data})'

    # ------------------------------------------------------------------------

    def get_color(self, edge):
        return (self.data >> (2*edge)) & 0b11

    def set_color(self, edge, c):
        assert self.get_color(edge) == 0
        return Dodecahedron(self.data | (c << (2*edge)))

    def ansi_color(self, color):
        return [37, 31, 32, 36][color]  # white, red, green, blue

    def to_list(self):
        return [self.ansi_color(self.get_color(edge)) for edge in range(30)]

    def draw_line_by_line(self):
        yield from self.structure.format(*self.to_list()).split('\n')

    def draw(self):
        print(self.structure.format(*self.to_list()))

    # ------------------------------------------------------------------------

    def iter_neighbors(self, v, u, rot):
        pivot = self.neighbors[v].index(u)
        yield from (self.neighbors[v][(pivot+rot*i)%3] for i in range(3))

    def expand_tree(self, v, u, rot):
        visited = [v]
        queue = deque((w,v) for w in self.iter_neighbors(v, u, rot))
        while queue:
            w, p = queue.popleft()
            if w in visited:
                continue
            visited += [w]
            queue += [(q, w) for q in self.iter_neighbors(w, p, rot) if q != w]
        return visited

    def iter_automorphism(self):
        if not self.morphs:
            base = None
            for v, u in self.pairs:
                for rot in [1,-1]:
                    tree = self.expand_tree(v, u, rot)
                    if base is None:
                        base = tree
                    self.morphs += [[v for _, v in sorted(zip(base, tree))]]
        yield from self.morphs

    @staticmethod
    def shift_color(c, k):
        return [
            [0,1,2,3], [0,2,3,1], [0,3,1,2],
            [0,1,3,2], [0,2,1,3], [0,3,2,1],
        ][k][c]

    def transform(self, morph, co_shift):
        dodec = Dodecahedron(0)
        for u, v in self.pairs:
            c = self.shift_color(self.get_color(self.edges[u,v]), co_shift)
            dodec = dodec.set_color(self.edges[morph[u],morph[v]], c)
        return dodec

    def canonical_repr(self):
        return min( self.transform(m, s) for m in self.iter_automorphism()
                                         for s in range(6) )

    # ------------------------------------------------------------------------

    def extract_occurrences(self):
        occurs = []
        for v in range(20):
            uncolored = sum(self.get_color(self.edges[u,v]) == 0 for u in self.neighbors[v])
            if uncolored == 0:
                continue
            occurs += [(uncolored, v)]
        occurs.sort(reverse=True)
        return occurs

    def info_spec(self, v):
        return [(self.get_color(self.edges[u,v]), u) for u in self.neighbors[v]]

    def info_exists(self, spec):
        return {c for c, _ in spec if c != 0}

    def info_missing(self, spec):
        return {1,2,3} - self.info_exists(spec)

    def info_holes(self, spec):
        return [u for c, u in spec if c == 0]

    def search(self):
        dodec = self
        occurs = dodec.extract_occurrences()
        while occurs and occurs[-1][0] == 1:
            _, v = occurs.pop()
            co_v = dodec.info_spec(v)
            [c] = dodec.info_missing(co_v)
            [u] = dodec.info_holes(co_v)
            co_u = dodec.info_spec(u)
            if c in dodec.info_exists(co_u):
                return
            dodec = dodec.set_color(dodec.edges[u,v], c)
            occurs = dodec.extract_occurrences()
        if not occurs:
            yield dodec
            return
        _, v = occurs.pop()
        co_v = dodec.info_spec(v)
        [u, *_] = dodec.info_holes(co_v)
        co_u = dodec.info_spec(u)
        for c in dodec.info_missing(co_v):
            if c in dodec.info_exists(co_u):
                continue
            recur_dodec = dodec.set_color(dodec.edges[u,v], c)
            yield from recur_dodec.search()

    def canon_search(self):
        return {dodec.canonical_repr() for dodec in self.search()}

# ============================================================================

dodecs = list(Dodecahedron().search())
n = len(dodecs)
nr = 2
nc = n // nr
for i in range(nr):
    for columns in zip(*[dodecs[nc*i+j].draw_line_by_line() for j in range(nc)]):
        for col in columns:
            print(col, end='      ')
        print()
    print('\n')

print('=========================================================================================\n\n')

[dodec] = Dodecahedron().canon_search()
dodec.draw()