bang.py
6.4 kB · python · 209 lines
1import itertools2from itertools import product, permutations34# THE BANG56def corners(dimension):7 return list(product((0, 1), repeat=dimension))89def code_to_filled(code, cells):10 return frozenset(cells[i] for i in range(len(cells)) if (code >> i) & 1)1112def filled_to_code(filled, cells):13 return sum(1 << i for i, c in enumerate(cells) if c in filled)1415# SYMMETRY1617def symmetries(dimension):18 return [(perm, flips)19 for perm in permutations(range(dimension))20 for flips in product((0, 1), repeat=dimension)]2122def apply_symmetry(element, corner):23 perm, flips = element24 return tuple(corner[perm[i]] ^ flips[i] for i in range(len(corner)))2526def orbit_codes(filled, cells, group):27 out = set()28 for g in group:29 image = frozenset(apply_symmetry(g, c) for c in filled)30 out.add(filled_to_code(image, cells))31 return out3233# ALGEBRA - GF(2) ALGEBRAIC NORMAL FORM3435def anf_coefficients(filled, cells):36 dimension = len(cells[0])37 coeff = {c: (1 if c in filled else 0) for c in cells}38 for axis in range(dimension):39 for c in cells:40 if c[axis] == 1:41 lower = tuple(c[j] if j != axis else 0 for j in range(dimension))42 coeff[c] ^= coeff[lower]43 return coeff4445def algebraic_degree(filled, cells):46 coeff = anf_coefficients(filled, cells)47 return max([sum(c) for c in cells if coeff[c] == 1], default=-1)4849def anf_string(filled, cells):50 dimension = len(cells[0])51 coeff = anf_coefficients(filled, cells)52 names = ["x", "y", "z", "w", "v", "u"]53 terms = []54 for c in sorted(cells, key=lambda t: (sum(t), t)):55 if coeff[c] == 1:56 terms.append("1" if sum(c) == 0 else "".join(names[i] for i in range(dimension) if c[i]))57 return "+".join(terms) if terms else "0"5859# GENUS - WHICH KIND OF RULE6061def _level_set_aligned(filled, cells):62 by_popcount = {}63 for c in cells:64 by_popcount.setdefault(sum(c), set()).add(c in filled)65 if all(len(v) == 1 for v in by_popcount.values()):66 return tuple(sorted(pc for pc, v in by_popcount.items() if True in v))67 return None6869def _axis_pins_aligned(filled, cells):70 dimension = len(cells[0])71 for r in range(dimension + 1):72 for axes in itertools.combinations(range(dimension), r):73 predicted = frozenset(c for c in cells if all(c[a] == 0 for a in axes))74 if predicted == filled:75 return tuple(axes)76 return None7778def _orbit_members(filled, cells):79 dimension = len(cells[0])80 group = symmetries(dimension)81 out = set()82 for g in group:83 out.add(frozenset(apply_symmetry(g, c) for c in filled))84 return out8586def level_set(filled, cells):87 found = [_level_set_aligned(m, cells) for m in _orbit_members(filled, cells)]88 found = [f for f in found if f is not None]89 return min(found) if found else None9091def axis_pins(filled, cells):92 found = [_axis_pins_aligned(m, cells) for m in _orbit_members(filled, cells)]93 found = [f for f in found if f is not None]94 return min(found) if found else None9596def genus(filled, cells):97 if level_set(filled, cells) is not None:98 return "iso"99 if axis_pins(filled, cells) is not None:100 return "axis"101 return "compound"102103# INDEX WIDTH104105def index_width(dimension):106 return len(str(2 ** (2 ** dimension) - 1))107108# THE DESIGN109110class Design:111112 def __init__(self, code, dimension, cells, canonical=None, class_rep=None, orbit_size=None):113 self.i = code114 self.dimension = dimension115 self._cells = cells116 self.filled = code_to_filled(code, cells)117 self.canonical = canonical118 self.class_rep = class_rep119 self.orbit_size = orbit_size120121 @property122 def name(self):123 return f"mrly_{self.i:0{index_width(self.dimension)}d}"124125 def parity_rule(self):126 return sorted(self.filled)127128 def degree(self):129 return algebraic_degree(self.filled, self._cells)130131 def anf(self):132 return anf_string(self.filled, self._cells)133134 def genus(self):135 return genus(self.filled, self._cells)136137 def level_set(self):138 return level_set(self.filled, self._cells)139140 def axis_pins(self):141 return axis_pins(self.filled, self._cells)142143 def metadata(self):144 ls = self.level_set()145 ax = self.axis_pins()146 return {147 "name": self.name,148 "i": self.i,149 "dimension": self.dimension,150 "parity_rule": [list(c) for c in self.parity_rule()],151 "genus": self.genus(),152 "level_set_S": list(ls) if ls is not None else None,153 "axis_pins": list(ax) if ax is not None else None,154 "degree": self.degree(),155 "anf": self.anf(),156 "canonical": self.canonical,157 "class_rep": self.class_rep,158 "orbit_size": self.orbit_size,159 }160161 def __repr__(self):162 flag = "*" if self.canonical else " "163 return f"<{self.name}{flag} d={self.dimension} {self.genus()} deg={self.degree()} anf={self.anf()}>"164165# THE UNIVERSE - ONE BANG PER DIMENSION166167class Universe:168169 def __init__(self, dimension):170 self.dimension = dimension171 self._cells = corners(dimension)172 self.total = 2 ** (2 ** dimension)173 self._group = symmetries(dimension)174 self._class_of = {}175 self._first_of_class = {}176 self._orbit_size = {}177 self._bang()178179 def _bang(self):180 for code in range(self.total):181 filled = code_to_filled(code, self._cells)182 orbit = orbit_codes(filled, self._cells, self._group)183 rep = min(orbit)184 self._class_of[code] = rep185 self._orbit_size[code] = len(orbit)186 if rep not in self._first_of_class:187 self._first_of_class[rep] = code188189 def _is_canonical(self, code):190 return self._first_of_class[self._class_of[code]] == code191192 def design(self, code):193 rep_code = self._first_of_class[self._class_of[code]]194 return Design(code, self.dimension, self._cells,195 canonical=self._is_canonical(code),196 class_rep=rep_code,197 orbit_size=self._orbit_size[code])198199 def all(self):200 return [self.design(code) for code in range(self.total)]201202 def canonical(self):203 return [d for d in self.all() if d.canonical]204205 def distinct_count(self):206 return len(self._first_of_class)207208def bang(dimension):209 return Universe(dimension)