#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
第940 — SGL_6(F_2) のハミルトン閉路の**独立検証器**。
Python 3 の標準ライブラリだけで動く（numpy 不要）。読むのは `sgl6_cycle_mat.txt` だけ。

`sgl6_cycle_mat.txt` の一行 = 一頂点 = 6×6 の F_2 上の対称行列を、
行ごとに 6 桁の 0/1 で（6 個を空白で区切って）印字したもの。

検査するもの（Orel 2015 の定義に照らして全数）:
  [1] 各行が対称であること
  [2] 各行が F_2 上で可逆であること（掃き出しで階数 6）
  [3] 行数 = |SGL_6(F_2)| = 888832 = 2^12 · 7 · 31 · ... （Orel の公式）
      全行が相異なり、集合として SGL_6(F_2) を尽くすこと
  [4] 階数 1 の対称行列がちょうど 63 個（= 2^6 − 1）であること
  [5] 閉路の各辺（末尾→先頭を含む 888832 本）で、差 A − B = A + B の階数が
      ちょうど 1 であること
"""
import sys
import time

t0 = time.time()
n = 6
FN = sys.argv[1] if len(sys.argv) > 1 else 'sgl6_cycle_mat.txt'


def rank_f2(rows):
    """6 本の 6 ビット整数の F_2 上の階数。"""
    rs = list(rows)
    r = 0
    for c in range(n):
        piv = -1
        for i in range(r, n):
            if (rs[i] >> c) & 1:
                piv = i
                break
        if piv < 0:
            continue
        rs[r], rs[piv] = rs[piv], rs[r]
        for i in range(n):
            if i != r and ((rs[i] >> c) & 1):
                rs[i] ^= rs[r]
        r += 1
    return r


def is_sym(rows):
    for i in range(n):
        for j in range(i + 1, n):
            if ((rows[i] >> j) & 1) != ((rows[j] >> i) & 1):
                return False
    return True


def key(rows):
    k = 0
    for i in range(n):
        k |= rows[i] << (n * i)
    return k


# ---------------------------------------------------------------- 読み込み
mats = []
for line in open(FN):
    line = line.strip()
    if not line:
        continue
    parts = line.split()
    assert len(parts) == n, line
    mats.append(tuple(int(p[::-1], 2) for p in parts))
print(f"[0] 入力 {FN} : {len(mats)} 行   ({time.time()-t0:.1f}s)")

nsym = sum(1 for m in mats if is_sym(m))
print(f"[1] 対称である行 = {nsym} / {len(mats)}")
ninv = sum(1 for m in mats if rank_f2(m) == n)
print(f"[1] 可逆である行（掃き出し） = {ninv} / {len(mats)}   ({time.time()-t0:.1f}s)")

# ---------------------------------------------------------------- 母集団
IDX = {}
b = 0
for i in range(n):
    for j in range(i, n):
        IDX[(i, j)] = b
        b += 1
NB = b
full = set()
rank1 = set()
for code in range(1 << NB):
    rows = [0] * n
    for (i, j), bit in IDX.items():
        if (code >> bit) & 1:
            rows[i] |= 1 << j
            rows[j] |= 1 << i
    rk = rank_f2(rows)
    if rk == n:
        full.add(key(rows))
    elif rk == 1:
        rank1.add(tuple(rows))
print(f"[2] |S_6(F_2)| = 2^{NB} = {1<<NB}")
print(f"[2] |SGL_6(F_2)| = {len(full)}   ({time.time()-t0:.1f}s)")

ks = [key(m) for m in mats]
print(f"[3] 行数 = |SGL_6(F_2)| : {len(mats) == len(full)}")
print(f"[3] 全行が相異なる      : {len(set(ks)) == len(ks)}")
print(f"[3] 行の集合 = SGL_6(F_2) : {set(ks) == full}")

# ---------------------------------------------------------------- 階数 1
print(f"[4] 階数 1 の対称行列の個数 = {len(rank1)}   (2^6 − 1 = 63)")

# 階数 1 の対称行列は x x^T の形（x ≠ 0）であることも確かめる
outer = set()
for x in range(1, 1 << n):
    rows = [0] * n
    for i in range(n):
        if (x >> i) & 1:
            rows[i] = x
    outer.add(tuple(rows))
print(f"[4] {{x x^T : x ≠ 0}} = 階数 1 の対称行列 : {outer == rank1}")

# ---------------------------------------------------------------- 辺
bad = 0
used = set()
for t in range(len(mats)):
    a = mats[t]
    b2 = mats[(t + 1) % len(mats)]
    d = tuple(a[i] ^ b2[i] for i in range(n))
    if rank_f2(d) != 1:
        bad += 1
    else:
        used.add(d)
print(f"[5] 閉路の辺の総数（末尾→先頭を含む） = {len(mats)}")
print(f"[5] 差 A + B の階数が 1 でない辺 = {bad} 本")
print(f"[5] 使われた階数 1 の元の種類 = {len(used)} / {len(rank1)}")

# ---------------------------------------------------------------- 次数
import random
random.seed(0)
degs = set()
for _ in range(100):
    m = mats[random.randrange(len(mats))]
    d = 0
    for s in rank1:
        w = tuple(m[i] ^ s[i] for i in range(n))
        if key(w) in full:
            d += 1
    degs.add(d)
print(f"[6] 無作為 100 頂点の次数の集合 = {sorted(degs)}   （SGL_6 は正則でない）")

ok = (nsym == len(mats) and ninv == len(mats) and len(mats) == len(full)
      and len(set(ks)) == len(ks) and set(ks) == full and bad == 0)
print(f"\n[判定] {'**合格**' if ok else '**不合格**'}  "
      f"頂点 {len(full)} / 行 {len(mats)} / 相異なる {len(set(ks))==len(ks)} / "
      f"集合一致 {set(ks)==full} / 悪い辺 {bad}")
print(f"所要 {time.time()-t0:.1f} 秒")