"""Reproduce Table 2 using triangle vertices and side lengths. Run with Python 3.""" from collections import Counter from math import isqrt DATA = [ "00+ 01+ 02+ 00- 01- 11+ 10- 20+", "01+ 00- 01- 11+ 11- 21+ 21- 31+", "01+ 00- 01- 10+ 11+ 11- 21+ 21-", "01+ 01- 11+ 10- 11- 21+ 20- 21-", "00- 01- 10+ 11+ 10- 11- 21+ 21-", ] def cell(i, j, half): corner = (i, j) if half == "+" else (i + 1, j + 1) return tuple(sorted((corner, (i + 1, j), (i, j + 1)))) def orientations(shape): result = set() current = shape for _ in range(6): for flip in (False, True): transformed = [tuple((x + y, -y) if flip else (x, y) for x, y in t) for t in current] xmin = min(x for t in transformed for x, y in t) ymin = min(y for t in transformed for x, y in t) result.add(tuple(sorted(tuple(sorted((x - xmin, y - ymin) for x, y in t)) for t in transformed))) current = [tuple((-y, x + y) for x, y in t) for t in current] return sorted(result) SHAPES = [orientations([cell(int(i), int(j), half) for i, j, half in line.split()]) for line in DATA] def boards(area): result = {} for a in range(1, area + 1): for b in range(1, area + 1): for lo in range(min(a, b) + 1): sq = 2 * a * b - lo * lo - area if sq < 0: continue hi = isqrt(sq) if hi * hi != sq or hi > min(a, b): continue sides = (a - lo, b - hi, hi, a - hi, b - lo, lo) orbit = [t[s:] + t[:s] for t in (sides, sides[::-1]) for s in range(6)] result.setdefault(min(orbit), (a, b, lo, hi)) return sorted(result.values()) def packing_counts(q): a, b, lo, hi = q board = {} for i in range(a): for j in range(b): for half in ("+", "-"): t = cell(i, j, half) if all(lo <= x + y <= a + b - hi for x, y in t): board[t] = 1 << len(board) assert len(board) == 2 * a * b - lo * lo - hi * hi options = [] for shape in SHAPES: masks = set() for oriented in shape: for dx in range(a): for dy in range(b): translated = [tuple((x + dx, y + dy) for x, y in t) for t in oriented] if all(t in board for t in translated): masks.add(sum(board[t] for t in translated)) options.append(sorted(masks)) counts = [0] * 6 def count(used, depth): counts[depth] += 1 if depth < 5: for mask in options[depth]: if not mask & used: count(used | mask, depth + 1) count(0, 0) return counts if __name__ == "__main__": assert len({s[0] for s in SHAPES}) == 5 expected = { 40: [8, 159, 1840, 7622, 1836, 0], 41: [3, 63, 755, 3228, 942, 0], 42: [4, 66, 806, 3382, 1808, 0], 43: [5, 102, 1489, 8005, 3730, 5], } for area in (40, 41, 42, 43): total = Counter() for q in boards(area): c = packing_counts(q) if q == (4, 6, 1, 2): assert c == [1, 36, 535, 2887, 1468, 5] else: assert c[-1] == 0 total.update(dict(enumerate(c))) print(q, c) totals = [total[k] for k in range(6)] assert totals == expected[area] print("AREA", area, "totals", totals)