"""
Genetic algorithm approach - maintain a population of candidate schedules
and evolve them through crossover and mutation.
"""
import itertools, math, random as rnd, json, sys

N = 24
TOTAL = 276
POP_SIZE = 100

def norm(p,q): return (min(p,q), max(p,q))

def count_pairs(sched):
    pairs = set()
    for day in sched:
        for b in day:
            pairs.update(norm(p,q) for p,q in itertools.combinations(b, 2))
    return len(pairs)

def random_schedule():
    nums = list(range(N))
    return [[tuple(sorted(rnd.sample(nums, 6))) for _ in range(4)] 
            for _ in range(6)]

def mutate(sched):
    """Swap two random elements from different boats on a random day."""
    sched = [list(d) for d in sched]
    d = rnd.randrange(6)
    day = [list(b) for b in sched[d]]
    b1, b2 = rnd.sample(range(4), 2)
    p1, p2 = rnd.randrange(6), rnd.randrange(6)
    day[b1][p1], day[b2][p2] = day[b2][p2], day[b1][p1]
    sched[d] = [tuple(sorted(b)) for b in day]
    return sched

def mutate_aggressive(sched):
    """Replace a random day entirely."""
    sched = [list(d) for d in sched]
    d = rnd.randrange(6)
    nums = list(range(N))
    rnd.shuffle(nums)
    sched[d] = [tuple(sorted(nums[i*6:(i+1)*6])) for i in range(4)]
    return sched

# Start with a population of random schedules + the best known
print("=== Genetic Algorithm for 6-day schedule ===")

# Seed with best known
best_known = [
    [(5, 7, 9, 13, 21, 23), (11, 14, 15, 17, 18, 22), (4, 6, 10, 16, 19, 20), (0, 1, 2, 3, 8, 12)],
    [(8, 10, 12, 14, 15, 20), (1, 3, 5, 9, 13, 18), (0, 6, 11, 16, 19, 23), (2, 4, 7, 17, 21, 22)],
    [(5, 13, 14, 15, 16, 19), (1, 2, 3, 4, 11, 23), (0, 9, 10, 17, 20, 22), (6, 7, 8, 12, 18, 21)],
    [(3, 8, 16, 17, 19, 22), (2, 5, 10, 13, 18, 20), (0, 1, 7, 14, 15, 21), (4, 6, 9, 11, 12, 23)],
    [(0, 4, 5, 8, 11, 13), (1, 10, 17, 20, 22, 23), (7, 12, 16, 18, 19, 21), (2, 3, 6, 9, 14, 15)],
    [(0, 4, 14, 15, 18, 23), (1, 2, 8, 9, 16, 19), (5, 6, 12, 13, 17, 22), (3, 7, 10, 11, 20, 21)],
]

population = [best_known]
for _ in range(POP_SIZE - 1):
    population.append(random_schedule())

fitness = [count_pairs(s) for s in population]
best_fit = max(fitness)
best_idx = fitness.index(best_fit)
best_sched = population[best_idx]

print(f"Initial best: {best_fit}/{TOTAL}")

generation = 0
no_improve = 0

while no_improve < 200:
    generation += 1
    
    # Create new population
    new_pop = []
    
    # Keep the best (elitism)
    elite_count = max(1, POP_SIZE // 10)
    elite_indices = sorted(range(len(population)), key=lambda i: -fitness[i])[:elite_count]
    for idx in elite_indices:
        new_pop.append([list(d) for d in population[idx]])
    
    # Fill rest with offspring
    while len(new_pop) < POP_SIZE:
        # Tournament selection
        t1, t2 = rnd.sample(range(len(population)), 2)
        p1 = population[t1] if fitness[t1] > fitness[t2] else population[t2]
        t3, t4 = rnd.sample(range(len(population)), 2)
        p2 = population[t3] if fitness[t3] > fitness[t4] else population[t4]
        
        # Crossover: take some days from each parent
        child = []
        for d in range(6):
            if rnd.random() < 0.5:
                child.append([list(b) for b in p1[d]])
            else:
                child.append([list(b) for b in p2[d]])
        
        # Mutation
        if rnd.random() < 0.3:
            child = mutate(child)
        if rnd.random() < 0.05:
            child = mutate_aggressive(child)
        
        new_pop.append(child)
    
    population = new_pop
    fitness = [count_pairs(s) for s in population]
    
    max_fit = max(fitness)
    if max_fit > best_fit:
        best_fit = max_fit
        best_idx = fitness.index(max_fit)
        best_sched = [list(d) for d in population[best_idx]]
        no_improve = 0
        print(f"  Gen {generation}: {best_fit}/{TOTAL}")
        if best_fit == TOTAL:
            print("\nFOUND!")
            import json
            print(json.dumps(best_sched))
            sys.exit(0)
    else:
        no_improve += 1
    
    # Every 20 generations, inject some fresh blood
    if generation % 20 == 0:
        for i in range(POP_SIZE // 5):
            idx = rnd.randrange(POP_SIZE)
            population[idx] = random_schedule()
            fitness[idx] = count_pairs(population[idx])

print(f"\nBest: {best_fit}/{TOTAL}")
if best_fit > 274:
    print(f"Best schedule: {best_sched}")