Zezombye wrote:Premièrement j'aimerais dire que cette épreuve a été ma préférée, notamment car il était possible de la résoudre "à la main" sans nécessairement faire d'algorithmes compliqués ou même de programmer tout court (cf shadow qui a eu presque 9000 sur la calto).
J'avais testé vite fait la 3ème épreuve et... je n'avais rien compris aux commandes : j'allais à droite, ça allait à droite puis à gauche, et puis ça sortait de l'écran. De ce que les autres candidats disaient, il fallait contrôler une spirale, mais la trajectoire n'avait pas grand chose à voir avec une spirale.
Du coup j'ai ouvert le programme (casio) dans BIDE et j'ai commencé à l'étudier un peu. Il y a tout d'abord plusieurs variables :
- p et w, qui sont des constantes utilisées pour le PRNG (générateur aléatoire)
- a, seed du PRNG (c'est pas 42 là, bizarre)
Ces variables sont utilisées pour le PRNG qui est la fonction y9(), avec l'expression "y9(a) -> a".
La représentation de la fonction y9 est en "hachures" (/////////) ce qui confirme que c'est un PRNG.
Il y a ensuite les variables pour la spirale et les points :
- z, position actuelle
- t, position juste avant
- s, score
- v, modifieur de l'argument de z
- f, multiplicateur utilisé pour l'affichage uniquement
- b = 0.085, rayon de chaque point
- n = 9, nombre de points
Et quelques listes :
- list4 : positions de chaque point (en coordonnées polaires)
- list6 : liste de toutes les itérations de v
Hé oui : on fonctionne ici sur des coordonnées polaires (ce qui explique le déplacement en cercle/spirale dans le sens trigonométrique).
À chaque itération (appui sur une des flèches) :
- a devient l'itération suivante du PRNG (y9(a) -> a)
- L'argument de z (valeur réelle) augmente ou diminue de v
- L'angle de z (valeur imaginaire) est calculée par une formule qui dépend notamment de a (et est donc aléatoire).
Quant au calcul du score :
- À chaque itération, on enlève 500 * distance parcourue (déterminée avec des calculs chelous avec des e^i, mais c'est juste un calcul de distance entre z et t)
- Lorsqu'on atteint un point, on gagne 1500, mais avec 2 pénalités : pénalité de distance au centre (-500*distance) et pénalité d'argument (-500*différence d'argument) : la valeur réelle de z doit être le plus proche possible de l'argument du point. (chaque pénalité a une valeur maximum de 500, mais ça sert un peu à rien vu que si on a 500 de pénalité on risque pas d'être dans les premiers :E)
Par une coincidence mathématique, lorsqu'on se dirige vers le centre du point, la pénalité d'argument diminue ; pas besoin donc de faire attention à la respecter, il suffit de viser le centre.
Le problème pour obtenir le meilleur score, c'est qu'une fois rentré dans le point, on gagne les 1500 (moins les pénalités), et bien sûr on ne peut pas gagner 2 fois la récompense d'un même point. Il faut donc que l'itération (qui dépend de a, donc de l'aléatoire) place z le plus proche possible du centre, ce qui n'est pas toujours possible...
Voici pour le fonctionnement, maintenant ma méthode :
Comme la trajectoire était assez imprévisible, j'ai fait une simulation en java pour notamment prédire les trajectoires.
4h plus tard, la simulation était presque prête, mais il y avait quelques erreurs de trajectoire : un score sur ma simulation différait du programme par 4 points. Je ne me suis pas laissé avoir par la pensée que c'était une erreur de précision : je sais depuis galactik que les erreurs de précision, c'est de l'ordre du millionième, et ce n'était pas la cause de la différence de 4 points.
Je regarde attentivement le code (c'était juste une retranscription de celui de casio), et l'erreur venait de la ligne transcrite "`Z + V + i(.04 + A / W) / (9Abs ReP Z + 1) -> Z`", que j'avais séparée en 2 parties :
- Code: Select all
z.re = z.re+v;
z.im = z.im+(0.04+a/w)/(9*Math.abs(z.re)+1);
Mais comme le calcul de la partie imaginaire prenait en compte la partie réelle, et que je calculais la partie réelle avant l'imaginaire, ça causait des petites erreurs (le z.re étant déjà à l'itération suivante). La solution est simple : calculer la partie imaginaire avant la partie réelle.
La simulation étant maintenant parfaite (une liste donne le même score sur la simulation et sur la calto), il ne restait qu'à l'améliorer.
Tout d'abord, la calto limite les possibilités : l'appui sur les flèches droite/gauche fait une itération, et il n'est pas possible d'augmenter ou diminuer v de plus que 0.01.
De ce fait, j'ai modifié le code pour qu'une itération ne se fasse que lorsqu'on appuie sur la flèche haute ; ainsi on peut modifier la valeur de v à sa guise. J'ai également mis comme incrément une puissance de 2 (0.0078125/4), pour éviter les pertes de précision dues au floating-point.
Mon "prédicteur", qui traçait le chemin suivi pour un v donné, prédisait au départ également le chemin suivi pour v +/- incrément, mais j'ai enlevé ça suite à la modification du code permettant de modifier v comme on veut. Il prédisait aussi les 200 prochaines itérations, mais ce n'était pas très utile étant donné que, pour faire une ligne droite, on était obligé de changer v à chaque fois. La version finale du prédicteur prédit donc l'emplacement de z (en rouge) et la direction prise (en vert), pour mieux l'aligner sur le centre du point visé.
Maintenant, quel chemin prendre ? On pourrait croire que c'est tout simplement un problème du voyageur, où il faut trouver le chemin le plus court entre tous les points. Mais un problème de taille se pose : il est absolument impossible d'aller en contresens du cercle trigonométrique sans repasser par le centre (qui fait perdre assez beaucoup de points). On ne peut pas aller de 4 vers 9, par exemple. Du coup mon bruteforce du problème du voyageur avait juste trouvé une solution impossible.
Pas grave, il suffit de faire manuellement : un petit script python avec la matrice des coûts (générée avec 500*distance entre les points), et une fonction chemin(j,k,l,m,n,o,p,q) qui calcule les coûts, et il est possible de trouver le chemin le plus court en faisant des essais manuels. Il faut prendre ce résultat avec des pincettes car il ne prend pas en compte les rayons (le coût étant moins grand si on vise le bord des points) mais c'est un bon outil de comparaison.
- Code: Select all
mat = [[0.0, 639.8758650193196, 71.10442060204466, 423.95186425858145, 331.14380293171877, 161.45686697021324, 373.03170861562603, 261.0731151968173, 586.4373544809774], [639.8758650193196, 0.0, 709.368357885116, 462.70974506153203, 382.82839628019946, 725.8710101543168, 941.7930688633227, 645.1635101630433, 1027.648437944569], [71.10442060204466, 709.368357885116, 0.0, 464.44722453447923, 400.08940513293805, 160.6728290075972, 340.4323542215803, 296.6436795055611, 546.9575199959714], [423.95186425858145, 462.70974506153203, 464.44722453447923, 0.0, 464.176892264874, 579.9797778530555, 796.9239745409624, 614.0147428390028, 577.5250505787424], [331.14380293171877, 382.82839628019946, 400.08940513293805, 464.176892264874, 0.0, 362.74137436674374, 565.403951395421, 262.4540702256918, 872.1724054160846], [161.45686697021324, 725.8710101543168, 160.6728290075972, 579.9797778530555, 362.74137436674374, 0.0, 226.3899318570202, 163.5532072741689, 701.1504907088186], [373.03170861562603, 941.7930688633227, 340.4323542215803, 796.9239745409624, 565.403951395421, 226.3899318570202, 0.0, 312.42883353647136, 800.2366772401842], [261.0731151968173, 645.1635101630433, 296.6436795055611, 614.0147428390028, 262.4540702256918, 163.5532072741689, 312.42883353647136, 0.0, 842.72080016074], [586.4373544809774, 1027.648437944569, 546.9575199959714, 577.5250505787424, 872.1724054160846, 701.1504907088186, 800.2366772401842, 842.72080016074, 0.0]]
def chemin(j,k,l,m,n,o,p,q):
j-=1
k-=1
l-=1
m-=1
n-=1
o-=1
p-=1
q-=1
print(mat[0][j]+mat[j][k] + mat[k][l] + mat[l][m] + mat[m][n] + mat[n][o] + mat[o][p] + mat[p][q])
Avec le script python, on trouve que le meilleur chemin est 3->9->4->2->5->8->6->7. En faisant ce chemin manuellement, à l'aide du prédicteur, j'ai un score de 9213. Pas mal, mais très loin de 10 444, et un peu loin du 2ème qui était à 9303. Je me dis que le 1er doit avoir une technique secrète, car c'était impossible de gagner plus de 1000 points uniquement avec de l'optimisation de chemin, il y avait un autre chemin que le mien. Mais je n'arrivais pas à voir lequel.
En faisant mon algorithme pour tracer des droites parfaites, je suis nonchalamment resté appuyé sur la flèche haute, pour regarder le tracé de la spirale. Je faisais ça à partir de ma liste de 9213 (j'avais donc déjà les 8 points), puis la spirale passe par le centre, et puis... plus rien. Ma simulation ne répondait plus. Je pensais initialement que c'était à cause d'une division par 0 ou quelque chose d'autre, mais la console affichait "score increased by 1500". J'ai su alors comment arriver au club des 10 000 : il suffisait de repasser par le centre après être passé par les 8 points.
En rétrospective, j'aurais dû le voir : la boucle principale avait une condition de sortie de list4[1] > n, lorsque j'ai recopié le code je me disais que le programme s'arrêtait lorsqu'on était passé par les 8 points, mais quand je suis passé par les 8 points le programme ne s'était pas arrêté... (et je me suis même dit que c'était bizarre car il n'y avait que 8 points donc la condition n'était pas remplissable)
Du coup, retour sur mon script python pour choisir un chemin se terminant par 1, et je trouve que le meilleur chemin est 3->9->4->2->5->8->7->6->1, suivi de près par 3->9->4->2->5->8->6->7->1.
Une coincidence, ou un choix machiavélique de Critor (car les positions des points sont générées aléatoirement) mais il est quasiment impossible de passer de 7 à 6 : il faut s'arrêter pile sur le bord de 7, puis avoir un segment suffisamment petit (la longueur étant déterminée par l'aléatoire) pour passer au ras du 6 sans le dépasser. C'est donc totalement dépendant de l'aléatoire, et coincidence de plus, la seed par défaut donnait un segment assez petit pour faire le 7->6. J'ai alors un score de 10392. On voit par exemple ci-contre que j'effleure le 6, mais je ne peux pas le toucher parce que je ne suis pas bien positionné.
Car oui, il était possible d'influencer l'aléatoire : en itérant alors qu'on était toujours au centre, seule la valeur de l'angle changeait (avec des 0 ajoutés à la liste pour chaque itération). Il suffisait donc de choisir un nombre d'itérations qui donne un angle de départ proche de 0 (pour aller directement sur 3), et l'aléatoire était changé. Un petit bout de code plus tard, et j'obtiens la liste suivante :
- Code: Select all
ArrayList<Integer> listeIter = new ArrayList<Integer>();
double j = 0;
for (int i = 0; i < 100000; i++) {
a = y9(a);
j += (0.04+a/w);
if (j%(2*Math.PI) < 0.001 || j%(2*Math.PI) > (2*Math.PI-0.001) ) {
System.out.println("angle de "+j%(2*Math.PI)+" pour "+i+" iterations");
listeIter.add(i);
//System.out.println(sb.toString());
}
}
System.out.println(listeIter.toString());
System.exit(0);
[683, 6611, 7308, 10065, 11146, 16614, 24882, 31202, 33105, 39926, 55024, 56161, 57800, 61276, 62248, 62356, 67729, 85818, 87519, 91454, 97464]
J'ai testé manuellement et j'obtiens un 7->6 possible pour 31202 itérations initiales, avec un score de 10394... mais malheureusement, la nSpire ne supportant pas une liste de 31000 nombres, ma participation est invalide. :E
J'agrandis la tolérance d'angle en me limitant cette fois à 10000, et je fais un algorithme qui trace automatiquement le chemin le plus droit possible en passant par les points donnés :
- Code: Select all
int[] listeIter = {506, 683, 730, 911, 924, 1052, 1277, 1348, 1373, 2175, 2198, 3168, 3211, 3462, 3734, 3980, 4869, 5533, 5558, 5974, 6567, 6611, 7308, 7427, 7805, 8748, 8869, 9413, 9795, 9805};
for (int i = 0; i < listeIter.length; i++) {
nbIterations = listeIter[i];
init();
if (auto()) {
System.out.println("score final = "+s);
System.out.println(nbIterations + "x{0} + "+list6.toString().replaceAll("\\[", "{").replaceAll("\\]", "}"));
}
}
Mais la valeur d'argument variant beaucoup de 3 vers 9, faire une ligne droite vers 9 est impossible car cela résulte en des segments très longs... je modifie alors mon algorithme pour que, lorsque la ligne droite est impossible, il aille vers le bord du point. Mais ça ne suffit pas toujours à passer le 3->9, et dans tous les cas testés l'algorithme n'arrive pas à passer le 7->6. Il faut un facteur humain.
(la vidéo a une assez mauvaise qualité, mais bon ça vous donne une idée de l'algo)
https://i.imgur.com/SvZTDLk.mp4Je fais donc un prédicteur amélioré en me basant sur l'algorithme : il règle la valeur de v de telle sorte à se diriger vers le centre du point visé (c'est en fait mon algorithme, mais qui n'agit pas automatiquement). Mais me diriger vers le bord du 9 rend le chemin trop court, et je ne peux pas faire le 7->6 car le segment est trop long. Je place donc mon chemin au même endroit du 9 (à peu près à la moitié du rayon), j'arrive à faire le 7->6, mais... je ne gagne que 0.5 points. Les lignes droites n'auront pas vraiment amélioré mon score.
Comprenant que pour atteindre les 10444 il me fallait un algorithme chelou, et que je ne savais pas faire de tel algorithme, je suis parti jouer à overwatch. :E
(le code utilisé est ici :
https://pastebin.com/Xw4BiRvu)
by 
Dans un article précédent nous t'avons présenté le TI-Python, module externe permettant l'exécution de scripts Python sur ta TI-83 Premium CE, et t'avions annoncé la présence du module math. Par la suite, nous avions exploré son module builtins.>>> from explmod import *
.islower()=<bound_method>
.rstrip()=<bound_method>
isfinite()=<function>
pi=3.14159
Les optimisation m'on fait gagner presque 200 points mais je reste loin derrière avec mon 8900... 
