π
<-
Chat plein-écran
[^]

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

Re: Concours de rentrée 2019 - défi de Python

Message non lude M4x1m3 » 09 Nov 2019, 18:26

Bon j'ai vu que plusieurs personnes avaient expliqué leur démarche pour le défis tracé, donc Je me suis dit que j'allais faire la même pour le défis python :p

En gros, ma recherche s'est faite en 4 parties :
  1. Réflexion
  2. Bruteforce (intelligent)
  3. Exploitation d'un ""bug""
  4. 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: Tout sélectionner
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 :D
Image
"Regression testing"? What's that? If it compiles, it is good, if it boots up it is perfect.
Avatar de l’utilisateur
M4x1m3Programmeur
Niveau 13: CU (Calculateur Universel)
Niveau 13: CU (Calculateur Universel)
Prochain niv.: 62.6%
 
Messages: 170
Images: 12
Inscription: 13 Oct 2019, 21:10
Localisation: Bas-Rhin (67)
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: M1 Informatique
Twitter/X: M4xi1m3
GitHub: M4xi1m3

Re: Concours de rentrée 2019 - défi de Python

Message non lude critor » 09 Nov 2019, 19:00

Super, merci à toi ! :)
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41465
Images: 14479
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2019 - défi de Python

Message non lude Pavel » 09 Nov 2019, 19:40

Merci pour l'explication de ta méthode @M4x1m3!

J'ai aussi récemment posté quelques détails de ma méthode sur le forum Casio Planet:
https://www.planet-casio.com/Fr/forums/ ... ast#170510

J'espère que c'est OK si je les reposte ici.

J'ai mis mon code Python dans un dépôt git. Ce code trouve le meilleur score en quelques minutes et converge la plupart du temps vers 49.32057 ou 49.32079. Dans la suite, je vais essayer d'expliquer le fonctionnement de ce code.

1. Quelques observations

Le calcul du score favorise les équipes de dix pokémons.

Les points d'attaque sont des nombres rationnels.

La somme de tous les points d'attaque est censée être normalisée à 1.

Il y a un problème d'arrondi qui probablement peut être exploité pour contourner la normalisation.

2. Optimisation du calcul du score

J'ai commencé par optimiser le calcul du score.

J'ai ajouté une liste "pokemons" qui est remplie une fois au début du programme, contrairement à la fonction "getattack()" qui calcule les compétences des pokémons à chaque appel de cette fonction. J'ai aussi ajouté une fonction "fast_score()" qui utilise cette liste.

Voici le code:
Code: Tout sélectionner
pokemons = []

for l in range(94):
  mseed(42)
  for k in range(l + 1):
    mrandom()
  pokemons.append(mrandint(1, mrandmax))

def fast_score(code):
  pkt = [0.0 for l in range(21)]
  for k in range(10):
    p = code[19 - k] / 93.0
    for l in range(21):
      if pokemons[code[k]] & (1 << l):
        pkt[l] += p
  size = 0
  for k in range(10):
    if code[19 - k] > 0:
      size += 1
  score = 0.0
  for k in pkt:
    if k:
      score += log(e + k * size)
  return score

3. Initialisation de l'équipe de pokémons

Au début du programme, mon équipe de pokémons est composée d'un seul pokémon Bulbizarre avec 93 points d'attaque:
Code: Tout sélectionner
code = [0 for k in range(20)]
code[19] = 93

4. Recherche de la meilleure équipe de pokémons

J'ai utilisé l'algorithme de recuit simulé.

Pour modifier l'état de mon équipe de pokémons à chaque iteration de l'algorithme, j'ai implémenté deux fonctions: "random_pokemon()" et "random_attack()".

La fonction "random_pokemon()" remplace aléatoirement l'un des pokémons par un autre qui n'est pas encore présent dans l'équipe.

La fonction "random_attack()" choisit au hasard deux pokémons de l'équipe et un delta, puis incrémente les points d'attaque de l'un de ces deux pokémons par le delta et diminue les points d'attaque de l'autre de ces deux pokémons du même delta. De cette manière, la somme des points d'attaque de tous les pokémons de l'équipe ne change pas et reste toujours à 93. Les nouveaux points d'attaque sont conservés s'ils donnent un score plus élevé. Cette opération est répétée plusieurs fois.

Voici le code de ces deux fonctions:
Code: Tout sélectionner
def random_pokemon(code):
  n = randint(0, 9)
  v = randint(0, 93)
  if not v in code[:10]:
    code[n] = v

Code: Tout sélectionner
def random_attack(code):
  score_max = fast_score(code)
  for k in range(300):
    while True:
      i = randint(10, 19)
      j = randint(10, 19)
      if i != j:
        break
    d = randint(-93, 93)
    vi = code[i] + d
    vj = code[j] - d
    if vi >= 0 and vi <= 93 and vj >= 0 and vj <= 93:
      code_next = code.copy()
      code_next[i] = vi
      code_next[j] = vj
      score_next = fast_score(code_next)
      if score_max < score_next:
        code[:] = code_next
        score_max = score_next

5. Recherche des meilleurs points d'attaque

Dans la meilleure équipe de pokémons trouvée par l'algorithme de recuit simulé, il y a dix pokémons mais il n'y a que deux pokémons qui ont plus d'un point d'attaque. Ces deux sont Abra et Tentacool.

Pour trouver les meilleurs points d'attaque pour Abra et Tentacool, je vérifie toutes les valeurs possibles et je garde celles qui apportent le meilleur score:
Code: Tout sélectionner
for i in range(ord('2'), 256):
  for j in range(ord('e'), 256):
    code = code_max.replace('2', chr(i)).replace('e', chr(j))
    score = setst(code)
    if score_max < score:
      score_max = score
      print('%.5f' % score, code, i, j)
Dernière édition par Pavel le 10 Nov 2019, 17:26, édité 4 fois.
Avatar de l’utilisateur
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Prochain niv.: 83.6%
 
Messages: 107
Inscription: 19 Sep 2018, 10:50
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Concours de rentrée 2019 - défi de Python

Message non lude Lephe » 09 Nov 2019, 21:13

Dans la meilleure équipe de pokémons trouvée par l'algorithme de recuit simulé, il y a dix pokémons mais il n'y a que deux pokémons qui ont plus d'un point d'attaque. Ces deux sont Abra et Tentacool.

Ce qui n'est pas surprenant puisque ce sont eux qui ont le plus d'attaques !

J'en profite pour partager une de mes astuces. Le score est une fonction croissante de l'ensemble d'attaques de chaque Pokémon, ie. si on rajoute des attaques à un Pokémon le score augmente toujours.

Or, 20 Pokémon sur les 93 ont un ensemble d'attaques inclus dans celui d'un autre. On peut donc les éliminer d'office et se ramener à 73 Pokémon, ce qui aide à accélérer les calculs. :)

J'espère que c'est OK si je les reposte ici.

Absolument aucun problème, bien au contraire :)
Avatar de l’utilisateur
LephePartenaire
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Prochain niv.: 67.7%
 
Messages: 386
Inscription: 15 Juin 2018, 19:53
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Concours de rentrée 2019 - défi de Python

Message non lude critor » 10 Nov 2019, 16:25

Coucou chers gagnants.

Pour ceux qui ne se sont pas encore manifestés là-dessus, ce serait donc sympa de nous fournir quelques lignes d'explication de votre méthode sur ce sujet. :)
Vous pouvez faire ça ici, sur Planète Casio, ou encore par courriel.

Idéalement d'ici le week-end prochain.

Merci à vous. :)
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41465
Images: 14479
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2019 - défi de Python

Message non lude Zocipal » 10 Nov 2019, 17:53

Bonjour,
Voici mes explications pour le concours Python. Je ne vais expliquer ici que ma dernière façon de faire (la meilleure), mais sachez que j'ai fait beaucoup de scripts plus simples avant m'ayant permis d'obtenir mon score. Celui-là permet juste de le faire plus vite.

L'idée est de bruteforce via le code et donc setst().
Voici le code en entier avec en commentaire les explications
Show/Hide spoilerAfficher/Masquer le spoiler
Code: Tout sélectionner
import os
import random
import string
import sys
import time

from tqdm import tqdm # Juste pour afficher une barre de chargement

from numworks import * # Fichier du concours converti avec Cython


def disablePrint(): # Juste pour pas que ça print plein de choses inutiles
    sys.stdout = open(os.devnull, 'w')


def enablePrint():
    sys.stdout = sys.__stdout__


def randomStringwithDigitsAndSymbols(stringLength=2): # pour générer la chaîne aléatoire
    password_characters = string.ascii_letters + string.digits + string.punctuation
    return ''.join(random.choice(password_characters) for i in range(stringLength))




disablePrint()
x = 4
code = randomStringwithDigitsAndSymbols(20) # génère le code en partant d'un fait au hasard.
ancien = setst(code)[0]
used = []
while True:
    disablePrint()
    for z in range(1,4): # ici de 1/1 lettre à 3/3 lettres
        enablePrint()
        print("[INFO] Change tester form from {} to {}".format(z-1, z))
        disablePrint()
        for i in tqdm(range(len(code) - z)): 
            for michel in range(int(94**(z*0.5))):
                random.seed = random.randint(1, 100) * michel - z ** i
                oldcode = code
                while True:
                    try:
                        code = list(code)
                        code[i:i + z] = randomStringwithDigitsAndSymbols(z)
                        code = ''.join(code)
                        assert code not in used
                    except AssertionError:
                        continue
                    else:
                        a, b = setst(code)
                        used.append(code)
                        break
                if a > ancien:
                    ancien = a
                    enablePrint()
                    print("A = ", a, "B =", code, "C =", pkl)
                    disablePrint()
                else:
                    code = oldcode

Pour ce qui est dans la boucle :
Le script va améliorer le code. Il va changer lettre par lettre le code et voir si le résultat est meilleur.
Puis 2 lettres par 2 lettres... 3 lettres par 3 lettres...
ex : code "banane" donne 5
ca va tester "canane" puis "danane" puis "bbnane" ... intelligement puis imaginont il a trouvé "donone"=6 il va faire "pznone" "dpzone" "dopzne" "donpze" donopz" ...
Juste en laissant tourner et avec un peu de chance on arrive à mon score facilement
On peut arriver au score maximal en changeant la longueur du code de base (le miens = 20 caractères, celui du meilleur 33 caractères je crois)

En 5 minutes on obtient un code supérieur à 49.09


Merci pour votre lecture !
Image
Avatar de l’utilisateur
ZocipalProgrammeur
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 60.7%
 
Messages: 113
Inscription: 12 Sep 2019, 20:15
Localisation: Hauts-de-France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: 1ère Maths Physique NSI

Re: Concours de rentrée 2019 - défi de Python

Message non lude cent20 » 10 Nov 2019, 19:04

Nous sommes en train de préparer notre compte rendu ... ça arrivera dans quelques jours.
Image
Enseignant de mathématiques et d'informatique. Spécialité NSI : Des projets, des tutos, mais aussi de l'art
Calculatrice NumWorks : Des applications et des jeux, scripts, 📙 Découvrir la NumWorks
Avatar de l’utilisateur
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 45.9%
 
Messages: 1009
Images: 64
Inscription: 17 Mai 2012, 09:49
Localisation: Avignon
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: nsi_xyz

Re: Concours de rentrée 2019 - défi de Python

Message non lude critor » 10 Nov 2019, 19:57

Pour les gagnants qui n'en avaient pas, les comptes premium ont été activés. :)
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41465
Images: 14479
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2019 - défi de Python

Message non lude cent20 » 10 Nov 2019, 23:57

critor a écrit:Coucou chers gagnants.
Pour ceux qui ne se sont pas encore manifestés là-dessus, ce serait donc sympa de nous fournir quelques lignes d'explication de votre méthode sur ce sujet. :)
Merci à vous. :)


Voila on l'a fini. Il est ici : concours de rentrée 2019 - Le défi python / Pokemon. Tu peux copier / coller si tu veux, reformuler si tu as le temps, faire un lien (ou pas) si le coeur t'en dit.
Image
Enseignant de mathématiques et d'informatique. Spécialité NSI : Des projets, des tutos, mais aussi de l'art
Calculatrice NumWorks : Des applications et des jeux, scripts, 📙 Découvrir la NumWorks
Avatar de l’utilisateur
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 45.9%
 
Messages: 1009
Images: 64
Inscription: 17 Mai 2012, 09:49
Localisation: Avignon
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: nsi_xyz

Re: Concours de rentrée 2019 - défi de Python

Message non lude NeOtuX » 11 Nov 2019, 20:41

Félicitations à tous les participants qui se sont intéressés au défi, ainsi qu'aux organisateurs !

Comme il est de coutume je fais un petit retour sur ma méthode. A l'instar de Pavel j'ai repris mon outil de l'an dernier : l'algorithme génétique.

Dans un premier temps il me fallait "modéliser" un individu (Ici il s'agit de la main complète de 10 Pokemon). En y réfléchissant, j'ai réalisé que le code de participation constituait déjà en lui même une modélisation de l'individu !

J'ai donc créé un générateur de main qui tirait aléatoirement 20 caractères et remodelé légèrement la fonction de calcul de score pour l'accélérer. Je n'avais besoin de rien de plus pour faire tourner l'algorithme génétique, qui a très rapidement permis d'atteindre le score maximum "honnête" (voir ci-dessous) de 49.3173.

Sauf que mon générateur de main avait un petit défaut : il incluait un caractère en trop (celui après le tilde dans la table ASCII), normalement hors borne. Dans la pratique cela permettait de gratter quelques digits dans la normalisation des puissances !

Malheureusement le caractère en question n'est pas passé par mail lors de ma participation. D'ailleurs on voit dans le classement que j'en ai deux alors que c'est la même, à un problème de copier/coller près ! ;) J'ai pu rectifier le soucis quelques jours plus tard en comprenant le problème.

Par manque de temps, je n'ai pas effectué la dernière étape pourtant facile du bruteforce sur les caractères spéciaux, sachant que les caractères liés aux Pokemon devaient déjà être les bons. J'ai vu que ça n'avait pas échappé à certains qui ont su apporter cette petite finition qui a fait la différence : bravo !

Merci à ceux qui détaillent leur méthode, on constate qu'on a tous des façons de faire différentes, c'est chouette !
Avatar de l’utilisateur
NeOtuXMembre UPECS
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 56.3%
 
Messages: 192
Inscription: 18 Mai 2012, 08:58
Genre: Homme
Calculatrice(s):
MyCalcs profile

PrécédenteSuivante

Retourner vers News Divers

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 49 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
1171 utilisateurs:
>1154 invités
>11 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)