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

→ **MyCalcs** profile · by **Zocipal** » 11 Nov 2019, 21:27

Je n'ai pas trop compris

Tu peux donner ton code ?
Merci,

→ **MyCalcs** profile · by **NeOtuX** » 11 Nov 2019, 21:54

Qu'est-ce que tu n'as pas compris exactement ?

Le code pour générer une population d'individus (i.e. un certain nombre de decks chacun composé de 10 Pokemons) c'est du style :

Pop = [''.join(chr(rd.randint(0, 94)+33) for i in range(NB_POKEMONS)) for j in range(NB_DECKS)]

Le code pour calculer le score des individus de cette population c'est celui du concours (Version Python Numworks) à quelques optimisations.

L'algorithme génétique qui utilise ces deux premiers éléments et qui permet de mixer les gènes des individus pour ne garder/croiser que les meilleurs c'est exactement celui décrit sur la page Wikipédia (Voir le schéma récapitulatif) : https://fr.wikipedia.org/wiki/Algorithm ... C3%A9tique.

Je n'ai pas les moyens dans l'immédiat de te fournir mon code complet mais les implémentations de cet algorithme en Python sont légions sur le net ! D'ailleurs l'an passé nous étions plusieurs à avoir choisi cette voie et à avoir partagé nos sources ici.

Si tu as une question plus précise n'hésite pas !

→ **MyCalcs** profile · by **NeOtuX** » 12 Nov 2019, 11:43

Salut Zocipal, j'ai pris quelques minutes sur le forum de Planète Casio pour donner plus de détails, que voici plus bas. Si tu as des questions n'hésite pas !

Le principe de l'algorithme génétique est beaucoup plus simple que ce qu'on pense. Il ressemble à ce que tout un chacun sait de la théorie de l'évolution : les meilleurs individus d'une population survivent et se reproduisent pour créer de nouveaux individus. Les individus les plus mauvais se reproduisent moins et leurs gènes ne sont pas perpétuées d'une génération sur l'autre. A terme les individus les plus adaptés subsistent.

Pour faire tourner cet algorithme il faut définir ce qu'est un individu et expliciter ce que veut dire un "bon" individu par opposition à un "mauvais" individu.

Dans le cadre de cette épreuve, il est clair qu'un individu est une main complète. L'avantage est que le nombre maximum de cartes dans la main est connu : 10. On sait qu'une carte associe à un numéro de Pokemon une puissance. Par conséquent un individu est modélisable par 10 couples [Numéro de Pokemon, Puissance]. Dans la pratique, il était plus simple de considérer le code de participation en tant que modélisation, puisque 20 caractères suffisent à définir intégralement les 10 cartes d'une main.

Pour ce qui est de discerner les bons individus des moins bons, et bien le concours fournissait une fonction qui permettait en donnant un code de participation d'obtenir directement le score associé.

L'algorithme réalise donc les étapes suivantes :

0) Générer au hasard une population d'individus. Dans notre cas cela revient à créer un certain nombre de chaînes de 20 caractères.

1) Calculer le score de chaque individu de la population et les trier du meilleur au moins bon.

2) Faire un tirage au hasard de deux individus que l'on appelle "parents", proportionnellement à leur score (Tirage par roue de la fortune). C'est à dire que plus le score d'un individu est élevé, plus il a de chance d'être choisi comme parent. Cette étape s’appelle la sélection.

3) Échanger des gènes entre deux parents pour créer un ou deux enfants. On parle d'enjambement. Concrètement ici une gêne d'un individu est un couple [Numéro de Pokemon, Puissance]. Dans le cas de la modélisation choisie, une gène est donc constituée de deux caractères de la chaîne. Un enfant c'est donc également une chaine de 20 caractères, dont la plupart sont recopiés d'un premier parent et quelques-uns sont recopiés d'un second.

4) Muter les enfants. Pour ajouter un peu d'entropie et éviter que l'algorithme ne tourne trop sur lui même (Peut-on parler de consanguinité ?), on change aléatoirement mais pas systématiquement une gène d'un enfant.

5) Générer une nouvelle population à partir de tous les nouveaux enfants en gardant quelques-uns des parents. On peut dire qu'il s'agit d'une nouvelle génération. Puis recommencer à l'étape 1).

Quelques remarques :

- Le procédé est stochastique c'est à dire qu'il repose en grande partie sur des tirages aléatoires. Il est donc possible que seuls des optimums locaux soient trouvés et que l'optimum global ne le soit jamais ! Il est donc nécessaire d'ajouter en étape 5) un contrôle de la population capable de "resetter" une partie de la population si l'on sent que ça stagne.

- Le paramétrage est primordial. Notamment le choix de la taille de la population, le nombre de gènes croisées entre les parents pour créer un enfant, le pourcentage de chance de muter les enfants etc.

- L'algorithme est implémentable sur la quasi totalité des calculatrices du concours. Pas forcément besoin du Python d'ailleurs, il faut des tableaux et/ou des chaînes de caractère. Avec plus ou moins de vitesse d'exécution cependant. Sur mon PC perso (Intel Xeon E5-2687W v4, 12 coeurs à 3,5Ghz) le score de 49.3173 est atteint dans la minute.

- J'aurais aimé cette année faire du recuit simulé comme Pavel mais je n'ai pas eu l'occasion de m'y mettre.

→ **MyCalcs** profile · by **Zocipal** » 12 Nov 2019, 12:53

Merci pour ton explication ! Si jamais à un moment tu as moyen de publier ton code ce serait top car ça m'a l'air fort intéressant !
Qu'est-ce que du recuit simulé ?

→ **MyCalcs** profile · by **Pavel** » 12 Nov 2019, 13:29

Zocipal wrote:Qu'est-ce que du recuit simulé ?

Lors du concours de l'année dernière, je cherchais un aperçu des différentes méthodes d'optimisation et j'ai trouvé ce livre. Il contient une brève description de l'algorithme génétique, du recuit simulé et de nombreuses autres méthodes.

→ **MyCalcs** profile · by **Amiga68000** » 14 Nov 2019, 14:08

Bonjour,

Bravo pour vos algo de code génétique, c'est vraiment très intéressant, va falloir que je creuse cette technique
Bravo et merci pour le concours j'ai appris beaucoup.
A la fois sur python, les algos (que je tenterais de creuser à tête reposée)

Voici ma méthode, un peu plus classique ou du moins à l'ancienne.
J'ai essayé plein de trucs, dans différentes voies
J'ai essayé de vous les synthétiser par étapes

1ere étape - Brute force
J'ai commencé par du bruteforce en tirant aléatoirement des lots de 10 individus et des priorités aléatoires
Score= 46 pas plus !

2eme étape - Jauger les pokemon
Un peu moins bourrin, j'ai jaugé chaque pokemon un à un
Ça m'a permis de les classer

3eme étape - Comprendre l'algo
Comprendre le code et l'algo, j'en ai fait un excel :
https://drive.google.com/file/d/0B57RCsRGB1yrZWN2akxUUHM4Vkx2WEVaUS1sV045d0h4S24w/view?usp=drivesdk
Dans la colonne [Y], vous rentrez votre priorité d'attaque en face du pokemon choisi
en cellule [Y2] vous récupérez le score
/!\ le score est l'ancien évaluation.

Pour l'excel, il a fallu que je cartographgie mes pokemon :

Code: Select all: def cartographie(): priorite=9 global pkcarto pkcarto=[] lgn=["ID","Points","nb de X","valeurs"] #pkcarto.append(lgn) for i in range(1,95): pk(i,priorite) # pkcarto.append(pkt) t="" for j in range(len(pkt)): t+=str(int(pkt[j])) if j!=len(pkt)-1: t+="," print("signature.append(["+str(t)+"]) #"+str(i)) pk(i,0) return

C'est là que j'ai compris que :
- la somme des priorités devait < 187
- l'enregistrement d'une priorité devait se faire de la plus petite valeur vers la plus grande sinon par enchantement des individus disparaissaient de votre lot de pokemon.

4eme étape - classer les pokemon, méthode 2
j'ai vu que 2 pokemon 63 et 72 sortaient du lot.
J'ai alors fait 100.000 tirages de 10 pokemeon avec les 63 et 72 avec priorité 1
A chaque fois je relevais les score pour l'ajouter à la moyenne de chaque pokemon contenu dans le tirage
But : les classer

5eme étape - varier les priorités
En prenant les pokemon avec les meilleurs résultats, j'ai fait varier toutes les priorités. Je suis arrivé à un très bon résultat (3eme je crois), malheureusement la combinaison était déjà prise, il a fallu que je réduise mes priorités pour arriver sur une combinaison et un score vierge
C'est là où j'ai eu mon classement

6eme étape - combinaisons
En prenant les meilleurs pokemons de l'étape 4, (30 environ, je me souviens plus du chiffre exact), j'ai fait toutes les combinaisons possibles par récursivité
Ça n'a pas amélioré mon score

Autre chose, je ne me suis pas penché sur la cas de la correction de score routine setst pour mieux comprendre les différences de score

Voilà mes étapes à peu près dans l'ordre, j'ai fait plein de petites routines pour celà
Voici mon code global, n'hésitez pas à me faire vos remarque, je suis pas un pro de la prog.

Bonne lecture

Arnaud

Code: Select all: #cas import time signature=[] signature.append([1,1,1,1,0,0,0,1,1,1,0,1,0,1,0,1,1,0,1,0,0]) #1 signature.append([1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,0,0,1,0,0,0]) #2 signature.append([0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1]) #3 signature.append([1,1,0,1,0,1,1,0,1,1,0,1,1,0,0,0,0,0,0,1,0]) #4 signature.append([0,1,0,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,1]) #5 signature.append([1,0,0,0,1,1,1,0,1,1,1,1,0,1,1,0,1,0,0,1,0]) #6 signature.append([0,0,0,1,0,0,1,1,1,1,0,0,0,1,0,1,1,1,0,0,1]) #7 signature.append([0,1,0,1,1,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,0]) #8 signature.append([0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,0,1,0]) #9 signature.append([1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1]) #10 signature.append([1,1,1,0,0,0,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0]) #11 signature.append([0,1,0,1,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,0]) #12 signature.append([0,1,1,0,1,0,0,0,1,1,0,0,1,0,0,0,0,0,1,1,1]) #13 signature.append([1,0,0,0,0,1,1,0,1,0,1,0,0,1,1,1,0,0,0,1,0]) #14 signature.append([1,0,1,1,1,1,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0]) #15 signature.append([1,1,0,0,0,1,1,1,1,0,1,1,1,0,1,0,1,0,0,1,1]) #16 signature.append([1,1,0,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,0,0,0]) #17 signature.append([1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,1,1,1,1]) #18 signature.append([0,1,0,1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1]) #19 signature.append([1,1,1,0,0,0,1,1,1,1,0,0,1,0,0,1,1,1,1,0,0]) #20 signature.append([0,1,1,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,1,0,1]) #21 signature.append([0,1,0,1,1,1,1,0,1,1,0,0,0,1,0,1,0,1,1,0,1]) #22 signature.append([0,1,0,1,1,1,1,1,0,1,1,1,0,0,1,1,0,1,1,0,0]) #23 signature.append([1,1,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,1,1,1,1]) #24 signature.append([1,0,0,1,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,0]) #25 signature.append([1,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,1,1,0,0]) #26 signature.append([0,0,0,1,1,1,0,0,1,0,1,0,0,1,1,1,1,1,1,0,1]) #27 signature.append([0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,1,1,0,0,1,0]) #28 signature.append([0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,1,0,0,1,1]) #29 signature.append([1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0]) #30 signature.append([1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,1,1,0,0,1]) #31 signature.append([0,0,1,1,1,0,1,1,1,0,0,0,0,0,0,1,0,1,0,0,1]) #32 signature.append([1,1,1,1,1,0,1,0,0,1,0,0,1,0,1,0,1,1,0,1,0]) #33 signature.append([0,1,0,0,1,1,0,0,0,0,1,1,1,0,0,0,1,0,1,1,0]) #34 signature.append([1,1,1,0,1,1,0,1,0,1,0,0,1,0,1,0,0,1,1,0,1]) #35 signature.append([0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1]) #36 signature.append([1,0,0,0,0,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,1]) #37 signature.append([1,1,1,0,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,0,1]) #38 signature.append([0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,1,1,1,1,0]) #39 signature.append([1,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1,0,0,1,0,1]) #40 signature.append([0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,1,0,0,0,0,1]) #41 signature.append([1,0,0,1,0,1,1,0,0,1,1,0,1,1,0,1,1,0,1,0,0]) #42 signature.append([1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,0,1,0,1,0]) #43 signature.append([0,1,1,1,1,1,1,1,0,0,0,1,1,0,1,0,0,0,0,0,1]) #44 signature.append([0,1,1,1,0,1,1,1,1,0,0,0,0,1,1,0,0,1,0,0,0]) #45 signature.append([0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,1,0,1,0]) #46 signature.append([0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,0]) #47 signature.append([0,0,0,0,0,1,1,0,0,1,0,1,1,1,0,1,0,1,1,0,1]) #48 signature.append([1,0,1,0,0,0,1,1,0,0,0,0,1,0,1,1,1,0,1,0,0]) #49 signature.append([1,1,0,1,1,1,1,0,1,0,0,1,0,0,0,0,1,0,1,1,0]) #50 signature.append([1,1,1,1,1,1,0,0,1,0,1,0,1,1,0,0,1,0,0,1,0]) #51 signature.append([1,0,0,0,1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0,0]) #52 signature.append([1,1,0,1,1,1,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0]) #53 signature.append([0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0]) #54 signature.append([0,1,0,1,1,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0]) #55 signature.append([1,0,1,1,0,1,0,1,1,1,1,0,1,1,1,0,0,0,1,0,0]) #56 signature.append([1,0,1,1,0,1,0,1,1,0,0,1,1,0,1,1,0,0,1,1,0]) #57 signature.append([1,1,0,1,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,0,0]) #58 signature.append([0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,1]) #59 signature.append([1,0,0,1,0,0,0,0,1,1,1,1,1,1,0,0,0,1,0,1,0]) #60 signature.append([0,1,0,1,1,1,0,0,1,0,0,1,0,1,0,1,0,0,0,0,1]) #61 signature.append([1,1,1,0,0,1,0,1,1,0,0,1,0,1,1,1,1,0,1,0,1]) #62 signature.append([0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1]) #63 signature.append([0,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1]) #64 signature.append([0,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,0,1,1,1,1]) #65 signature.append([0,1,1,0,1,0,0,1,1,0,0,1,1,1,1,1,0,1,0,1,0]) #66 signature.append([1,1,0,0,0,1,1,1,0,0,0,0,1,1,0,1,1,1,1,0,0]) #67 signature.append([1,1,1,1,0,0,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0]) #68 signature.append([0,1,1,0,1,1,1,0,1,1,0,1,1,0,0,1,1,0,0,1,1]) #69 signature.append([0,1,0,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0,1,1,0]) #70 signature.append([1,1,0,0,0,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,0]) #71 signature.append([1,0,0,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1]) #72 signature.append([1,0,0,1,0,0,1,1,0,0,1,1,1,1,0,1,0,1,1,1,0]) #73 signature.append([1,0,0,0,1,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,0]) #74 signature.append([1,1,1,1,0,1,1,0,0,1,0,1,1,0,1,0,0,0,1,1,1]) #75 signature.append([1,0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,0,1,0,1]) #76 signature.append([1,1,0,0,1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0]) #77 signature.append([1,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,1,0,0]) #78 signature.append([1,1,0,0,1,1,1,1,0,0,0,0,0,1,0,1,0,1,1,1,1]) #79 signature.append([0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1]) #80 signature.append([0,1,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,1,1,0,1]) #81 signature.append([0,1,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,1,1,0]) #82 signature.append([0,1,1,1,0,1,0,0,1,0,1,1,1,1,0,1,0,1,0,0,0]) #83 signature.append([1,1,1,0,1,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1]) #84 signature.append([1,0,0,1,1,1,1,1,1,1,1,0,0,1,1,1,0,0,1,1,0]) #85 signature.append([0,0,0,1,1,1,0,1,1,1,1,0,0,1,1,0,1,0,0,0,1]) #86 signature.append([1,1,1,0,0,0,0,1,1,0,1,1,1,0,0,1,0,0,0,0,1]) #87 signature.append([1,1,1,0,1,0,0,0,1,1,1,0,0,1,1,1,1,0,1,0,1]) #88 signature.append([0,1,0,1,0,1,0,0,1,1,1,0,1,0,1,1,0,1,1,0,1]) #89 signature.append([1,0,0,0,0,0,1,1,1,0,0,1,1,0,1,1,1,1,1,0,0]) #90 signature.append([0,1,0,1,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0]) #91 signature.append([0,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,0,1,1,1,0]) #92 signature.append([1,0,0,1,0,1,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1]) #93 signature.append([0,0,0,1,1,0,1,0,1,0,1,1,1,0,0,1,1,1,0,0,1]) #94 """ Tente d'être le meilleur le meilleur de tous les dresseurs en relevant notre défi. Ton but est simple, tu dois te constituer la main Pokémon la plus puissante possible sachant que bien évidemment les Pokémons ont des compétences différentes, et ce sous les seules règles suivantes : seuls les Pokémon n°1 à 94 sont autorisés ta main ne peut contenir qu'un maximum de 10 Pokémons tous les Pokémons dans ta main doivent être différents 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) Cas particuliers; si le Pokémon est déjà dans ta main sa priorité d'attaque sera mise à jour; et p=0 retire le Pokémon de ta main. """ from math import * def mmod(a,b): #modulo a b return a%b #0 Nspire MicroPython #1 NumWorks Python #2 G90/35+E2 Python #3 G75/85/95 CasioPython #4 83PCE Python/PyAdapt #5 HP Prime CAS #6 G90/35+E2 KhiCAS def getplatform(): k=-1 try: if chr(256)==chr(0): k=[6,5][("HP" in version())>0] except: pass if k>=0: return k try: import sys try: if sys.platform=="nspire": k=0 elif sys.platform.startswith("TI-Python"): k=4 except: k=3 except: try: import kandinsky k=1 except: k=2 return k def getlinechars(o=False): # c,k=2**31-1,getplatform() c=2**31-1 k=getplatform() #=-1 sur PC if k>=0: c=[53,o and 99 or 29,o and 509 or 21,31,32,c,c][k] return c lnm=["Bulbizarre","Herbizarre","Florizarre","Salameche","Reptincel","Dracaufeu","Carapuce","Carabaffe","Tortank","Chenipan","Chrysacier","Papilusion","Aspicot","Coconfort","Dardargnan","Roucool","Roucoups","Roucarnage","Rattata","Rattatac","Piafabec"] lnm.extend(["Rapasdepic","Abo","Arbok","Pikachu","Raichu","Sabelette","Sablaireau","Nidoran F","Nidorina","Nidoqueen","Nidoran M","Nidorino","Nidoking","Melofee","Melodelfe","Goupix","Feunard","Rondoudou","Grodoudou","Nosferapti","Nosferalto"]) lnm.extend(["Mystherbe","Ortide","Rafflesia","Paras","Parasect","Mimitoss","Aeromite","Taupiqueur","Triopikeur","Miaouss","Persian","Psykokwak","Akwakwak","Ferosinge","Colossinge","Caninos","Arcanin","Ptitard","Tetarte","Tartard","Abra","Kadabra"]) lnm.extend(["Alakazam","Machoc","Machopeur","Mackogneur","Chetiflor","Boustiflor","Empiflor","Tentacool","Tentacruel","Racaillou","Gravalanch","Grolem","Ponyta","Galopa","Ramoloss","Flagadoss","Magneti","Magneton","Canarticho","Doduo","Dodrio","Otaria"]) lnm.extend(["Lamantine","Tadmorv","Grotadmorv","Kokiyas","Crustabri","Fantominus","Spectrum","Ectoplasma"]) #na,pkl=21,[] na=21 pkl=[] #mrandmax,mrand,mfmax,nn,mp=2**31-1,0,93,getlinechars(True)-na,na//2 mrandmax=2**31-1 mrand=0 mfmax=93 nn=getlinechars(True)-na mp=na//2 #quotien de la division entière, 21//2 = 10 def mround(f): #renvoie l'entier le plus proche # 0.5 --> 1 # 0.4 --> 0 #-0.4 --> 0 #-1.4 --> -1 #-1.5 --> -2 #-1.6 --> -2 d=mmod(abs(f),1) #resultat = 0.xxxxx return (mfloor(abs(f))+(d>=.5))*(1-2*(f<0)) def mfloor(f): #Arrondi -mfloor(-5.2)=-5 return round(f)-(round(f)>f) def mceil(f): #arrondi SUP return round(f)+(round(f)<f) def mseed(s): global mrand mrand=mmod(s,mrandmax) def mrandom(): mseed(mrand*16807) return float(mrand/mrandmax) def muniform(mini,maxi): return mrandom()*(maxi-mini)+mini def mrandint(mini,maxi): return mround(muniform(mceil(mini),mfloor(maxi))) def mf2f(n): return float(n/mfmax) #mfmax=93 def mbit(a,b): return mmod((a//(2**b)),2) def getattack(p,pts): #p=numéro de l'individu #pts=l[2]/somme(l[2]) global pkt # mseed(42) #mrand=42 # print(str(pts)) # for k in range(p+1): # mrandom() #génère p+1 fois mrand # a,pka=mrandint(1,mrandmax),"" # a=mrandint(1,mrandmax) pka="" npka=0 # print("p="+str(p)) # print(signature[p]) for j in range(na): #na=21 # if mbit(a,j)!=0: if signature[p][j]==1: pka+="X" npka+=1 pkt[j]+=pts else: pka+=" -"[getplatform()>=5] # print("pka="+pka) return pka def i2c(k): return chr(k+33) def c2i(c): return ord(c)-33 def f2mf(f): return mround(float(f*mfmax)) #mfmax=93 def clean(): #recalcule tous les l[2] des individus global pkl #données des individus # t,s=0,0 s=0 t=0 for l in pkl: #t=somme(priorités) t+=l[1] #t=t+l[1] # print("t="+str(t)) for l in pkl: l[2]=f2mf(l[1]/(t or 1)) #t or 1 pour eviter la division par 0 # l[2]=mround(float(l[1]/(t or 1)*93)) #mround = entier le plus proche s+=l[2] #s=s+l[2] --> s= sommes des l[2] if(l[2]<=0): # print("-----") # print("t="+str(t)) # print("remove "+str(l)) pkl.remove(l) #on enlève l'individu return clean() #on reitère return s #on renvoie def pk_ORIGINE(n,p=1,d=2): global pkt, pkl n-=1 if n>=0 and n<len(lnm): new=True for k in range(len(pkl)): if pkl[k][0]==n: new,pkl[k][1]=False,max(p,0) if new and len(pkl)<mp: pkl.append([n,max(p,0),0]) ptt,pkt,t,st=clean(),[0 for k in range(na)],0,"" for l in pkl: s=getattack(l[0],l[2]/ptt) if d: sn=" "+lnm[l[0]] if len(sn)>nn: sn=sn[:nn] print(s+sn+" #"+str(l[0]+1)+" (f="+str(l[1])+")") st=i2c(l[0])+st+i2c(l[2]) for k in pkt: if(k): t+=log(e+k*len(pkl)) if(d): if(d>=2): print("Bon score ? Si oui envoie code suivant a info@tiplanet.org :") print(""+st) return float(t) def pk(n,p=1,d=2): global pkt,pkl global sign #on décrémente de 1, la liste commence à 0 n-=1 if n>=0 and n<len(lnm): #le n° correspond à un individu new=True for k in range(len(pkl)): if pkl[k][0]==n: #individu existant, on remplace sa priorité new=False pkl[k][1]=max(p,0) #nouvelle priorité if new and len(pkl)<mp: #nouvel individu et poignée de 10 non pleine pkl.append([n,max(p,0),0]) #ajout de l'individu #calcul des attaques # ptt,pkt,t,st=clean(),[0 for k in range(na)],0,"" ptt=clean() #recalcule les l[2] et renvoie la somme des l[2] pkt=[0 for k in range(na)] # [0 0 ... 0 0 0] t=0 st="" for l in pkl: s=getattack(l[0],l[2]/ptt) #maximiser l[2]/ppt if d: sn=" "+lnm[l[0]] if len(sn)>nn: sn=sn[:nn] st=i2c(l[0])+st+i2c(l[2]) for k in pkt: if(k): #k<>0 t+=log(e+k*len(pkl)) #LN log neperien # print(t,e,k,len(pkl)) # if(d): # print(""+st) sign=""+st return float(t) def setst(st): s,pkl[:],n=0,[],len(st)//2 for k in range(n): s=pk_ORIGINE(c2i(st[n-1-k])+1,c2i(st[n+k+len(st)%2]),k+1>=n) return s #print("pk(n,p) pour rajouter le Pokemon n a ta main avec p points d'attaque.") # print(s+sn+" #"+str(l[0]+1)+" (f="+str(l[1])+")") # # # # ICI CODE PERSO # # # import csv from random import randint """ if len(pkl)>9: numPkARetirer=pkl[randint(0,len(pkl)-1)]][0] pk(numPkARetirer,0) """ #ALGO de recherche def affListe(listepkl): for k in listepkl: print(lnm[k[0]]+" #"+str(k[0]+1)+" (f="+str(k[1])+")" ) def brutforce(): global pkl global pklMAX global scoreMax global score #construction d'une liste de 10 for i in range(20): numPk=randint(1,94) force=randint(1,10) score=pk(numPk,force) scoreMax=score print("===== Liste depart") pkl=[[25, 1, 0], [81,1, 0], [46,1, 0], [19, 1, 0], [49, 1, 0], [50, 1, 0], [66, 1, 0], [34, 1, 0], [71, 35, 0], [62, 143, 0]] pklMAX=list(pkl) affListe(pklMAX) #bouclage pour trouver meilleur score for i in range(20000): # print("\n************** Iterration="+str(i)) if i%1000==0:print(i) # n=len(pkl)-1 # print(n) # if n==9: n=7 #onnenleve pas 72 ni 63 numPkARetirer=pkl[randint(0,n)][0]+1 # print("----- supprimer "+str(numPkARetirer)) pk(numPkARetirer,0) # affListe(pkl) while len(pkl)<10: numPk=72 while numPk==72 or numPk==63: numPk=randint(1,94) # force=randint(1,10) force=1 # print("+++++ Ajouter "+str(numPk)) score=pk(numPk,force) # print("SCORE="+str(score)) # affListe(pkl) if score>scoreMax: scoreMax=score pklMAX=list(pkl) print("\nMAX --------------------------------") print("score ="+str(scoreMax)) affListe(pklMAX) else: pkl=list(pklMAX) return def ScanStatPKi(numPkFixe): global pkl #on fixe 72 et 63 #pour chaque PKi de 1 à 93 # on tire n combinaisons aléatoires, # on note le score pour le PKi #à la fin on classe les PKi selon leur score print(numPkFixe) score=0 scoreMax=0 ctr=0 #on remplace l'élément pkl[7][0]=numPkFixe-1 #teste si numPkFixe est dans la plage pkl de 0 à 6 for i in range(0,7): if pkl[i][0]+1==numPkFixe: boucler=True while boucler: n=randint(1,94) if n!=numPkFixe and n!=72 and n!=63: pkl[i][0]=n boucler=False boucle=2000 #bouclage pour trouver meilleur score for i in range(boucle): #if i%1000==0:print(i) n=6 #onnenleve pas 72 ni 63, ni numPkFixe del pkl[0] boucler=True while boucler: #len(pkl)<10: numPk=randint(1,94) boucler=False for k in pkl: if k[0]+1==numPk: #il y a déjà un num boucler=True #on a un numéro pkunit=[] pkunit.append(numPk-1) pkunit.append(1) pkunit.append(1) pkl.insert(6,pkunit) score=pk(pkl[0][0]+1,1) scoreMax+=score score=scoreMax/boucle data=[] data.append(numPkFixe) data.append(score) #Score return data def scanstat(): global pkl start_time=time.time() pkl=[[25,1,0],[81,1,0],[46,1,0],[19,1,0],[49,1,0],[50,1,0],[66,1,0],[34,1,0],[71,35,0],[62,143,0]] d=[] for i in range(1,95): #range(1,95) --> 1 à 94 if i!=72 and i!=63: d.append(ScanStatPKi(i)) print("Temps d execution : "+str( (time.time() - start_time))) sauve(d) return d #scanstat() def init(): pk(3) pk(43) pk(85) pk(75) pk(71) pk(62) pk(16) pk(6) pk(72,35) pk(63,143) return def scoreprio(pk1,pk2): #max 186 data=[] data.append(0) data.append(pk1) data.append(0) data.append(pk2) data.append(0) smax=0 for p1 in range(1,177): #K186-8-1 for p2 in range(1,178-p1): if p1<p2: pk(pk1,p1) s=pk(pk2,p2) else: pk(pk2,p2) s=pk(pk1,p1) if s>smax: smax=s data[0]=smax data[2]=p1 data[4]=p2 # pkl=[] pk(pk1,0) pk(pk2,0) return data def duelprio(): start_time=time.time() d=[] for i in range(1,94): for j in range(i,95): d.append(scoreprio(i,j)) print("pk "+str(i)+" vs pk "+str(j)) print("Temps d execution : "+str( (time.time() - start_time))) sauve(d) # Affichage du temps d execution return d def duel(numpk,r): #crée une ligne se scores du numpk vs chaque element dans r priorite=1 pkduel=[] pk(numpk,priorite) for i in r: if numpk!=i: pkduel.append(pk(i,priorite)) pk(i,0) else: pkduel.append(0) pk(numpk,0) return pkduel def matriceduel(): p=[] r=range(1,95) r=[16,23,62,69,71,75,88] r=range(1,4) r=range(1,95) for i in r: p.append(duel(i,r)) return p def cartographie(): priorite=9 global pkcarto pkcarto=[] lgn=["ID","Points","nb de X","valeurs"] #pkcarto.append(lgn) for i in range(1,95): pk(i,priorite) # pkcarto.append(pkt) t="" for j in range(len(pkt)): t+=str(int(pkt[j])) if j!=len(pkt)-1: t+="," print("signature.append(["+str(t)+"]) #"+str(i)) pk(i,0) return def sauve(p): #sauvegarde une matrice p en csv #with open("L:/_Datas/11 - Arnaud/Python - DEFI/table.csv", "w") as f_write: with open("d:/table.csv", "w") as f_write: writer = csv.writer(f_write,delimiter=";") writer.writerows(p) return def seek(id): smax=0 for i in range(1,130): s=pk(id,i) if s>smax: smax=s priorite=i score=pk(id,priorite) print("pk("+str(id)+","+str(priorite)+")=" +str(score) ) return score def valeur(priorite=1): #renoie une liste de chaque score ID seul l=[] for i in range(1,95): s=pk(i,priorite) l.append(s) pk(i,0) print(s) return def estdanspkl(ID): r=False for p in pkl: if p[0]+1==ID: r=True break return r def meilleurID(IDaexclure=0): #renvoie le meilleur ID priorite=1 IDmax=0 smax=0 if len(pkl)==10: IDmax=0 else: for ID in range(1,95): if ID!=IDaexclure: if not(estdanspkl(ID)): #l'ID n'est pas dans la liste pkl s=pk(ID,priorite) if s>smax: #score meilleur smax=s IDmax=ID pk(ID,0) return IDmax def creermeilleurID(): ID=meilleurID() if ID!=0: pk(ID) seekall() return def seekall(): for p in pkl: score=seek(p[0]+1) return score def scan(): #max 186 #186-8 = 178 smax=0 f63=94 f72=0 f03=0 pk(63,f63) for i in range(1,178-1): for j in range(1,178-i): # for k in range(1,178-i-j): pk(3,i) s=pk(72,j) st=setst(""+sign) if st>smax: smax=st # f63=i f72=i f03=j print("MAX setst="+str(smax)) print("S="+str(s)) # print("Signature="+sign+" "+str(st)) print(" P72="+str(i)+" P03="+str(j)) pk(63,f63) pk(72,f72) pk(3,f03) return def combi(level,levelmax,pkpossibles,smax=0,pkdeb=0): #on incrémente le niveau d'arbo l=level+1 # print("l="+str(l)) if l>levelmax: #on est arrivé en bas de l'arbo souhaitée #on peut faire les calculs s=seekall() print("s="+str(s)) if s>smax: smax=s print("smax=",str(smax)) else: # for i in pkpossibles: for ii in range(pkdeb,len(pkpossibles)): i=pkpossibles[ii] #☺ if not(estdanspkl(i)): #l'ID n'est pas déjà dans la liste # print("id="+str(i)) #on ajoute l'individu pk(i) #on descend en arbo smax=combi(l,levelmax,pkpossibles,smax,ii+1) pk(i,0) #on eneleve l'individu return smax def trouvecombi(): pkpossibles=[16,62,71,23,69,75,88] pkpossibles=[16,62,71,23,69] smax=combi(0,3,pkpossibles) return smax # # # RESULTATS # # def initamiga(): #amiga68000 #record à battre = 49,31730 #49.31975298152274 pk(3,1) pk(62,1) pk(71,1) pk(16,1) pk(43,1) pk(85,1) pk(47,1) pk(51,1) pk(72,32) pk(63,128) #la somme des priorités <=186 return """ transmis le 14/10/19 via amiga68000 XXXXX XXXXXXXXX X Florizarre XXX X XX X XXXX X X Tartard XX X XXXXX XXXX X Empiflor XX XXXX XXX X X XX Roucool XXXX XXX XXXXX X X Mystherbe X XXXXXXXX XXX XX Dodrio X XXX XXXXXX XXXX Parasect XXXXXX X X XX X X Triopikeur X XXXX X XXXXX XXX X Tentacool XXXX XXXXXXXXXX XXXX Abra Bon score ? Si oui envoie code suivant a info@tiplanet.org : _hSOuK0g^#""""""""3h 49.31975298152274 """ def initk(): #record à battre = 49,31730 #49.32078546995182 pk(3,1) pk(62,1) pk(71,1) pk(16,1) pk(43,1) pk(85,1) pk(47,1) pk(51,1) pk(72,35) pk(63,143) #la somme des priorités <=186 return """ XXXXX XXXXXXXXX X Florizarre XXX X XX X XXXX X X Tartard XX X XXXXX XXXX X Empiflor XX XXXX XXX X X XX Roucool XXXX XXX XXXXX X X Mystherbe X XXXXXXXX XXX XX Dodrio X XXX XXXXXX XXXX Parasect XXXXXX X X XX X X Triopikeur X XXXX X XXXXX XXX X Tentacool XXXX XXXXXXXXXX XXXX Abra Bon score ? Si oui envoie code suivant a info@tiplanet.org : _hSOuK0g^#""""""""3i 49.32078546995182 """ def init5(): #record à battre = 49,31730 #49.28269871690558 pk(16,1) pk(51,1) pk(58,1) pk(62,1) pk(71,1) pk(76,1) pk(5,1) pk(6,1) pk(72,35) pk(63,143) return def init4(): #record à battre = 49,31730 #49.138894711933105 pk(85,1) pk(89,1) pk(69,1) pk(73,1) pk(90,1) pk(86,1) pk(88,1) pk(87,1) pk(72,35) pk(63,143) return def init3(): #record à battre = 49,31730 # pk(63,64) pk(3,1) pk(72,16) pk(62,1) pk(71,1) pk(16,1) pk(43,1) #13 X pk(23,1) pk(16,1) pk(75,1) return def init21(): #record à battre = 49,31730 #49.274636982498805 pk(63,61) #56 pk(3,1) pk(72,16) pk(5,1) pk(43,1) pk(47,1) pk(85,1) #17.0724019377368 pk(16,1) # pk(62,1) # pk(71,1) pk(23,1) # pk(69,1) # pk(75,1) pk(88,1) # seek(63) # seek(72) return def init1(): #record à battre = 49,31730 #49.28984977976379 pk(63,61) #56 pk(3,1) pk(72,16) pk(5,1) pk(43,1) pk(47,1) pk(85,1) #17.0724019377368 # pk(16,1) # pk(62,1) pk(71,1) # pk(23,1) pk(69,1) pk(75,1) # pk(88,1) # seek(63) # seek(72) return def init2(): #record à battre = 49,31730 #49.31571202586076 pk(3,1) pk(5,1) pk(43,1) pk(47,1) pk(85,1) #17.0724019377368 pk(16,1) pk(62,1) pk(71,1) # pk(23,1) # pk(69,1) # pk(75,1) # pk(88,1) pk(72,35) pk(63,143) #56 return #algo() """ print("\nMAX --------------------------------") print(scoreMax) affListe(pklMAX) """ print("--------------------------------") print("pk(n,p) pour rajouter\nle Pokemon n a ta main\navec p points d'attaque.") #end

Si vous avez besoin de plus d'explication je suis dispo

→ **MyCalcs** profile · by **edgar13** » 14 Nov 2019, 14:29

Vous vous demandez comment j'ai fait 14eme? Tant mieux.
Tout d'abord j'ai commencé en classant les pokémons "a la main" puis ayant fait le classement je leur ai attribuer les meilleurs points d’attaque possibles toujours "a la main".
Ça m'a bien pris 4h.

Mais j'ai fait un premier score de 49 et quelques.
Pourquoi j'ai fait tout ça à la main? Parce que je ne savais pas trop comment faire un brute force approprié.
Mais finalement mon frère qui a un Asus 7 en a fait un mais il n'a pas pu tourner longtemps car il en avais besoin.

J'ai un peu amélioré son score en faisant quelques boucles python et j'ai obtenu 49,308.

Par contre je n'ai plus le code.

→ **MyCalcs** profile · by **Tituya** » 15 Nov 2019, 00:07

Bonjour bonjour, j'aurai aimé savoir quand est-ce que les résultats "officiels" seront affichés, je suis impatient de voir ce que les autres vont choisir comme lots !

Je sais que ça prend un temps monstre mais c'est pour savoir !

Je n'avais pas expliqué ma méthode sur ce forum, la voici :
Malgré ma place relativement petite dans ce concours (Tout de même 7ème, c'est honorable

), je vous partage ici mes différentes recherches dans ma quête de trouver le meilleur score possible !

L'aire de la recherche :
Avant de chercher l'automatisation, j'avais rempli à la main le score renvoyé par chaque pokémons, me permettant donc d'obtenir une base d'équipe assez complète. Malgré le fait que certains pokémons ne soit pas terribles en équipe, j'obtenais tout de même des résultats convaincants ! (Deuxième version du script). J'avais trouvé 49.936 points !

Puis je cherchais (comme beaucoup) à la main les points d'attaque qui renvoyaient le plus haut score ! J'ai très vite remarqué que seul 2 pokémons pouvaient faire varier drastiquement le score : Abra et Tentacool !

L'aire de l'automatisation :
J'avais déjà formé une équipe me donnant un paquet de points. J'ai donc eu l'idée de lancer un premier script pour chaque pokemon afin de tester si un pokémon renvoyait un score que je n'avais pas vu !
[small](PETIT POINT : J'ai malheureusement perdu la liste de mes pokémons à cause d'un problème de clef USB ayant été volée ou oubliée... (plus pratique sur clef quand tu bosses au lycée sur le concours pendant les cours d'SI :E)). Donc les scripts qui suivent ont été réécrits...

[/small]

Code: Select all: for a in range(94): pk(a,1) s=st print("score final =",setst(s)) if setst(s)>49.3: print(f" OK pour a = {a}, s={setst(s)} pour {st}") pk(a,0)

Puis je testais la priorité d'attaque de chacun de ces pokémons grâce à un script comme ça :

Code: Select all: for a in range(150): pk(62,a) s=st print("score final =",setst(s)) if setst(s)>49.3: print("OK !") print(a,setst(s),"pour",st) pk(62,0)

Grâce à ces petits scripts, j'ai tout de même réussi à trouver des scores comme 49.3158 points !

-Puis à partir d'un moment je me suis demandé comment le code était créé. J'ai vite remarqué que chaque pokémon correspondait à une valeur dans le code (genre par exemple le pokemon numéro 63 correspond à "_" et le pokemon 62 correspond à "^".)

Enfin brefs, les dix premiers caractères du code représentent les pokémons pris. Et cette valeur est facilement manipulable !

J'ai donc créé un script avec tous les caractères possibles (Je n'ai malheureusement pas pensé à la table ASCII). Au final, j'ai pris le problème à l'envers en fait.
J'y ai ajouté une vérification pour savoir si le score trouvé était déjà envoyé par un "concurrent". Et hop ! Plus qu'à laisser tourner !

Ce qui m'a permis de trouver sans effort (Juste beaucoup de temps) des combinaisons auxquelles je n'avais pas pensé ! Puis j'ai cherché automatiquement quel pokemon me donnait cette lettre dans le code !

J'ai pris le sujet à l'envers pour en tirer le plus possible avec ma petite échelle de lycéen lambda... J'ai surtout passé énormément de temps à chercher des choses en tous genres, essayer d'automatiser des bouts de code, je pense sincèrement que ce concours m'a pris plus d'une vingtaine d'heures !
Entre désillusions, avec des tentatives de bruteforce de plusieurs heures sans succès. Ou la joie de voir mon petit programme renvoyer soudainement un "OK pour cette valeur" !

Au final, ce concours m'a permis d'améliorer grandement ma maitrise en python ! Et étonnamment, réussir à obtenir une place sans comprendre une ligne du script fourni :E. Comme quoi, avec le temps et la persévérance on peut réussir même sans tout comprendre !

Bien joué à tous/toutes pour ce concours ! Et particulièrement à Cent20 qui m'a poussé sans le savoir à une compétition personnelle entre lui et moi

!

→ **MyCalcs** profile · by **cent20** » 15 Nov 2019, 21:12

Tituya wrote:J'ai pris le sujet à l'envers pour en tirer le plus possible avec ma petite échelle de lycéen lambda... J'ai surtout passé énormément de temps à chercher des choses en tous genres, essayer d'automatiser des bouts de code, je pense sincèrement que ce concours m'a pris plus d'une vingtaine d'heures !
Entre désillusions, avec des tentatives de bruteforce de plusieurs heures sans succès. Ou la joie de voir mon petit programme renvoyer soudainement un "OK pour cette valeur" !

Au final, ce concours m'a permis d'améliorer grandement ma maitrise en python ! Et étonnamment, réussir à obtenir une place sans comprendre une ligne du script fourni :E. Comme quoi, avec le temps et la persévérance on peut réussir même sans tout comprendre !

Bien joué à tous/toutes pour ce concours ! Et particulièrement à Cent20 qui m'a poussé sans le savoir à une compétition personnelle entre lui et moi !

Je confirme que ça m'a bien occupé aussi. Quand on a vu un squatteur s'intercaler entre Golden Man et mon score on a ragé ! On pensait que ce n'était pas possible. On a alors réussi à te dépasser et on pensait naïvement que c'était fini, que tu ne pouvais plus nous séparer mais non tu as trouvé un autre code intermédiaire ...

→ **MyCalcs** profile · by **Golden Man** » 16 Nov 2019, 09:49

Tout d'abord je voulais remercier les organisateurs pour ce concours génial et très instructif.

Ma méthode :

On a commencé avec cent20 par analyser le programme en le commentant blocs par blocs, voire lignes par lignes, afin d'avoir une vision d'ensemble plus nette.

A l'aide de la fonction setst(), j'ai pu analyser la lecture du code score (et donc sa construction) et j'ai effectué quelques tests pour voir si les couples (n,p) étaient lié et changeant leur position sur le code.

J'ai ensuite écrit un script pour tester les caractères optimaux sur le "membre de gauche" (les 10 derniers caractères du code) et j'ai pu augmenter considérablement des petits scores que j'avais.

Code :

Code: Select all: lc = [None,"!","!","!","!","!","!","!","!","!","!"] carac = '!"#$%&'+"'"+'()*+^;_,-./0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' def cons(liste): global cc cc = "" for j in range(len(liste)): cc = cc+liste[j] def turboBoost(pokemons,vitesse=1,style=1): lc[0]=pokemons for l in range(vitesse+3): for i in range(1,11): global cc cons(lc) scores = [0] for k in range(len(carac)): lc[i] = carac[k] cons(lc) score = setst(cc) scores.append(score) lc[i] = carac[scores.index(max(scores))-1] cons(lc) 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)

Une fois ce membre optimisé, j'ai fait pareil pour le membre de droite :

Code :

Code: Select all: def chasseAuxPokemons(vitesse=1): lcp = ["!","!","!","!","!","!","!","!","!","!"] for l in range(vitesse+3): for i in range(10): global cc cons(lcp) scores = [0] for k in range(len(carac)): lcp[i] = carac[k] cons(lcp) turboBoost(cc,1,0) score = setst(cc) scores.append(score) lcp[i] = carac[scores.index(max(scores))-1]

Après avoir tourné quelques heures la nuit, j'avais trouvé le 49.3173033 que je pensais être le maximum, puisque je n'avais pas de code au dessus en réponse.
J'ai alors envoyé un code qui me donnait un score juste en dessous de ceux qui étaient déjà donnés