"""
Permutation-based search for 6-day schedule.
Each day is a permutation π of {0..23}. Boats = π({0..5}), π({6..11}), π({12..17}), π({18..23}).

Two people meet when their permuted values fall in the same block of size 6.
"""
import itertools
import math
import random as rnd
import json

N = 24
TOTAL_PAIRS = math.comb(N, 2)

BLOCKS = [set(range(i*6, (i+1)*6)) for i in range(4)]

def pairs_covered_by_perm(perm):
    """Return set of pairs covered by one permutation-day."""
    pairs = set()
    for b in range(4):
        group = [i for i in range(N) if perm[i] // 6 == b]
        pairs.update(itertools.combinations(group, 2))
    return pairs

def count_pairs_from_perms(perms):
    pairs = set()
    for perm in perms:
        for b in range(4):
            group = [i for i in range(N) if perm[i] // 6 == b]
            pairs.update(itertools.combinations(group, 2))
    return len(pairs)

def perms_to_schedule(perms):
    """Convert list of 6 permutations to schedule."""
    schedule = []
    for perm in perms:
        boats = [[] for _ in range(4)]
        for i in range(N):
            boats[perm[i] // 6].append(i)
        schedule.append([tuple(sorted(b)) for b in boats])
    return schedule

# Let's try a more powerful local search:
# Use the permutation representation and swap entries within permutations

# Start with the best schedule found so far (271/276)
# Let me just restart from scratch with more iterations

def random_perm():
    nums = list(range(N))
    rnd.shuffle(nums)
    return nums

def perturb_perm(perm):
    """Swap two random positions in a permutation."""
    perm = list(perm)
    i, j = rnd.sample(range(N), 2)
    perm[i], perm[j] = perm[j], perm[i]
    return perm

def local_search_permutations(restarts=20, iters_per_restart=100000):
    best_overall = 0
    best_perms = None
    
    for restart in range(restarts):
        perms = [random_perm() for _ in range(6)]
        cov = count_pairs_from_perms(perms)
        best_local = cov
        best_local_perms = [list(p) for p in perms]
        stuck = 0
        
        for it in range(iters_per_restart):
            # Pick a random day and perturb it
            d = rnd.randrange(6)
            new_perm = perturb_perm(perms[d])
            old_perm = perms[d]
            perms[d] = new_perm
            
            new_cov = count_pairs_from_perms(perms)
            
            if new_cov >= cov:
                cov = new_cov
                stuck = 0
                if cov > best_local:
                    best_local = cov
                    best_local_perms = [list(p) for p in perms]
                    print(f"  R{restart} I{it}: {cov}/{TOTAL_PAIRS}")
                    if cov == TOTAL_PAIRS:
                        print("\nFOUND!")
                        return perms
            else:
                perms[d] = old_perm
                stuck += 1
                if stuck > 20000:
                    # Random restart within
                    perms = [random_perm() for _ in range(6)]
                    cov = count_pairs_from_perms(perms)
                    stuck = 0
        
        print(f"Restart {restart}: best = {best_local}/{TOTAL_PAIRS}")
        if best_local > best_overall:
            best_overall = best_local
            best_perms = best_local_perms
    
    return best_perms

print("=== Permutation-based local search ===")
result = local_search_permutations(restarts=5, iters_per_restart=50000)

if result:
    cov = count_pairs_from_perms(result)
    print(f"\nBest found: {cov}/{TOTAL_PAIRS}")
    
    if cov == TOTAL_PAIRS:
        schedule = perms_to_schedule(result)
        print("\n=== SOLUTION ===")
        print(json.dumps(schedule))
    else:
        # Analyze missing pairs
        pairs = set()
        for perm in result:
            for b in range(4):
                group = [i for i in range(N) if perm[i] // 6 == b]
                pairs.update(itertools.combinations(group, 2))
        missing = set(itertools.combinations(range(N), 2)) - pairs
        print(f"\nMissing {len(missing)} pairs:")
        for p in sorted(missing)[:30]:
            print(f"  {p}")
        
        # Print schedule
        schedule = perms_to_schedule(result)
        print("\nSchedule:")
        for i, day in enumerate(schedule):
            print(f"  Day {i+1}: {day}")
        
        # Write to file for later analysis
        with open('/tmp/best_schedule.json', 'w') as f:
            json.dump(schedule, f)
        print("\n(Also saved to /tmp/best_schedule.json)")