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 : 10ⁿ 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 . 10¹⁹ possibilités. Toute force brute est impossible.

Attaque n°2 : 10ⁿ 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.

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.

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 » » »%%%
Out[17] : 49.031613189324844

Après :

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

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 :

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.
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é !

Vincent ROBERT

Enseignant de mathématiques et de spécialité NSI, Lycée Louis Pasteur d’Avignon.
Aime compter jusqu’à 666 mais s’arrête souvent à 42.
Auteur du livre Découvrir la calculatrice NumWorks.

nsi.xyz