Forum de mathématiques - Bibm@th.net

Ernst

Membre

Inscription : 30-01-2024

Messages : 370

défi formule

Bonjour,

En utilisant tous les chiffres et chaque opérateur + - * / une seule fois, résoudre :
1 1 1 1 1 1 1 1 1 1 = 5
(les parenthèses sont autorisées)

Le défi, c’est de trouver un programme Python capable de chercher et d’afficher toutes les solutions.

Ernst

Membre

Inscription : 30-01-2024

Messages : 370

Re : défi formule

Bonjour,

Ne voulant pas laisser un problème sans solution, la voici : l’idée est d’abord de regrouper les chiffres pour obtenir toutes les combinaisons possibles de cinq nombres (puisqu’il y a quatre opérateurs), puis de représenter les expressions sous forme d’arbres syntaxiques abstraits (AST) afin d’éviter la gestion des parenthèses, qui ne sont réintroduites qu’à la fin pour l’affichage.

import time
from fractions import Fraction
from itertools import combinations

OPERATORS = ('+', '-', '*', '/')
COMMUTATIVE = {'+', '*'}

# ============================================================
# 1. Partitions des 10 chiffres '1' en 5 nombres
# ============================================================

def generate_partitions():
    digits = "1" * 10
    for cuts in combinations(range(1, 10), 4):
        parts = []
        last = 0
        for c in cuts:
            parts.append(int(digits[last:c]))
            last = c
        parts.append(int(digits[last:]))
        yield parts

# ============================================================
# 2. Application sûre des opérateurs
# ============================================================

def apply_op(a, b, op):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    if op == '/':
        if b == 0:
            return None
        return a / b
    return None

# ============================================================
# 3. Programmation dynamique par segments AVEC opérateurs
# ============================================================

def solve_partition(numbers):
    """
    DP[i][j] :
      clé   = (Fraction valeur, frozenset ops_utilisés)
      valeur = liste de représentations structurelles
    """

    n = len(numbers)
    DP = [[dict() for _ in range(n)] for _ in range(n)]

    # Feuilles : aucune opération utilisée
    for i in range(n):
        DP[i][i][(Fraction(numbers[i]), frozenset())] = [None]

    # Segments croissants
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            cell = DP[i][j]

            for k in range(i, j):
                left = DP[i][k]
                right = DP[k + 1][j]

                for (lv, lopset), lreps in left.items():
                    for (rv, ropset), rreps in right.items():

                        used_ops = lopset | ropset

                        for op in OPERATORS:
                            if op in used_ops:
                                continue

                            # commutativité contrôlée
                            if op in COMMUTATIVE and lv > rv:
                                continue

                            val = apply_op(lv, rv, op)
                            if val is None:
                                continue

                            new_ops = used_ops | {op}
                            key = (val, new_ops)

                            reps = cell.setdefault(key, [])
                            for lr in lreps:
                                for rr in rreps:
                                    reps.append((op, lr, rr))

    return DP[0][n - 1]

# ============================================================
# 4. Reconstruction du texte
# ============================================================

def build_text(rep, numbers_iter):
    if rep is None:
        return str(next(numbers_iter))
    op, left, right = rep
    return f"({build_text(left, numbers_iter)} {op} {build_text(right, numbers_iter)})"

# ============================================================
# 5. Résolution globale
# ============================================================

def solve():
    solutions = set()

    for numbers in generate_partitions():
        results = solve_partition(numbers)

        for (val, opset), reps in results.items():
            if val == 5 and len(opset) == 4:
                for rep in reps:
                    expr = build_text(rep, iter(numbers))
                    solutions.add(expr)

    return solutions

# ============================================================
# 6. Exécution avec chronométrage
# ============================================================

if __name__ == "__main__":
    start = time.perf_counter()

    sols = solve()

    end = time.perf_counter()

    for s in sorted(sols):
        print(s)

    print(f"\nNombre total de solutions : {len(sols)}")
    print(f"Temps d'exécution : {end - start:.3f} secondes")

Et la sortie du programme :

▼solutions

(((11 * 11) - 11) / (11 + 11))
((1111 - 1) / ((1 + 1) * 111))

Nombre total de solutions : 2
Temps d'exécution : 0.095 secondes

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 496

Re : défi formule

RE,

Merci pour la solution...
Le défi, était double :
1. Trouver en calcul mental
2. Ensuite, le passage à la programmation (c'était une autre histoire...)

Après pas mal de tâtonnements,  je m'étais persuadé que c'était impossible !
Dans ces conditions, victime du blocage mental installé, je ne risquai pas d'avancer...
Impressionnant !
Et t'as pondu ça tout seul sans recours à l'IA ? Fichtre !

Parce que sinon, moi  je peux battre un champion d'échecs avec l'aide du module Stockfish 16 (Elo >= 3000 pts)
N-B:  Magnus Carlsen, ex  champion du monde, plus fort Elo jamais obtenu par un humain : 2850 pts environ...). Ce module -gratuit - peut fonctionner sur diverses machines par le truchement d'un GUI adapté ARENA Chess...
Le futur module Stockfish 17 pourra utiliser jusqu'à 512 cœurs et aura un ELO dont on estime qu'il avoisinera les 3640  pts...
Stratosphérique : 200 points ELO d'écart représentent un fossé très large...
J'ai eu ponctuellement un ELO autour de 1850 pts, c'est déjà pas si mal pour un pur amateur comme moi mais "ridicule" pour espérer quoi que soit dans une joute avec les ténors français (ELO > 2300).

@+