"""Find a 6-day schedule covering all 276 pairs, via greedy + backtracking.
Day 1 is fixed to the four 'bands' to break symmetry."""
import random
from itertools import combinations
from lib import verify, all_pairs

N, BOATS, SIZE, DAYS = 24, 4, 6, 6


def day_new_pairs(day, covered):
    new = set()
    for boat in day:
        for a, b in combinations(sorted(boat), 2):
            if (a, b) not in covered:
                new.add((a, b))
    return new


def greedy_day(covered, rng, tries=400):
    """Build one partition (4 boats of 6) greedily maximizing new pairs."""
    best, best_score = None, -1
    for _ in range(tries):
        people = list(range(N))
        rng.shuffle(people)
        boats = [[] for _ in range(BOATS)]
        # assign people one by one to the boat (with space) that yields most new pairs
        order = people[:]
        for p in order:
            cand = [i for i in range(BOATS) if len(boats[i]) < SIZE]
            scored = []
            for i in cand:
                s = sum(1 for q in boats[i] if (min(p, q), max(p, q)) not in covered)
                scored.append((s, i))
            mx = max(s for s, _ in scored)
            choices = [i for s, i in scored if s == mx]
            boats[rng.randrange(len(choices))]  # noop for determinism style
            boats[rng.choice(choices)].append(p)
        score = len(day_new_pairs(boats, covered))
        if score > best_score:
            best_score, best = score, [b[:] for b in boats]
    return best, best_score


def build(seed=0):
    rng = random.Random(seed)
    # Day 1: bands
    day1 = [list(range(0, 6)), list(range(6, 12)), list(range(12, 18)), list(range(18, 24))]
    schedule = [day1]
    covered = set()
    for boat in day1:
        for a, b in combinations(boat, 2):
            covered.add((a, b))
    for d in range(1, DAYS):
        day, _ = greedy_day(covered, rng)
        schedule.append(day)
        for boat in day:
            for a, b in combinations(sorted(boat), 2):
                covered.add((a, b))
    return schedule, len(all_pairs() - covered)


if __name__ == "__main__":
    best_sched, best_missing = None, 999
    for seed in range(2000):
        sched, missing = build(seed)
        if missing < best_missing:
            best_missing = missing
            best_sched = sched
            print(f"seed {seed}: missing = {missing}")
            if missing == 0:
                break
    ok, info = verify(best_sched)
    print("FULL COVER:", ok, "| missing:", info['missing'],
          "| total meetings:", info['total_meetings'], "| excess:", info['repeat_excess'])
    if ok:
        import json
        zero = [[sorted(b) for b in day] for day in best_sched]
        with open("solution6_greedy.json", "w") as f:
            json.dump(zero, f)
        print("saved solution6_greedy.json")