files / problems / covering / compute / build_p28_partition.py
#!/usr/bin/env python3
"""Replay the certified merge chain from the r=28 p=64 partition to p=28."""
from __future__ import annotations
import argparse
from pathlib import Path
# Each entry contains the two disjoint block merges selected by the exact
# syndrome search in search_partition_merges.c. Labels are canonicalized
# after every entry, so these are labels at the indicated intermediate p.
MERGE_CHAIN = [
((0, 3), (1, 5)), # 64 -> 62
((0, 4), (1, 5)), # 62 -> 60
((0, 5), (1, 6)), # 60 -> 58
((0, 5), (1, 7)), # 58 -> 56
((0, 6), (1, 7)), # 56 -> 54
((0, 7), (2, 3)), # 54 -> 52
((2, 3), (4, 14)), # 52 -> 50
((2, 4), (3, 15)), # 50 -> 48
((4, 7), (6, 46)), # 48 -> 46
((7, 10), (8, 15)), # 46 -> 44
((10, 12), (11, 13)), # 44 -> 42
((10, 12), (13, 16)), # 42 -> 40
((13, 21), (14, 22)), # 40 -> 38
((15, 17), (16, 18)), # 38 -> 36
((15, 18), (16, 21)), # 36 -> 34
((17, 20), (23, 26)), # 34 -> 32
((22, 25), (23, 26)), # 32 -> 30
((22, 26), (24, 25)), # 30 -> 28
]
EXPECTED_BLOCK_SIZES = [
1584, 2889, 60, 541, 1398, 93, 77, 932, 167, 30, 3293, 232,
3728, 250, 182, 3277, 683, 136, 30, 930, 15, 465, 4194, 279,
135, 15, 465, 31,
]
def read_labels(path: Path) -> list[int]:
labels: list[int] = []
with path.open("r", encoding="utf-8") as handle:
for raw in handle:
line = raw.split("#", 1)[0]
labels.extend(int(token) for token in line.split())
return labels
def find(parent: list[int], value: int) -> int:
while parent[value] != value:
parent[value] = parent[parent[value]]
value = parent[value]
return value
def join(parent: list[int], left: int, right: int) -> None:
left = find(parent, left)
right = find(parent, right)
if left != right:
parent[right] = left
def merge_twice(
labels: list[int], blocks: int,
merges: tuple[tuple[int, int], tuple[int, int]],
) -> list[int]:
flat = [value for pair in merges for value in pair]
assert len(set(flat)) == 4
assert all(0 <= value < blocks for value in flat)
parent = list(range(blocks))
for left, right in merges:
join(parent, left, right)
root_label: dict[int, int] = {}
for block in range(blocks):
root = find(parent, block)
if root not in root_label:
root_label[root] = len(root_label)
assert len(root_label) == blocks - 2
return [root_label[find(parent, label)] for label in labels]
def main() -> None:
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument("--parent", type=Path, required=True)
parser.add_argument("--output", type=Path, required=True)
args = parser.parse_args()
labels = read_labels(args.parent)
assert len(labels) == 26111
assert sorted(set(labels)) == list(range(64))
blocks = 64
for merges in MERGE_CHAIN:
labels = merge_twice(labels, blocks, merges)
blocks -= 2
assert sorted(set(labels)) == list(range(blocks))
assert blocks == 28
sizes = [labels.count(block) for block in range(blocks)]
assert sizes == EXPECTED_BLOCK_SIZES
args.output.write_text(
"# Certified coarsening of partition_r28_n26111_p64.txt.\n"
"# Exact recursive merge search reduced 64 blocks to 28; no "
"minimality claim.\n"
"# Generated by compute/build_p28_partition.py.\n"
+ " ".join(str(label) for label in labels)
+ "\n",
encoding="utf-8",
)
print(
"built %s: labels=%d blocks=%d sizes=%s"
% (args.output, len(labels), blocks, ",".join(map(str, sizes)))
)
if __name__ == "__main__":
main()