import random
import math
import copy

# Define the standard QWERTY layout with coordinates, including space
STANDARD_QWERTY = [
    ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'],
    ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'],
    ['z', 'x', 'c', 'v', 'b', 'n', 'm'],
    [' ']  # Space bar in a separate row
]

# Create a list of positions based on the standard layout
def get_position_list(layout):
    positions = []
    for row_idx, row in enumerate(layout):
        for col_idx, key in enumerate(row):
            positions.append((col_idx, row_idx))
    return positions

POSITION_COORDS = get_position_list(STANDARD_QWERTY)

# Define parameters for the genetic algorithm
POPULATION_SIZE = 200    # Increased population size for better diversity
GENERATIONS = 1000
MUTATION_RATE = 0.2      # Increased mutation rate for more exploration
TOURNAMENT_SIZE = 5
ELITISM_COUNT = 5        # Number of top individuals to carry over to the next generation

# Function to calculate Euclidean distance between two positions
def distance(pos1, pos2):
    x1, y1 = pos1
    x2, y2 = pos2
    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

# Fitness function: lower total distance is better
def fitness(layout, text, position_coords):
    total_distance = 0
    # Map each key to its position based on the layout
    key_to_pos = {key: position_coords[idx] for idx, key in enumerate(layout)}

    for i in range(len(text) - 1):
        key1 = text[i]
        key2 = text[i + 1]
        if key1 in key_to_pos and key2 in key_to_pos:
            pos1 = key_to_pos[key1]
            pos2 = key_to_pos[key2]
            total_distance += distance(pos1, pos2)
        else:
            # Assign a large penalty if key not in layout
            total_distance += 100
    return total_distance

# Initialize population with random layouts
def initialize_population(characters, population_size):
    population = []
    for _ in range(population_size):
        individual = characters[:]
        random.shuffle(individual)
        population.append(individual)
    return population

# Selection: Tournament Selection with Elitism
def selection(population, fitnesses, tournament_size, elitism_count):
    # Sort population based on fitness
    sorted_population = [x for _, x in sorted(zip(fitnesses, population), key=lambda pair: pair[0])]
    # Elitism: carry the top individuals to the next generation
    elites = sorted_population[:elitism_count]
    selected = elites.copy()
    # Tournament selection for the rest
    while len(selected) < len(population):
        tournament = random.sample(list(zip(population, fitnesses)), tournament_size)
        tournament = sorted(tournament, key=lambda x: x[1])
        winner = copy.deepcopy(tournament[0][0])
        selected.append(winner)
    return selected

# Crossover: Partially Mapped Crossover (PMX) for better genetic diversity
def crossover(parent1, parent2):
    size = len(parent1)
    child1, child2 = [None]*size, [None]*size

    # Choose crossover points
    pt1, pt2 = sorted(random.sample(range(size), 2))

    # Create offspring by copying the slice from parents
    child1[pt1:pt2] = parent1[pt1:pt2]
    child2[pt1:pt2] = parent2[pt1:pt2]

    def fill_child(child, parent_other):
        for gene in parent_other[pt1:pt2]:
            if gene not in child:
                pos = parent_other.index(gene)
                while child[pos] is not None:
                    pos = parent_other.index(child[pos])
                child[pos] = gene
        # Fill remaining positions with genes from parent_other
        for gene in parent_other:
            if gene not in child:
                for i in range(size):
                    if child[i] is None:
                        child[i] = gene
                        break
        return child

    child1 = fill_child(child1, parent2)
    child2 = fill_child(child2, parent1)

    return child1, child2

# Mutation: Swap two keys
def mutate(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            j = random.randint(0, len(individual) - 1)
            individual[i], individual[j] = individual[j], individual[i]
    return individual

# Genetic Algorithm
def genetic_algorithm(text, position_coords, population_size, generations, mutation_rate, tournament_size, elitism_count):
    # Sanitize and prepare the characters to include in the keyboard
    text = text.lower()
    valid_chars = set('abcdefghijklmnopqrstuvwxyz ')
    sanitized_text = ''.join([c for c in text if c in valid_chars])
    characters = list(set(sanitized_text))
    if ' ' in sanitized_text and ' ' not in characters:
        characters.append(' ')
    # Ensure we have exactly the required number of keys, pad if necessary
    required_keys = len(position_coords)  # 27 positions (a-z and space)
    if len(characters) < required_keys:
        # Add random characters to fill
        while len(characters) < required_keys:
            char = random.choice('abcdefghijklmnopqrstuvwxyz ')
            if char not in characters:
                characters.append(char)
    elif len(characters) > required_keys:
        # Truncate to required keys
        characters = characters[:required_keys]

    # Initialize population
    population = initialize_population(characters, population_size)

    best_layout = None
    best_fitness = float('inf')

    for gen in range(1, generations + 1):
        # Evaluate fitness
        fitnesses = [fitness(ind, sanitized_text, position_coords) for ind in population]

        # Find the best in current population
        min_fitness = min(fitnesses)
        if min_fitness < best_fitness:
            best_fitness = min_fitness
            best_layout = population[fitnesses.index(min_fitness)]
            print(f"Generation {gen}: Best Fitness = {best_fitness}")

        # Early stopping if perfect fitness is achieved
        if best_fitness == 0:
            print("Perfect layout found!")
            break

        # Selection with Elitism
        selected = selection(population, fitnesses, tournament_size, elitism_count)

        # Crossover to produce offspring
        offspring = []
        for i in range(0, population_size - elitism_count, 2):
            parent1 = selected[i]
            parent2 = selected[i + 1] if i + 1 < population_size - elitism_count else selected[0]
            child1, child2 = crossover(parent1, parent2)
            offspring.extend([child1, child2])

        # Add elites to the offspring
        offspring.extend(selected[:elitism_count])

        # Mutation
        population = [mutate(child, mutation_rate) for child in offspring]

    return best_layout, best_fitness

# Example usage
if __name__ == "__main__":
    # Example text
    text = "hello world this is an example text to optimize the keyboard layout using genetic algorithm and the quick brown fox jumps over the lazy dog"

    # Get position coordinates based on the standard layout
    position_coords = POSITION_COORDS

    # Run genetic algorithm
    best_layout, best_fitness = genetic_algorithm(
        text=text,
        position_coords=position_coords,
        population_size=200,        # Increased population size for better diversity
        generations=1000,
        mutation_rate=0.2,           # Increased mutation rate for more exploration
        tournament_size=5,
        elitism_count=5
    )

    # Define row lengths for visualization, including the space bar
    row_lengths = [10, 9, 7, 1]  # Adjusted to include the space

    print("\nBest Keyboard Layout:")
    # Arrange the best layout back to QWERTY rows
    output_layout = []
    idx = 0
    for length in row_lengths:
        row = best_layout[idx:idx + length]
        output_layout.append(row)
        idx += length
    for row in output_layout:
        print(' '.join(row))
    print(f"\nBest Fitness (Total Distance): {best_fitness}") // Explain what this code does.