# How Voting Systems Work 8, Exercise 3: which voter layout gives the map-drawer most power?
# Assumed model: 9 of the 16 blocks vote A, placed at random (seeded); count seats over all 117 maps.
import random
from itertools import product

SIZE, PER = 4, 4

def neighbours(cell):
    r, c = cell
    return [(r + dr, c + dc) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))
            if 0 <= r + dr < SIZE and 0 <= c + dc < SIZE]

def pieces_from(start, free):
    frontier = {frozenset([start])}
    for _ in range(PER - 1):
        frontier = {p | {n} for p in frontier for cell in p
                    for n in neighbours(cell) if n in free and n not in p}
    return frontier

def all_maps(free=None):
    free = frozenset(product(range(SIZE), repeat=2)) if free is None else free
    if not free:
        yield []
        return
    for piece in pieces_from(min(free), free):
        for rest in all_maps(free - piece):
            yield [piece] + rest

maps = list(all_maps())
cells = list(product(range(SIZE), repeat=2))
random.seed(31)
best = None
for trial in range(1, 9):
    a_cells = set(random.sample(cells, 9))
    tally = {}
    for plan in maps:
        s = sum(sum(c in a_cells for c in d) > PER // 2 for d in plan)
        tally[s] = tally.get(s, 0) + 1
    spread = max(tally) - min(tally)
    print(f"layout {trial}: A seats range {min(tally)}-{max(tally)}  {dict(sorted(tally.items()))}")
    if best is None or spread > best[0]:
        best = (spread, trial, a_cells)
print("widest range: layout", best[1])
for r in range(SIZE):
    print("".join("A" if (r, c) in best[2] else "B" for c in range(SIZE)))

# Output when run:
# layout 1: A seats range 1-3  {1: 68, 2: 47, 3: 2}
# layout 2: A seats range 1-3  {1: 28, 2: 84, 3: 5}
# layout 3: A seats range 1-2  {1: 56, 2: 61}
# layout 4: A seats range 1-3  {1: 40, 2: 76, 3: 1}
# layout 5: A seats range 1-2  {1: 53, 2: 64}
# layout 6: A seats range 1-3  {1: 26, 2: 86, 3: 5}
# layout 7: A seats range 1-3  {1: 17, 2: 84, 3: 16}
# layout 8: A seats range 1-2  {1: 46, 2: 71}
# widest range: layout 1
# AAAB
# BBAA
# BBAB
# AABA