Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
8 novembre 2010 1 08 /11 /novembre /2010 10:59

« Le compte est bon » est un célèbre jeu télévisé, d'abord autonome, puis intégré à l'émission « Des chiffres et de lettres ». Le principe est simple, on tire au hasard un nombre entre 101 et 999. Deux candidats devront aboutir à ce résultat d'après six nombres tirés au hasard parmi la liste suivante : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75 et 100 en utilisant les quatre opérations arithmétiques de base. Nous allons voir ensemble comment réaliser une application permettant de trouver une solution à ce jeu en langage Python.

 

Données utilisables

Chaque opération possible (addition, multiplication, soustraction et division) est une opération binaire. C'est-à-dire qu'elle fait intervenir deux opérandes. À partir de notre liste de 6 entiers, on va former des paires sur lesquelles on effectuera les opérations. On n'a le droit d'utiliser chaque nombre qu'une fois, mais on peut réutiliser le résultat d'une opération précédente. Donc à chaque fois qu'on fait une opération, on « perd » les deux opérandes, et on « gagne » le résultat de l'opération.

 

On voit ainsi se dessiner l'esquisse d'un algorithme récursif de type backtracking.

 

Capture d’écran 2010-11-08 à 11.04.19

Réduisons l'espace de recherche

Prenons deux nombres A et B au hasard. On peut remarquer plusieurs choses :

  • L'addition est commutative. C'est-à-dire que A + B et B +A donneront toujours le même résultat. Il en est de même pour la multiplication. Il est donc inutile de faire la deuxième opération si on a déjà fait la première.

  • Si A = B, la soustraction donnera 0. Faire rentrer 0 dans nos données donnera des calculs ultérieurs inutiles ou interdits. On peut donc éviter ce calcul :

    • A + 0 = A (inutile)

    • A x 0 = 0 (inutile)

    • A : 0 est interdit

  • Si A < B, la soustraction donnera un entier négatif (on sort de l'espace de solutions) et la division entière donnera 0. Ce sont donc également des calculs inutiles.

 

Ces constatations nous amènent à ne faire que les opérations pour A >= B, et à éviter la soustraction si A = B. On réduit donc de plus de moitié notre espace de recherche, gagnant ainsi un temps précieux !

 

Générateur de paires d'entiers

Nos quatre opérations étant binaires, nous devons, à partir d'une liste d'entiers, générer toutes les paires d'opérandes possibles. Cela est facilement réalisable en utilisant une liste triée par ordre décroissant. Il suffit de maintenir deux index sur cette liste. On déplace un index à chaque accès et un autre chaque fois que le premier sort des limites de la liste. On s'arrête lorsque l'on ne peut plus rien déplacer.

 

Journal des opérations

Afin de pouvoir afficher les étapes du calcul lorsque l'on a trouvé une solution, on utilise une liste de chaînes de caractères. Après chaque opération, on note celle-ci dans la liste. Si un nœud de l'arbre d'exploration n'a donné aucun résultat, on l'enlève de la liste.

 

Code source de notre programme

 #!/usr/bin/python



import sys



# Les quatre fonctions arithmetiques de base

add = lambda x, y: x + y

sub = lambda x, y: x - y

mul = lambda x, y: x * y

div = lambda x, y: x // y



class Operation:

"""

Classe associant une operation a sa description textuelle, pour pouvoir

afficher le detail des calculs effectues lorsqu'on a trouve le resultat.

"""

def __init__(self, func, desc):

"""

Constructeur : initialise les deux champs

func : pointeur vers la function qui fait le calcul

desc : chaine de caractere, descriptif

"""

self.func = func

self.desc = desc



# Les quatre operations

ALL_OPERATIONS = (Operation(add, "+"), Operation(sub, "-"),

Operation(mul, "x"), Operation(div, ":"))



# Les operations qui ne peuvent pas donner 0 comme resultat

OPERATIONS = (Operation(add, "+"), Operation(mul, "x"),

Operation(div, ":"))



#----------------------------------------------------------------------------



class PairIterator:

"""

Classe donnant une suite de paire de nombres a partir d'une liste de

nombres.



"""

def __init__(self, nums):

assert len(nums) >= 2, "La liste doit contenir au moins 2 elements"

self.nums = nums

self.index1 = 0

self.index2 = 1



def __iter__(self):

""" La classe est son propre iterateur. """

return self



def __next__(self):

""" Renvoie la prochaine paire d'entiers """

# Si on est arrive au bout de la liste de paires

if self.index2 == len(self.nums):

raise StopIteration

# Cree une paire

p = (self.nums[self.index1], self.nums[self.index2])



# Avance la position pour la prochaine fois

if self.index2 < len(self.nums) - 1:

self.index2 += 1

else:

self.index1 += 1

self.index2 = self.index1 + 1



return p



def next(self):

"""

Meme fonction que la precedente, par souci de compatibilite

avec python 2.x

"""

return self.__next__()

#----------------------------------------------------------------------------



def algo(entiers, aTrouver, log=[]):

"""

Fonction de recherche de solutions.



Parametres:

entiers: liste de donnees utilisables (entiers)

aTrouver: resultat auquel aboutir (entier)

log: liste des operations deja effectuees (liste de chaines)

"""

assert len(entiers) >= 2, "La liste doit contenir au moins 2 elements"



# Pour chaque paire d'entiers

paires = PairIterator(entiers)

for paire in paires:

# On evite de faire des calculs qui donnent 0 comme resultat

ops = OPERATIONS if paire[0] == paire[1] else ALL_OPERATIONS

for op in ops:

# On fait le calcul

resultat = op.func(paire[0], paire[1])

# Note l'operation dans le journal

log.append("%d %s %d = %d" % (paire[0], op.desc, paire[1],

resultat))



# Si on a trouve la solution

if resultat == aTrouver:

# On affiche les operations effectuees et on quitte

for ligne in log:

print(ligne)

sys.exit(0)

else:

# On prend les autres nombres et le resultat de l'operation

entiers2 = [n for n in entiers if n not in paire]

entiers2.append(resultat)

# et on recommence

entiers2.sort(reverse = True)

if len(entiers2) >= 2:

algo(entiers2, aTrouver, log)

# L'operation n'a pas donne de resultat, on l'enleve du journal

log.pop()



#----------------------------------------------------------------------------



VALIDES = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100)



if len(sys.argv) != 8:

print("Pas assez d'arguments.")

print("usage : compte nb1 nb2 nb3 nb4 nb5 nb6 aTrouver")

sys.exit(1)

else:

try:

entiers = [ int(i) for i in sys.argv[1:7] ]

aTrouver = int(sys.argv[-1])

except:

print("Les arguments de ce programmes doivent etre des entiers")

sys.exit(2)



# Verifie que le nombre a trouver est valide

if aTrouver <= 100 or aTrouver >=1000:

print("Argument invalide")

print("Le nombre a trouver doit etre compris entre 101 et 999")

sys.exit(3)



# Verifie que tous les nombres sont dans la liste des valides

if any(e not in VALIDES for e in entiers):

print("Argument(s) invalide(s)")

print(("Les nombres doivent etre dans la liste %s" % (str(VALIDES))))

sys.exit(3)



entiers.sort(reverse = True)

algo(entiers, aTrouver)

print ("Aucun resultat.")

Partager cet article

Repost 0
Published by Olivier - dans Programmation
commenter cet article

commentaires

Présentation

Recherche

Liens