# =========================================================
# Génération de la grille de roulement des TP en Python
# pour 18 à 36 élèves avec de 6 à 12 TP (en 6 à 12 séances)
# www.gecif.net
# Juin 2026
# =========================================================

import itertools
import random

# ==============================================================================
# CONFIGURATION DYNAMIQUE (Modifiez ces valeurs selon vos besoins)
# ==============================================================================
NB_ELEVES  = 18   # Choix possibles : 18, 21, 24, 27, 30, 33, 36
NB_SEANCES = 6    # Choix possibles : 6, 7, 8, 9, 10, 11, 12
# ==============================================================================

# Calcul automatique du nombre de TP requis (lignes)
NB_TP = NB_ELEVES // 3

# Génération des identifiants des élèves.
# Pour dépasser les 26 lettres de l'alphabet (A-Z), on utilise des numéros ("E01", "E02", etc.)
ELEVES = ["E{0:02d}".format(i + 1) for i in range(NB_ELEVES)]

# Génération de tous les trios possibles et mélange initial pour introduire de l'aléa
TRIOS_POSSIBLES = list(itertools.combinations(ELEVES, 3))
random.shuffle(TRIOS_POSSIBLES)

# Initialisation de la grille vide (NB_TP lignes x NB_SEANCES colonnes)
grille = [[None for _ in range(NB_SEANCES)] for _ in range(NB_TP)]


def est_valide(trio, ligne, col):
    """Vérifie les contraintes pour le trio dans la case (ligne, col)."""

    # 1. Contrainte Ligne (TP) : Un élève ne fait pas deux fois le même TP
    for c in range(NB_SEANCES):
        if grille[ligne][c] is not None:
            for eleve in trio:
                if eleve in grille[ligne][c]:
                    return False

    # 2. Contrainte Colonne (Séance) : Un élève ne fait pas deux TP en même temps
    for l in range(NB_TP):
        if grille[l][col] is not None:
            for eleve in trio:
                if eleve in grille[l][col]:
                    return False

    # 3. Contrainte de Non-Répétition des Duos (Brassage maximal)
    duos_du_trio = list(itertools.combinations(trio, 2))
    for l in range(NB_TP):
        for c in range(NB_SEANCES):
            if grille[l][c] is not None:
                if l == ligne and c == col:
                    continue
                for duo in duos_du_trio:
                    if duo[0] in grille[l][c] and duo[1] in grille[l][c]:
                        return False
    return True


def resoudre(index_case=0):
    """Algorithme de Backtracking généralisé."""
    total_cases = NB_TP * NB_SEANCES
    if index_case == total_cases:
        return True

    ligne = index_case // NB_SEANCES
    col = index_case % NB_SEANCES

    for trio in TRIOS_POSSIBLES:
        if est_valide(trio, ligne, col):
            grille[ligne][col] = trio

            if resoudre(index_case + 1):
                return True

            grille[ligne][col] = None # Backtrack

    return False


# --- EXÉCUTION ET AFFICHAGE ---
print("Recherche d'une solution pour {0} élèves, {1} TP et {2} séances...".format(NB_ELEVES, NB_TP, NB_SEANCES))

if resoudre():
    print("\n--- TABLEAU DE ROULEMENT GÉNÉRÉ ---")

    # Construction dynamique de l'en-tête des séances
    entete = "{0:<8} | ".format("")
    for s in range(NB_SEANCES):
        entete += "Séance {0:<3} | ".format(s + 1)
    print(entete)
    print("-" * (11 + (13 * NB_SEANCES)))

    # Affichage des lignes de TP
    for i in range(NB_TP):
        ligne_str = "TP {0:<4} | ".format(i + 1)
        for j in range(NB_SEANCES):
            trio = grille[i][j]
            trio_str = "{0}-{1}-{2}".format(trio[0], trio[1], trio[2])
            ligne_str += "{0:<10} | ".format(trio_str)
        print(ligne_str[:-3])
else:
    print("\nAucune solution parfaite trouvée.")
    print("Note : Plus le nombre de séances est élevé, plus le problème mathématique devient saturé et difficile à résoudre.")