by 
Il s'agissait donc de créer à l'aide d'un script fourni une main de Pokémons la plus puissante possible.
Nous avons reçu un total écrasant de 183 participations de la part de 27 participants différents :
- 3 participants ont utilisé entre autres une HP Prime ou son logiciel d'émulation
- 2 participants ont utilisé entre autres une TI-83 Premium CE ou son logiciel d'émulation
- 1 participant a utilisé entre autres une Casio Graph 90+E ou son logiciel d'émulation
24ème :
On commence doucement avec grandben49 qui nous présente son équipe de 10 Pokémons. Pensant qu'il faut du piquant pour avancer, il en confie la gestion à Dardagnan. Cette équipe bien échelonnée totalise 43,4213 points.23ème :
Passé maître au jeu pierre-papier-ciseaux, thecamouflage a constitué une équipe similaire mais en nommant à sa tête Gravalanch et en le faisant seconder en prime par Racaillou. Ces ajouts de poids lui permettent d'atteindre 44,4569 points.22ème :
Rémi G. procède de même mais motive son équipe en la confiant à l'infatigable Tartard. Et ça marche, avec maintenant 46,3762 points.21ème :
Nous arrivons maintenant à KikooDX, présent à la fois sur TI-Planet et sur Planète Casio. Croyant en l'intelligence collective il nomme non pas un mais quatre chefs pour conduire son équipe au combat, et comme tout bon dresseur Pokémon il choisit bien évidemment des chefs de types tous différents : Florizarre, Rattatac, Abra et Tentacool. Une stratégie qui rapporte 46,6735 points.https://www.planet-casio.com/Fr/forums/ ... ast#171151KikooDX wrote:J'explique ce que j'ai fait pour obtenir mon score terrible.
J'ai fait une boucle tirant 10 Pokémons aléatoires et les assigne à l'équipe. J'ai laissé tourner le script deux semaines sur mon RPi, j'ai vu que les résultats n'étaient pas terribles (mon max. était un peu plus de 47) et j'ai arrêté. En gros j'ai tenté la méthode facile, faire un script non optimisé avec une méthode bancale, et ça n'a pas marché.
(Et heureusement.)
20ème :
Ekter en ce qui le concerne croit aux vertues de l'égalité. Dans l'équipe à coloration végétale qu'il t'a constituée, aucun Pokémon n'a plus de pouvoir qu'un autre. Et effectivement ces nobles intentions lui permettent de s'inscrire au classement avec 47,1412 points.19ème :
Ti64CLi++, actif sur TI-Planet et sur Planète Casio, nous sort pour sa part une équipe bicéphale avec Abra et Tentacool, bien évidemment de types différents. Il récolte ainsi 47,6148 points.18ème :
Krevo_ participant lui aussi à TI-Planet et à Planète Casio nous met également Abra à la tête de son équipe mais fortement secondé de Florizarre, là encore deux chefs de types différents. Un duo visiblement gagnant puisque cela lui permet de se hisser à 48,1623 points.17ème :
Renaud42 donne cette fois-ci une puissance écrasante à Abra, tout en le faisant assister par Tentacool, qui commande lui-même à un trio de chefs intermédiaires Reptincel-Roucool-Chetiflor, que des types différents. Ces grandes compétences en dessage de Pokémon lui permettent ainsi de monter à 48,9534 points.16ème :
Avec Filoji il n'y a plus que deux Pokémons supérieurs aux autres, Abra secondé par Tentacool. La disparition des échelons intermédiaires est visiblement payante avec 49,2890 points.15ème :
Captainluigi a fait appel entre autres à une TI-83 Premium CE pour nous remettre le même duo Abra-Tentacool. Parmi le reste des troufions, il nous fait évoluer Chetiflor en Empiflor tout en nous rajoutant Rattatac et Roucool. Des ajustements lui permetant d'atteindre 49,2930 points.https://www.planet-casio.com/Fr/forums/ ... tml#170787Captainluigi wrote:Voici ma technique assez simple:
J'ai du passer 20 heures dessus, pour rien
- Tout d'abord j'ai lancé des boucles pour tester toutes les possibilités possibles
, et j'ai obtenu environ 46.
- J'ai lancé des boucles pour déterminer à partir du score des 46 la meilleure combinaison possible de caractères, et au final j'ai donc obtenu 49.29
14ème :
edgar13 a cherché entre autres sur TI-83 Premium CE pour nous proposer sa propre version de l'équipe gagnante Abra-Tentacool. Chez les simples soldats nous avons donc cette fois-ci à la fois Chetiflor et Empiflor, ainsi que le retour de Dodrio. 49,3089 points.viewtopic.php?f=49&t=23011&start=250#p247987edgar13 wrote:Vous vous demandez comment j'ai fait 14ème ? Tant mieux.
Tout d'abord j'ai commencé en classant les pokémons "a la main" puis ayant fait le classement je leur ai attribué 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.
13ème :
Voici maintenant venir Cyril S. qui a cherché sur HP Prime et nous propose sa déclinaison de l'équipe Abra-Tentacool, nous rajoutant Reptincel et Parasect parmi les autres. On progresse à 49,3101 points.12ème :
Disperseur nous reprend le couple Abra-Tentacool. Mais cette fois-ci, il nous accompagne les autres d'un Dodrio. 49,3139 points.
https://www.planet-casio.com/Fr/forums/ ... tml#170645Disperseur wrote:Voici donc une petite explication de la technique que j'ai employée pour obtenir mon score.
Face à la fonction pk() dont le code m'as un peu effrayé, j'ai choisi de ne pas essayer de le comprendre et de l'utiliser tel quelle. Tout d'abord j'ai créé une fonction qui prenait en entrée la liste des Pokémons déjà ajoutés et qui me donnait le Pokémon suivant pour obtenir le meilleur score. Cette fonction testait tout simplement un à un en ajoutant, enregistrant leur score puis retirant tous les Pokémons (les 94). Néanmoins cette fonction n’agissait pas sur les compétences des Pokémons et n’obtenait pas le meilleur score. J'ai ensuite créé une autre fonction pour exploiter la précédente, qui me donnait la meilleure main à partir d'un Pokémon de 'base' que je lui donnais. Par la suite j'ai retiré ce paramètre et j'ai obtenu LA meilleure main de 10 Pokémons sans modifier leurs compétences. N'obtenant ainsi qu'un score autour de 47, j'ai décidé de jouer à la main sur les compétences de chacun de mes 10 Pokémons. Donc en partant du premier, je tentais de modifier ces compétences en augmentant le paramètre concerné dans la fonction pk(). Si je voyais mon score diminuer, alors je revenais sur la meilleure valeur. Et ainsi de suite pour les 10. Ensuite j'ai tenté de remplacer les Pokémons n'ayant pas subi de modification de compétences par d'autres plus performants, en utilisant toujours ma première fonction (suppression du Pokémon à remplacer, appel de la fonction avec la liste des 9 autres Pokémons et obtention du meilleur Pokémon à mettre à la place). Ainsi j'ai obtenu, en affinant la technique et en testant plusieurs configurations, un score d'environ 49,301...
Je suis désolé, j'aurais bien voulu vous partager le code de cette fonction, mais en rédigeant ce message et en la cherchant, je me suis rendu compte que je l'avait supprimée
Là-dessus, je tiens à féliciter les premiers de ce classement et à leur dire que je suis toujours dans la course
11ème :
Amiga68000 nous ressort la même équipe, mais avec un Abra un peu plus puissant au détriment de son lieutenant Tentacool. Les autres sont également moins bien dotés avec 1,08% de puissance chacun. 49,3142 points.Amiga68000 wrote:Bravo pour vos algos 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 tenterai 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.Voilà mes étapes à peu près dans l'ordre, j'ai fait plein de petites routines pour celà Voici ci-dessous mon code global, n'hésitez pas à me faire vos remarques, je suis pas un pro de la prog. Bonne lecture
- 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 !- Jauger les Pokémon :
Un peu moins bourrin, j'ai jaugé chaque Pokémon un à un. Ça m'a permis de les classer.- Comprendre l'algo :
Comprendre le code et l'algo, j'en ai fait un Excel.
Dans la colonne Y, vous rentrez votre priorité d'attaque en face du Pokémon choisi. En cellule Y2 vous récupérez le score.le score est l'ancienne évaluation.
Pour l'excel, il a fallu que je cartographgie mes Pokémons. C'est là que j'ai compris que :
- la somme des priorités devait être inférieure à 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 Pokémon.
- 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- Classer les Pokémon, méthode 2 :
J'ai vu que 2 Pokémons 63 et 72 sortaient du lot. J'ai alors fait 100.000 tirages de 10 Pokémons avec les 63 et 72 avec priorité 1. A chaque fois je relevais le score pour l'ajouter à la moyenne de chaque Pokémon contenu dans le tirage. But : les classer.- Varier les priorités :
En prenant les Pokémons avec les meilleurs résultats, j'ai fait varier toutes les priorités. Je suis arrivé à un très bon résultat (3ème 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- Combinaisons :
En prenant les meilleurs Pokémons de l'étape 4, (30 environ, je ne 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.
Si vous avez besoin de plus d'explication je suis dispo.
viewtopic.php?f=49&t=23011&start=250#p247986Amiga68000 wrote:
- 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
10ème :
Encephalogramme nous sort lui aussi la même équipe, avec un Abra un peu plus puissant. Le reste c'est le commun des mortels avec plus que 1,05% chacun. Score 49,3155 points.Encephalogramme wrote:Le but était de faire une sorte de force brute 'réfléchie', j'ai donc commencé par classer les Pokémons par score dans un tableau. J'ai repéré quelques Pokémons particulièrement forts en terme de points, et je les ai choisis comme base. Par la suite, j'ai fait tourner pendant quelques heures du random sur 6 ou 7 Pokémons, avec le reste pris dans les meilleurs Pokémons du tableau, et une fois la meilleure combinaison de Pokémons trouvée, j'ai refait tourner du random au niveau des points d'attaques, tout en modifiant la plage de nombre random pour gagner en points à chaque fois. Bon j'ai fini 10ème, mais je me suis arrêté de chercher quand j'ai vu que tout le monde bloquait en dessous de 49,32 :3
9ème :
Même équipe chez Afyu, avec un Tentacool un peu moins effacé. Et surtout, plus que 1,04% chacun pour le reste qui n'est plus que de la chair à canon. Score 49,3159 points.Afyu wrote:Voici comment j'ai procédé pour la résolution du défi Python dont j'ai découvert l'existence vers le 16 ou 17 octobre.Après avoir effectué quelques test manuellement, j'ai écrit un programme en Python pour optimiser ma recherche. J'ai récupéré la ressource NumWorks proposée pour le concours, que j'ai complétée. L'idée est de tester des mains de 10 Pokémons et de comparer chaque nouveau score obtenu avec le meilleur score obtenu jusqu'à présent. J'ai donc créé une liste qui va contenir le meilleur score (ou plutôt les meilleurs scores successifs obtenus au cours de la recherche). J'aurais pu créer une variable globale pour stocker mon meilleur score, mais ne maitrisant pas la syntaxe pour ça, j'ai préféré créer une liste scoreliste qui s'allonge avec chaque nouveau meilleur score. Il suffit alors de prendrescoreliste[-1]pour récupérer le dernier élément, donc le meilleur score. Et j'ai fait de même pour les codes avec codeliste. Par la suite, j'ai créé une variable score_max qui stocke la valeurscoreliste[-1]. Je tenais à avoir la liste des Pokémon et des puissances associées de chacun de mes meilleurs scores. C'est pour cette raison que j'affiche le meilleur scorescoreliste[-1], le code associécodeliste[-1]ainsi que la liste des Pokémons pokemon et la liste des puissances associées attaque. La première ligne est écrite avec un>=et non pas un>pour stocker un nouveau score s'il est meilleur que le dernier meilleur score obtenu, ou s'il est égal à ce dernier. C'est peut-être peu pertinent, mais ça permet de changer de temps en temps la liste des Pokémons ou des puissances sur laquelle le programme effectue ses tests, même si le meilleur score n'évolue plus.
- Code: Select all
if score>=score_max:
atta.append(attaque[:])
poke.append(pokemon[:])
if score>score_max:
print(scoreliste[-1],iii)
print("#",score,codeliste[-1])
print("# poke",poke[-1])
print("# atta",atta[-1])
print("")
score_max=score
viewtopic.php?f=49&t=23011&p=248148#p248146Afyu wrote:J'ai initialisé ma liste des Pokémons pokemon et ma liste des puissances attaque avec des 1, je crois.
- Code: Select all
pokemon=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] (ou pokemon=[1]*10)
attaque=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] (ou attaque=[1]*10)Je remplis la main avec la boucle ci-contre.
- Code: Select all
for kkk in range(10):
pk(pokemon[kkk],attaque[kkk])Et je la vide avec la boucle ci-contre.
- Code: Select all
for jjj in range(10):
pk(pokemon[jjj],0)J'ai commencé mes recherches en remplaçant une puissance d'attaque par un nombre tiré aléatoirement. Le rang de l'attaque est également choisi aléatoirement entre 0 et 9, ce qui désigne un des 10 Pokémons de la main.
- Code: Select all
rang=randint(0,9)
attaque[rang]=randint(1,200)Dans un second programme, je cherche en modifiant non pas l'attaque des Pokémons, mais leur numéro parmi les 94 disponibles avec des nombres tirés aléatoirement, encore une fois.
- Code: Select all
rang=randint(0,9)
pokemon[rang]=randint(1,94)Je récupère ma meilleure main de Pokémon, avec les puissances associées, et je fais travailler mes deux programmes sur chaque meilleure main trouvée, en la changeant lorsqu'elle est améliorée. Après quelques essais (ici 10), je reprends ma recherche avec comme liste de départ la dernière meilleure main obtenue. Et j'effectue des changements sur cette main pour espérer améliorer mon score. Je ne repars pas d'une main totalement aléatoire à chaque fois que j'améliore mon meilleur score.
- Code: Select all
if nb_chgt==10:
attaque=atta[-1] (ou pokemon=poke[-1] dans l'autre programme)Après quelques min...jours de calculs, j'ai obtenu un score proche de 49,3154 avec O#0K_g^huS""1""h"""" mais qui est enregistré dans le tableau des participations sous un score un peu inférieur : 49,31486. Mon meilleur score ne s'améliorant plus, j'ai changé mon approche. J'ai essayé de modifier les puissances d'attaque, mais de 1 en 1. Je choisis un Pokémon aléatoirement, dans ma meilleure main trouvée jusqu'alors et je modifie la puissance de ce Pokémon de 1 (donc j'ajoute 1 ou je retranche 1).
- Code: Select all
rang=randint(0,9)
attaque[rang]+=2*randint(0,1)-1En tirant un entier aléatoirement valant 0 ou 1, puis en prenant son double (donc 0 ou 2) et enfin en lui retranchant 1, on obtient un entier qui vaut -1 ou 1. Les deux lignes de code précédentes peuvent être compactées en une seule.
- Code: Select all
attaque[randint(0,9)]+=2*randint(0,1)-1J'ai abandonné ma première syntaxe en une ligneattaque[randint(0,9)]=attaque[randint(0,9)]+2*randint(0,1)-1au profit d'une écriture avec un+=parce que les deux nombres tirés aléatoirement avecrandint(0,9)sont très souvent différents, et ça ne m'intéresse pas.
Avec cette nouvelle approche, j'ai de nouveau pu améliorer mon meilleur score pour atteindre 49,31730 et même 49,31859 (le 19/10) et 49,31975 le 19/10 au soir !
- Code: Select all
49.31730339247606
'O#0K_g^huS""3""f""""'
poke [51, 85, 72, 62, 71, 63, 43, 16, 3, 47]
atta [4, 4, 61, 2, 2, 235, 3, 2, 3, 3]
49.3185945083636
'O#0K_g^huS""3""g""""'
poke [51, 85, 72, 62, 71, 63, 43, 16, 3, 47]
atta [2, 3, 61, 2, 2, 239, 2, 4, 2, 2]
Cette nouvelle approche m'a montré à chaque nouveau meilleur score que les puissances d'attaque de tous mes Pokémons se rapprochaient toujours plus de 2, sauf pour 2 Pokémons. J'ai fini par essayer, à la main, des puissances d'attaque toutes égales à 2, sauf pour les deux Pokémons exceptions. Et j'ai modifié mon programme pour que l'ajustement des puissances ne se fasse que pour les deux Pokémons exceptions.
Les deux Pokémon en question étant placés en position 2 et 5, j'ai donc modifié mon choix du rang pourrang=3*randint(0,1)+2qui donne un nombre entier aléatoire qui vaut 2 ou 5.
Oui ? De quoi ? J'aurais pu tout simplement mettre les deux Pokémon en question en position 0 et 1 et tirer un nombre entier entre 0 et 1 avecrandint(0,1)? Euh...bah...euh... c'est pas faux. Bien vu ! pfff xD Mais pourquoi faire simple quand on peut faire compliqué ?Avec les deux dernières puissances proches de 60 et de 230, j'ai obtenu les scores 49,3188 et 49,3197. Puis pour des puissances d'attaque à 35 et à 143 et à 1 pour les 8 autres Pokémons, j'ai obtenu le score ultime de 49,3207 (le 21/10) !!
- Code: Select all
49.31975298152274
'O#0K_g^huS""3""h""""'
poke [51, 85, 72, 62, 71, 63, 43, 16, 3, 47]
atta [2, 2, 58, 2, 2, 234, 2, 2, 2, 2]
49.32078546995182
'O#0K_g^huS""3""i""""'
poke [51, 85, 72, 62, 71, 63, 43, 16, 3, 47]
atta [1, 1, 35, 1, 1, 143, 1, 1, 1, 1]
Super enthousiaste (naïvement ? Peut-être bien, oui...), j'envoie mes scores à Critor en espérant que la différence d'évaluation ne soit pas trop grande... et là c'est le drame ! Mes codes valent en fait 49,3151. La looooooose !
Je suis donc allé éplucher le forum et j'ai compris que les codes étaient passés dans la moulinettesetst()pour retrouver le score et que c'est ce score qui est validé et ajouté dans le tableau des participations.
J'ai donc modifié mon programme en conséquence, en calculant le score avecsetst("code_obtenu")avant de le comparer à mon meilleur score.
- Code: Select all
score=setst(codeliste[-1])
J'ai finalement compris (alors que c'était expliqué sur le forum, depuis le début du défi ! Mais quand on ne sait pas lire, hein...) que si la somme des puissances dépasse 100, alors toutes les puissances sont réduites par la fonctionsetst(), avec le même coefficient multiplicateur, pour que leur somme ne dépasse plus 100, puis arrondies à l'unité. Si les puissances réduites sont trop petites, alors l'arrondi à l'unité donne 0, ce qui explique la disparition de certains Pokémon de la main lorsqu'on ajoute un Pokémon avec une trop grande puissance. La liste pkl contient le numéro de chaque Pokémon de la main, ainsi que sa puissance associée et un troisième nombre. Ce dernier nombre est la valeur retenue, après réduction et arrondi à l'unité. J'ai donc découvert que mon 35 devient 18 et que mon 143 devient 72. Pour respecter la proportionalité, il aurait au moins fallu avoir 17,5 et 71,5 (et 0,5 pour les 8 autres puissances, du coup ?). Après quelques essais, j'ai vu que la somme des puissances pouvait être comprise entre 93 et 97. Mais même avec cette petite tolérance, je n'ai pas réussi à retrouver de très bons scores. Après des heures de calcul, uniquement sur les deux puissances différentes de 1, pas moyen d'obtenir de nouveau un score supérieur à 49,3185... très déçu, j'abandonne et me lance dans la résolution du 3ème défi.Le dernier jour ouvert pour la participation, vers 22h45, je me décide à lancer un ultime calcul. Le calcul de la dernière chance. Juste avant, je vais éplucher le forum, une fois encore, à la recherche d'une bonne idée. Je découvre qu'il est possible de passer des caractères codés avec un\suivi d'un nombre. J'ai sauté sur l'occasion et j'ai testé à la main quelques caractères écrits avec cette nouvelle écriture, jusqu'à retrouver mes 3 très bons scores au-dessus de 49,318 !! Un de ces trois scores n'avait pas encore été soumis, d'après le tableau des participations, alors j'en profite, j'envoie 2 mails (à 23h40 et 23h52 ! Plus que 8 min, tic tac tic tac !!).
Ces codes ressemblent à ça, le 35 et le 143 étant remplacés par des caractères codés avec un \ suivi d'une chaîne de caractère.
- Code: Select all
setst('O#0K_g^huS""\x3D""\x99""""')
49.318885384185236
setst('O#0K_g^huS""\x42""\xB2""""')
49.31951877543954
Et finalement, un participant est sorti de nulle part en soumettant 18 codes, en réservant la plupart des codes encore dispo, juste quelques heures avant moi. Tant pis, je suis finalement 9ème. Mais je suis content d'avoir essayé jusqu'au bout et d'avoir trouvé une main qui donne un score de 49,3207 si on ne le repasse pas dans la moulinettesetst()et qui n'utilise pas de caractères bizarres commençant par un\.
Je remercie grandement toutes les personnes qui ont permis à ce concours d'exister et qui ont permis d'avoir autant de lots très intéressants !Je donne ici mon script complet, même pas nettoyé pour montrer mes traces de recherches.
- Code: Select all
#score=[]
codeliste=[0]
scoreliste=[0]
#cas
from math import *
def mmod(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()
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,[]
mrandmax,mrand,mfmax,nn,mp=2**31-1,0,93,getlinechars(True)-na,na//2
def mround(f):
d=mmod(abs(f),1)
return (mfloor(abs(f))+(d>=.5))*(1-2*(f<0))
def mfloor(f):
return round(f)-(round(f)>f)
def mceil(f):
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 f2mf(f):
return mround(float(f*mfmax))
def mf2f(n):
return float(n/mfmax)
def mbit(a,b):
return mmod((a//(2**b)),2)
def getattack(p,pts):
global pkt
mseed(42)
for k in range(p+1):
mrandom()
a,pka=mrandint(1,mrandmax),""
for j in range(na):
if mbit(a,j)!=0:
pka+="X"
pkt[j]+=pts
else:
pka+=" -"[getplatform()>=5]
return pka
def i2c(k):
return chr(k+33)
def c2i(c):
return ord(c)-33
def clean():
global pkl
t,s=0,0
for l in pkl:
t+=l[1]
for l in pkl:
l[2]=f2mf(l[1]/(t or 1))
s+=l[2]
if(l[2]<=0):
pkl.remove(l)
return clean()
return s
def pk(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)
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\nenvoie code suivant\na info@tiplanet.org :")
scoreliste.append(float(t))
codeliste.append(""+st)
#score.append(setst(st))
#print(""+st)
return float(t)
def setst(st):
s,pkl[:],n=0,[],len(st)//2
for k in range(n):
s=pk(c2i(st[n-1-k])+1,c2i(st[n+k+len(st)%2]),k+1>=n)
return s
print("pk(n,p) pour rajouter\nle Pokemon n a ta main\navec p points d'attaque.")
#end
score_max=0
poke=[]
atta=[]
pokemon=[57, 72, 5, 43, 3, 69, 89, 62, 63, 16]
#attaque=[1, 1, 1, 1, 1, 1, 1, 1, 59, 236]
#pokemon=[51, 85, 72, 62, 71, 63, 43, 16, 3, 47]
#dd=9
attaque=[1, 1, 17, 1, 1, 68, 1, 1, 1, 1]
#pokemon=[1]*10
#attaque=[dd]*10
nb_chgt=0
from random import randint
for iii in range(50):
#pokemon=[randint(1,94) for y in range(10)]
#attaque=[randint(1,200) for y in range(10)]
if iii>0: # et si iii vaut 0, on évite cette boucle et on ajoute un premier score non nul dans scoreliste
#pokemon[randint(0,9)]+=2*randint(0,1)-1#randint(1,94)
#rang=randint(0,9)
rang=3*randint(0,1)+2
#pokemon[randint(0,9)]=randint(1,94)
#attaque[rang]-=1
#attaque[rang]=max(attaque[rang]+2*randint(0,1)-1,1)
#rang=randint(0,9)
#rang=8-rang #3*randint(0,1)+2
#pokemon[rang]=randint(1,94)
#attaque[rang]=max(1,93-(sum(attaque[:])-attaque[rang]))
#attaque[rang]=randint(1,50)
attaque[rang]+=2*randint(0,1)-1
#attaque[3*randint(0,1)+2]+=1*(2*randint(0,1)-1)
for kkk in range(10):
pk(pokemon[kkk],attaque[kkk])
score=setst(codeliste[-1]) # ici le vrai score
if score>=score_max:
atta.append(attaque[:])
poke.append(pokemon[:])
#code=codeliste[-1]
if score>score_max:
print(scoreliste[-1],iii) # ici le score avant évaluation dans setst()
print("#",score,codeliste[-1])
#print("#",setst(code))
print("# poke",poke[-1])
print("# atta",atta[-1])
print("")
score_max=score
for jjj in range(10):
pk(pokemon[jjj],0)
nb_chgt+=1
if nb_chgt==20:
#pokemon=poke[-1]
attaque=atta[-1]
8ème :
cent20 repart sur l'équipe gagnante Abra-Tentacool mais nous en fait une version poids-lourd en nous remontant les autres à 1,05% et leur ajoutant un Grolem. Tout ça pour 49,3169 points.cent20 & Golden man wrote:En naviguant par hasard sur le site TI-Planet, nous sommes tombé sur un défi Python et comme se perfectionner en Python était l’un de nos objectifs, autant joindre l’utile à l’agréable.
Pour le défi python 2019 des sites internet TI-Planet et Planète Casio, il fallait se constituer une main de 10 Pokémons maximum et leur attribuer une priorité d’attaque.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)
Dans la suite de l’article, le 'nous' fait référence aux participants cent20 et Golden man, car nous avons réalisé les recherches en commun.
https://nsi.xyz/concours-de-rentree-2019-Le-defi-python-Pokémoncent20 & Golden man wrote:
- PREMIERS TESTS "À LA MAIN"
Comme beaucoup de joueurs, nous avons commencé par générer des mains au petit bonheur la chance, gratifié d’un score maximum de 44,2 nous sommes vite passé à une autre méthode. Nous aurions bien voulu commencer les recherches sur la NumWorks, mais les problèmes de mémoire dont elle souffre rendent ces recherches impossibles. Ajouter quelques lignes de codes au script de 3.7 Ko aurait fait planter la calculatrice. Nous sommes donc passé sur Thonny et y avons exécuté nos scripts Python.- ATTAQUE N°1 : 10N TIRAGES ALÉATOIRES
Après avoir neutralisé les fonctions print, les affichages des scripts du concours, et rajouté quelques variables globales, une boucle de tirage aléatoire fut codée.
Le résultat n’est pas optimal, on ne tire aléatoirement que les Pokémons en pensant naïvement que les forces sont forcement des entiers entre 1 et 10. Mais on arrive à fabriquer des scores aux alentours de 46,2. En une nuit, on arrive péniblement à réaliser entre 4 et 7 millions de tirages. A ce stade de la recherche, compte tenu de nos hypothèses, on cherche une solution optimale parmi 3 x 10^19 possibilité. Toute force brute est impossible.
- Code: Select all
import random
score, scoremax = 0.0, 0.0
code, codemax = 0.0, 0.0
tentative = 0
def tiragemain():
for i in range(1,11,1):
pokemonaleatoire = random.randint(1,94)
score=pk(pokemonaleatoire,i)
return score,code
while score<49.3:
# Les trois lignes ci-dessous réinitialisent le script, qui tourne sans s'arrêter
na,pkl=21,[]
lnm =["Bulbizarre","Herbizarre","Florizarre","Salameche","Reptincel","Dracaufeu",
"Carapuce","Carabaffe","Tortank","Chenipan","Chrysacier","Papilusion","Aspicot",
"Coconfort","Dardargnan","Roucool","Roucoups","Roucarnage","Rattata","Rattatac",
"Piafabec","Rapasdepic","Abo","Arbok","Pikachu","Raichu","Sabelette","Sablaireau",
"Nidoran F","Nidorina","Nidoqueen","Nidoran M","Nidorino","Nidoking","Melofee",
"Melodelfe","Goupix","Feunard","Rondoudou","Grodoudou","Nosferapti","Nosferalto",
"Mystherbe","Ortide","Rafflesia","Paras","Parasect","Mimitoss","Aeromite","Taupiqueur",
"Triopikeur","Miaouss","Persian","Psykokwak","Akwakwak","Ferosinge","Colossinge","Caninos",
"Arcanin","Ptitard","Tetarte","Tartard","Abra","Kadabra","Alakazam","Machoc","Machopeur",
"Mackogneur","Chetiflor","Boustiflor","Empiflor","Tentacool","Tentacruel","Racaillou",
"Gravalanch","Grolem","Ponyta","Galopa","Ramoloss","Flagadoss","Magneti","Magneton",
"Canarticho","Doduo","Dodrio","Otaria","Lamantine","Tadmorv","Grotadmorv","Kokiyas",
"Crustabri","Fantominus","Spectrum","Ectoplasma"]
mrandmax,mrand,mfmax,nn,mp=2**31-1,0,93,getlinechars(True)-na,na//2
tentative = tentative+1
score,code = tiragemain()
if score>scoremax:
scoremax = score
codemax = code
print("################# tirage n°",tentative,"score =", scoremax,"avec le code", codemax,"#################", round(score,8))- ATTAQUE N°2 : RECHERCHE DES POKÉMON FORTS !
On décide de faire tourner le script précédent et de mémoriser les compositions des mains supérieures à 46. On va donc réaliser quelques millions de tirages, et dénombrer les Pokémons qui ont permis de faire une main supérieure à 46.
Le lendemain, nous avons un histogramme qui nous donne des Pokémons performants :
- Code: Select all
[0, 54, 25, 143, 11, 99, 39, 23, 5, 10, 6, 11, 9, 17, 10, 31, 70, 13, 12, 10, 48, 15, 38, 51, 18, 6, 21, 33, 13, 19, 5, 8, 13, 48, 13, 33, 35, 5, 31, 24, 31, 9, 33, 94, 28, 13, 5, 106, 16, 8, 34, 51, 27, 6, 13, 3, 36, 33, 42, 4, 17, 9, 72, 311, 3, 16, 30, 25, 32, 74, 13, 60, 172, 40, 12, 62, 44, 1, 8, 38, 6, 32, 15, 22, 21, 101, 25, 24, 73, 19, 26, 5, 33, 4, 18]
Le Pokémon 63 (Abra) est sorti 311 fois dans la nuit dans des mains valant plus de 46 points. Le 64 lui était très mauvais, et il n’était que dans 3 mains valant plus de 46 points.
- Code: Select all
if score>46:
for i in listeobtenu:
benchmark46(i,score)- ATTAQUE N°3 : TIRAGES ALÉATOIRES SUR LISTE OPTIMALE
Le deuxième jour, nous avons poursuivi les tirages aléatoires mais sur des listes optimales générées à l’aide de l’histogramme de la veille.Au lieu de tirer au hasard un Pokémon parmi 94, on le tirait dans une liste prédéfinie à diverses positions (nous pensions que la force était la position, donc un entier entre 1 et 11).
- Liste large :
[ 3 , 5 , 16 , 33, 43, 47, 51, 58, 62, 63, 69, 71, 72, 73, 75, 76, 85, 88 ]- Liste short :
[ 3 , 5 , 16 , 47, 62, 63, 69, 72, 75, 85, 88]
5 000 000 de tirages plus tard, pas de grandes améliorations, 47.6 est notre meilleur score, mais c’est déjà un joli résultat.
- Code: Select all
def tiragemain():
listeobtenu =[]
top = [ 3 , 5 , 16 , 47, 62, 63, 69, 72, 75, 85, 88]
random.shuffle(top)
for i in range(1,11,1):
pokemonaleatoire = top[i-1]
listeobtenu.append(pokemonaleatoire)
score=pk(pokemonaleatoire,i)
for i in listeobtenu:
benchmark(i,score)
if score>47:
for i in listeobtenu:
benchmark47(i,score)
return score,code,listeobtenu- ATTAQUE N°4 : VALEUR MOYENNE DES MAINS
Toutes les tentatives pour optimiser la valeur moyenne des mains ont échouées. Le calcul lui même de cette moyenne n’étant pas concluant.- ATTAQUE N°5 : RECHERCHE DES POKÉMON FORTS SUR ℝ
En lisant le forum associée à ce défi sur Planète Casio, on croit comprendre qu’il n’y a pas un nombre fini de combinaisons, donc si on tire n dans les entiers entre 1 et 94, p lui serait un réel. On relance les scripts précédents et miracle on passe au dessus de 47.8.
- Code: Select all
def tiragemain():
listeobtenu =[]
for i in range(1,11,1):
pokemonaleatoire = random.randint(1,94)
listeobtenu.append(pokemonaleatoire)
score=pk(pokemonaleatoire,uniform(0,2**31-1))
if score>46:
for i in listeobtenu:
benchmark47(i,score)
return score,code,listeobtenuAprès avoir affiné la liste des Pokémons optimaux, on relance les autres scripts qui mélangent, permutent, tirent d’après la liste optimale, et on obtient nos premiers score à 48.
- Code: Select all
0^uxOeh%_##>(6#))*&#
48.12835164090643
^heO0xku#_D#’’#%$*.0
48.14694065075124- ATTAQUE N°6 : ÉLIMINATION DES PLUS FAIBLES
N’étant pas certains d’avoir la main optimale, on essaye de remplacer un Pokémon par tous les autres pour voir si le score s’améliore. Cette méthode ne permet pas de progresser.- ATTAQUE N°7 : TENTATIVE DE SPÉCIFICATIONS DES FONCTIONS
On décide alors de documenter le code, de le décrypter, d’essayer de voir si on ne peut pas faire le problème à l’envers, c’est une attaque par spécification du code.
- Code: Select all
def mmod(a, b):
# retourne la partie décimale de a a vérifier
# si a est un entier, retourne 0
# ?? intérêt , a % b économise de la mémoire
return a % b
def getplatform():
# retourne la valeur 1
# ?? intérêt ?
return 1
def getlinechars(o=False):
# Cette fonction est une bague. Elle est appelée une unique fois avec true
# et alors getlinechars(True) retourne 99
c = 2 ** 31 - 1
k = getplatform()
# ?? k = 1 ;-)
if k >= 0:
# k = 1 donc est exécuté dans 100% des cas ...
c = [53, o and 99 or 29, o and 509 or 21, 31, 32, c, c][k]
return c # c= 99 ... sauf astuce et codage plus bas ^^
# pas défaut, en l'absence de True getlinechars() retourne 29Les premières fonctions sont faciles à spécifier. Les variables sont rigolotes.
- Code: Select all
na = 21
# 42/2 ? :-) Utilisé 2 fois, jamais modifié
mrandmax = 2 ** 31 - 1
# valeur max d'un entier positif signé codé en 32 bits... spé NSI inside
mrand = 0
# rien d'aléatoire ici, sera modifié par la fonction mseed()
mfmax = 93
# 94-1
nn = getlinechars(True) - na
# nn = 99-21 = 78 (sans calculatrice !)
mp = na // 2
# mp = 10, jamais modifié, utilisé une seule fois f° pkMais nous sommes restés coincés sur les fonctions getattack(), clean() et surtout pk(). Par contre la fonction setst() nous a passionnés !
Ci-contre le script original à peine modifié, commenté et codé en pep8.
- Code: Select all
# cas
import math
# pas utilisé ?
"""Ajouts"""
# sera utilisé dans nos scripts
code = 0.0
"""Fin des ajouts"""
def mmod(a, b):
# retourne la partie décimale de a a vérifier
# si a est un entier, retourne 0
# ?? intérêt , a % b économise de la mémoire
return a % b
def getplatform():
# retourne la valeur 1
# ?? intérêt ?
""" modifié, 1 avant 2 maintenant"""
return 2
def getlinechars(o=False):
# Cette fonction est une bague. Elle est appelée une unique fois avec true
# et alors getlinechars(True) retourne 99
c = 2 ** 31 - 1
k = getplatform()
# ?? k = 1 ;-)
if k >= 0:
# k = 1 donc est éxécuté dans 100% des cas ...
c = [53, o and 99 or 29, o and 509 or 21, 31, 32, c, c][k]
return c # c= 99 ... sauf astuce et codage plus bas ^^
# pas défaut, en l'absence de True getlinechars() retourne 29
na = 21
# 42/2 ? :-) Utilisé 2 fois, jamais modifié
pkl = []
# une liste
lnm = ["Bulbizarre", "Herbizarre", "Florizarre", "Salameche", "Reptincel", "Dracaufeu", "Carapuce",
"Carabaffe", "Tortank", "Chenipan", "Chrysacier", "Papilusion", "Aspicot", "Coconfort",
"Dardargnan", "Roucool", "Roucoups", "Roucarnage", "Rattata", "Rattatac", "Piafabec",
"Rapasdepic", "Abo", "Arbok", "Pikachu", "Raichu", "Sabelette", "Sablaireau", "Nidoran F",
"Nidorina", "Nidoqueen", "Nidoran M", "Nidorino", "Nidoking", "Melofee", "Melodelfe", "Goupix",
"Feunard", "Rondoudou", "Grodoudou", "Nosferapti", "Nosferalto", "Mystherbe", "Ortide",
"Rafflesia", "Paras", "Parasect", "Mimitoss", "Aeromite", "Taupiqueur", "Triopikeur", "Miaouss",
"Persian", "Psykokwak", "Akwakwak", "Ferosinge", "Colossinge", "Caninos", "Arcanin", "Ptitard",
"Tetarte", "Tartard", "Abra", "Kadabra", "Alakazam", "Machoc", "Machopeur", "Mackogneur",
"Chetiflor", "Boustiflor", "Empiflor", "Tentacool", "Tentacruel", "Racaillou", "Gravalanch",
"Grolem", "Ponyta", "Galopa", "Ramoloss", "Flagadoss", "Magneti", "Magneton", "Canarticho",
"Doduo", "Dodrio", "Otaria", "Lamantine", "Tadmorv", "Grotadmorv", "Kokiyas", "Crustabri",
"Fantominus", "Spectrum", "Ectoplasma"]
# la liste des pokemons
mrandmax = 2 ** 31 - 1
# valeur max d'un entier positif signé codé en 32 bits... spé NSI inside
mrand = 0
# rien d'aléatoire ici, sera modifié par la fonction mseed()
mfmax = 93
# 94-1
nn = getlinechars(True) - na
# nn = 99-21 = 78 (sans calculatrice !) si k =1
# nn = 509-21 = 488 (sans calculatrice !) si k =2
mp = na // 2
# mp = 10, jamais modifié, utilisé une seule fois f° pk (mp = p maximum je pense)
def mround(f):
# arrondi f à l'entier le plus proche
d = mmod(abs(f), 1)
return (mfloor(abs(f)) + (d >= .5)) * (1 - 2 * (f < 0))
def mfloor(f):
# arrondi f à l'entier naturel inférieur
return round(f) - (round(f) > f)
def mceil(f):
# arrondi f à l'entier naturel supérieur
return round(f) + (round(f) < f)
def mseed(s):
global mrand
# modifie une variable globale sans retourner aucune valeur
# mrand est le reste dans la division euclidienne de s par mrandmax
# suprenant car mrandmax est l'entier maximum, filouterie ?
# Si s=mrandmax alors elle réaffecte 0 à mrand,
# Si s!=mrandmax elle affecte s à mrand
mrand = mmod(s, mrandmax)
def mrandom():
# un générateur aléatoire sans fonction random ...
# je dois creuser - à tester en profondeur
mseed(mrand * 16807)
return float(mrand / mrandmax)
def muniform(mini, maxi):
# à coup sur une loi uniforme sur un intervalle
# je dois creuser - à tester en profondeur
return mrandom() * (maxi - mini) + mini
def mrandint(mini, maxi):
# à coup sur un tirage d'entier naturel
# je dois creuser - à tester en profondeur
return mround(muniform(mceil(mini), mfloor(maxi)))
def f2mf(f):
# Multiple f par 93 car c'est le dernier pokemon en commençant à 0
# en retourne l'arrondi de ce nombre
# ?? a quoi ça sert ??
return mround(float(f * mfmax))
def mf2f(n):
# retourne un réel obtenu en divisant n par 93
return float(n / mfmax)
def mbit(a, b):
# a tester
# renvoie le reste de la division euclidienne de a // 2**b et 2
# autrement dit, permet de savoir si le quotient de la division euclidienne
# de a par 2**b est impair (retourne 1) ou pair (retourne 0)
return mmod((a // (2 ** b)), 2)
def getattack(p, pts):
# Permet d'obtenir l'attaque du pokemon en fonction de son indice n (ici p)
# Et d'un parametre (l[2] dans le code) qui change avec le clean()
global pkt
mseed(42)
for k in range(p + 1):
mrandom()
a = mrandint(1, mrandmax)
pka = ""
for j in range(na):
if mbit(a, j) != 0:
# Si a / 2^j est impair, la condition est valide et on gagne des points
pka += "X"
pkt[j] += pts
else:
# Else parfaitement inutile
pka += " -"[getplatform() >= 5]
return pka
def i2c(k):
# Transforme un nombre décimal en chaine de caractère
return chr(k + 33)
def c2i(c):
# transforme une chaine de caractère ayant un élèment en valeur décimale
# cette valeur décimale sera comprise entre 32 (a) et 89 (z)
return ord(c) - 33
def clean():
global pkl
t = 0
s = 0
for l in pkl:
t += l[1]
# On rajoute 1 a tout les p des pokemons de la liste
for l in pkl:
# Affecte l[1] / t (si t est superieur a 1) / 93 (fonction f2mf) a l[2]
l[2] = f2mf(l[1] / (t or 1))
# Ajoute le resultat obtenu a s
s += l[2]
if (l[2] <= 0):
# Si l[2] <= 0: le pokemon est supprime et la fonction engage une recursion
pkl.remove(l)
return clean()
return s
def pk(n, p=1, d=2):
global pkt, pkl, code # @@ AJOUT code @@
n -= 1 # Permet de selectionner le bon indice du pokemon
if n >= 0 and n < len(lnm):
# Verifie la validite de l'indice n
# Ajoute un pokemon a la liste s'il est nouveau
# Sinon, actualise la position si p >= 0 et met 0 sinon
new = True
for k in range(len(pkl)):
# C'est cette boucle qui verifie si le pokemon est deja selectionne
# RAPPEL : pkl[k][0] est l'indice du pokemon k qui sont a nous
# PEU IMPORTE p
if pkl[k][0] == n:
new = False
pkl[k][1] = max(p,0)
# S'il est nouveau, on le dompte et il est a nous !
if new and len(pkl) < mp:
pkl.append([n, max(p, 0), 0])
# Initialisation des variables
ptt = clean() # Fonction la plus obscure, les recursions, c'est chiant
# J'ai du mal a bien discerner son fonctionnement
# du coup on ne sait pas combien vaut ptt embétant ça
pkt = [0 for k in range(na)] # Une liste avec 21 zeros dedans
t = 0
# initialise le score à 0
st = ""
# initilise la chaine de caractère donnant le code
for l in pkl:
# Chaque l est de la forme
# l = [n ; max(0;p) ; 0 (pour l'instant...) ]
# Et represente un pokemon de notre main, peu importe sa position
s = getattack(l[0], l[2] / ptt)
# j'ai l'impression que le pokemon n affronte le n+2
if d:
sn = " " + lnm[l[0]]
if len(sn) > nn:
sn = sn[:nn]
"""" print(s + sn)""" # desactivé
st = i2c(l[0]) + st + i2c(l[2])
# Fabrique le code en ajoutant par la gauche le pokemon et par la droite sa force
for k in pkt:
if (k):
t += math.log(math.exp(1) + k * len(pkl))
if (d):
"""if (d >= 2):
print("Bon score ? Si oui\nenvoie code suivant\na info@tiplanet.org :") """ # neutralisé
"""print("" + st)""" # neutralisé
code = ""+st # @@ AJOUT @@
return float(t)
def setst(st):
s = 0
# Initialise le score à 0
pkl[:] = []
# vide la liste pkl de son contenu
n = len(st) // 2
# Mesure la longueur de la chaine de caractère (20) et divise par 2
# utilisé pour la boucle for ci-dessous
# la partie gauche c'est le codage des pokemon en ACSII décimal
# la partie gauche c'est les forces en ACSII décimal
# L'ordre des poid et des pokemons n'a aucune importance tant que le pokemon conserve sa force
# En changeant l'ordre de 2 pokemons ou de 2 poid aucune différence (merci kevin)
for k in range(n):
s = pk(c2i(st[n - 1 - k]) + 1, c2i(st[n + k + len(st) % 2]), k + 1 >= n)
return s- ATTAQUE N°8 : MANIPULATIONS AUTOUR DU CODE RÉPONSE
La liste des Pokémons est codée en dur dans le script, mais il n’en est rien de leurs qualités ni de la valeur de force optimale pour chaque Pokémon. Cette dernière est donc calculée. Or la chaîne de caractère du code réponse semble peu varier lorsque de l’on tire depuis une liste fixé de Pokémons. Nous comprenons que :
- La partie gauche code la liste des Pokémons.
- La partie droite leur force.
- Pour un code "ABCDEFGHIJ0987654321", on a 10 couples [i](un exemple est ici en gras) qui définissent les 10 Pokémons et leurs points d’attaque.
- On peut faire de jolies permutations sans changer le score obtenu car les couples n’influent pas les uns sur les autres.
- Il n’y a aucune clé de vérification, on peut tester des codes au hasard sans avoir la moindre idée de la main des Pokémons et de leur forces.
- Les forces sont codés par des caractères ASCII, on n’est plus du tout dans ℝ mais de retour dans ℕ.
- Code: Select all
def i2c(k):
# Transforme un nombre décimal en chaine de caractère
return chr(k + 33)
def c2i(c):
# transforme une chaine de caractère ayant un élèment en valeur décimale
# cette valeur décimale sera comprise entre 32 (a) et 89 (z)
return ord(c) - 33En modifiant à la main la partie droite de la chaîne de caractères, on arrive à modifier très substantiellement le score, à la hausse comme à la baisse. Notre premier 49 est obtenu en bricolant à la main la chaîne de caractère.
C’était assez jouissif il faut dire, en changeant un caractère parmi les 10 derniers, notre score pouvait plonger OU augmenter bien plus vite que tous nos algorithme de tirages aléatoires qui tournaient des nuits complètes... Ce code réponse ne contient que 20 caractères, on connaît déjà les 10 premiers (du moins on le pense) il ne nous reste plus qu’à utiliser la force brute sur les dix derniers caractères.
- Code: Select all
u^KhxO_%#l"""l"""%%%
Out[17] : 49.031613189324844- ATTAQUE N°9 : FORCE BRUTE POUR TRAITER LES CHAINES DE CARACTÈRE DU CODE RÉPONSE
Grace à notre compréhension obtenue avec l’attaque n°08, on a supposé que pour une liste de 10 pokémons, il existe une suite de forces optimales.
On a ainsi écrit un petit script permettant de trouver cette suite optimale.
- Code: Select all
lc = [None,"!","!","!","!","!","!","!","!","!","!"]
carac = '!"#$%&'+"'"+'()*+^;_,-./0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def cons(liste):
# Construit le code
global cc
cc = ""
for j in range(len(liste)):
cc = cc+liste[j]
def turboBoost(pokemons,vitesse=1,style=1):
# Prend une main de pokemon et lui donne des steroides
# la chaine finale sous forme de liste pour modifier les caracteres
lc[0]=pokemons
# les caracteres a tester (tout ce qui est possible)
for l in range(vitesse+3):
# creation du code par test (5x ou 4x pour trouver "l'etat stable" a tout les coups)
# vitesse 1 = rapide, vitesse 2 = lent mais plus sur
for i in range(1,11):
# On initialise tout
global cc
cons(lc)
scores = [0]
for k in range(len(carac)):
# On recense le score pour chaque caractere
lc[i] = carac[k]
cons(lc)
score = setst(cc)
scores.append(score)
# On prend le gagnant, c'est notre partie de cle
lc[i] = carac[scores.index(max(scores))-1]
# on cree le code final
cons(lc)
# style pour la fonction (purement cosmetique)
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)On remarque qu’il est nécessaire d’avoir une liste pour modifier les éléments de la chaîne de caractères un par un à une position donnée.
Rien qu’avec ce script, on a pu augmenter considérablement le score des meilleurs Pokémons issus des attaques précédentes.Avant :
- Code: Select all
u^KhxO_%#l"""l"""%%%
Out[17] : 49.031613189324844
Après :
- Code: Select all
turboBoost("u^KhxO_%#l")
25 %
==========..............................
50 %
====================....................
75 %
==============================..........
100 %
========================================
u^KhxO_%#l"""^""1""" : 49.29025926955508 : u^KhxO_%#l"""d""3"""Cette optimisation du membre de droite nous permettait de faire la même chose pour le membre de gauche.
On a alors écrit une fonction utilisant notre fonction d’optimisation pour tester chaque caractères pour le membre de gauche en optimisant le score à chaque fois pour trouver le code parfait.
- Code: Select all
def chasseAuxPokemons(vitesse=1):
# La vitesse 1 m'a prise 9h mais a bien fonctionnée
lcp = ["!","!","!","!","!","!","!","!","!","!"]
for l in range(vitesse+3):
for i in range(10):
# On initialise tout
global cc
cons(lcp)
scores = [0]
for k in range(len(carac)):
# On cree la liste de Pokemons avec les caractères
lcp[i] = carac[k]
cons(lcp)
# On applique le booster de performances dessus (rapide et sans les barres de %)
turboBoost(cc,1,0)
# On recense les scores
score = setst(cc)
scores.append(score)
# On prend le gagnant, c'est notre nouveau Pokemon
lcp[i] = carac[scores.index(max(scores))-1]Grace à cette fonction, on a pu obtenir le TOP résultat, le fameux 49,31730.
On a donc envoyé des scores légèrement en dessous pour pouvoir nous qualifier dans les premiers.
- Code: Select all
_h#^g0KuOS""""""""7u
49.31730339247606- ATTAQUE N°10 : FORCE BRUTE OUI MAIS ...
Nous avions exclu quelques caractères de cette force brute, on a donc réussi uniquement à obtenir le premier TOP résultat qui était déjà pris, le fameux 49,31730 mais pas au delà. Quand les premiers 49.319 et 49.32 ont commencé à sortir, nous avons compris que nous avions trop traîné, et qu’en intégrant d’autres caractères de la table ASCII nous aurions pu finir premier. Nous pensions que 49,31730 était le résultat optimal, nous n’avons pas testé davantage alors qu’on avait à priori la bonne méthode. Mais notre échec relatif nous à gonflé à bloc pour le défi historique, que nous avons fait en Python cela va de soit et sur PC car la mémoire de la NumWorks à la date d’octobre 2019 ... enfin vous voyez de quoi on veut parler, sinon il suffit de lire ceci : Script qui refuse de s’exécuter sur la Numworks N0100 pour comprendre de quoi il en retourne.- CONCLUSIONS
Nombres de tirages réalisés au total : entre 20 000 000 et 30 000 000 maximum. 3 scripts tournaient au maximum en même temps, sur deux ordinateurs distincts. L’année prochaine, il faudra compter sur nous ! Et cette fois-ci on commencera le défi le jour J et pas en retard. Pavel va devoir ... heu non rien du tout, Pavel est très au dessus du niveau moyen.
Nous remercions les organisateurs des sites TI-Planet et Planète Casio pour ce bon moment, cette recherche était passionnante, nous a réveillé la nuit (histoire de vérifier que les scripts tournaient bien) et maintenant les listes en Python n’ont plus de secret pour nous. Sur un autre sujet, nous supplions l’équipe de NumWorks d’augmenter la mémoire allouée aux scripts Python sur la N0100 et la N0110. Ne pas pouvoir écrire un script de plus de 4Ko est une absurdité !
7ème :
Nous passons maintenant à Tituya, membre de TI-Planet et de Planète Casio avec là encore une équipe dirigée par le couple Abra-Tentacool. Particularité ici, les bidasses ont la compagnie de leur meilleur ami Caninos. Résultat 49,3171 points.Tituya wrote:Malgré ma place relativement petite dans ce concours (tout de même 7ème, c'est honorable
L'ère de la recherche :
Avant de chercher l'automatisation, j'avais rempli à la main le score renvoyé par chaque Pokémon, me permettant donc d'obtenir une base d'équipe assez complète. Malgré le fait que certains Pokémons ne soient 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 !
viewtopic.php?f=49&t=23011&start=250#p248007 https://www.planet-casio.com/Fr/forums/ ... tml#170779Tituya wrote:L'ère 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 Pokémon afin de tester si un Pokémon renvoyait un score que je n'avais pas vu !
(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)). Donc les scripts qui suivent ont été réécrits...
- 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 Pokémon numéro 63 correspond à '_' et le Pokémon 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 Pokémon 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 tout genree, essayé 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 maîtrise en Python ! Et étonnamment, réussir à obtenir une place sans comprendre une ligne du script fourni.
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 !
6ème :
Golden man nous remet le couvert avec la même équipe, avec juste un petit peu plus de puissance pour Tentacool. Ce qui fait toute la différence avec 49,3171 points. 
viewtopic.php?f=49&t=23011&start=250#p248024Golden man wrote: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 bloc par bloc, voire ligne par ligne, 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és en changeant leur position dans 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: 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: 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.
5ème :
Zocipal nous produit une énième version d'équipe dirigée par Abra-Tentacool, en nous saupoudrant leurs sous-fifres d'un Triopikeur qui lui permet bién évidemment de passer la dernière décimale du score précédent au chiffre 3 supérieur : 49,3173 points. 
viewtopic.php?f=49&t=23011&start=240#p247818Zocipal wrote: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 ci-contre le code en entier avec en commentaire les explications.
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. Ça va tester 'canane' puis 'danane' puis 'bbnane'... intelligement puis imaginons 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 mien 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 !
- 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
4ème :
Ne0tuX, membre aussi bien de TI-Planet que de Planète Casio, nous exhibe la même équipe mais avec un Abra un peu plus puissant, au détriment de ses esclaves qui tombent à 1,04% de puissance chacun. Et il a visiblement raison de procéder ainsi, puisque le score monte à 49,3181 points ! Ne0tux wrote: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 Pokémons). 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 Pokémons 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 !
viewtopic.php?f=49&t=23011&start=240#p247864 ou https://www.planet-casio.com/Fr/forums/ ... tml#170778 et suivantsNe0tux wrote:Le code pour générer une population d'individus (i.e. un certain nombre de decks chacun composé de 10 Pokémons) 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 près. 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). Je n'ai pas les moyens dans l'immédiat de 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.
Je prends quelques minutes pour donner plus de détails, que voici plus bas. Le principe de l'algorithme génétique est beaucoup plus simple que ce que l'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 Pokémon une puissance. Par conséquent un individu est modélisable par 10 couples [Numéro de Pokémon, 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 :Quelques remarques :
- 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 Pokémon, 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).
Si tu as une question plus précise n'hésite pas ! Merci à ceux qui détaillent leur méthode, on constate qu'on a tous des façons de faire différentes, c'est chouette !
- 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.
3ème :
Avec redgl0w nous avons les Pokémons communs assaisonnés d'un Caninos et réduits à 1,03% de puissance chacun. Résultat 49,3195 points ! redgl0w wrote:J'ai remarqué que la fonctionsetst()n'était pas utilisé, et j'ai vite compris que elle servait à tester des codes. J'ai aussi remarqué que quand on change à peine le string qu'elle prend,le résultat change très peu. Grâce à cette propriété, j'ai essayé de bruteforce cette fonction, en changeant 3 caractères à chaque fois. Si le score est meilleur que l'ancien, alors je me remet à bruteforce, mais avec le nouveau code généré.
2nd :
M4x1m3 qui a cherché principalement sur NumWorks et accessoirement sur HP Prime nous remet quasiment la même équipe, avec comme simple différence un Triopikeur en queue de peloton, qui lui apporte biené videmment 3 millièmes à maintenant 49,3198 points ! 
M4x1m3 wrote:En gros, ma recherche s'est faite en 4 parties :
- Réflexion
- Bruteforce (intelligent)
- Exploitation d'un 'bug'
- Bruteforce (intelligent) ×2
viewtopic.php?f=49&t=23011&start=240#p247751M4x1m3 wrote: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 (sûrement pour pouvoir valider les résultats de façon consistante et pour éviter de stocker toutes les infos), notamment avec les fonctions 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""""""").
- Code: Select all
from math import *
def mmod(a, b):
return a % b;
def getlinechars(o=False):
c,k=2**31-1,1
if k>=0:
c=[53,o and 99 or 29,o and 509 or 21,31,32,c,c][k]
return c
na = 21;
pokemons_in_team = [];
lnm = ["Bulbizarre","Herbizarre","Florizarre","Salameche","Reptincel","Dracaufeu","Carapuce","Carabaffe","Tortank","Chenipan","Chrysacier","Papilusion","Aspicot","Coconfort","Dardargnan","Roucool","Roucoups","Roucarnage","Rattata","Rattatac","Piafabec","Rapasdepic","Abo","Arbok","Pikachu","Raichu","Sabelette","Sablaireau","Nidoran F","Nidorina","Nidoqueen","Nidoran M","Nidorino","Nidoking","Melofee","Melodelfe","Goupix","Feunard","Rondoudou","Grodoudou","Nosferapti","Nosferalto","Mystherbe","Ortide","Rafflesia","Paras","Parasect","Mimitoss","Aeromite","Taupiqueur","Triopikeur","Miaouss","Persian","Psykokwak","Akwakwak","Ferosinge","Colossinge","Caninos","Arcanin","Ptitard","Tetarte","Tartard","Abra","Kadabra","Alakazam","Machoc","Machopeur","Mackogneur","Chetiflor","Boustiflor","Empiflor","Tentacool","Tentacruel","Racaillou","Gravalanch","Grolem","Ponyta","Galopa","Ramoloss","Flagadoss","Magneti","Magneton","Canarticho","Doduo","Dodrio","Otaria","Lamantine","Tadmorv","Grotadmorv","Kokiyas","Crustabri","Fantominus","Spectrum","Ectoplasma"]
mrandmax = 2147483647;
mrand = 0;
mfmax = 93;
nn = 78;
def mround(f):
d = mmod(abs(f), 1)
return (mfloor(abs(f))+(d>=.5))*(1-2*(f<0))
def mfloor(f):
return round(f)-(round(f)>f)
def mceil(f):
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 f2mf(f):
return mround(float(f * 93))
def mf2f(n):
return float(n / 93)
def mbit(a,b):
return mmod((a//(2**b)),2)
def getattack(pokemon_id,pts):
global pkt
mseed(42)
for k in range(pokemon_id + 1):
mrandom()
a = mrandint(1,mrandmax);
for j in range(na):
if mbit(a,j)!=0:
pkt[j]+=pts
def i2c(k):
return chr(k+33)
def c2i(c):
return ord(c)-33
def clean():
global pokemons_in_team
sum_of_priorities = 0;
s = 0;
# Calcule la somme des priorités.
for current_pokemon in pokemons_in_team:
sum_of_priorities += current_pokemon[1];
for current_pokemon in pokemons_in_team:
#
current_pokemon[2] = f2mf(current_pokemon[1]/(sum_of_priorities or 1))
s += current_pokemon[2]
# Check si on fait du sale.
if(current_pokemon[2] <= 0):
pokemons_in_team.remove(current_pokemon)
return clean()
return s
def pk(pokemon_id, priority = 1, d=2):
global pkt, pokemons_in_team
pokemon_id -= 1 # Obtenir id dans tableau (1-94 transformé en 0-93)
if pokemon_id >= 0 and pokemon_id < len(lnm): # Check si id valide
new = True
for k in range(len(pokemons_in_team)):
if pokemons_in_team[k][0] == pokemon_id: # Check si pokemon déjà rentré
new = False;
pokemons_in_team[k][1] = max(priority, 0);
if new and len(pokemons_in_team) < 10: # Si nouveau et pas d'autre pkm dans l'équipe
pokemons_in_team.append([pokemon_id,max(priority, 0),0]) # Ajout dans l'équipe
ptt = clean();
pkt = [0] * 21;
total_score = 0;
input_string = "";
for current_pokemon in pokemons_in_team:
getattack(current_pokemon[0], current_pokemon[2]/ptt)
input_string = i2c(current_pokemon[0]) + input_string + i2c(current_pokemon[2])
for k in pkt:
if(k):
total_score += log(e+k*len(pokemons_in_team))
return float(total_score), input_string
def setst(input_string):
score = 0;
pokemons_in_team[:] = [];
num_pokemon = len(input_string) // 2;
for k in range(num_pokemon):
score = pk(
c2i(
input_string[num_pokemon - 1 - k]
) + 1,
c2i(
input_string[num_pokemon + k + len(input_string) % 2]
),
k + 1 >= num_pokemon
)
return score
print("pk(n,p) pour rajouter\nle Pokemon n a ta main\navec p points d'attaque.")
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 prend 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éfi 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 [i]final_string; si le score de newstring est supérieur à l'ancien, on recommence, mais avec la nouvelle chaine)[/i].
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.
- Code: Select all
from random import randint;
import original; # original.py est le fichier contenant le code du défi.
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);
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 tenté 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 3è participation est arrivée, 49.31975298152274 (OKSgu_#0h^"A""\x9f""""").
4 - Bruteforce (intelligent) ×2
Je croyais avoir tapé le max avec le 49.31975, mais voyant 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 modifié 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éfi :
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 sûr, mais je pense que 49.32 est un maximum qui ne peut être dépassé). Vivement l'année prochaine
1er :
Enfin Pavel, sévissant sur TI-Planet et sur Planète Casio, a cherché entre autres à la fois sur Casio Graph 90+E et HP Prime pour nous apporter la touche finale. Même équipe, mais en réduisant les Pokémons annexes à seulement 1,02% de puissance chacun, il donne la toute puissance à Abra, pour un zénith de 49,3208 points ! 
Pavel wrote:Merci pour l'explication de ta méthode M4x1m3 !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.
- Code: Select all
from math import *
from random import *
from time import *
def mmod(a,b):
return a%b
def getplatform():
return 1
def getlinechars(o=False):
c,k=2**31-1,getplatform()
if k>=0:
c=[53,o and 99 or 29,o and 509 or 21,31,32,c,c][k]
return c
na,pkl,lnm=21,[],["Bulbizarre","Herbizarre","Florizarre","Salameche","Reptincel","Dracaufeu","Carapuce","Carabaffe","Tortank","Chenipan","Chrysacier","Papilusion","Aspicot","Coconfort","Dardargnan","Roucool","Roucoups","Roucarnage","Rattata","Rattatac","Piafabec","Rapasdepic","Abo","Arbok","Pikachu","Raichu","Sabelette","Sablaireau","Nidoran F","Nidorina","Nidoqueen","Nidoran M","Nidorino","Nidoking","Melofee","Melodelfe","Goupix","Feunard","Rondoudou","Grodoudou","Nosferapti","Nosferalto","Mystherbe","Ortide","Rafflesia","Paras","Parasect","Mimitoss","Aeromite","Taupiqueur","Triopikeur","Miaouss","Persian","Psykokwak","Akwakwak","Ferosinge","Colossinge","Caninos","Arcanin","Ptitard","Tetarte","Tartard","Abra","Kadabra","Alakazam","Machoc","Machopeur","Mackogneur","Chetiflor","Boustiflor","Empiflor","Tentacool","Tentacruel","Racaillou","Gravalanch","Grolem","Ponyta","Galopa","Ramoloss","Flagadoss","Magneti","Magneton","Canarticho","Doduo","Dodrio","Otaria","Lamantine","Tadmorv","Grotadmorv","Kokiyas","Crustabri","Fantominus","Spectrum","Ectoplasma"]
mrandmax,mrand,mfmax,nn,mp=2**31-1,0,93,getlinechars(True)-na,na//2
def mround(f):
d=mmod(abs(f),1)
return (mfloor(abs(f))+(d>=.5))*(1-2*(f<0))
def mfloor(f):
return round(f)-(round(f)>f)
def mceil(f):
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 f2mf(f):
return mround(float(f*mfmax))
def mf2f(n):
return float(n/mfmax)
def mbit(a,b):
return mmod((a//(2**b)),2)
def getattack(p,pts):
global pkt
mseed(42)
for k in range(p+1):
mrandom()
a,pka=mrandint(1,mrandmax),""
for j in range(na):
if mbit(a,j)!=0:
pka+="X"
pkt[j]+=pts
else:
pka+=" -"[getplatform()>=5]
return pka
def i2c(k):
return chr(k+33)
def c2i(c):
return ord(c)-33
def clean():
global pkl
t,s=0,0
for l in pkl:
t+=l[1]
for l in pkl:
l[2]=f2mf(l[1]/(t or 1))
s+=l[2]
if(l[2]<=0):
pkl.remove(l)
return clean()
return s
def pk(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)
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\nenvoie code suivant\na info@tiplanet.org :")
print(""+st)
return float(t)
def setst(st):
s,pkl[:],n=0,[],len(st)//2
for k in range(n):
s=pk(c2i(st[n-1-k])+1,c2i(st[n+k+len(st)%2]),False)
return s
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
def random_pokemon(code):
n = randint(0, 9)
v = randint(0, 93)
if not v in code[:10]:
code[n] = v
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
seed(time())
code = [0 for k in range(20)]
code[19] = 93
score = fast_score(code)
code_max = code.copy()
score_max = score
# find team using simulated annealing
t = 1.0
while t > 0.0001:
t *= 0.999
code_next = code.copy()
random_pokemon(code_next)
random_attack(code_next)
score_next = fast_score(code_next)
if score_max < score_next:
code_max[:] = code_next
score_max = score_next
print('%.5f' % score_max, ''.join([chr(code_max[k] + 33) for k in range(20)]))
delta = score_next - score;
if delta >= 0 or random() < exp(delta / t):
code[:] = code_next
score = score_next
# find attack points using brute force
code_max = ''.join([chr(code_max[k] + 33) for k in range(20)])
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)
viewtopic.php?f=49&t=23011&start=240#p247755 ou https://www.planet-casio.com/Fr/forums/ ... tml#170510 et suivantsPavel 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.
- 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.- 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.
- 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- 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- 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- 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)
Merci à tous pour votre enthousiasme, vos messages sympa, vos explications exhaustives et participations méticuleusement construites !
14 lots sont prévus pour vous récompenser, et nous allons maintenant pouvoir procéder à leur choix en commentaires. @Pavel, à toi l'honneur.
Référence : https://www.planet-casio.com/Fr/forums/ ... 981&page=1
Crédits images : Pokémons
Bien joué à tous !
