π
<-
Chat plein-écran
[^]

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

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

Unread postby Zocipal » 11 Nov 2019, 21:27

Je n'ai pas trop compris :-)
Tu peux donner ton code ?
Merci,
Image
User avatar
ZocipalPremium
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 36.7%
 
Posts: 89
Joined: 12 Sep 2019, 20:15
Location: Hauts-de-France
Gender: Male
Calculator(s):
Class: 1ère Maths Physique NSI

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

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

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

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

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

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

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

Unread postby 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.
User avatar
PavelPremium
Niveau 0: MI (Membre Inactif)
Niveau 0: MI (Membre Inactif)
Level up: 50%
 
Posts: 33
Joined: 19 Sep 2018, 10:50
Gender: Male
Calculator(s):

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

Unread postby 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
User avatar
Amiga68000Premium
Niveau 0: MI (Membre Inactif)
Niveau 0: MI (Membre Inactif)
Level up: 0%
 
Posts: 16
Joined: 12 Oct 2019, 22:17
Gender: Not specified
Calculator(s):

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

Unread postby 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. :D
Par contre je n'ai plus le code.
Minecraft 3D Ti 83 PCE avec Azerpogba

11.5%

Image
User avatar
edgar13Modo
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Level up: 24%
 
Posts: 456
Images: 21
Joined: 04 Jan 2019, 20:31
Location: Sur TI-Planet voyons
Gender: Male
Calculator(s):
Class: Première Maths-Physique-chimie-S.V.T.

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

Unread postby 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 ! :D 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 ! :D
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 ;) !
User avatar
TituyaPremium
Niveau 1: MD (Membre Débutant)
Niveau 1: MD (Membre Débutant)
Level up: 0%
 
Posts: 4
Joined: 15 Nov 2019, 00:02
Gender: Not specified
Class: TS

Online

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

Unread postby 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 ... :o
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: 16.2%
 
Posts: 192
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 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. :D

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
L'algorithmique, ça me passionne.
Projet en cours
: Solveur de sudoku en python
User avatar
Golden ManPremium
Niveau 0: MI (Membre Inactif)
Niveau 0: MI (Membre Inactif)
Level up: 0%
 
Posts: 10
Joined: 12 Oct 2019, 13:03
Location: Avignon
Gender: Male
Calculator(s):
Class: Terminale S

PreviousNext

Return to News Divers

Who is online

Users browsing this forum: MSN [Bot] and 11 guests

-
Search
-
Featured topics
Omega, le fork étendant les capacités de ta NumWorks, même en mode examen !
Comparaisons des meilleurs prix pour acheter sa calculatrice !
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
123
-
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.
690 utilisateurs:
>637 invités
>48 membres
>5 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)