| """Validate a packing of n unit squares (possibly rotated) in the container [0, side]^2. |
| |
| Exact mode: side and every coordinate are Fraction/int and each direction (c, s) |
| satisfies c^2 + s^2 == 1 exactly (axis-aligned, or Pythagorean like 3/5, 4/5). |
| Then the verdict is a proof (eps = 0, no tolerance). |
| Float mode: verdict means "valid within eps"; NOT a proof. Worst violations are reported. |
| """ |
| from __future__ import annotations |
| from dataclasses import dataclass |
| from fractions import Fraction |
| import math |
|
|
| Num = object |
|
|
|
|
| @dataclass(frozen=True) |
| class Sq: |
| x: Num |
| y: Num |
| c: Num |
| s: Num |
|
|
|
|
| def _is_exact(v) -> bool: |
| return isinstance(v, (Fraction, int)) and not isinstance(v, bool) |
|
|
|
|
| def _radius(u, q: Sq): |
| """Half-extent of unit square q (edge dirs (c,s), (-s,c)) projected on unit axis u.""" |
| ux, uy = u |
| return (abs(ux * q.c + uy * q.s) + abs(-ux * q.s + uy * q.c)) / 2 |
|
|
|
|
| def penetration(a: Sq, b: Sq): |
| """Min overlap depth over the 4 separating axes. >0: interiors overlap; <=0: apart/touching.""" |
| dx, dy = b.x - a.x, b.y - a.y |
| axes = ((a.c, a.s), (-a.s, a.c), (b.c, b.s), (-b.s, b.c)) |
| return min(_radius(u, a) + _radius(u, b) - abs(dx * u[0] + dy * u[1]) for u in axes) |
|
|
|
|
| def outside_amount(q: Sq, side): |
| """How far q sticks out of [0, side]^2. <= 0 means inside.""" |
| h = (abs(q.c) + abs(q.s)) / 2 |
| return max(h - q.x, q.x + h - side, h - q.y, q.y + h - side) |
|
|
|
|
| def validate(squares, side, eps=None, expected_n=None, max_report=10): |
| n = len(squares) |
| exact = _is_exact(side) and all(_is_exact(v) for q in squares for v in (q.x, q.y, q.c, q.s)) |
| if exact: |
| side = Fraction(side) |
| squares = [Sq(*(Fraction(v) for v in (q.x, q.y, q.c, q.s))) for q in squares] |
| if eps is None: |
| eps = Fraction(0) if exact else 1e-9 |
| one = Fraction(1) if exact else 1.0 |
| unit_tol = 0 if exact else 1e-9 |
| bad, issues = 0, [] |
|
|
| def flag(msg): |
| nonlocal bad |
| bad += 1 |
| if len(issues) < max_report: |
| issues.append(msg) |
|
|
| if expected_n is not None and n != expected_n: |
| flag(f"expected {expected_n} squares, got {n}") |
| for i, q in enumerate(squares): |
| if abs(q.c * q.c + q.s * q.s - one) > unit_tol: |
| flag(f"square {i}: (c, s) is not a unit vector") |
|
|
| max_outside = 0 |
| for i, q in enumerate(squares): |
| o = outside_amount(q, side) |
| if o > eps: |
| flag(f"square {i}: outside container by {float(o):.3e}") |
| max_outside = max(max_outside, o) |
|
|
| max_overlap = 0 |
| order = sorted(range(n), key=lambda i: squares[i].x) |
| for pos, i in enumerate(order): |
| a = squares[i] |
| for j in order[pos + 1:]: |
| b = squares[j] |
| dx = b.x - a.x |
| if dx * dx > 2: |
| break |
| dy = b.y - a.y |
| if dx * dx + dy * dy > 2: |
| continue |
| p = penetration(a, b) |
| if p > eps: |
| flag(f"squares {i},{j}: overlap depth {float(p):.3e}") |
| max_overlap = max(max_overlap, p) |
|
|
| return {"valid": bad == 0, "mode": "exact" if exact else f"float(eps={eps})", |
| "proof": exact and bad == 0, "n": n, "max_overlap": float(max_overlap), |
| "max_outside": float(max_outside), "violations": bad, "issues": issues} |
|
|
|
|
| def parse_squares(items): |
| """items: list of dicts, one form for all squares. |
| Exact: {"x","y","c","s"} as ints/strings like "3/5". |
| Float: {"x","y","theta_rad"} or {"x","y","theta_deg"} (unit must be explicit; we never guess).""" |
| if not items: |
| return [] |
| if all("c" in d and "s" in d for d in items): |
| return [Sq(*(Fraction(str(d[k])) for k in ("x", "y", "c", "s"))) for d in items] |
| for key, conv in (("theta_rad", float), ("theta_deg", lambda v: math.radians(float(v)))): |
| if all(key in d for d in items): |
| out = [] |
| for d in items: |
| t = conv(d[key]) |
| out.append(Sq(float(d["x"]), float(d["y"]), math.cos(t), math.sin(t))) |
| return out |
| raise ValueError("use c/s, theta_rad, or theta_deg consistently for all squares") |
|
|
