"""
Try to construct a 5-day schedule using a more targeted approach.
We represent the schedule as a 5×24 matrix where entry (d,p) ∈ {0,1,2,3}
is the boat of person p on day d.

We search using a combination of algebraic construction and local optimization.
"""

import itertools
import random
import math
from collections import defaultdict, Counter

N = 24
BOAT_SIZE = 6
BOATS_PER_DAY = 4
DAYS = 5
TOTAL_PAIRS = math.comb(N, 2)

def matrix_to_schedule(M):
    """Convert 5×24 matrix to schedule (list of days, each day is 4 tuples of 6)."""
    schedule = []
    for d in range(DAYS):
        boats = [[] for _ in range(BOATS_PER_DAY)]
        for p in range(N):
            boats[M[d][p]].append(p)
        schedule.append([tuple(sorted(boats[b])) for b in range(BOATS_PER_DAY)])
    return schedule

def schedule_to_matrix(schedule):
    """Convert schedule to 5×24 matrix."""
    M = [[0]*N for _ in range(DAYS)]
    for d, day in enumerate(schedule):
        for b, boat in enumerate(day):
            for p in boat:
                M[d][p] = b
    return M

def count_pairs(M):
    """Count distinct pairs covered."""
    pairs = set()
    for d in range(DAYS):
        for b in range(BOATS_PER_DAY):
            people = [p for p in range(N) if M[d][p] == b]
            pairs.update(itertools.combinations(people, 2))
    return len(pairs)

def check_valid(M):
    """Check the matrix is valid (each symbol appears 6 times per row)."""
    for d in range(DAYS):
        counts = Counter(M[d])
        if set(counts.values()) != {6}:
            return False
    return True

# Let me try a completely different approach:
# Use the concept of "mutually orthogonal Latin squares" (MOLS)
# 
# 4 MOLS of order 4 give us an affine plane of order 4, which has 
# 16 points, 4 parallel classes of 4 lines each... but we need 24 points.
# 
# Instead, let me try to directly search using a smarter representation.
# 
# Each person is assigned a 5-bit vector (or 5-digit base-4).
# The condition "no two at distance 5" is equivalent to 
# "the code has covering radius..."
# 
# Actually, let me try to use the finite field GF(4) and GF(6).
# We have 24 = 4 * 6 elements.
# 
# Let people be (a, b) where a ∈ GF(4), b ∈ GF(6) (but GF(6) doesn't exist).
# 
# OK, let's use Z_4 × Z_6 with people labeled (x,y) where x∈{0,1,2,3}, y∈{0,1,2,3,4,5}.
#
# Let me define 5 partitions based on functions f_i: Z_4 × Z_6 → Z_4.
#
# f_0(x,y) = x  (by first coordinate)
# f_1(x,y) = (x + y) mod 4
# f_2(x,y) = (x + 2y) mod 4
# f_3(x,y) = (x + 3y) mod 4
# f_4(x,y) = ???  We need something that gives balanced 4 groups and covers remaining pairs.

# Let's analyze more carefully what pairs are covered by f_0..f_3
# and see if we can find f_4.

def analyze_z4z6():
    """Analyze the Z_4 × Z_6 construction."""
    people = [(x, y) for x in range(4) for y in range(6)]
    
    # Maps for first 4 days
    maps = [
        ("f0 (by x)", lambda x, y: x),
        ("f1 (x+y)", lambda x, y: (x + y) % 4),
        ("f2 (x+2y)", lambda x, y: (x + 2*y) % 4), 
        ("f3 (x+3y)", lambda x, y: (x + 3*y) % 4),
    ]
    
    all_pairs = set()
    for name, f in maps:
        groups = defaultdict(list)
        for x, y in people:
            groups[f(x, y)].append((x, y))
        
        pairs = set()
        for g in groups.values():
            # Convert (x,y) to indices
            indices = [6*x + y for x, y in g]  # person = 6*x + y
            pairs.update(itertools.combinations(indices, 2))
        
        all_pairs.update(pairs)
        print(f"{name}: {len(pairs)} pairs, {len(groups[0])} per group")
        for g_idx, members in groups.items():
            print(f"  Group {g_idx}: {sorted(members)}")
    
    print(f"\nTotal distinct pairs covered by first 4 days: {len(all_pairs)}")
    print(f"Missing: {TOTAL_PAIRS - len(all_pairs)}")
    
    # What are the missing pairs?
    all_possible = set(itertools.combinations(range(N), 2))
    missing = all_possible - all_pairs
    print(f"Missing pairs: {sorted(list(missing)[:30])}...")
    
    # Convert missing pairs to (x,y) coordinates
    missing_xy = []
    for p, q in missing:
        x1, y1 = p // 6, p % 6
        x2, y2 = q // 6, q % 6
        missing_xy.append(((x1, y1), (x2, y2)))
    
    print("\nMissing pairs analysis:")
    # Group by (x1, x2) differences
    diff_counter = Counter()
    for (x1, y1), (x2, y2) in missing_xy:
        diff = (x1 - x2) % 4, y1 - y2
        diff_counter[diff] += 1
    for diff, count in sorted(diff_counter.items(), key=lambda x: -x[1]):
        print(f"  diff x={diff[0]}, y={diff[1]}: {count} pairs")
    
    # Try to find f_4
    print("\nSearching for f_4...")
    # f_4(x,y) = (ax + by + c) mod 4 for some a, b, c
    # Need each residue to appear exactly 6 times.
    # Since there are 24 people, if the function is affine and b is odd,
    # then each residue appears 24/4 = 6 times.
    # (Because for each x, as y varies over 0..5, (ax+by+c) mod 4 cycles through...)
    # Actually, we need the function to be surjective and balanced.
    
    best_new = 0
    best_f4 = None
    
    # Try different linear functions: f(x,y) = (a*x + b*y + c) % 4
    for a in range(4):
        for b in range(1, 4):
            if b % 2 == 0:
                continue  # b must be odd for balance
            for c in range(4):
                f = lambda x, y, a=a, b=b, c=c: (a*x + b*y + c) % 4
                
                # Check balance
                groups = defaultdict(list)
                for x, y in people:
                    groups[f(x, y)].append((x, y))
                
                if all(len(g) == 6 for g in groups.values()):
                    # Count new pairs covered
                    pairs = set()
                    for g in groups.values():
                        indices = [6*x + y for x, y in g]
                        pairs.update(itertools.combinations(indices, 2))
                    
                    new_pairs = len(pairs - all_pairs)
                    if new_pairs > best_new:
                        best_new = new_pairs
                        best_f4 = (a, b, c, pairs)
                        print(f"  f(x,y) = ({a}x + {b}y + {c}) mod 4: {new_pairs} new pairs")
                        
                        if new_pairs == len(missing):
                            print("  FOUND! This completes the coverage.")
                            return (a, b, c, pairs)

analyze_z4z6()