π
<-
Chat plein-écran
[^]

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

Online

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

Unread postby 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: 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 :D
"Regression testing"? What's that? If it compiles, it is good, if it boots up it is perfect.
User avatar
M4x1m3Prog.
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Level up: 0.5%
 
Posts: 29
Joined: 13 Oct 2019, 21:10
Location: Bas-Rhin (67)
Gender: Male
Calculator(s):
Class: Terminale S

Online

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

Unread postby critor » 09 Nov 2019, 19:00

Super, merci à toi ! :)
Image
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 99.6%
 
Posts: 34027
Images: 8827
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

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

Unread postby 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: Select all
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: Select all
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: Select all
def random_pokemon(code):
  n = randint(0, 9)
  v = randint(0, 93)
  if not v in code[:10]:
    code[n] = v

Code: Select all
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: Select all
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)
Last edited by Pavel on 10 Nov 2019, 17:26, edited 4 times in total.
User avatar
PavelPremium
Niveau 0: MI (Membre Inactif)
Niveau 0: MI (Membre Inactif)
Level up: 50%
 
Posts: 32
Joined: 19 Sep 2018, 10:50
Gender: Male
Calculator(s):

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

Unread postby 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 :)
User avatar
LephePartner
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 30.3%
 
Posts: 248
Joined: 15 Jun 2018, 19:53
Gender: Male

Online

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

Unread postby 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
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 99.6%
 
Posts: 34027
Images: 8827
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

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

Unread postby 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
Code: Select all
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
User avatar
ZocipalPremium
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 32.8%
 
Posts: 79
Joined: 12 Sep 2019, 20:15
Location: Hauts-de-France
Gender: Male
Calculator(s):
Class: 1ère Maths Physique NSI

Online

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

Unread postby cent20 » 10 Nov 2019, 19:04

Nous sommes en train de préparer notre compte rendu ... ça arrivera dans quelques jours.
Bonjour Anonymous !

Intéressé par la spécialité NSI en 1ère
?
Visite donc
https://nsi.xyz !
User avatar
cent20Premium
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Level up: 0.8%
 
Posts: 142
Images: 9
Joined: 17 May 2012, 09:49
Location: Avignon
Gender: Male
Calculator(s):

Online

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

Unread postby critor » 10 Nov 2019, 19:57

Pour les gagnants qui n'en avaient pas, les comptes premium ont été activés. :)
Image
User avatar
critorAdmin.
Niveau 18: DC (Deus ex Calculatorum)
Niveau 18: DC (Deus ex Calculatorum)
Level up: 99.6%
 
Posts: 34027
Images: 8827
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
Class: Lycée
YouTube: critor3000
Twitter: critor2000
Facebook: critor.ti

Online

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

Unread postby cent20 » 10 Nov 2019, 23:57

critor wrote: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.
Bonjour Anonymous !

Intéressé par la spécialité NSI en 1ère
?
Visite donc
https://nsi.xyz !
User avatar
cent20Premium
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Level up: 0.8%
 
Posts: 142
Images: 9
Joined: 17 May 2012, 09:49
Location: Avignon
Gender: Male
Calculator(s):

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

Unread postby 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 !
User avatar
NeOtuXPremium
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Level up: 21.1%
 
Posts: 148
Joined: 18 May 2012, 08:58
Gender: Male
Calculator(s):

PreviousNext

Return to News Divers

Who is online

Users browsing this forum: No registered users and 2 guests

-
Search
-
Featured topics
Concours TI-Planet-Casio de rentrée 2019. 3 défis pour plus d'une 15aine de calculatrices graphiques et nombre de goodies sortant de l'ordinaire ! :D
Comparaisons des meilleurs prix pour acheter sa calculatrice !
12
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...

Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety 
-
Stats.
687 utilisateurs:
>659 invités
>22 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)