Les solutions Python du podium

On termine les corrigés de l’édition 2025 de la Battle Dev Thales. Et pour ce corrigé, on présente les solutions des 3 équipes qui sont arrivées tout en haut du podium !

Dans ce challenge, il était question d’analyser les systèmes de défense et leur coût d’utilisation, de façon à trouver la meilleure combinaison permettant de défendre complètement l’abri, et cela au moindre coût d’utilisation.

Contrairement aux autres challenges et nos mécaniques habituelles, ce challenge ne présentait pas une solution unique. Selon les jeux de données, plusieurs solutions étaient possibles. N’importe laquelle de ces solutions permettaient de valider le challenge. Dans le futur, de plus en plus de nos challenges permettront ce mode de fonctionnement, ce qui permettra de travailler sur des algorithmes plus sophistiqués.

Chaque solution a été codée en Python.

• Solution #1, ThalesCramptés
• Solution #2, denilb
• Solution #3, Arglancecht

Solution #1 en Python, par ThaLesCramptés? de l’Epita, Paris

# Partie 1 : Détermination de la couverture cible
length = len(systems[0].split(':')[2])
target = (1 << length) - 1

# Partie 2 : Transformation des systèmes en données exploitables
s = []
for sys in systems:
    l, cost, act = sys.split(':')
    cost = int(cost)
    act = int(act, 2)
    s.append((l, cost, act))
    
# Partie 3 : Définition de la fonction récursive bf
def bf(i=0, cost=0, covered=0, took=''):
    if i >= len(systems):
        if covered == target:
            return (cost, took)
        else:
            return (float('inf'), None)
    
    # Partie 4 : Exploration des 2 choix possibles
    ct, tt = bf(i+1, cost + s[i][1], covered|s[i][2])
    cd, td = bf(i+1, cost, covered)
    
    # Partie 5 : Sélection de la meilleure combinaison
    if ct < cd:
        return ct, tt + s[i][0]
    else:
        return cd, td
    

# Lancement et affichage
a, b = bf()
print(b)

Partie 1 : Détermination de la couverture cible

La première ligne sert à identifier combien de minutes dure l’assaut. On prend la longueur de la séquence binaire du premier système, ici 12.

Puis on calcule la valeur target, c’est-à-dire la combinaison binaire où toutes les minutes sont couvertes.
Le calcul (1 << length) - 1 permet de créer un nombre dont tous les bits sont à 1 sur 12 positions : en binaire, c’est 111111111111.

Ce sera l’objectif final : parvenir à cette couverture complète grâce à un ensemble de systèmes bien choisis.

Partie 2 : Transformation des systèmes en données exploitables

Ici, on transforme les données textuelles en structures numériques plus faciles à manipuler.

Chaque élément de la liste systems est découpé pour extraire :

• la lettre du système (l),
• son coût (cost),
• et sa séquence binaire (act).

La séquence binaire est ensuite convertie en entier (int(act, 2)), ce qui permet d’utiliser plus tard les opérateurs bit à bit pour combiner les couvertures.

On stocke le tout dans une liste de tuples (l, cost, act) pour simplifier les manipulations dans la fonction principale.

Partie 3 : Définition de la fonction récursive bf

La fonction bf (pour brute force) est le cœur du programme.

Elle explore toutes les combinaisons possibles des systèmes, un à un, pour déterminer la meilleure configuration.

Ses paramètres permettent de suivre :

• l’index courant i,
• le coût accumulé cost,
• la couverture actuelle covered,
• et la liste des systèmes sélectionnés took.

Le cas de base intervient lorsque tous les systèmes ont été testés (i >= len(systems)).

Si la couverture actuelle correspond à la cible (covered == target), on renvoie le coût total et la combinaison de systèmes.

Sinon, on retourne un coût infini, ce qui exclura cette branche de la solution optimale.

Partie 4 : Exploration des 2 choix possibles

Pour chaque système, deux chemins sont explorés récursivement :

1. Activer le système → on ajoute son coût et on combine sa couverture (covered | s[i][2]).
2. L’ignorer → on conserve le coût et la couverture actuelle.

Le | est un OU binaire : il permet de fusionner les minutes couvertes par plusieurs systèmes.

Ces deux appels retournent chacun un couple (coût total, combinaison) que la suite du code va comparer pour garder le plus intéressant.

Partie 5 : Sélection de la meilleure combinaison

Après avoir évalué les deux branches, le code compare leurs coûts :

• si l’ajout du système réduit le coût total (ct < cd), on garde cette solution et on ajoute la lettre du système à la chaîne de résultat ;
• sinon, on garde la branche sans ce système.

Ce mécanisme garantit que la fonction renvoie toujours la combinaison de systèmes la moins coûteuse assurant la couverture complète.

L’ensemble du processus se répète récursivement jusqu’à trouver la configuration optimale.

Solution #2 en Python, par denilb de Polytech, Marseille

# Partie 1 : Initialisation des variables
best = float('inf')
ans = None

# Partie 2 : Parcours de toutes les combinaisons possibles
for mask in range(1<<len(systems)):
    # Partie 3 : Activation et cumul des systèmes sélectionnés
    actif = []
    cost = 0
    couv = [0] * 12
    for i in range(len(systems)):
        if mask>>i&1 == 0:
            continue
        let, nrj, seq = systems[i].split(':')
        actif.append(let)
        cost += int(nrj)
        for j, x in enumerate(seq):
            if x == '1':
                couv[j] = 1
    # Partie 4 : Vérification de la couvertue complète
    if all(couv):
        # Partie 5 : Mise à jour de la meilleure solution
        if cost < best:
            best = cost
            ans = actif

# Affichage de la solution
print(''.join(ans))

Partie 1 : Initialisation des variables

On commence par initialiser deux variables de suivi :

• best représente le coût minimal trouvé jusqu’ici, initialisé à l’infini pour pouvoir être remplacé dès qu’une solution valide apparaît ;
• ans contiendra la meilleure combinaison de systèmes sous forme de liste.

Cette étape prépare la boucle principale qui va parcourir toutes les combinaisons possibles.

Partie 2 : Parcours de toutes les combinaisons possibles

Ici, on parcourt tous les entiers possibles de 0 à 2^n - 1, où n est le nombre de systèmes (ici 12).

Chaque entier mask représente une combinaison de systèmes, grâce à sa représentation binaire :

• un bit à 1 signifie que le système est activé,
• un bit à 0 signifie qu’il ne l’est pas.

C’est une approche dite bitmask, très utilisée dans les problèmes combinatoires.

Partie 3 : Activation et cumul des systèmes sélectionnés

À chaque combinaison (mask), on initialise trois éléments :

• actif : la liste des lettres des systèmes sélectionnés,
• cost : le coût énergétique total,
• couv : une liste de 12 zéros représentant les minutes de l’assaut.

On parcourt ensuite chaque système (i) et on teste s’il est actif dans le masque (mask >> i & 1).

S’il l’est :

• on ajoute sa lettre dans actif,
• on additionne son coût,
• et on marque dans couv les minutes couvertes (en mettant 1 là où le système est actif).

Partie 4 : Vérification de la couvertue complète

Une fois les systèmes sélectionnés traités, on vérifie si toutes les minutes sont couvertes.

La fonction all(couv) retourne True si tous les éléments de couv valent 1, c’est-à-dire que chaque minute de l’assaut est protégée par au moins un système actif.

Partie 5 : Mise à jour de la meilleure solution

Si la combinaison actuelle couvre bien toutes les minutes et coûte moins cher que la meilleure trouvée jusque-là, elle devient la nouvelle référence.

À la fin de la boucle, ans contient les systèmes optimaux, et on les affiche sous forme d’une chaîne de lettres collées ('BDEG' par exemple).

Solution #3 en Python, par Arglancecht de Thales, Toulouse

# Partie 0 : import de la fonction combinations
from itertools import combinations

# Partie 1 : Structuration des données
syst = {k.split(":")[0] : (int(k.split(":")[1]), k.split(":")[2]) for k in systems}

# Partie 2 : Définition des bornes et variables de suivi
possibilities = None
coutmax = sum(v[0] for v in syst.values())

# Partie 3 : Parcours des combinaisons possibles
for n in range(2,10):
    for ls in combinations(syst, r=n):
        # Partie 4 : Calcul du coût et couverture de la combinaison
        cout = sum(syst[l][0] for l in ls)
        if coutmax < cout:
            continue
        minutes = [False]*12
        for l in ls:
            v = syst[l][1]
            minutes = [ (minu or bi == "1") for bi, minu in zip(v, minutes)]
        # Partie 5 : Vérification et mise à jour de la meilleure solution
        if not all(minutes):
            continue
        possibilities = ls
        coutmax = cout

# Affichage de la solution
print(*possibilities, sep="")

Partie 0 : import de la fonction combinations

On commence par importer combinations depuis le module standard itertools, une fonction pratique qui permet de générer automatiquement toutes les combinaisons possibles d’éléments d’une liste sans avoir à coder de boucles imbriquées.

Partie 1 : Structuration des données

Ici, on transforme la liste systems en un dictionnaire syst, où chaque clé est la lettre du système (de A à L).

Chaque valeur associée contient :

• le coût énergétique (entier),
• et la séquence binaire décrivant les minutes actives.

Ce format rend le code plus lisible et permet un accès direct par nom de système, pratique pour la suite lorsqu’on testera des combinaisons.

Partie 2 : Définition des bornes et variables de suivi

Deux variables importantes sont initialisées :

• possibilities contiendra la meilleure combinaison trouvée,
• coutmax est initialisé à la somme des coûts de tous les systèmes, soit le pire cas possible.

Ainsi, toute combinaison qui réussira à couvrir toutes les minutes avec un coût inférieur remplacera cette valeur maximale.

Partie 3 : Parcours des combinaisons possibles

Le cœur de l’algorithme repose sur itertools.combinations, qui génère toutes les combinaisons possibles de systèmes pris n par n.

Ici, on limite la taille des combinaisons entre 2 et 9 systèmes (probablement pour réduire le temps de calcul).

Chaque combinaison ls est une liste de lettres représentant les systèmes sélectionnés (par exemple ('B', 'E', 'G')).

Partie 4 : Calcul du coût et couverture de la combinaison

On calcule d’abord le coût total de la combinaison. Si celui-ci dépasse déjà le meilleur coût trouvé (coutmax), on passe à la suivante pour gagner du temps.

Puis, on crée une liste minutes de 12 valeurs False, représentant les minutes non couvertes.

Chaque système actif met à jour cette liste en positionnant True là où la séquence contient un 1.

La ligne avec zip(v, minutes) permet de fusionner progressivement les séquences, en appliquant un OU logique (minu or bi == "1").

Partie 5 : Vérification et mise à jour de la meilleure solution

Si la couverture n’est pas complète (not all(minutes)), on ignore la combinaison.

Sinon, elle devient la nouvelle meilleure solution (possibilities), et on met à jour le coût minimal (coutmax).

À la fin, on affiche la combinaison optimale de lettres, sans séparateur (par exemple BDEG).

Conclusion

Ces trois solutions trouvent toutes la bonne combinaison de systèmes, mais elles reposent sur la construction de toutes les combinaisons possibles, ce qui devient rapidement lourd dès que le nombre de systèmes augmente.

La différence entre elles tient surtout à la manière de parcourir ces combinaisons :

• la première le fait récursivement,
• la deuxième via un compteur binaire (bitmask),
• la troisième avec les combinations d’itertools.

Dans le cadre de la Battle Dev, cette approche restait parfaitement adaptée : claire, efficace et bien calibrée pour le volume de données proposé !

Et encore un grand Bravo à toutes les participantes et à tous les participants pour leur logique, leur créativité et la qualité de leurs solutions !