Auteur : Kevin FEDYNA

NumApps

Pac-Man en python, NumWorks

Au début des années 80 il y avait sur la console ATARI en jeu de labyrinthe qui connu en grand succès : Pac-Man. Manger des pac-gommes sans se faire manger soit même, tout un programme !

Capture d’écran du jeux

Commandes

FlèchesRetour arrière
Se déplacer sur la grille du jeuInterrompt le jeu,
sans possibilité de le reprendre

Un peu de technique

Si vous souhaitez en savoir plus sur les aspects techniques de ce jeu, lisez l’article de présentation :
Un Pac-Man sur ta Numworks, en python

Télécharger

Nous vous proposons 2 liens distincts, le premier est le lien vers la source du créateur de l’application, le deuxième est un lien alternatif en cas de problème. Seul le premier lien garanti de disposer de la dernière version de l’application.

A noter : Le jeu ne fonctionne correctement sur la calculatrice mais pas sur le workshop 😕

NumApps

Tetris en python, NumWorks

Un incontournable de la Gameboy des années 90. Un jeu de puzzle dans lequel la patience fini par payer ou couter cher. Dans cette version, on peut commencer directement au niveau 42 !

Captures d’écran du jeux

Commandes

FlèchesClearOK
Déplacer les TetrominosRetournerLancer la partie

Un peu de technique

Si vous souhaitez en savoir plus sur les aspects techniques de ce jeu, lisez l’article de présentation :
Un Tetris en python pour la NumWorks

Télécharger

Nous vous proposons 2 liens distincts, le premier est le lien vers la source du créateur de l’application, le deuxième est un lien alternatif en cas de problème. Seul le premier lien garanti de disposer de la dernière version de l’application.

Projets

labohelp, nous allons vous aider sur labomep !

Labomep est un exerciseur de mathématiques en ligne, gratuit et facile à prendre en main. Il est utilisé par de nombreux enseignants français pour faire progresser leurs élèves.
Nous avons conçu labohelp pour aider les élèves à résoudre les petits problèmes qu’ils rencontrent parfois sur la labomep.

Labomep vous connaissez ?

Considéré comme un instrument de torture mathématique par certains, source d’angoisses pour d’autres, labomep est un formidable outil pour s’entraîner sur les automatismes du point de vue du prof.

Et lorsque les élèves comprennent qu’on va les faire travailler et que l’on peut contrôler finement ce travail, vérifier par exemple s’il est fait au dernier moment, vient alors le moment où certain tentent de trouver toutes les parades pour passer à travers, éventuellement en inventant des bugs imaginaires.

Certains enseignants renoncent alors à utiliser cet outil alors que 90% des problèmes rencontrés par les élèves sont imaginaires ou facilement dépassables.

Le site internet labohelp va vous aider à résoudre les principaux problèmes rencontrés par les élèves.

Le cahier des charges

L’idée de base est donc de proposer un chemin de résolution aux principaux problèmes rencontrés sous labomep. Il s’agit dans 90% des cas de problèmes annexes, qui n’ont rien de mathématique. Et quand c’est un problème en mathématiques, un peu d’autonomie de la part de l’élève et quelques prises d’initiatives peuvent aider ou suffire.

Le format flash étant obsolète et déprécié, labohelp n’aidera pas les élèves à résoudre leur problème avec le plugin flash dans le navigateur web.

Ainsi par un jeu de question / réponse, l’assistant aide l’utilisateur (un élève) à résoudre tout seul son problème.

Si le problème n’est pas résolu, il invite l’utilisateur à contacter son professeur mais des précautions sont prises pour éviter les abus.

Les URLs générées sur labohelp étant uniques, si un enseignant reçoit une demande d’élève qui se trouve dans la base de donnée, il lui suffit de copier / coller cette adresse et de l’envoyer à l’élève.

Ainsi à un élève vraiment de mauvaise fois qui ne trouverait pas la page de connexion on pourrait lui envoyer cette adresse : http://labohelp.nsi.xyz/index.php?ref=12

Laborobot répond à vos questions sur labohelp !

Pour rendre l’outil plus agréable, un petit robot est conçu. Un concours interne à l’équipe de développement du site (votation truquée bien évidemment) décide que le robot élu sera le croquis numéro 6.

Le croquis est donc réalisé au propre avec quelques améliorations graphiques, puis numérisé au format PNG et on y applique la charte graphique du site générée tout à fait aléatoirement sur coolors.co.

Tout est désormais en place pour développer un site amusant et coloré !

Choix techniques

L’idée étant de profiter de ce projet pour apprendre / progresser dans la maîtrise des langages HTML / PHP il est décidé de réaliser un unique script PHP, qui servira toutes les pages en interrogeant un annuaire de questions / réponses.

Après quelques tentatives infructueuses (car peu pertinentes) avec un fichier CSV, nous partons sur un fichier XML qui nous permettra de structurer facilement l’annuaire de questions / réponses.

L’unique script php de 400 lignes est ainsi capable de générer les nombreuses pages de ce labohelp.
D’après nos informations, il y aurait plus de 42 pages, et on me souffle dans l’oreillette qu’il y aurait des pages cachées (6 à la date du 11 février 2020), ainsi qu’un menu caché qui sera accessible ultérieurement ! Sauras-tu les retrouver ?

Bien évidemment, une feuille de style CSS habille le site internet, vous pouvez d’ailleurs le visiter sans la feuille de style ou avec celle-ci. Pour désactiver la feuille de style, il suffit de rajouter &style=no à la fin de l’adresse de la page visitée.

Minimaliste mais efficace, la feuille de style intègre également la gestion des écrans ayant une petite résolution avec la déclaration CSS

@media screen and (max-width: 1000px) {

}

Du coup si l’écran de l’ordinateur offre une résolution très faible, le navigateur affichera la version pour smartphone du site.

Le site labohelp, pour qui ?

  • Pour les élèves qui se noient dans un verre d’eau
  • Pour les élèves qui cherchent une réponse à un problème courant
  • Pour les enseignants qui souhaitent l’utiliser avec leurs élèves

Il est possible de faire évoluer l’annuaire de questions / réponses, si vous êtes enseignant et que vous souhaitez l’enrichir contactez-nous.

Si vous êtes un élève, la réponse à vos problèmes sur labomep se trouve peut-être sur labohelp.nsi.xyz, nous ne répondrons à aucun message concernant un bug sur labomep envoyé par un élève.

Projets

Un Pac-Man sur ta Numworks, en python

Rond comme un ballon, et plus jaune qu’un citron, c’est lui Pac-Man ! Pac-Man débarque sur ta NumWorks ! Aide le à manger toutes les pac-gommes en évitant les fantômes et accumule le plus grand score.

Bon jeu !

URL courte de cet article : nsi.xyz/pacman

Pac-Man débarque sur ta NumWorks !

Aide le à manger toutes les pac-gommes en évitant les fantômes et accumule le plus grand score. Pour cela, tu peux :

  • Manger des pac-gommes (10)
  • Manger des super pac-gommes (50)
  • Manger les fantômes (200, 400, 800, puis 1600)

Si tu manges tout les fantômes a chaque super pac-gommes, tu obtiendras même un bonus de 12000 points !

Bon jeu !

Pac-Man, un sacré projet…

Comme toujours, sur nsi.xyz, on aime raconter l’histoire derrière nos projets.

Celle là commence dans une cuisine. Je commençais à faire à manger quand le patron  m’a envoyé un message concernant un bug sur un de ses projets « un jeu en une soirée » : Treasure

L’idée me plaisait, j’avais envie de faire pareil. Mais quel jeu choisir ?

🤓  Je vais tenter de faire un jeu en une nuit aussi vous m’avez motivé. Une idée ?
🧐 Pacman, tout autre jeu serait trop facile pour toi 😅

Pac-Man, ca paraissait infaisable… Des IA différentes pour chaque fantômes, des collisions, des tableaux et encore des tableaux, tout ça dans 32Ko max !

On est parti !

Première étape : Comment stocker la carte ?

Déjà, posons nous la question suivante : C’est quoi la carte dans Pac-Man ?

La carte, c’est soit :

  • Les chemins : On peut se balader dessus, les fantômes aussi.
  • Les murs : Comme on peut le penser, c’est l’inverse des chemins, on ne peut pas les traverser.

Du coup, on est sauvé ! Le tableau contiendra uniquement des 1 (pour les murs) ou des 0 (pour les chemins). Ainsi, on passe d’un tableau 2D de Booléen à un tableau 1D d’entier.
L’astuce est simple mais efficace : Une ligne de 1 et de 0 peut être convertie en entier grâce au fait que l’ordinateur code les entier en binaire.
En plus de réduire la complexité en espace, ça réduit aussi celle en temps, ce qui est pratique quand on parle d’un jeu tel que Pac-Man sur une calculatrice.

Deuxième étape : Construire la carte

Je commence déjà par choisir une taille pour les cases : 10px.
Sachant que la NumWorks dispose d’un écran de 222 px de haut, je sais que ma carte fera 22 cases de haut.Retour ligne automatique
A l’aide d’un logiciel professionnel et d’une image sur Internet, je crée une image blanche de 18x22px (Pourquoi 18 ? Je ne sais pas) que je commence à colorier de façon à obtenir ceci :

Et cette carte se traduit par le tableau suivant :

bits = 18  # Le nombre de bits pour chaque entiers, ce sera utile plus tard
terrain = (262143,131841,187245,187245,131073,186285,135969,252783,249903,251823,1152,251823,249903,251823,131841,187245,147465,219051,135969,195453,131073,262143)

Encore une fois, on utilise des tuple pour gagner en mémoire.

Maintenant, il ne reste plus qu’a rendre la carte à l’écran.
Et pour ca, on utilise une belle fonction :

def render():
    global terrain
    for l in range(len(terrain)):
        for c in range(bits):
            fill_rect(c*10+140,l*10+1,10,10,colors[0])
            if terrain[l]>>(bits-1-c) & 1:
                for d in ((1,0),(0,1),(-1,0),(0,-1)):
                    if 0 <= l + d[0] <= len(terrain) - 1 and 0 <= c + d[1] <= bits - 1 and not terrain[l + d[0]]>>(bits-1-(c+d[1])) & 1:
                        fill_rect(c*10+140+9*(d[1]==1),l*10+1+9*(d[0]==1),1+9*(d[1]==0),1+9*(d[0]==0),colors[1])

Pour faire simple, cette fonction lit les entier comme s’ils était des tableaux de 1 et de 0. Pour chaque case, elle dessine un carré noir. Si la case est un 1, elle regarde dans les 4 direction possibles, si un 0 s’y trouve, alors elle dessine un mur de ce côté.

En rajoutant une petite fonction pour du pré-rendu que je ne détaillerai pas, on obtiens déjà ceci :

Troisième étape : Ajouter de « la classe » au jeu

Outre l’aspect douteux de ce jeu de mot, il est temps de créer une classe pour Pac-Man et ses amis.
Ainsi née la classe Entity qui contiendra, à elle seule, toutes les méthodes pour le jeu. En effet, si on ne considère pas l’entrée des directions, les fantômes et Pac-Man se déplacent de la même manière sur la carte.

Pour faire court, cette classe contient 4 méthodes :

  • Le constructeur : initialise tout les attributs de l’entité.
  • espace : C’est la méthode qui teste les collision, grâce à elle, les fantômes et Pac-Man ne tournent que sur les intersections sans déborder sur les murs. Et évidemment, ils ne traversent pas non plus les murs.
  • move : C’est la méthode qui fait se déplacer les entités, qui réactualise les pac-gommes et super pac-gommes (j’y viendrai plus tard) et qui gère les collisions Pac-Man / Fantômes et Pac-Man / pac-gommes.
  • ia : Détermine la direction des fantômes.

Attardons-nous sur la méthode ia :

def ia(self,x,y):
    if self.f:
        while True:
            d = randint(0,3)
            dx, dy = ((-0.1,0),(0,-0.1),(0,0.1),(0.1,0))[d]
            if d != (3,2,1,0)[self.d] and self.espace(dx,dy):
                self.d = d
                break
    else:
        distances = [9999 for _ in range(4)]
        for i in range(4):
            if i != (3,2,1,0)[self.d]:
                dx, dy = ((-0.1,0),(0,-0.1),(0,0.1),(0.1,0))[i]
                if self.espace(dx,dy):
                    distances[i] = sqrt((self.y + dy - y)**2 + (self.x + dx - x)**2)
        self.d = distances.index(min(distances))

On voit qu’elle comporte deux parties, c’est un des éléments clés de Pac-Man : quand les fantômes sont dans l’état effrayé, ils choisissent une direction au hasard, sinon, ils choisissent la direction qui leur permet d’avoir la plus courte distance euclidienne à un point. Rajoutons que les fantômes n’ont pas le droit de faire demi-tour.

Mais une question se pose : Quel est donc ce point que visent les fantômes ?

Quatrième étape : Les fantômes débarquent !

Dans Pac-Man, il y a quatre fantômes. Mais il n’y a pas que leur couleur qui change, leur comportement aussi !

Petit listing exhaustif :

Blinky poursuit Pac-Man, ainsi le point qu’il cherche à atteindre et le point au centre de Pac-Man.

Pinky est la plus intelligente, ainsi le point qu’elle cherche à atteindre est deux cases devant Pac-Man dans la direction qu’il regarde.

Inky est un peu plus farceur, pour savoir ou il vise, il faut prendre en compte la position de Blinky et de Pac-Man. Posons v le vecteur Blinky-Point deux cases devant Pac-Man dans la direction qu’il regarde, Inky visera le point situé à 2v, ce qui le rend imprévisible.

Clyde quant à lui est un froussard, il agit comme Blinky quand à lui, est à 4 « mètres » de Pac-Man, mais vise un angle de la carte quand il est proche de Pac-Man.

Cinquième étape : Déplacer Pac-Man

Les fantômes maintenant capables de changer de direction, il n’en n’est rien pour Pac-Man…Retour ligne automatique
Comment se déplace Pac-Man ? Pac-Man se déplace jusqu’au bout d’un chemin avant de s’arrêter. Si on lui donne une direction, il la prendra dès qui le pourra sauf si la direction en question est la direction opposée à celle qu’il emprunte déjà.

Du coup, avec nos méthodes et un peu d’astuce, c’est tout simple !

for i in range(4):
    if keydown(i):
        if i == (3,2,1,0)[pacman.d]:
            pacman.d = i
        pacman.nd = i
if pacman.espace():
    pacman.d = pacman.nd

Sixième étape : Gestion des pac-gommes

Vous l’aurez peut-être remarqué mais le jeu est relativement fluide et rapide.Retour ligne automatique
Tout ça repose sur une grosse optimisation sur les pac-gommes, sans cette optimisation, le jeu tourne à 4 IPS.

Une question importante se pose : Comment réussir à afficher et rafraichir les pac-gommes ?

Une première approche innocente serait de stocker les pac-gommes sous forme de tableau de 0, 1 et 2 et le parcourir en affichant ou non les précieuses gommes. Sauf que là, bonjour le temps pour chaque image…

Une deuxième approche est de créer deux listes d’entier et d’utiliser les opérateurs binaires et les soustractions pour stocker les pac-gommes.Retour ligne automatique
Enfin, et c’est la l’énorme gain de temps. Pour chaque entités, après un mouvement, on regarde dans les deux listes si une (super) pac-gomme se trouve sur la case précédente, que ce soit un mur ou non, et on dessine une pac-gomme si besoin. Et c’est comme ça qu’on atteint une fluidité de jeu.

En plus, au lieu d’un parcours de liste, on a juste a implémenter les cinq lignes suivantes :

px, py = int(self.x - 5.5*dx), int(self.y - 5.5*dy)
if pacgommes[py]>>(bits-1-px) & 1:
    fill_rect(px*10+144,py*10+5,2,2,(250, 207, 173))
if superpacgommes[py]>>(bits-1-px) & 1:
    fill_rect(px*10+143,py*10+4,4,4,(250, 207, 173))

Septième étape : Gestion du score et des états des fantômes

Pour le score, on a juste à implémenter les règles citées en début d’article.

Pour la gestion des états des fantômes, c’est un peu plus compliqué qu’une simple variable.
Il faut rajouter un attribut afin que lorsqu’on mange un fantôme, il ne soit plus effrayé sans pour autant que les autres ne le soient plus.
Enfin, il faut rajouter une clock qui nous permettra de rendre leur état normal au fantômes après un certain temps en le rendant blanc juste avant pour alerter le joueur.

Conclusion

Evidemment, je ne me suis pas attardé sur tous les détails car se serait beaucoup trop long. Mais ce sont les éléments principaux pour un Pac-Man.
Je n’ai pas rajouté les changement de phases entre Chase et Scatter, de peur d’impacter les performances ou de dépasser la place disponible en mémoire.
Le Pac-Man fini rend bien :

Code jouable disponible ici :

Projets

Un Tetris en python pour la NumWorks

Tout le monde sait qu’une calculatrice programmable sert à jouer à des jeux. Or quand on parle de jeux, un des premiers à nous venir en tête est Tetris, alors pourquoi pas un Tetris pour NumWorks ?

Ainsi, après un démineur, un snake, on vous propose cette fois ci le jeu mythique de la Gameboy adapté en flat design et codé en python pour la NumWorks.

Donne moi 32 ko, je te ferai un Tetris !

Jusqu’à la version 13.2 d’Epsilon, l’OS officiel de la NumWorks, faire un jeu en python sur la couche graphique de la NumWorks était impossible et les scripts commençaient à planter dès qu’ils pesaient 3-4 ko.

Avec un tas python heap de 32 ko, on peut enfin commencer à s’amuser et monter des projets dont le code source pèse près de 8ko.

Le récit de la création d’un jeu en image

Tout commença le 19 avril 2020 dans une nuit confinée.

🧐 Bon on vient de finir nos trois projets en python, on fait quoi maintenant ?
🤓 Oh on peut acheter des contrefaçon de Gameboy sur Aliexpress pour 10€ ! Et il y a 400 jeux dedans.
🧐 La nuit porte conseil, on en parle demain, enfin dans quelques heures !

Le lendemain :

🧐 Bon on fait un Tetris. Je viens de lire l’article sur Wikipédia, c’est passionnant. Par contre par un mot à Arthur, il va nous piquer notre idée sinon. Et cette fois, on ne stocke pas coordonnées des cases occupées dans des matrices, et on va utiliser la fonction get_pixel() de la NumWorks pour déterminer si une case est occupée ou non.

et c’est ainsi qu’un premier Tétrominos apparaît à l’écran.

🤓 J’ai peut être fini la collision
🧐 Hein ?! Mais j’ai pas commencé moi…
🧐 Bon je partage l’écran. Qu’est ce qu’on a dit déjà ? 120 pixels pour le menu, 120 pixels pour le score et 42 pixels pour le jeu en lui même c’est bien ça ?


🧐 Bon je viens de finir la maquette d’une ébauche de menu, reste à le coder !
🤓 et moi je viens de finir les collisions …
🧐 Pour les couleurs ça sera délicat et subtil. On va s’écarter du code couleur original.

🧐 Et du coup on va faire un rappel dans le menu
🤓 On fixe les points d’ancrage dans les pièces, et ainsi elles peuvent tourner

Rendu final souhaité (et obtenu)

🤓 Astuce : Si tu joues sur Omega, alors l’interface du jeu n’est plus orange mais rouge, elle s’adapte au fork de Epsilon.

🧐 D’ailleurs faudra que je relance l’équipe de développement de Omega, ils m’ont promis un tas python de 120 ko et j’ai l’impression que ce projet n’avance pas !
🧐 Bon ils sont encore sur répondeur, ils ont du bloquer mon numéro !
🤓 On fait une pause, j’ai envie de jouer un peu :

🧐 Bon je vais spoiler Critor de tiplanet.org mais toujours aucune info à Arthur !
🤓 Score codé, avec des fonctions polynôme et les points marqués dépendent du niveau du jeu …
🧐 Niveau max : 99, Score max : 999 999
🤓 Vitesse du jeux codé, avec une fonction logarithme népérien car un polynôme n’était pas adapté …

🧐 Bon maintenant s’agit de faire un gros score, histoire d’être certain que Critor ne nous batte pas !

Commencé un dimanche, fini le mercredi suivant, c’était presque trop facile !

🧐 Je reviens, je vais conseiller à Critor de commencer level 42, ça plantera son score !

Meilleurs scores

🧐 Il a commencé sa partie directement au niveau 42, du coup son score est à peine acceptable !🤓 En plus, il a triché ! Il a utilisé une vision prédictive triple et la grille d’aide !

Bien évidemment, il a nié avoir triché 🙄

Je ne les ai même pas utilisés, c’était pour mettre à l’écran le maximum d’éléments visuels, car j’étais parti pour l’utiliser également comme photo d’illustration d’article

Xavier Andréani, alias Critor du tiplanet.org

Mais nous ne sommes pas dupes non plus !

Réagir ou commenter ce jeu

N’hésitez à réagir à cet article sur le forum tiplanet.org associé :
Tetris en Python pour NumWorks 13.2.0+

Vous pouvez également réagir à l’annonce de ce Tetris posté sur twitter :

Projets

Solveur de Sudoku en Python

C’était il y a quelques semaines, je me baladais sur le Play Store en quête de divertissement quand j’ai trouvé la perle rare : une application de sudoku. Je m’y suis donc mis (je n’y avais jamais joué auparavant) et je me suis découvert une passion pour ce jeu mathématique.

Or, comme dit le proverbe :

Il faut être intelligemment paresseux. 

J’ai donc réalisé un solveur de sudoku en Python, avec une interface graphique utilisateur (GUI).

Présentation du projet :

L’objectif :

Un script capable de résoudre n’importe quel sudoku, des plus simples aux plus complexes.

Cahier des charges :

  • Le programme doit résoudre n’importe quel sudoku.
  • Bien optimisé pour ne pas être trop gourmand en RAM et en mémoire.
  • Il doit présenter une interface graphique intuitive et plaisante :
    • Une grille bien dessinée et interactive.
    • La case survolée par la souris doit changer de couleur.
    • Il suffit d’appuyer sur une touche du pavé numérique pour entrer le chiffre et sur Effacer pour effacer.
    • Un bouton avec Entrée comme raccourcis pour résoudre le sudoku.

Réflexions :

La principale question est la suivante : Comment résout-on un Sudoku ?
Après recherches personnelles puis, sur Internet, j’ai obtenu une liste de méthodes de recherches :

  • Par inclusion : Si une case admet une seule possibilité de nombre, alors ce nombre est solution.
  • Par exclusion : Si un secteur admet une seule case possible pour un nombre, alors ce nombre est solution. Est appelé secteur, une ligne, une colonne ou un carré.
  • Par paires exclusives : Si un couple de nombre (n,m) est possible sur deux cases d’un secteur, alors la probabilité qu’ils soient sur d’autres cases du secteur est de 0.
  • Par triplets exclusifs :
    • Triplet parfait : Comme pour les paires exclusives mais avec un triplet (n,m,k).
    • Triplet tronqué : Le triplet est présent sur deux cases et présente deux nombres du triplet sur une troisième.
    • Triplet doublement tronqué : Le triplet est présent sur une case et présente deux nombres du triplet sur deux autres.
  • Choix multiple (ou essais-erreur) : On teste une des possibilité d’une case présentant le moins de possibilité si et seulement si la grille est figée dans un état.

Programmation du moteur de résolution :

Pour bien programmer, il est important d’avoir les idées claires.

Aussi, j’ai commencé par m’occuper de toutes les méthodes de recherche en omettant l’essais-erreur.
Car il faut être capable de résoudre les possibilité d’une grille avant de savoir si elle est figée…

Pour tout le script, grille est le tableau qui stocke la grille et grilleFinie celui qui stocke « l’état » des cases, c’est-à-dire, si leur valeur est solution de la case (True) ou non (False).

J’ai organisé mon travail en 3 parties :

Moteur principalRecherche pour une caseVérification
La fonction chercher()La fonction solutions()La fonction verifier()

La fonction verifier(l=0,c=0)

Commençons par la plus simple : cette fonction accepte deux paramètres qui représentent la ligne et la colonne dans la grille.

Si l == 0 et c == 0 (quand on écrit verifier()), alors la fonction vérifie toutes les cases de la grille.
Pour tout vérifier, on suit la logique suivante pour chaque cases :

La case contient une listeLa case contient un entier
Si la liste contient 1 élément différent de 0 : VraiSi entier différent de 0 : Vrai

Si on donne des valeurs différentes à l et c, on vérifie juste la case en appliquant la logique précédente en voulant que la case contienne une liste.

Le code :

def verifier(l=0,c=0):
    global grille,grilleFinie
    if not l and not c:
        for i in range(9):
            for j in range(9):
                if type(grille[i][j]) is list:
                    if len(grille[i][j]) == 1 and grille[i][j][0]:
                        grilleFinie[i][j] = True
                        grille[i][j] = grille[i][j][0]
                else:
                    if grille[i][j] != 0:
                        grilleFinie[i][j] = True
    else:
        if type(grille[l][c]) is list:
            if len(grille[l][c]) == 1 and grille[l][c][0]:
                grilleFinie[l][c] = True
                grille[l][c] = grille[l][c][0]

La fonction solutions(l,c,ites)

C’est la fonction la plus longue du script (un beau bébé de 131 lignes), cette fonction applique un certain nombre d’opérations sur une case et ses 3 secteurs.

Cette fonction prend en compte trois paramètres obligatoires :

  • l pour la ligne de la case
  • c pour la colonne de la case
  • ites pour le nombre d’itérations dans la couche de récursion (voir fonction chercher())

Dans un premier temps, il faut savoir dans quel carré se situe la case, et pour ça, on a besoin de deux lignes :

lc = l in [0,1,2] and [0,1,2] or l in [3,4,5] and [3,4,5] or l in [6,7,8] and [6,7,8]
cc = c in [0,1,2] and [0,1,2] or c in [3,4,5] and [3,4,5] or c in [6,7,8] and [6,7,8]

On pourrait décomposer chacune de ces lignes en 6 lignes pour mieux comprendre :

lc = l in [0,1,2] and [0,1,2] or l in [3,4,5] and [3,4,5] or l in [6,7,8] and [6,7,8]
# Est strictement equivalent à :
if l in [0,1,2]:
    lc = [0,1,2]
elif l in [3,4,5]:
    lc = [3,4,5]
elif l in [6,7,8]:
    lc = [6,7,8]
# Avec : l in [0,1,2] ssi 0 <= l <= 2

Intéressons nous maintenant aux méthodes de recherche :
Elles ne s’activerons que si la case de grilleFinie correspondante contient False.

Par inclusion :

Si nous sommes sur la première itération de la couche, on affecte à la case une liste contenant tout les nombre de 1 à 9, on supprimera au fur et à mesure les issues impossibles.

Ensuite, pour chaque case (i,j) avec (i,j) != (l,c) de chaque secteur :

  • Si la case contient un entier : On supprime, s’il est dedans, le nombre de la liste des issues possibles.
  • Si la case contient une liste : On la passe.

Ainsi, on supprime toute les valeurs qui ne sont pas solution.

Le code :

if not grilleFinie[l][c]:
    if not ites:
        grille[l][c] = [1,2,3,4,5,6,7,8,9]
    for k in range(9):
        if grilleFinie[l][k] and grille[l][k] in grille[l][c] and k != c:
            grille[l][c].remove(grille[l][k])
        if grilleFinie[k][c] and grille[k][c] in grille[l][c] and k != l:
            grille[l][c].remove(grille[k][c])
    for i in lc:
        for j in cc:
            if grilleFinie[i][j] and grille[i][j] in grille[l][c] and (i,j) != (l,c):
                grille[l][c].remove(grille[i][j])
    verifier(l,c)

Par exclusion :

Il faut que cette méthode se déclenche après une itération car toute les listes d’issues probables doivent être définies.

Cette méthode est en deux parties :

Pour chaque nombre contenus dans la liste des possible, on :

  • Compte le nombre d’apparition du nombre dans chaque secteur
  • Si le nombre n’apparaît pas, il est solution car sa probabilité d’être solution est 1

Une fois qu’on a trouvé la solution, il est important de supprimer la possibilité dans les autres secteurs (si un seul secteur permet de déduire la solution, il faut « débloquer » les autres)

Ainsi, on code :

if not grilleFinie[l][c] and ites:
    for nb in grille[l][c]:
        compteur = [0,0,0]
        for k in range(9):
            if not grilleFinie[l][k] and k != c:
                for n in grille[l][k]:
                    compteur[0] += int(n == nb)
            if not grilleFinie[k][c] and k != l:
                for n in grille[k][c]:
                    compteur[1] += int(n == nb)
        for i in lc:
            for j in cc:
                if not grilleFinie[i][j] and (i,j) != (l,c):
                    for n in grille[i][j]:
                        compteur[2] += int(n == nb)
        if compteur[0] == 0 or compteur[1] == 0 or compteur[2] == 0:
            grilleFinie[l][c] = True
            grille[l][c] = nb   
            for k in range(9):
                if not grilleFinie[l][k] and grille[l][c] in grille[l][k] and k != c:
                    grille[l][k].remove(grille[l][c])
                if not grilleFinie[k][c] and grille[l][c] in grille[k][c] and k != l:
                    grille[k][c].remove(grille[l][c])
            for i in lc:
                for j in cc:
                    if not grilleFinie[i][j] and grille[l][c] in grille[i][j] and (i,j) != (l,c):
                        grille[i][j].remove(grille[l][c])
            break

Attardons-nous sur deux points importants :

compteur[x] += int(n == nb)

Cette ligne permet de coder la condition et le compteur sur la même ligne. En effet, si la condition retourne True, alors le compteur gagne 1, sinon, il gagne 0, ce qui est exactement ce qu’on veut.

break

A la fin du code, le break est nécessaire car il permet de ne pas faire planter le programme. En effet, la boucle parente (c’est-à-dire, celle la « plus proche ») du break est :

Une fois qu’on a trouvé la solution, il ne faut plus chercher, donc arrêter la boucle avec un break.

Par paires exclusives :

Le « principe » est le même : la méthode ne se déclenche qu’après une itération et on observe les 3 secteurs de la case.

Il faut que la case contienne une liste de 2 de longueur.

Pour les paires, c’est assez simple, il s’agit de vérifier si la même paire est présente sur une autre case, et si oui, éliminer les composantes de la paire dans les autres cases du secteur concerné.

Ainsi, on code :

    if not grilleFinie[l][c] and ites and len(grille[l][c]) == 2:
        existe = [False,False,False]
        for k in range(9):
            if not grilleFinie[l][k] and grille[l][k] == grille[l][c] and k != c:
                existe[0] = True
            if not grilleFinie[k][c] and grille[k][c] == grille[l][c] and k != l:
                existe[1] = True
        for i in lc:
            for j in cc:
                if not grilleFinie[i][j] and grille[i][j] == grille[l][c] and (i,j) != (l,c):
                    existe[2] = True
        if existe[0]:
            for k in range(9):
                if not grilleFinie[l][k] and grille[l][k] != grille[l][c]:
                    for n in grille[l][k]:
                        if n in grille[l][c]:
                            grille[l][k].remove(n)
        if existe[1]:
            for k in range(9):
                if not grilleFinie[k][c] and grille[k][c] != grille[l][c]:
                    for n in grille[k][c]:
                        if n in grille[l][c]:
                            grille[k][c].remove(n)
        if existe[2]:
            for i in lc:
                for j in cc:
                    if not grilleFinie[i][j] and grille[i][j] != grille[l][c]:
                        for n in grille[i][j]:
                            if n in grille[l][c]:
                                grille[i][j].remove(n)

Ici, pas de nouvelles astuces de programmation, juste beaucoup de boucles et conditions imbriquées.

Par triplet exclusifs :

C’est ici que les choses se corsent…
On note que c’est la partie la plus longue de la fonction, faisant 42 lignes.

En effet, même si on applique le même principe que pour les paires, il faut aussi permettre au programme de détecter quand les triplets ne sont pas complets (cf début de l’article).

Il faut que la case contienne une liste de 3 de longueur.

Partie 1 : La recherche du triplet, quel qu’il soit

    existe = [[],[],[]]
    decompo = [[grille[l][c][0],grille[l][c][1]],[grille[l][c][1],grille[l][c][2]],[grille[l][c][0],grille[l][c][2]]]
    for k in range(9):
        if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
            existe[0].append(grille[l][k])
        if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
            existe[1].append(grille[k][c])
    for i in lc:
        for j in cc:
            if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
                existe[2].append(grille[i][j])

Qu’est-ce qu’il se passe ?

Pour commencer, on organise notre pensée :

existedecompo
Liste contenant une liste des triplets/couples correspondant à la conditionListe contenant les couples possibles à partir du triplet de départ
[a,b,c] => [a,b],[b,c],[a,c]

Ensuite, pour chaque case de chaque secteur, on regarde si :

  • La case contient le triplet souhaité
  • La case contient un des couples de decompo

A l’aide de la condition suivante :

(grille[k][c] == grille[l][c] or grille[k][c] in decompo

Partie 2 : La vérification du triplet

    for k in range(3):
        triplet = []
        if len(existe[k]) == 2:
            for i in [0,1]:
                for n in existe[k][i]:
                    if n not in triplet:
                        triplet.append(n)
            if triplet != grille[l][c]:
                existe[k] = False
        else:
            existe[k] = False

Qu’est-ce qu’il se passe ?

Pour chaque secteur :

On vérifie qu’il y ait bien existence de 2 éléments.
On vérifie ensuite que les éléments présents dans les couples/triplets donne bien le triplet de départ (afin d’éviter que les paires ne s’immiscent et créent des erreurs).

Si une de ces condition n’est pas respectée, existe devient False pour le secteur concerné.

Partie 3 : Suppression des possibilités dans les autres cases

C’est comme pour les paires exclusives à la différence près que l’on doit également vérifier que les autres cases ne contiennent pas un des couples de existe.

Code final :

    if not grilleFinie[l][c] and ites and len(grille[l][c]) == 3:
        existe = [[],[],[]]
        decompo = [[grille[l][c][0],grille[l][c][1]],[grille[l][c][1],grille[l][c][2]],[grille[l][c][0],grille[l][c][2]]]
        for k in range(9):
            if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
                existe[0].append(grille[l][k])
            if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
                existe[1].append(grille[k][c])
        for i in lc:
            for j in cc:
                if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
                    existe[2].append(grille[i][j])
        for k in range(3):
            triplet = []
            if len(existe[k]) == 2:
                for i in [0,1]:
                    for n in existe[k][i]:
                        if n not in triplet:
                            triplet.append(n)
                if triplet != grille[l][c]:
                    existe[k] = False
            else:
                existe[k] = False
        if existe[0]:
            for k in range(9):
                if not grilleFinie[l][k] and grille[l][k] != grille[l][c] and grille[l][k] not in existe[0]:
                    for n in grille[l][k]:
                        if n in grille[l][c]:
                            grille[l][k].remove(n)
        if existe[1]:
            for k in range(9):
                if not grilleFinie[k][c] and grille[k][c] != grille[l][c] and grille[k][c] not in existe[1]:
                    for n in grille[k][c]:
                        if n in grille[l][c]:
                            grille[k][c].remove(n)
        if existe[2]:
            for i in lc:
                for j in cc:
                    if not grilleFinie[i][j] and grille[i][j] != grille[l][c] and grille[i][j] not in existe[2]:
                        for n in grille[i][j]:
                            if n in grille[l][c]:
                                grille[i][j].remove(n)

La fonction chercher(ee=0,ite=0)

Cette fonction est une fonction récursive, c’est-à-dire, capable de se lancer elle-même pour résoudre des problèmes plus complexes.

La première partie est juste une déclaration de variables suivie d’un affichage console d’un arbre :

    global grilleFinie,grille
    iterations = 0
    grilleTest = [[0]*9 for n in range(9)]
    grilleBack = [[0]*9 for n in range(9)]
    cellBack = [0,0,9,[]]
    if ee:
        print(ite,"iter"+"s"*(ite!=1))
    print(" "*(ee-1)+"|"*(ee!=0)+"_ couche",ee,end=" => ")

On retrouve ici les astuces avec les conditions pour afficher ou non certains caractères.
En python, « x »*5 retourne « xxxxx », ainsi, « x »*0 retourne «  »

Tableau des variables :

grilleTestgrilleBackcellBack
Sauvegarde de la grille avant fonction solutions()Sauvegarde de la grille avant récursionSauvegarde de la case modifiée pour essais-erreur

On aborde ensuite une boucle do…while. Petit problème, elles n’existent pas en python, il est donc nécessaire de la recréer. Et pour ça, on écrit une boucle infinie (un while toujours vrai) avec la condition contenant un break ou un return (qui arrête la fonction et non la boucle).

Voici donc la base :

    while "solution non determinee":
        grilleTest = copie(grille)
        for i in range(9):
            for j in range(9):
                solutions(i,j,iterations)
        if grilleFinie == [[True]*9 for n in range(9)]:
            print(iterations,"iter"+"s"*(iterations!=1))
            affG()
            return True

A cause d’un bug incompréhensible, j’ai du recréer la méthode .copy() des liste, d’où la fonction copie()

Ce système est déjà capable de résoudre jusqu’aux sudokus « difficiles » de certaines applications et revues.

Pourquoi un return True et pas un break ?

Notre récursion fonctionne sur une condition (remplie pour rappel, uniquement si la grille est « figée ») que voici :

    if grilleTest == grille:
            grilleBack = copie(grille)
            for i in range(9):
                for j in range(9):
                    if not grilleFinie[i][j] and cellBack[2] > len(grille[i][j]):
                        cellBack = [i,j,len(grille[i][j]),grille[i][j]]
            for n in cellBack[3]:
                grille[cellBack[0]][cellBack[1]] = n
                if chercher(ee+1,iterations):
                    return True
                else:
                    grilleFinie = [[False]*9 for n in range(9)]
                    grille = copie(grilleBack)
                    verifier()
            return False  
        else:
            iterations += 1

Elle est organisée en 3 parties distinctes :

  • On commence par faire une sauvegarde de la grille.
  • On sélectionne la case avec le moins de possibilité de réponses, on garde ses coordonnées et son contenu.
  • Pour chaque possibilité, on lance la fonction en couche n+1.
    • Si la fonction renvoie True (d’où le return True), on renvoie TrueRetour ligne automatique
      Cela permet de tuer les fonctions enfants d’un coup.
    • Sinon, on remet la grille dans l’état sauvegardé.
  • Si toutes les possibilités sont testés et qu’aucune solution n’est trouvé, on renvoie False.

Seulement, il nous manque une dernière chose : Que se passe t’il si le programme attribue une mauvaise solution pour une case ?

Il se trouve que, quand il se trompe, le programme finit par attribuer des listes vides à des cases (car la résolution rend impossible la possibilité d’un nombre sur la case), il suffit de donc de détecter ces cases avant de vérifier que la grille soit « figée ».

    for i in range(9):
        for j in range(9):
            if grille[i][j] == []:
                return False

Programmation du moteur graphique :

Comme vous pouvez le remarquer, on observe que le texte d’aide nous explique d’appuyer sur des touches, et oui : pour la GUI, il faut faire de la programmation événementielle !

A savoir :

  • J’ai nommé ma fenêtre fenetre et mon canevas (support pour le graphisme) interface.
  • J’ai crée un tableau cases des ID des cases et un tableau textCase associé.
  • Cet attribut pour les cases activefill="#e0e0e0" permet d’avoir les cases grisées au survol de la souris.

La fonction event(touche)

Cette fonction est la fonction liée à la fenêtre par fenetre.bind("<Key>",event) ce qui veut dire que quand on va appuyer sur une touche, les informations vont être envoyées à la fonction (d’où le paramètre touche).

touche est un objet contenant plusieurs variables, on s’intéresse à la variable keysym (le nom en clair de la touche), ainsi : toucheK = touche.keysym

Commençons par le plus simple :

    if toucheK == "Return":
        chercher()
    if toucheK == "Delete":
        nouv()
     
    # La fonction nouv()
    def nouv():
        global grille,grilleFinie,textCase
        grille = [[0]*9 for n in range(9)]
        grilleFinie = [[False]*9 for n in range(9)]
        textCase = [[False]*9 for n in range(9)]
        interface.delete("case")

Si j’appuie sur Entrer, je commence la recherche, sur Suppr, j’efface tout.

Maintenant, le plus intéressant, si je veux ajouter un chiffre.

Voici le code :

    if toucheK in "123456789":
            eff = False
            if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
                interface.delete(interface.find_closest(touche.x,touche.y)[0])
                eff = True
            for i in range(9):
                for j in range(9):
                    if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                        if not eff and not grille[i][j]:
                            grille[i][j] = int(toucheK)
                        if eff:
                            grille[i][j] = int(toucheK)
                            textCase[i][j] = False
                        break
                if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                    break
            affG(i,j,toucheK)

Ce script commence par détecter s’il y a un chiffre sur la case et si oui, il le supprime.

Le script cherche ensuite à quelle case correspond les coordonnées de l’événement. Une fois trouvées, s’il n’a rien effacée et que la case est vide, il la remplit, s’il a effacé un nombre, il change la valeur de la case et précise qu’il n’y a pas de nombre.

Enfin, les deux break permettent de sortir des deux boucles.
Nous verrons après la fonction affG.

Si je veux enlever un chiffre, il suffit d’appuyer sur Effacer pour lancer ce code :

    if toucheK == "BackSpace":
        if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
            interface.delete(interface.find_closest(touche.x,touche.y)[0])
            for i in range(9):
                for j in range(9):
                    if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                        grille[i][j] = 0
                        textCase[i][j] = False
                        break
                if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                    break

Ce code est très similaire à celui de l’ajout d’un nombre.

La fonction affG(x=-1,y=-1,nb=-1)

Quand on observe la fonction, deux choses sont frappantes : les lignes 7 et 11.

    def affG(x=-1,y=-1,nb=-1):
        global textCase,cases
        if (x,y) == (-1,-1):
            for x in range(9):
                for y in range(9):
                    if not textCase[x][y]:
                        interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=str(grille[x][y]),font=("Helvetica","16","bold"),fill="#0f0fa0",tags="case")
        else:
            if not textCase[x][y]:
                textCase[x][y] = True
                interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=nb,font=("Helvetica","16","bold"),tags="case")

Ces lignes positionne un texte au milieu de la case correspondante en lui ajoutant un tag (une étiquette) : « case ».
On remarque que quand x = y = -1, les nombres sont ajoutés en #0f0fa0.

Ce tag permet à la fonction nouv() de pouvoir supprimer tout les textes en une ligne.

Conclusion :

Notre programme est doté d’une interface graphique agréable permettant de bien visualiser nos sudoku pour les rentrer de façon intuitive. Notre cahier des charges semble être respecté.

Mais l’est-il vraiment ?

Il nous reste à vérifier s’il est capable de résoudre n’importe quel sudoku. Pour cela, je pars du principe suivant :

Qui peut le plus, peut le moins.

Ainsi, je décide de l’essayer avec Al Escargot, le sudoku le plus difficile du monde.

Pour ordre d’idée, il est classé 100 étoiles (contre 7 max pour ceux de revues) soit 5000 coups pour le résoudre, ce qui équivaut à environ 3 jours pour un habitué.

On entre donc la grille :

Après moins d’une seconde :

On remarque l’arbre en retour discret sur notre IDE :

Notre solveur remplit parfaitement ses fonction !

Code complet :

Voici le code complet, en téléchargeable puis en texte :

    # Solveur de Sudoku
    # par Fedyna K.
     
    from tkinter import Tk,Canvas
     
    # GUI
     
    fenetre = Tk()
    fenetre.title("Solveur de Sudoku - NSI")
    fenetre.resizable(False,False)
     
    interface = Canvas(fenetre,width=400,height=500,bg="white")
    interface.pack()
    interface.create_text(5,400,anchor="nw",text="Pour ajouter un chiffre, survolez la case correspondante et appuyez sur\nle pavé numérique.",tags="i")
    interface.create_text(5,435,anchor="nw",text="Pour supprimer un chiffre, survolez la case et appuyez sur 'Effacer'.",tags="i")
    interface.create_text(5,455,anchor="nw",text="Pour résoudre la grille, appuyez sur 'Entrer'.",tags="i")
    interface.create_text(5,480,anchor="nw",text="Pour tout effacer, appuyez sur 'Suppr'.",tags="i")
     
    interface.create_rectangle(12,7,15,379,fill="black")
    interface.create_rectangle(381,7,384,379,fill="black")
    interface.create_rectangle(12,7,384,10,fill="black")
    interface.create_rectangle(12,376,384,379,fill="black")
    cases = [[0]*9 for n in range(9)]
    textCase = [[False]*9 for n in range(9)]
    ic = 0
    ie = 0
    for i in range(15,369,40):
        jc = 0
        je = 0
        for j in range(10,364,40):
            cases[jc][ic] = interface.create_rectangle(i+ie,j+je,i+ie+40,j+je+40,fill="white",activefill="#e0e0e0")
            jc += 1
            if jc in [3,6]:
                interface.create_rectangle(12,j+43+je,384,j+40+je,fill="black")
                je += 3
        ic += 1
        if ic in [3,6]:
            interface.create_rectangle(i+43+ie,7,i+ie+40,379,fill="black")
            ie += 3
     
    def event(touche):
        global grille,textCase,cases
        toucheK = touche.keysym
        if toucheK in "123456789":
            eff = False
            if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
                interface.delete(interface.find_closest(touche.x,touche.y)[0])
                eff = True
            for i in range(9):
                for j in range(9):
                    if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                        if not eff and not grille[i][j]:
                            grille[i][j] = int(toucheK)
                        if eff:
                            grille[i][j] = int(toucheK)
                            textCase[i][j] = False
                        break
                if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                    break
            affG(i,j,toucheK)
        if toucheK == "Return":
            chercher()
        if toucheK == "Delete":
            nouv()
        if toucheK == "BackSpace":
            if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
                interface.delete(interface.find_closest(touche.x,touche.y)[0])
                for i in range(9):
                    for j in range(9):
                        if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                            grille[i][j] = 0
                            textCase[i][j] = False
                            break
                    if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
                        break
     
    def affG(x=-1,y=-1,nb=-1):
        global textCase,cases
        if (x,y) == (-1,-1):
            for x in range(9):
                for y in range(9):
                    if not textCase[x][y]:
                        interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=str(grille[x][y]),font=("Helvetica","16","bold"),fill="#0f0fa0",tags="case")
        else:
            if not textCase[x][y]:
                textCase[x][y] = True
                interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=nb,font=("Helvetica","16","bold"),tags="case")
       
    fenetre.bind("<Key>",event)
     
    # Moteur de resolution
     
    def nouv():
        global grille,grilleFinie,textCase
        grille = [[0]*9 for n in range(9)]
        grilleFinie = [[False]*9 for n in range(9)]
        textCase = [[False]*9 for n in range(9)]
        interface.delete("case")
     
    def solutions(l,c,ites):
        global grille,grilleFinie
        verifier()
       
        lc = l in [0,1,2] and [0,1,2] or l in [3,4,5] and [3,4,5] or l in [6,7,8] and [6,7,8]
        cc = c in [0,1,2] and [0,1,2] or c in [3,4,5] and [3,4,5] or c in [6,7,8] and [6,7,8]
       
        # Methode de recherche : Inclusion
       
        if not grilleFinie[l][c]:
            if not ites:
                grille[l][c] = [1,2,3,4,5,6,7,8,9]
            for k in range(9):
                if grilleFinie[l][k] and grille[l][k] in grille[l][c] and k != c:
                    grille[l][c].remove(grille[l][k])
                if grilleFinie[k][c] and grille[k][c] in grille[l][c] and k != l:
                    grille[l][c].remove(grille[k][c])
            for i in lc:
                for j in cc:
                    if grilleFinie[i][j] and grille[i][j] in grille[l][c] and (i,j) != (l,c):
                        grille[l][c].remove(grille[i][j])
            verifier(l,c)
           
        # Methode de recherche : Exclusion (ap 1 iteration)
       
        if not grilleFinie[l][c] and ites:
            for nb in grille[l][c]:
                compteur = [0,0,0]
                for k in range(9):
                    if not grilleFinie[l][k] and k != c:
                        for n in grille[l][k]:
                            compteur[0] += int(n == nb)
                    if not grilleFinie[k][c] and k != l:
                        for n in grille[k][c]:
                            compteur[1] += int(n == nb)
                for i in lc:
                    for j in cc:
                        if not grilleFinie[i][j] and (i,j) != (l,c):
                            for n in grille[i][j]:
                                compteur[2] += int(n == nb)
                if compteur[0] == 0 or compteur[1] == 0 or compteur[2] == 0:
                    grilleFinie[l][c] = True
                    grille[l][c] = nb  
                    for k in range(9):
                        if not grilleFinie[l][k] and grille[l][c] in grille[l][k] and k != c:
                            grille[l][k].remove(grille[l][c])
                        if not grilleFinie[k][c] and grille[l][c] in grille[k][c] and k != l:
                            grille[k][c].remove(grille[l][c])
                    for i in lc:
                        for j in cc:
                            if not grilleFinie[i][j] and grille[l][c] in grille[i][j] and (i,j) != (l,c):
                                grille[i][j].remove(grille[l][c])
                    break
                   
        # Methode de recherche : Paires exclusives
       
        if not grilleFinie[l][c] and ites and len(grille[l][c]) == 2:
            existe = [False,False,False]
            for k in range(9):
                if not grilleFinie[l][k] and grille[l][k] == grille[l][c] and k != c:
                    existe[0] = True
                if not grilleFinie[k][c] and grille[k][c] == grille[l][c] and k != l:
                    existe[1] = True
            for i in lc:
                for j in cc:
                    if not grilleFinie[i][j] and grille[i][j] == grille[l][c] and (i,j) != (l,c):
                        existe[2] = True
            if existe[0]:
                for k in range(9):
                    if not grilleFinie[l][k] and grille[l][k] != grille[l][c]:
                        for n in grille[l][k]:
                            if n in grille[l][c]:
                                grille[l][k].remove(n)
            if existe[1]:
                for k in range(9):
                    if not grilleFinie[k][c] and grille[k][c] != grille[l][c]:
                        for n in grille[k][c]:
                            if n in grille[l][c]:
                                grille[k][c].remove(n)
            if existe[2]:
                for i in lc:
                    for j in cc:
                        if not grilleFinie[i][j] and grille[i][j] != grille[l][c]:
                            for n in grille[i][j]:
                                if n in grille[l][c]:
                                    grille[i][j].remove(n)
               
        # Methode de recherche : Triplets exculsifs (hors triplet induit)
               
        if not grilleFinie[l][c] and ites and len(grille[l][c]) == 3:
            existe = [[],[],[]]
            decompo = [[grille[l][c][0],grille[l][c][1]],[grille[l][c][1],grille[l][c][2]],[grille[l][c][0],grille[l][c][2]]]
            for k in range(9):
                if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
                    existe[0].append(grille[l][k])
                if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
                    existe[1].append(grille[k][c])
            for i in lc:
                for j in cc:
                    if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
                        existe[2].append(grille[i][j])
            for k in range(3):
                triplet = []
                if len(existe[k]) == 2:
                    for i in [0,1]:
                        for n in existe[k][i]:
                            if n not in triplet:
                                triplet.append(n)
                    if triplet != grille[l][c]:
                        existe[k] = False
                else:
                    existe[k] = False
            if existe[0]:
                for k in range(9):
                    if not grilleFinie[l][k] and grille[l][k] != grille[l][c] and grille[l][k] not in existe[0]:
                        for n in grille[l][k]:
                            if n in grille[l][c]:
                                grille[l][k].remove(n)
            if existe[1]:
                for k in range(9):
                    if not grilleFinie[k][c] and grille[k][c] != grille[l][c] and grille[k][c] not in existe[1]:
                        for n in grille[k][c]:
                            if n in grille[l][c]:
                                grille[k][c].remove(n)
            if existe[2]:
                for i in lc:
                    for j in cc:
                        if not grilleFinie[i][j] and grille[i][j] != grille[l][c] and grille[i][j] not in existe[2]:
                            for n in grille[i][j]:
                                if n in grille[l][c]:
                                    grille[i][j].remove(n)
               
           
    def verifier(l=0,c=0):
        global grille,grilleFinie
        if not l and not c:
            for i in range(9):
                for j in range(9):
                    if type(grille[i][j]) is list:
                        if len(grille[i][j]) == 1 and grille[i][j][0]:
                            grilleFinie[i][j] = True
                            grille[i][j] = grille[i][j][0]
                    else:
                        if grille[i][j] != 0:
                            grilleFinie[i][j] = True
        else:
            if type(grille[l][c]) is list:
                if len(grille[l][c]) == 1 and grille[l][c][0]:
                    grilleFinie[l][c] = True
                    grille[l][c] = grille[l][c][0]
                   
    def chercher(ee=0,ite=0):
        global grilleFinie,grille
        iterations = 0
        grilleTest = [[0]*9 for n in range(9)]
        grilleBack = [[0]*9 for n in range(9)]
        cellBack = [0,0,9,[]]
        if ee:
            print(ite,"iter"+"s"*(ite!=1))
        print(" "*(ee-1)+"|"*(ee!=0)+"_ couche",ee,end=" => ")
        while "solution non determinee":
            grilleTest = copie(grille)
            for i in range(9):
                for j in range(9):
                    solutions(i,j,iterations)
            for i in range(9):
                for j in range(9):
                    if grille[i][j] == []:
                        return False
            if grilleFinie == [[True]*9 for n in range(9)]:
                print(iterations,"iter"+"s"*(iterations!=1))
                affG()
                return True
            if grilleTest == grille:
                grilleBack = copie(grille)
                for i in range(9):
                    for j in range(9):
                        if not grilleFinie[i][j] and cellBack[2] > len(grille[i][j]):
                            cellBack = [i,j,len(grille[i][j]),grille[i][j]]
                for n in cellBack[3]:
                    grille[cellBack[0]][cellBack[1]] = n
                    if chercher(ee+1,iterations):
                        return True
                    else:
                        grilleFinie = [[False]*9 for n in range(9)]
                        grille = copie(grilleBack)
                        verifier()
                return False  
            else:
                iterations += 1
       
    def copie(l):
        re = [[0]*9 for n in range(9)]
        for i in range(9):
            for j in range(9):
                re[i][j] = l[i][j]
        return re
     
    nouv()
    fenetre.mainloop()
Projets

Le défi de python, concours tiplanet.org

En naviguant par hasard sur le site tiplanet.org, nous sommes tombé sur un défi Python et comme se perfectionner en python était l’un de nos objectifs, autant joindre l’utile à l’agréable.

Concours de rentrée 2019 – défi de Python

Pour le défi python 2019 des sites internet tiplanet.org et planet-casio.com , il fallait se constituer une main de 10 pokemons maximum et leur attribuer une priorité d’attaque.

Pour cela, un script Python va offrir à ta calculatrice la fonction pk(n,p) pour ajouter un Pokémon à ta main, avec :
n, le numéro de Pokémon de 1 à 94
p, la priorité d’attaque que tu souhaites donner au Pokémon en question (1 par défaut)

Dans la suite de l’article, le « nous » fait référence au participant 16 et au participant 17, car nous avons réalisé les recherches en commun.

Recherche pifométrique manuelle

Comme beaucoup de joueurs, nous avons commencé par générer des mains au petit bonheur la chance, gratifié d’un score maximum de 44,2 nous sommes vite passé à une autre méthode.

Nous aurions bien voulu commencer les recherches sur la NumWorks, mais les problèmes de mémoires dont-elle souffre à cette époque, avant la mise à jour 13.2 rendent ces recherches impossibles sur la calculatrice.

Ajouter quelques lignes de codes au script de 3.7 ko aurait fait planter la calculatrice.

Nous sommes donc passé sur Thonny et y avons exécuté nos scripts pythons

10 attaques mêlant force brute et analyse statistique

Attaque n°1 : 10n tirages aléatoires

Après avoir neutralisé les fonctions print(), les affichages des scripts du concours, et rajouté quelques variables globales, une boucle de tirage aléatoire fut codée :

import random
 
score, scoremax = 0.0, 0.0
code, codemax = 0.0, 0.0
tentative = 0
 
def tiragemain():
  for i in range(1,11,1):
    pokemonaleatoire = random.randint(1,94)
    score=pk(pokemonaleatoire,i)
  return score,code
 
while score<49.3:
  # Les trois lignes ci-dessous réinitialisent le script, qui tourne sans s'arrêter
  na,pkl=21,[]
  lnm =["Bulbizarre","Herbizarre","Florizarre","Salameche","Reptincel","Dracaufeu",
        "Carapuce","Carabaffe","Tortank","Chenipan","Chrysacier","Papilusion","Aspicot",
        "Coconfort","Dardargnan","Roucool","Roucoups","Roucarnage","Rattata","Rattatac",
        "Piafabec","Rapasdepic","Abo","Arbok","Pikachu","Raichu","Sabelette","Sablaireau",
        "Nidoran F","Nidorina","Nidoqueen","Nidoran M","Nidorino","Nidoking","Melofee",
        "Melodelfe","Goupix","Feunard","Rondoudou","Grodoudou","Nosferapti","Nosferalto",
        "Mystherbe","Ortide","Rafflesia","Paras","Parasect","Mimitoss","Aeromite","Taupiqueur",
        "Triopikeur","Miaouss","Persian","Psykokwak","Akwakwak","Ferosinge","Colossinge","Caninos",
        "Arcanin","Ptitard","Tetarte","Tartard","Abra","Kadabra","Alakazam","Machoc","Machopeur",
        "Mackogneur","Chetiflor","Boustiflor","Empiflor","Tentacool","Tentacruel","Racaillou",
        "Gravalanch","Grolem","Ponyta","Galopa","Ramoloss","Flagadoss","Magneti","Magneton",
        "Canarticho","Doduo","Dodrio","Otaria","Lamantine","Tadmorv","Grotadmorv","Kokiyas",
        "Crustabri","Fantominus","Spectrum","Ectoplasma"]
  mrandmax,mrand,mfmax,nn,mp=2**31-1,0,93,getlinechars(True)-na,na//2
  tentative = tentative+1
  score,code = tiragemain()
  if score>scoremax:
    scoremax = score
    codemax = code
    print("################# tirage n°",tentative,"score =", scoremax,"avec le code", codemax,"#################", round(score,8))

Le résultat n’est pas optimal, on ne tire aléatoirement que les Pokémons en passant naïvement que les forces sont forcement des entiers entre 1 et 10.

Mais on arrive à fabriquer des scores aux alentours de 46,2.
En une nuit, on arrive péniblement à réaliser entre 4 et 7 millions de tirages.

A ce stade de la recherche, compte tenu de nos hypothèses, on cherche une solution optimale parmi 3 . 1019 possibilités. Toute force brute est impossible.

Attaque n°2 : 10n tirages aléatoires

On décide de faire tourner le script précédent et de mémoriser les compositions des mains supérieures à 46

On va donc réaliser quelques millions de tirages, et dénombrer les Pokemons qui ont permis de faire une main supérieure à 46

  if score>46:
    for i in listeobtenu:
      benchmark46(i,score)

Le lendemain, nous avons un histogramme qui nous donne des Pokemons performant.

[0, 54, 25, 143, 11, 99, 39, 23, 5, 10, 6, 11, 9, 17, 10, 31, 70, 13, 12, 10, 48, 15, 38, 51, 18, 6, 21, 33, 13, 19, 5, 8, 13, 48, 13, 33, 35, 5, 31, 24, 31, 9, 33, 94, 28, 13, 5, 106, 16, 8, 34, 51, 27, 6, 13, 3, 36, 33, 42, 4, 17, 9, 72, 311, 3, 16, 30, 25, 32, 74, 13, 60, 172, 40, 12, 62, 44, 1, 8, 38, 6, 32, 15, 22, 21, 101, 25, 24, 73, 19, 26, 5, 33, 4, 18]

Le Pokemon 63 (Abra) est sorti 311 fois dans la nuit dans des mains valant plus de 46 points. Le 64 lui était très mauvais, et il n’était que dans 3 mains valant plus de 46 points.

Attaque n°3 : Tirages aléatoires sur liste optimale

Le deuxième jour, nous avons poursuivi les tirages aléatoires mais sur des listes optimales générées à l’aide de l’histogramme de la veille.

Liste large : [ 3 , 5 , 16 , 33, 43, 47, 51, 58, 62, 63, 69, 71, 72, 73, 75, 76, 85, 88 ]
Liste short : [ 3 , 5 , 16 , 47, 62, 63, 69, 72, 75, 85, 88]

Au lieu de tirer au hasard un Pokémon parmi 94, on le tirait dans une liste prédéfini à diverses positions (nous pensions que la force était la position, donc un entier entre 1 et 11)

def tiragemain():
  listeobtenu =[]
  top = [ 3 , 5 , 16 , 47, 62, 63, 69, 72, 75, 85, 88]
  random.shuffle(top)
  for i in range(1,11,1):    
    pokemonaleatoire = top[i-1]
    listeobtenu.append(pokemonaleatoire)
    score=pk(pokemonaleatoire,i)
  for i in listeobtenu:
    benchmark(i,score)
  if score>47:
    for i in listeobtenu:
      benchmark47(i,score)
  return score,code,listeobtenu

5 000 000 de tirages plus tard, pas de grandes améliorations, 47.6 est notre meilleur score, mais c’est déjà un joli résultat.

Attaque n°4 : Valeur moyenne des mains

Toutes les tentatives pour optimiser la valeur moyenne des mains ont échouées.
Le calcul lui même de cette moyenne n’étant pas concluant.

Attaque n°5 : Recherche des Pokémon forts sur R

En lisant le forum associée à ce défi sur Planète Casio, on croit comprendre qu’il n’y a pas un nombre fini de combinaison, donc si on tire n dans les entiers entre 1 et 94, p lui serait un réel. On relance les scripts précédents et miracle on passe au dessus de 47.8.

def tiragemain():
  listeobtenu =[]
  for i in range(1,11,1):    
    pokemonaleatoire = random.randint(1,94)
    listeobtenu.append(pokemonaleatoire)
    score=pk(pokemonaleatoire,uniform(0,2**31-1))
  if score>46:
    for i in listeobtenu:
      benchmark47(i,score)
  return score,code,listeobtenu

Après avoir affiné la liste des Pokémons optimaux, on relance les autres scripts qui mélangent, permutent, tirent d’après la liste optimale, et on obtient nos premiers score à 48.

code0^uxOeh%_##>(6#))*&#^heO0xku#_D#’’#%$*.0
Score48.1283516409064348.14694065075124

Attaque n°6 : Élimination des plus faibles

N’étant pas certains d’avoir la main optimale, on essaye de remplacer un Pokémon par tous les autres pour voir si le score s’améliore. Cette méthode ne permet pas de progresser.

Attaque n°7 : Tentative de spécifications des fonctions

On décide alors de documenter le code, de le décrypter, d’essayer de voir si on ne peut pas faire le problème à l’envers, c’est une attaque par spécification du code.

def mmod(a, b):
    # retourne la partie décimale de a a vérifier
    # si a est un entier, retourne 0
    # ?? intérêt , a % b économise de la mémoire
    return a % b
 
 
def getplatform():
    # retourne la valeur 1
    # ?? intérêt ?
    return 1
 
 
def getlinechars(o=False):
    # Cette fonction est une bague. Elle est appelée une unique fois avec true
    # et alors getlinechars(True) retourne 99
    c = 2 ** 31 - 1
    k = getplatform()
    # ?? k = 1 ;-)
    if k >= 0:
        # k = 1 donc est exécuté dans 100% des cas ...
        c = [53, o and 99 or 29, o and 509 or 21, 31, 32, c, c][k]
    return c  # c= 99  ... sauf astuce et codage plus bas ^^
    # pas défaut, en l'absence de True getlinechars() retourne 29

Les premières fonctions sont faciles à spécifier. Les variables sont parfois rigolotes :

na = 21
# 42/2 ? :-) Utilisé 2 fois, jamais modifié
mrandmax = 2 ** 31 - 1
# valeur max d'un entier positif signé codé en 32 bits... spé NSI inside
mrand = 0
# rien d'aléatoire ici, sera modifié par la fonction mseed()
mfmax = 93
# 94-1
nn = getlinechars(True) - na
# nn = 99-21 = 78 (sans calculatrice !)
mp = na // 2
# mp = 10, jamais modifié, utilisé une seule fois f° pk

mais nous sommes restés coincés sur les fonctions getattack(), clean() et surtout pk(). µ
Par contre la fonction setst() nous a passionné ! Le script original à peine modifié, commenté et codé en pep8 :

Attaque n°08 : Manipulations autour du code réponse

La liste des Pokémons est codée en dur dans le script, mais il n’en est rien de leurs qualités ni de la valeur de force optimale pour chaque Pokémon. Cette dernière est donc calculée. Or la chaîne de caractère du code réponse semble peu varier lorsque de l’on tire depuis une liste fixé de Pokémons.

Nous comprenons que :

  • La partie gauche code la liste des Pokémons
  • La partie droite leur force
  • Pour un code « ABCDEFGHIJ0987654321« , on a 10 couples (un exemple est ici en gras) qui définissent les 10 Pokémons et leurs points d’attaque.
  • On peut faire de jolie permutation sans changer le score obtenu car les couples n’influent pas les uns sur les autres
  • Il n’y a aucune clé de vérification, on peut tester des codes au hasard sans avoir la moindre idée de la main des Pokémons et de leur forces
  • Les forces sont codés par des caractères ASCII, on n’est plus du tout dans R mais de retour dans N.
def i2c(k):
    # Transforme un nombre décimal en chaine de caractère
    return chr(k + 33)
 
 
def c2i(c):
    # transforme une chaine de caractère ayant un élèment en valeur décimale
    # cette valeur décimale sera comprise entre 32 (a) et 89 (z)
    return ord(c) - 33

En modifiant à la main la partie droite de la chaîne de caractère, on arrive à modifier très substantiellement le score, à la hausse comme à la baisse. Notre premier 49 est obtenu en bricolant à la main la chaîne de caractère.

codeu^KhxO_%#l » » »l » » »%%%
Score49.031613189324844

C’était assez jouissif il faut dire, en changeant un caractère parmi les 10 derniers, notre score pouvait plonger OU augmenter bien plus vite que tous nos algorithme de tirages aléatoires qui tournaient des nuits complètes…

Ce code réponse ne contient que 20 caractères, on connaît déjà les 10 premiers (du moins on le pense) il ne nous reste plus qu’à utiliser la force brute sur les dix derniers caractères.

Attaque n°09 : Force brute

Grace à notre compréhension obtenue avec l’attaque n°08, on a supposé que pour une liste de 10 Pokémons, il existe une suite de forces optimales. On a ainsi écrit un petit script permettant de trouver cette suite optimale :

lc = [None,"!","!","!","!","!","!","!","!","!","!"]
carac = '!"#$%&'+"'"+'()*+^;_,-./0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def cons(liste):
    # Construit le code
    global cc
    cc = ""
    for j in range(len(liste)):
        cc = cc+liste[j]
def turboBoost(pokemons,vitesse=1,style=1):
    # Prend une main de pokemon et lui donne des steroides
    # la chaine finale sous forme de liste pour modifier les caracteres
    lc[0]=pokemons
    # les caracteres a tester (tout ce qui est possible)
    for l in range(vitesse+3):  
        # creation du code par test (5x ou 4x pour trouver "l'etat stable" a tout les coups)
        # vitesse 1 = rapide, vitesse 2 = lent mais plus sur
        for i in range(1,11):
            # On initialise tout
            global cc
            cons(lc)
            scores = [0]
           
            for k in range(len(carac)):
                # On recense le score pour chaque caractere
                lc[i] = carac[k]
                cons(lc)
                score = setst(cc)
                scores.append(score)
            # On prend le gagnant, c'est notre partie de cle
            lc[i] = carac[scores.index(max(scores))-1]
            # on cree le code final
            cons(lc)
         # style pour la fonction (purement cosmetique)
        if style:
            print(int((l+1)*100/(vitesse+3)),"%")
            if vitesse == 1:
                print("====="*(l+1)*2+"....."*(8-(l+1)*2))
            if vitesse == 2:
                print("===="*(l+1)*2+"...."*(10-(l+1)*2))
    score = setst(cc)
    print(cc+" :",score,": "+code)

On remarque qu’il est nécessaire d’avoir une liste pour modifier les éléments de la chaîne de caractères un par un à une position donnée.

Rien qu’avec ce script, on a pu augmenter considérablement le score des meilleurs Pokémons issus des attaques précédentes :

Avant :

u^KhxO_%#l » » »l » » »%%%Retour ligne automatique
Out[17] : 49.031613189324844

Après :

turboBoost(« u^KhxO_%#l »)Retour ligne automatique
25 %Retour ligne automatique
==========…………………………Retour ligne automatique
50 %Retour ligne automatique
====================………………..Retour ligne automatique
75 %Retour ligne automatique
==============================……….Retour ligne automatique
100 %Retour ligne automatique
========================================

u^KhxO_%#l » » »^ » »1″ » » : 49.29025926955508 : u^KhxO_%#l » » »d » »3″ » »

Cette optimisation du membre de droite nous permettait de faire la même chose pour le membre de gauche.

On a alors écrit une fonction utilisant notre fonction d’optimisation pour tester chaque caractères pour le membre de gauche en optimisant le score à chaque fois pour trouver le code parfait.

def chasseAuxPokemons(vitesse=1):
    # La vitesse 1 m'a prise 9h mais a bien fonctionnée
   
    lcp = ["!","!","!","!","!","!","!","!","!","!"]
    for l in range(vitesse+3):  
        for i in range(10):
            # On initialise tout
            global cc
            cons(lcp)
            scores = [0]
           
            for k in range(len(carac)):
                # On cree la liste de Pokemons avec les caractères
                lcp[i] = carac[k]
                cons(lcp)
                # On applique le booster de performances dessus (rapide et sans les barres de %)
                turboBoost(cc,1,0)
                # On recense les scores
                score = setst(cc)
                scores.append(score)
            # On prend le gagnant, c'est notre nouveau Pokemon
            lcp[i] = carac[scores.index(max(scores))-1]

Grace à cette fonction, on a pu obtenir le TOP résultat, le fameux 49,31730 :

code_h#^g0KuOS » » » » » » » »7u
Score49.31730339247606

On a donc envoyé des scores légèrement en dessous pour pouvoir nous qualifier dans les premiers.

Attaque n°10 : Force brute oui mais …

Nous avions exclus quelques caractères de cette force brute, on a donc réussi uniquement à obtenir le premier TOP résultat qui était déjà pris, le fameux 49,31730 mais pas au delà. Quand les premiers 49.319 et 49.32 ont commencé à sortir, nous avons compris que nous avions trop traîné, et qu’en intégrant d’autres caractères de la table ASCII nous aurions pu finir premier. Nous pensions que 49,31730 était le résultat optimal, nous n’avons pas testé davantage alors qu’on avait à priori la bonne méthode.

Mais notre échec relatif nous à gonflé à bloc pour le défi historique, que nous avons fait en python cela va de soit et sur PC car la mémoire de la NumWorks à la date d’octobre 2019 … enfin vous voyez de quoi on veut parler, sinon il suffit de lire ceci : Script qui refuse de s’exécuter sur la Numworks N0100 pour comprendre de quoi il retourne.

Conclusions

Nombres de tirages réalisés au total : entre 20 000 000 et 30 000 000 maximum.Retour ligne automatique
3 scripts tournaient au maximum en même temps, sur deux ordinateurs distincts.

L’année prochaine, il faudra compter sur nous ! Et cette fois-ci on commencera le défi le jour J et pas en retard. Pavel va devoir … heu non rien du tout, Pavel est très au dessus du niveau moyen. 😉

Nous remercions les organisateurs des sites tiplanet et planetcasio pour ce bon moment, cette recherche était passionnante, nous a réveillé la nuit (histoire de vérifier que les scripts tournaient bien) et maintenant les listes en python n’ont plus de secret pour nous.

Sur un autre sujet, nous supplions l’équipe de NumWorks d’augmenter la mémoire allouée aux scripts python sur la N0100 et la N0110. Ne pas pouvoir écrire un script de plus de 4ko est une absurdité !

Projets

Un générateur aléatoire de calcul mental en python pour…

Si les exercices répétitifs d’entrainement étaient tombés en disgrâce dans les précédents programmes scolaires, les nouveaux programmes de mathématiques les réintroduit, tout du moins en ce qui concerne les rituels de calcul mental en classe de seconde.

L’acquisition de ces réflexes est favorisée par la mise en place d’activités rituelles, notamment de calcul (mental ou réfléchi, numérique ou littéral). Elle est menée conjointement avec la résolution de problèmes motivants et substantiels, afin de stabiliser connaissances, méthodes et stratégies.

Extrait du programme de mathématiques, classe de seconde, 2019

Le script que nous avons conçu permet de pratiquer du calcul mental numérique, directement sur sa calculatrice, sans que les élèves n’aient la possibilité de tricher sur leur voisin et tout en proposant une correction personnalisée à chaque élève !

Un précédent script réalisé en mode texte

Un précédent script avait été codé en mode console, et il gérait un menu, lui aussi codé avec des print() et des input().

Fonctionnel, il manquait toutefois d’ergonomie, et le décalage du texte en temps réel dans le console pouvait perturber l’apprentissage.

Réécriture pour profiter de la couche graphique

Avec la sortie de la version 13.2.0 d’Espilon, le logiciel qui anime la NumWorks permet de disposer d’un tas python (heap) de 31ko et de fonctions natives tel que keydown() qui permet de récupérer le code de la touche pressée.

Une conception graphique minimaliste et intuitive a donc été pensée et codée pour sublimer ce générateur aléatoire de calculs.

Un script compatible avec notre menu graphique

En parallèle, nous avons développé Un menu en python pour les jeux sur la numworks et ce script exploite les possibilités de ce menu graphique.

RéglageOptions
ModeClassique , Rapide
Opération(s)+ , – , x , / , + – , x / , + – x , + – x /
Difficultéfacile, modéré, difficile, expert
Répétition20, 42, 50, 100, 120

Classique vs Rapide

Le mode classique interrompt le script et le chronomètre pour afficher si il y a une erreur, et indiquer quelle était la bonne réponse.

Le mode rapide est un mode d’entrainement intensif sans perturbation, que vous fassiez juste ou faux les calculs s’enchaînent et vous ne pourrez pas analyser vos erreurs.

Dans tous les cas, une fois la série de calcul terminée, un écran de synthèse résume le travail réalisé.

Quelques portions de code commentées

Le code qui génère le menu est documenté dans l’article associé : Un menu en python pour les jeux sur la numworks

Pour pouvoir être lu par notre script, la difficulté doit être représentée par un nombre.
Ainsi, on crée un code qui récupère un nombre en fonction de l’index de la première lettre dans un tableau.

["Difficulté", "  modéré", "difficile", "expert", "facile"],
dif = ["f", "m", "d", "e"].index(dif[0])

Ce dif sera un indice qui sera utilisé pour interroger la table de difficulté :

da = [1, 9]
db = [10, 19]
dc = [1, 10]
dd = [dc, [2, 10]]
diff = {"+": [[da] * 2, [db, da], [db, da], [db] * 2],
        "-": [[da] * 2, [db, da], [[10, 20], [10, 20]], [db] * 2],
        "*": [[dc] * 2, [dc] * 2, [[2, 10], [11, 20]], [[1, 25], [1, 25]]],
        "/": [dd, dd, dd, [[1, 20], [2, 20]]]}
def draw_line(x, y, clr, *ts) :

kandinsky ne dispose pas d’une fonction permettant de tracer des lignes. Or elle dispose d’une fonction qui allume un pixel d’une certaine couleur. Voici donc notre fonction pour tracer une ligne.

def draw_line(x, y, clr, *ts):
    for t in ts:
        d = list(map(lambda n: n // abs(n) if n != 0 else 0, t[0]))
        for i in range(t[1]):
            set_pixel(x + i * d[0], y + i * d[1], clr)
        x += i * d[0]
        y += i * d[1]

Quelques explications :
La fonction prend un couple (x,y) de départ, un couleur et des trajectoires (ts)

Ces trajectoires sont de la forme ([dx,dy],l)

d = list(map(lambda n: n // abs(n) if n != 0 else 0, t[0]))

Cette ligne permet d’obtenir une liste contenant uniquement des -1, 0, 1.

Améliorations possibles

Un mode d’apprentissage automatique si on dispose d’une mémoire de stockage permanente utilisable par python.

Un mode examen (Nécessite de « crypter » qq portions du code) : Le professeur génère un code unique, l’élève saisit ce code et fait une série aléatoire mais paramétré par le professeur. Un bon élève doué en programmation pourra toutefois bypasser le code et avoir tout juste sans rien faire !

Télécharger cette application

En l’état actuel, vous ne pouvez pas tester ce script directement depuis le workshop, car l’équipe de développement de la NumWorks n’a pas encore mappé les touches du clavier de l’ordinateur sur leur simulateur en ligne.

Quelques touches seulement sont actives sur le workshop, les 4 flèches, la touche Entrée et les touches Retour Arrière, Majuscule.

Ceci vous permet donc uniquement de tester le menu de cette application mais pour tester le générateur de calcul, il faudra charger le script sur la calculatrice.

Calculez bien !

Vous pouvez réagir à cet article sur le topic tiplanet.org de cette news : 
Snake, calcul mental, et interface lancement jeux Python

Quelques captures d’écrans