En gros, ma recherche s'est faite en 4 parties :
- Réflexion
- Bruteforce (intelligent)
- Exploitation d'un ""bug""
- Bruteforce (intelligent) x2
1 - Réflexion :
J'ai commencé par essayer de comprendre le script, renommer quelques variables. Je suis arrivé à ça. On se rend vite compte que le script utilise un générateur de nombres pseudo-aléatoires (surement pour pouvoir valider les résultats de façon consistante et pour éviter de stocker toutes les infos), notamment avec la fonction mseed et mrandom. Je me suis en-suite lancé dans l'exploration du code, notamment de la fonction getattack. On remarque que celle-ci défini le seed du générateur pseudo-aléatoire, et que celui-ci n'est utilisé que dans cette fonction. J'ai donc utilisé l'interpréteur python pour extraire la valeur de l'attaque de tous les pokémons, qui est ici, sous forme de tableur. À partir de là, mon cerveau commence à considérer les pokémons comme des chiffres. Bizarrement, Abra est OP. À partir de ça, et d'un peu de réflexion annexe (notamment sur la fonction qui calcule le score), j'ai pu avoir le premier score que j'ai rendu, qui était de 49.31488 (OKu0^gxh#_o"6""""""").
2 - Bruteforce intelligent :
Après avoir compris le script, j'ai commencé à bruteforce. La première étape était de comprendre comment fonctionne la fonction setst. Celle-ci prends les caractères du milieu vers l'extérieur, les caractères à gauche sont les pokémons et ceux à droite sont la priorité de chaque. J'ai donc compilé le code du défis comme module C avec Cython, par souci d'optimisation et pour gagner du temps. J'ai ensuite fait un petit script de bruteforce qui utilise de l'aléatoire et un peu de théorie de l'évolution (à chaque itération, on effectue une modification aléatoire sur final_string. Si le score de newstring est supérieur à l'ancien, on recommence, mais avec la nouvelle chaine) :
- Code: Select all
from random import randint;
import original; # original.py est le fichier contenant le code du défis.
import importlib;
import sys, os;
def blockPrint():
sys.stdout = open(os.devnull, 'w');
def enablePrint():
sys.stdout = sys.__stdout__;
final_string = '""""""""""""""""""""';
old_score = 0;
while True:
num_chars = randint(1, 5);
newstring = list(final_string);
for i in range(num_chars):
pos = randint(0, 19);
char = chr(randint(32, 127));
newstring[pos] = char;
newstring = "".join(newstring);
if (len(newstring) != 20):
continue;
blockPrint();
importlib.reload(original);
newscore = original.setst(newstring);
enablePrint();
if (newscore > old_score):
old_score = newscore;
final_string = newstring;
print(final_string, newscore);
Deuxième soumission, cette fois 49.31596 (0^geuOK#h_e3"""""""" ). Puis, après quelques jours de recherches, à aller nulle-part, pensant que je ne pourrais plus monter... la révélation arriva.
3 - Exploitation d'un ""bug"" :
Je ne sais pas si on peut qualifier ceci de bug, je ne l'appellerais pas un bug moi-même, plutôt une manière non conventionnelle de faire les choses... Je croyais, à la base, devoir me restreindre à la table ASCII. J'ai donc tenter d'entrer le caractère spécial "DEL" (\x1f). Et, à ma grande surprise, ça a marché. J'ai donc continué, toujours plus haut, à faire des choses bizarres, en sortant de la table ASCII. Ma 3e participation est arrivée, 49.31975298152274 (OKSgu_#0h^"A""\x9f""""" ).
4 - Bruteforce (intelligent) x2
Je croyais avoir tapé le max avec le 49.31975, mais voiyant le score de pavel (un beau 49.32), je me suis motivé à continuer. Je suis donc reparti sur un bruteforce, avec le même script qu'avant, sauf que je l'ai modifier pour échapper les caractères hors-ASCII et pour utiliser les caractères entre 32 et 1023. Et là, après 20 minutes de bruteforce et 2-3 ajustements, je suis arrivé à mon 49.32078546995182 (0hKS#O^_gu""\260"""""D" ). J'avais égalé le premier, j'étais heureux, après tant de taf.
Ce que j'ai pensé du défis :
Franchement, c'était cool. Il était pas trop dur, mais pas trop simple, et pouvait être, à mon avis, largement compris par un élève de seconde. La quantité de réflexion et de travail nécessaire à l'obtention de la première place me semble assez importante pour éviter de trop nombreuses égalités (je ne suis pas sur, mais je pense que 49.32 est un maximum qui ne peut être dépassé). Vivement l'année prochaine
J'ai pu rectifier le soucis quelques jours plus tard en comprenant le problème.
