"""Strong local search for the MINIMUM number of uncovered pairs with D=5.
Targeted moves (fix an uncovered pair by swapping) + annealing + reheats.
The proven lower bound is 8; we see how close we get."""
import random
from itertools import combinations
from lib import all_pairs

N, BOATS, SIZE, DAYS = 24, 4, 6, 5
NEED = all_pairs()

def counts(sched):
    c = {}
    for day in sched:
        for boat in day:
            for a, b in combinations(sorted(boat), 2):
                c[(a, b)] = c.get((a, b), 0) + 1
    return c

def rand_day(rng):
    p = list(range(N)); rng.shuffle(p)
    return [p[i*SIZE:(i+1)*SIZE] for i in range(BOATS)]

def boat_index(day):
    bi = {}
    for k, boat in enumerate(day):
        for p in boat: bi[p] = k
    return bi

def apply_swap(sched, cnt, d, b1, i, b2, j):
    p, q = sched[d][b1][i], sched[d][b2][j]
    b1r = [sched[d][b1][k] for k in range(SIZE) if k != i]
    b2r = [sched[d][b2][k] for k in range(SIZE) if k != j]
    for x in b1r:
        k = (min(p,x),max(p,x)); cnt[k]-=1
        if cnt[k]==0: del cnt[k]
    for x in b2r:
        k = (min(q,x),max(q,x)); cnt[k]-=1
        if cnt[k]==0: del cnt[k]
    for x in b1r:
        k=(min(q,x),max(q,x)); cnt[k]=cnt.get(k,0)+1
    for x in b2r:
        k=(min(p,x),max(p,x)); cnt[k]=cnt.get(k,0)+1
    sched[d][b1][i], sched[d][b2][j] = q, p

def swap_delta_missing(sched, cnt, d, b1, i, b2, j):
    p, q = sched[d][b1][i], sched[d][b2][j]
    b1r = [sched[d][b1][k] for k in range(SIZE) if k != i]
    b2r = [sched[d][b2][k] for k in range(SIZE) if k != j]
    dm = 0
    rem = [(p,x) for x in b1r] + [(q,x) for x in b2r]
    add = [(q,x) for x in b1r] + [(p,x) for x in b2r]
    # net per pair
    delta = {}
    for a,x in rem:
        k=(min(a,x),max(a,x)); delta[k]=delta.get(k,0)-1
    for a,x in add:
        k=(min(a,x),max(a,x)); delta[k]=delta.get(k,0)+1
    for k,dv in delta.items():
        old=cnt.get(k,0); new=old+dv
        if old==0 and new>0: dm-=1
        if old>0 and new==0: dm+=1
    return dm

def run(seed, iters=1500000):
    rng = random.Random(seed)
    sched = [rand_day(rng) for _ in range(DAYS)]
    cnt = counts(sched)
    cur = len(NEED - set(cnt.keys()))
    best = cur
    T = 2.5
    for it in range(iters):
        if cur <= 8:    # hit the proven bound
            break
        # targeted: with prob, pick an uncovered pair and try to unite them
        if rng.random() < 0.7:
            uncovered = list(NEED - set(cnt.keys()))
            p, q = rng.choice(uncovered)
            d = rng.randrange(DAYS)
            bi = boat_index(sched[d])
            bp, bq = bi[p], bi[q]
            if bp == bq:
                d2 = rng.randrange(DAYS); b1,b2 = rng.sample(range(BOATS),2)
                i,j = rng.randrange(SIZE), rng.randrange(SIZE)
            else:
                # move q into p's boat: swap q with some member of bp
                i = sched[d][bp].index(p)
                # pick a slot in bp to swap out (not p)
                slot = rng.choice([k for k in range(SIZE) if sched[d][bp][k]!=p])
                b1,b2,d2 = bq, bp, d
                i = sched[d][bq].index(q)
                j = slot
                b1,b2 = bq, bp
        else:
            d2 = rng.randrange(DAYS); b1,b2 = rng.sample(range(BOATS),2)
            i,j = rng.randrange(SIZE), rng.randrange(SIZE)
        dm = swap_delta_missing(sched, cnt, d2, b1, i, b2, j)
        if dm <= 0 or rng.random() < pow(2.718, -dm / T):
            apply_swap(sched, cnt, d2, b1, i, b2, j)
            cur += dm
            best = min(best, cur)
        T *= 0.999997
        if T < 0.15:
            T = 1.2   # reheat
    return best

if __name__ == "__main__":
    overall = 999
    for seed in range(40):
        b = run(seed)
        overall = min(overall, b)
        if b <= 8:
            print(f"seed {seed}: reached {b} uncovered (== proven lower bound!)")
            break
        if b < 14:
            print(f"seed {seed}: best {b} uncovered")
    print("BEST uncovered over runs:", overall, " | proven lower bound: 8")