files / problems / kissing-5d / compute / q6 / five_star_census.py

2.1 KB · on GitHub

#!/usr/bin/env python3
"""Census of 5-star unions after 4-star leftover.

A leftover 41-set whose U is not contained in any 4-star union has
star-cover at least 5.  This file only counts 5-star unions and the
seeds they contain.  It does not search extras.
"""

from __future__ import annotations

import json
import sys
from collections import Counter
from itertools import combinations
from pathlib import Path

HERE = Path(__file__).resolve().parent
sys.path.insert(0, str(HERE.parent / "q4"))
sys.path.insert(0, str(HERE.parent))

from sphere import extras_and_groups  # noqa: E402


def stars_of(D):
    out = []
    for i in range(5):
        for s in (-1, 1):
            bits = 0
            for j, r in enumerate(D):
                if r[i] == s * 4:
                    bits |= 1 << j
            out.append(bits)
    return out


def main() -> int:
    G = extras_and_groups(4)
    D = G["D"]
    seeds = list(G["groups"])
    stars = stars_of(D)
    hist = Counter()
    n_promising = 0
    max_ns = 0
    for comb in combinations(range(10), 5):
        U = 0
        for i in comb:
            U |= stars[i]
        k = U.bit_count()
        ns = sum(1 for m in seeds if m & ~U == 0)
        hist[(k, ns)] += 1
        if ns >= k + 1 and k >= 19:
            n_promising += 1
        if ns > max_ns:
            max_ns = ns
    pairs = [
        {"k": k, "n_seeds": ns, "n_pools": c, "promising": ns >= k + 1 and k >= 19}
        for (k, ns), c in sorted(hist.items())
    ]
    report = {
        "n_pools": 252,
        "pairs": pairs,
        "n_promising_by_part_count": n_promising,
        "max_seeds_in_a_pool": max_ns,
        "found_41": False,
        "comment": (
            "Census only.  A 5-star union can contain enough seeds to "
            "be promising by part-count; that is not a 41-code."
        ),
    }
    (HERE / "five_star_census.json").write_text(json.dumps(report, indent=2) + "\n")
    print(json.dumps({
        "n_pools": 252,
        "n_promising": n_promising,
        "max_ns": max_ns,
        "pairs": pairs,
    }, indent=2))
    return 0


if __name__ == "__main__":
    raise SystemExit(main())