Comment nous avons perdu 230 euros chez CJ Affiliate (Conversant)




[accueil]  [menu]  [suivez-nous !]  [chercher]

Concours : optimisons les petits carrés

---

Rappel du problème paru dans le Virus 11 :
 
Dessinez sur un bout de papier une grille 9 * 9.
Parmi les 81 cases blanches de cette petite grille, combien pouvez-vous en noircir, au maximum, sans jamais former d'alignement de quatre cases consécutives dans une des quatre directions (horizontale, verticale et les deux diagonales) ? Bien entendu, il faut non seulement trouver le nombre maximum, mais aussi un exemple.

Une solution a été proposée dans le Virus 13 (vous pouvez consulter le listing qui va avec l'article). A cette occasion nous vous invitions à proposer les vôtres.

Maintenant les participations sont closes, et vous trouverez ci-dessous les solutions retenues classées par temps d'exécution décroissant (" signifie seconde et ' minute). Tous les programmes ont été recompilés de la même façon pour la mesure. Comme certains programmes plantent sous Linux (qui ne pardonne pas les accès mémoires un peu louche), une autre mesure a donc été faite sous Ms-Dos 7.

Bien que ce problème soit clos, vous pouvez toujours envoyer vos remarques et vos questions à David.

Le grand gagnant est Patrice Torchet avec un programme qui trouve toutes les solutions (aux symétries prêts) en ... moins d'une seconde !!! Il faut aussi noter le programme de Laurent Mortroux qui tombe au-dessous des 10 secondes.

La solution de V. Menu, même si elle est loin d'être aussi rapide que les deux précédentes est particulièrement intéressante. Outre que le code est propre et clair, il est très souple : la version générale permet de choisir la taille de la grille et celle des alignements à interdire. La version optimisée, quant à elle, fixe la taille des alignements à 4.

 

(temps mesurés sur un K6-233 avec 64 Mo de RAM)

Patrice Torchet, nous explique sa méthode :

Préambule
81 cases blanches ou noires ça fait 2⁸¹ combinaisons. Si on note chaque combinaison sur une feuille de papier et qu’on les empile, la pile serait tellement grande que pour la parcourir de bout en bout, il faudrait plusieurs millions d’années (environ 25) en ce déplaçant à la vitesse de la lumière.
Heureusement, la contrainte sur les alignements élague sérieusement ce nombre de possibilité.

Optimisation du carré
Quand j’ai fait la première version du programme de remplissage, j’ai choisi de procéder case par case, contrairement à l'auteur de l'article qui procède ligne par ligne.

Etant un programmeur expérimenté, j’ai opté sciemment pour une programmation non structurée, ce qui m’a permis d’améliorer la vitesse d’exécution de chaque étape de calcul au détriment de la lisibilité générale. Au passage, cela me permet de mettre en place des shunts (arrêts anticipés) sans avoir à gérer le problème de ressortir des appels récursifs de la routine.

En termes techniques, la base du programme est une routine d’exploration d’un arbre binaire avec vérification des contraintes au vol. Autrement dit, je construit le carré case par case en commençant par noircir la case si j’en ai le droit (ce droit est la contrainte des alignements) et quand je mets la case à blanc, je vérifie que le nombre de cases blanches déjà utilisées plus le nombre minimum de case que je devrai laisser à blanc pour arriver à la fin du carré me laisse espérer une amélioration du score, si ca n‘est pas le cas, c’est que ce début de carré conduit à une impasse qu’il n’y a pas lieu d’évaluer plus avant, à ce moment, on recule pour construire un autre début de carré qu’on espère plus favorable.

Un autre aspect de mon programme prend à contre pied celui de l'auteur de l'article, mon programme ne fait qu’un seul parcours du carré en améliorant le score en cours de route, le score étant lui-même une contrainte car il est lié au nombre de cases blanches autorisées.

Les optimisations
1 - Exploitation de la symétrie verticale : une observation rapide montre que le carré se lit aussi bien de droite à gauche que de gauche à droite. Donc quand on évalue une ligne de la forme GD (figure 1), on évalue par la même occasion la ligne de la forme DG (figure 1) qui donnera les mêmes résultats avec des dispositions inversées entre la droite et la gauche sur l’ensemble du carré.

Fig. 1
GD : x0 x1 x2 x3 x4 x5 x6 x7 x8  ex : 001100110
DG : x8 x7 x6 x5 x4 x3 x2 x1 x0  ex : 011001100

Donc, en contrôlant d’abord les cases x0 et x8, on obtient des dispositions selon 4 familles (figure 2). En lisant à l’envers la famille 10, on obtient la famille 01, donc, ça n’est pas la peine d’évaluer la famille 01 qui ne pourra améliorer le résultat. Par contre les familles 11 et 00 donnent elles mêmes quand elles sont lues à l’envers. Pour ces familles, on recommence le même processus avec les cases x1 et x7, et ainsi de suite.

Fig. 2
10 : 1 x1 x2 x3 x4 x5 x6 x7 0
01 : 0 x7 x6 x5 x4 x3 x2 x1 1
11 : 1 x1 x2 x3 x4 x5 x6 x7 1
00 : 0 x1 x2 x3 x4 x5 x6 x7 0

Sur la première ligne, on élimine 240/512 possibilités, et il en reste 32 qui sont symétriques pour lesquelles il faudra appliquer le même procédé sur la ligne suivante. Mon programme fait l’élimination jusqu'à la troisième ligne, car au delà, le temps passé à faire le test est supérieur au temps qu’il fait gagner.

En contrepartie, si une combinaison de la famille 10 conduit à une solution, automatiquement, on aura une autre solution dans la famille 01 par simple lecture à l’envers.

Le code se présente sous la forme :

Si case 0 <> case 8 Alors
        Si case 0 < case 8 Alors Rejeter
Si Non Si case 1 <> case 7 Alors
        Si case 1 < case 7 Alors Rejeter
Si Non Si case 2 <> case 6 Alors
        Si case 2 < case 6 Alors Rejeter
...
Fin Si
Traiter

2 - Elimination d’un cas spécial : les 3 premières lignes constituent un cas spécial car il n’y a pas d’alignements verticaux ou en diagonales. Le premier réflexe est de faire un test qui vérifie qu’on a dépassé la troisième ligne avant de faire les tests pour les alignements verticaux et en diagonales. Bien qu’elles représentent 1 tiers des cases, il faut voir que chaque case et évaluée environ 2 fois plus souvent que la précédante. Donc ces 3 premières lignes ne représentent qu’une infime partie des calculs. Donc l’optimisation consiste à ajouter 3 lignes supplémentaires en début de tableau et à tester tous les alignements systématiquement.

3 - Ma variable ‘espoir’ : en cours de remplissage, c’est une variable indiquant le nombre de cases que je peux mettre à blanc tout en espérant égaler ou améliorer le score actuel. Quand la valeur de ‘espoir’ deviens inférieure à 1, c’est qu’aucune des fins de remplissage ne pourra égaler le score actuel, donc ce n’est pas la peine de les calculer.

Pour améliorer le fonctionnement de ‘espoir’, j’ai créé un tableau qui répond à la question ‘Quel est le minimum de cases à laisser en blanc pour terminer le remplissage du carré. Ce tableau est utilisé pour tarer ‘espoir’ afin d’arrêter les calculs le plus tôt possible. En l’occurrence, ‘espoir’ contient le nombre de cases que l’on peut laisser à blanc en plus du minimum indiqué par le tableau.

En termes imagés, le problème consiste à fabriquer un nombre à 6 chiffres, dont la somme des chiffres est supérieure à 49 et en ayant pas plus de 2 chiffres impairs consécutifs. Six chiffres, ca fait 1 million de possibilités mais les contraintes éliminent une énorme partie des valeurs.

Le principe consiste à commencer par le nombre le plus grand, puis, d’aller à reculons dans les valeurs. En mémorisant les sommes des nombres partiellement formés, on évite de refaire sans cesse les mêmes calculs.

Illustration (je l’ai fait à la mimine, alors y a peut être des boulettes, mais le principe est bon)

 

Vous voulez soutenir une information indépendante ? Rejoignez notre Club privé !


[homepage]  [RSS]  [archives]
[contact & legal & cookies]  [since 1997]