Exercices de combinatoires

A vrai dire, le calcul du nombre de possibilités avec Code en Bois ne vient pas du tout d'un client qui nous aurait posé la question, ni de l'argument marketting d'écrire sur l'emballage "plus de 50 000 combinaisons possibles" ou quoi que ce soit du genre. Non; nous avons tenté de faire ce calcul pour résoudre un autre problème, celui de la vérfication des programmes. Voici comment cela s'est passé.

A chaque fois qu'on présente Code en Bois à des enseignants, la question arrive systématiquement, ça ne manque jamais: "mais comment est-ce qu'on valide que le programme est correct?"

Pour répondre à cette question, nous apportons plusieurs éléments de réponses, mais aucun n'est pleinement satisfaisant, tout simplement parce qu'en algorithmique débranchée, il n'y a pas de miracle, pas de processeur pour exécuter le code, et donc la seule façon est de le vérifier à la main. Il y a donc toujours une possibilité d'erreur, de ne pas exécuter correctement, de valider un programme faux ou de déclarer faux un programme correct, par erreur; nous avons tourné le problème dans tous les sens, rien à faire en dehors de l'ajout d'un outil numérique ou en ligne. Enfin si, on s'est dit: si on fournissait à la fin du livret une liste de tous les programmes possibles, avec s'ils sont valides ou non pour tel ou tel défi. A première vue, pourquoi pas, mais on s'est dit "cette liste risque d'être longue, non?". Pour le savoir, il faut faire le calcul: il faut évaluer précisément le nombre de programmes possibles qu'on peut obtenir avec un kit individuel Code en Bois, composé de ses 25 briques, et de ses 10 chiffres aimantés. Après quelques minutes de réflexion, il semble vite très improbable qu'une annexe de cahier puisse contenir tous les programmes, car on arrive vite à des estimations élevées. Mais prenons les choses dans l'ordre.

Code en Bois intègre, dans un kit, 25 briques; Mais toutes les briques n'ont pas la même fonction; Certaines briques sont d'ailleurs identiques (4 AVANCE, 2 TIRE, 2 SI, etc;), certaines briques peuvent s'utiliser de plusieurs façons (PIVOTE: à droite ou à gauche, Répète tant que ou répète 0, 1, 2... 9 fois), d'autres briques apportent des contraintes (une brique SI oblige à placer une brique FIN SI après celle-ci). Certaines briques ne peuvent pas être placées n'importe où sans quoi le programme serait incorrect (la brique PAS de négation, les capteurs booléens qui doivent toujours être associées à une condition). Et bien sûr la longueur du programme qui varie de 1 ligne (une seule instruction bleue), à 18 lignes au maximum si on utilise toutes les actions, répétitions et conditions. 

On va chercher, dans un premier temps, à évaluer le nombre de possibilités du programme le plus long (18 lignes) qui utilise le plus de briques. Cela nous donnera une borne minimum de notre valeur. Le nombre de combinaisons de 18 éléments, dans l'ordre, vaut simplement:

‍18! = 6.402*10^15

C'est beaucoup ! Mais il faut corriger ce nombre à la baisse (certaines combinaisons sont impossibles ou redondantes (ex: 2 AVANCES identiques inversés cela revient au même), et à la hausse (on n'a pas pris en compte les 10 chiffres à choisir sur les répétitions par exemple).

On divise donc par les briques identiques: 18! / 4!2!2!2!2!2!2! (4 avance identique, 2 tire, 2 tourne, 2 répète, etc) cela donne 18!/768 combinaisons;

Chacune des 2 briques pivote peut être un "pivote gauche" ou "pivote droite", donc 4 combinaisons, donc: 18! *4 / 768

L'ensemble des briques bleues peut être disposé au milieu des briques dites de "contrôle" (répète, fin répète, si, fin si, sinon) qui sont au nombre de 9 (on exclut la pièce Début de Programme qui reste toujours au début, sinon c'est invalide).

On doit alors éliminer toutes les configurations où la disposition de ces 9 pièces de contrôle est incorrecte. ChatGPT + Grok (qui m'ont assisté dans cette tâche) me proposent un programme python exhaustif pour le faire il obtient: 1332 combinaisons valides pour 22680 totales, soit 37/360.

18! *4/768  * 37/630  = 18! * 37/120960

Ensuite on doit répartir les briques booléennes (présence d'ennemi, de trésor, etc.) sur les si ou les répète, ainsi que les 10 chiffres sur les répète, et éventuellement la brique “pas” de négation. Idem on me fournit un programme python qui donne 151 875 configurations possibles supplémentaires.

18! *4/768  * 37/630 * 151875 = 3.10 * 10^17

Cela nous donne le nombre de 3.1*10¹⁷ c'est à dire environ 300 millions de milliards de programmes uniques possibles, en utilisant l'intégralité des briques possibles. Toutefois, on peut retirer une brique au choix et proposer de refaire le calcul pour augmenter ce nombre. On l'augmentera d'une plus petite quantité, et ainsi de suite on additionne tous les programmes possibles de 17, 16, 15.... 1 ligne(s). Je n'ai pas été aussi loin dans le calcul, car le premier nombre obtenu était déjà au delà de l'imaginable. Si vous êtes calé en maths et en combinatoires, je suis preneur d'une analyse critique du raisonnement et du résultat! (marc@codeenbois.fr)

‍

‍

‍

‍

‍

‍

ANNEXES

Programme Python proposé par ChatGPT + Grok

from itertools import permutations

# Définir les pièces de contrôle
pieces = ['R1', 'R2', 'F1', 'F2', 'S1', 'S2', 'E1', 'E2', 'N']

def is_valid_control_structure(sequence):
    """
    Vérifie si une séquence de pièces de contrôle est valide :
    - Chaque R doit être suivi d'un F correspondant (R1-F1, R2-F2).
    - Chaque S doit être suivi d'un E correspondant (S1-E1, S2-E2).
    - N doit être entre un S et son E.
    - Les blocs doivent être bien imbriqués.
    """
    stack = []  # Pile pour suivre les blocs ouverts
    si_count = 0  # Compteur de SI non fermés
    sinon_used = False  # Indicateur pour SINON

    pairs = {'R1': 'F1', 'R2': 'F2', 'S1': 'E1', 'S2': 'E2'}

    for piece in sequence:
        if piece in ['R1', 'R2', 'S1', 'S2']:
            stack.append(piece)
            if piece in ['S1', 'S2']:
                si_count += 1
        elif piece == 'N':
            if si_count == 0 or sinon_used:
                return False  # SINON sans SI ouvert ou SINON déjà utilisé
            sinon_used = True
        elif piece in ['F1', 'F2', 'E1', 'E2']:
            if not stack:
                return False  # Ferme un bloc sans ouverture
            last_open = stack.pop()
            if piece != pairs.get(last_open):
                return False  # Mauvaise fermeture
            if piece in ['E1', 'E2']:
                si_count -= 1
                if sinon_used and si_count < 0:
                    return False

    return len(stack) == 0 and sinon_used and si_count == 0

# Générer toutes les permutations et utiliser un set pour éviter les doublons
all_permutations = set(permutations(pieces))

# Compter les arrangements valides
valid_count = 0
for perm in all_permutations:
    if is_valid_control_structure(perm):
        valid_count += 1
        # Décommentez pour voir des exemples valides
        # print("Valide:", " ".join(perm))

# Calculer correctement le nombre total
factorial_9 = 1
for i in range(1, 10):
    factorial_9 *= i  # 9! = 362,880

denominator = 2 * 2 * 2 * 2 * 1  # 2! * 2! * 2! * 2! * 1! = 16
total_count = factorial_9 // denominator  # 362,880 / 16 = 22,680

# Calculer le pourcentage
percentage = (valid_count / total_count) * 100

# Afficher les résultats
print(f"Nombre total d'arrangements : {total_count}")
print(f"Nombre d'arrangements valides : {valid_count}")
print(f"Pourcentage de cas valides : {percentage:.2f}%")

‍

‍

‍