# How Voting Systems Work 8, Exercise 2: rank three districts by Polsby-Popper
# Assumed shapes made of unit squares (row, col), all 12 cells in area.
from math import pi

def polsby_popper(cells):
    cells = set(cells)
    perimeter = sum((r + dr, c + dc) not in cells
                    for r, c in cells for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
    return 4 * pi * len(cells) / perimeter ** 2, perimeter

shapes = {
    "3x4 block": [(r, c) for r in range(3) for c in range(4)],
    "L shape": [(r, 0) for r in range(8)] + [(7, c) for c in range(1, 5)],
    "staircase": [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 5), (5, 5), (5, 6)],
}
for name, cells in sorted(shapes.items(), key=lambda kv: -polsby_popper(kv[1])[0]):
    score, perimeter = polsby_popper(cells)
    print(f"{name:<10} cells {len(cells)}  perimeter {perimeter:>2}  Polsby-Popper {score:.3f}")

# Output when run:
# 3x4 block  cells 12  perimeter 14  Polsby-Popper 0.769
# L shape    cells 12  perimeter 26  Polsby-Popper 0.223
# staircase  cells 12  perimeter 26  Polsby-Popper 0.223