Forums Casio - Actualités

Index du Forum > Actualités > Résultats du triconcours : les plus courageux !
Lephenixnoir
Hors ligne
Administrateur
Points: 13203
Défis: 136
Message
Posté le 28/11/2018 21:37

Résultats du triconcours : les plus courageux ! :

Ce soir nous clôturons le triconcours de rentrée 2018 avec les résultats de la troisième épreuve, l'épreuve de courage !

Vous avez été 17 à résoudre une variante du problème du voyageur de commerce aux airs de Dragon Ball masqué en Zelda. Le défi consistait à piloter le nuage Kinto-un en coordonnées polaires pour récoler les fragments perdus de la Triforce de Courage en un temps minimal, soit manuellement, soit en programmant une liste.

Vous avez été nombreux à partager vos méthodes pour, merci beaucoup ! Voyons ensemble ce que vous avez imaginé.

Sujet cousin sur TI-Planet : Triconcours de rentrée 2018 - résultats défi de Courage

Le classement des participants

16. Gam occupe la 16ème place de ce classement en récoltant 4 fragments sur sa TI-83 Premium CE, pour un total de 3842 points.


15. Hackcell, quant à elle, pourchasse 6 fragments et se hisse à 3885 points, sans détours.


Les gagnants : les plus courageux !

Bravo à tous ! Découvrons ensemble les méthodes que vous avec mises en oeuvre.

14. La 14ème place de notre classement revient à Nicodu95 qui a exploité des approximations manuelles sur l'émulateur HP Prime. pour atteindre 4556 points.


J'ai utilisé l'émulateur HP Prime. Armé de mon clavier et des flèches et après une bonne dose d'essais (et de re-essais), j'ai obtenu un score de 2800. J'ai ensuite tenté de comprendre un peu le fonctionnement de la "spirale", je suis arrivé à 4200 points. Puis j'ai copié la liste kinto pour pouvoir la modifier (et la sauvegarder), j'y ai rajouté quelques lignes de nombres avec un peu de raisonnement, 4555 points. Mais il m'a fallu surtout de la persévérance (et du temps).

13. Le candidat suivant est Disperseur, qui impose une marge fulgurante sur ces prédécesseurs en récoltant tous les fragments en deux temps, une Graph 35+E et 7721 points !

voila la petite explication de la maniere dont j'ai realise mon score (aussi petit soit-il):

Avant tout, sachez que j'ai cherché la solution vers le debut de l'epreuve. Le dernier envoi que j-ai effectué s'est fait la fin de la troisième ou quatrième semaine.

Au debut j'ai été un peut au hasard dans la liste 6. Puis j'ai fait une capture de l'ecran avec seulement les 8 pts et je l'ai imprimée en plusieurs exemplaires pour tester au crayon les chemins possibles. Puis au fur et à mesure que j'essayait des chemins je suis tombé sur une bonne methode (apres avoir fait un tas de tests pour comprendre comment le nuage se déplaçait aussi) qui consiste à tourner en mettant des "0" dans la liste 6 (ce qui ne me fait pas perdre de pts, eh oui )pour "viser" les pts et aller les chercher avec une grande valeur type "1" et en revenant à chaque fois en "0". Les trois derniers points, je les ais attrapés en tournant. C'est cette solution qui s'est avérée être la meilleure que j'etais capable de fournir.
Voila !

12. Alexot, toujours sur Graph 35+E, dépasse ce score en utilisant un arrangement complètement différent de l'ordre de parcours, cumulant 7746 points - laquelle de ces deux solutions aux voyageur de commerce est la meilleure ?


La méthode que j'ai utilisé pour obtenir mon score est assez simple : j'ai essayé de comprendre comment fonctionnait le programme en expérimentant dans l'option "Manuel". J'en ai déduit une interprétation de ce qu'il se passait quand on appuyais sur les différentes touches: le point qu'on contrôle fonctionne un peu comme une fusée attirée par une sorte de gravité vers le centre de l'écran, et pouvant se propulser vers l'avant(par "vers l'avant", je veux dire vers la direction dans laquelle elle va déjà). Appuyer sur gauche baisse l'intensité des propulseurs, droite augmente cette intensité, et appuyer sur gauche, droite, ou haut fait avancer plus ou moins la fusée selon l'intensité des propulseurs, et attire un peu la fusée vers le centre. En regardant la liste 6 générée, les nombres contenus dans celle-ci pourraient correspondre à l'intensité des propulseurs. Même si je doute que le programme fonctionne comme ça, et que c'est pas très rigoureux, en ayant en tête ce fonctionnement, on peut plus ou moins arriver à contrôler kinto1.
Puis j'ai un peu tatonné pour essayer d'ajuster ma trajectoire et d'atteindre tous les fragments.

11. Plus courageux encore, et toujours sur Graph 35+E, Massena grille la 11ème place avec ses 7794 points. Quel est son secret ?

Pareil que Shadow.

Je pense connaître enfin ce que c'est le karma. Le 4 Novembre, j'ai voulu ninja ma participation à 8500 pts. Juste pour créer un effet de surprise x) Mais je m'aperçois le lendemain que mon mail est envoyé à... Moi même. Seum.

10. eried termine 10ème sur l'émulateur HP Prime, avec un score de 8443 points. Il en parle sur son blog :


The description talks about our hero
in a cloud having to visit spots in a map keeping the score as maximum possible. At first, it was difficult to understand, but you basically have a polar function that you modify with parameters and you have to go between specific points while completing the route.

I started analyzing the positions of the layout with a Travelling Sales man Problem solver.


But, then you have to restrict your solution to what is possible. Playing the game goes like this:

1. Open the app
2. Press Symb and enter a list
3. See the updated map and score
4. Press Symb again and modify the list
5. Go to step 3

Some of the steps are quite slow, using the Calculator editor for lists is a pain, the brackets try to be smart, you have to copy the old list and change the ending of it to try different outcomes, etc.

So what was my solution this time?

A modified version of PrimeMon that also executed the code after you saved it in the HP Connectivity Kit. So you could have the list you were trying to edit and every time you hit Save, the HP Prime Virtual Calculator displayed the results instantly.

PrimeMon is a little tool that I wrote years ago, after PrimeComm (a much more complete toolset for the HP Prime) stopped working, that allows you to interface with the Virtual Prime for checking if you have syntax errors easily. This just exists because the HP Connectivity Kit editor is very primitive and does not check anything.

Using this little tool I was able to have a pleasant puzzle-like experience while watching a movie.



My score was again really poor, #10. But again, I had a lot of fun!

If I had to do it again, I would have coded a small routine to solve it in the calculator itself. That new modified app would wait for a screen tap and try to add elements (i.e. testing a range from -10 to 10) to the list keeping the distance as the minimum possible and stopping when is in radius of the tapped point.

9.À la 9ème position trône Jean B., utilisateur de TI-83 Premium CE et surtout d'un bug très habile qui permet de se téléporter en insérant des nombres complexes dans la liste. L'astuce n'a pas pu être acceptée, et il s'est rabattu sur une solution conventionnelle à 8793 points.


A force de petits tests manuels en modifiant KINTO, j'ai remarqué, entre autres, que le tracé forme globalement une spirale allant dans le sens inverse de celui des aiguilles d'une montre. De là on peut en déduire le chemin optimal, alors que cela paraît contre-intuitif au début : comme vous le voyez sur l'image de ma participation, il faut faire un grand trait au début faisant beaucoup diminuer le score.

8. La tête dans les nuages, Astrostellar survole avec sa TI-83 Premium CE la 8ème place par 8804 points.


J'avais tout d'abord compris qu'entre chaque valeur de ma liste, je n'avais le droit que de rajouter ± 0.01, ou alors de ne pas changer sa valeur... J'ai donc envoyé une première participation avec cette contrainte à 6614 points.
Après avoir compris que je pouvais mettre les valeurs que je souhaitais, j'ai repris ma candidature en faisant passer mon chemin par un point qui me faisait avant faire un grand détour. J'ai envoyé cette participation et j'ai eu 7718 points.
Puis j'ai re-réfléchi en cherchant le chemin le plus court permettant de relier les points dans le sens inverse des aiguilles d'une montre. J'ai trouvé le chemin qu'on suivi une grande partie des autres participants. J'ai donc envoyé une dernière participation en suivant ce chemin à 8804.3258 points.
Je me doutais qu'il y avait un "truc" pour gagner encore plus de points, vu la différence entre les 4 premiers participants et les autres, mais je n'ai pas trouvé ce que c'était (en regardant à l'intérieur du programme et en voyant des e^i, j'ai pris peur et n'ai pas compris le système de points ).
Les valeurs que j'ai mises dans ma liste, je les ai trouvées en tâtonnant : je rajoutais une dizaine de valeurs, je regardais ce que ça traçait, je modifiais ensuite certaines valeurs et je passais aux valeurs suivantes...

7. Retour sur Graph 35+E où Shadow15510 a mis au jour la méthode de téléportation à base de nombres complexes (la liste ici).

rectifie, je suis arrivé à 9500 mais aujourd'hui à 10h30...
Pour moi ma technique est je pense la plus longue et la moins rentable : tu entres un nombre tu regarde ce qu'il se passe... tu entre un autre nombres tu vois comment ça bouge et avec ça tu essaye de relier les 8 points sans histoire en optimisant les approches pour taper au coeur des ronds avec une précision au centième... Les optimisation m'on fait gagner presque 200 points mais je reste loin derrière avec mon 8900...

6. Ne0tux obtient la 6ème place et le prix de l'algorithme le plus hasardeux, en réutilisant son programme du défi précédent avant de tester sur Graph 35+E. Il atteint ainsi 9133 points !


Ce coup-ci je n'ai pas fait dans la finesse : j'ai repris l'algorithme génétique du défi force, remplacé la partie "problème" par celle des Dragon Balls et laissé tourné ce soir. Théoriquement ça ne devait pas du tout fonctionner puisque ce n'est vraiment pas du tout adapté comme technique (Nombre de gènes inconnu, le "croisement" n'a aucun sens, un individu peut-être meilleur si on lui enlève des gènes etc...). Mais comme c'est une méthode stochastique et que j'avais un trèfle à quatre feuilles sous le coude, à presque minuit j'avais dépassé les 9000 pts.

C'était un super défi encore, j'ai hâte d'avoir les explications de chacun. Merci à tous, organisateurs et participants !

Je joins à nouveau mon code commenté, si quelqu'un a des remarques, qu'il n'hésite pas ! En particulier, j’aimerais comprendre comment j'ai réussi à trouver un bon score alors que sur le papier ça ne devait pas fonctionner (juste de la chance ?)

Fichier joint : DB2.py

5. Le japonais Sentaro21 arrache la 5ème place en survolant le problème de 9431 points sur sa Graph 90+E. Comment a-t-il obtenu cette courbe élégante ?


I did not completely understand the rule.

I noticed 1500 points of the bonus by chance.
I understood that 1500*9=13500 points is maximam and the point given up is proportional to the length of the course.
I made trial and error to be able to link each cloud in the shortest.

However I thought that the movement every step had only 0 or +/-0.01.
I only made trial and error.
So,
I'm sorry. I did not have any high solving method.


BIDE is very convenient to watch a basic program.
Thanks very much.

4. Et c'est Ruadh, équipé d'une TI-83 Premier CE, qui fracasse le premier le plafond symbolique des 10000 en tablant un score de 10317 points.


Ma méthode a été assez simple, j'ai utilisé un bruteforce pour relier les centres de chaque cercle entre eux dans le sens trigonométrique en un nombre d'étapes que je faisais varier de manière à trouver le chemin qui minimisait la distance parcourue. Cette méthode ne donne pas de solution optimale, les participants classés devant moi ayant trouvé une trajectoire que je n'aurais pas pu trouver avec cette méthode, de plus, il y a certains cas où on entre dans le cercle avant de pouvoir atteindre le centre, ce qui n'attribue pas le maximum de points, mais le score final est tout de même assez satisfaisant.

3. Zezombye continue de faire grimper le compteur, jusqu'à 10392 points. Mention spéciale pour avoir envoyé une liste à 30000 éléments, bien trop pour les calculatrices du concours !


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 )
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 :
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.

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-dessous 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 :

        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.

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 :

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.mp4

Je 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.

(le code utilisé est ici : https://pastebin.com/Xw4BiRvu)

2. Le retour de Stefan Bauwens se produit à la seconde place, pour un total astronomique de 10400 points sur TI-Nspire. Mais comment a-t-il obtenu cette courbe si parfaite ?


Je vais faire de mon mieux pour expliquer comment j’ai obtenu mon score.
J'ai d'abord téléchargé le programme sur ma TI-83 +, mais j'ai vite compris c'était trop lent si je voulais vraiment faire une bonne tentative. Donc, j'ai téléchargé la version de TI-Nspire et je l'ai exécutée sur l'émulateur. C'était beaucoup plus rapide, en plus, c'était plus “pixel perfect”

J'ai joué avec les commandes et me suis rendu compte qu'il y avait un mouvement de fibonacci / circulaire en cours. Ma première tentative a été d'essayer de suivre "le flux naturel" et de collecter toutes les boules (de dragon). Chaque fois que j'en réussissais un, je copiais la liste kinto dans un fichier texte et je partais de là.
Cela s'est bien passé, mais il restait encore un long chemin à parcourir. J'ai ensuite essayé de modifier la liste manuellement avec des valeurs et de voir comment elle réagirait. Et effectivement, il y avait une certaine logique là-bas. Les valeurs plus petites produisent des mouvements plus courts et la valeur définit également la direction de l'angle. La modification manuelle de ces valeurs à l’aide d’essais et erreurs me permettrait très "facilement" d’obtenir des lignes relativement droites. J'ai aussi remarqué que toucher le centre de la balle donnait plus de points. À l'aide d'un papier et d'un stylo, j'ai recherché le chemin le plus court entre les balles (sans prendre en compte le dernier, car je ne l'avais pas encore découvert). J'ai modifié la liste pour suivre ce chemin de près. Cette méthode a très bien fonctionné et mon chemin a été assez efficace, mais en regardant le classement, je savais qu'il devait y avoir quelque chose de radicalement différent qui me manquait. Mon frère Jim a jeté un coup d'œil au code source et nous avons effectivement découvert une autre balle finale au centre après avoir traversé la 8e balle.
En continuant sur le chemin que j'avais déjà, j'ai obtenu un score autour de 10348. Pas mal, mais j'en voulais plus.
Jim a créé un petit programme d'amour pour dessiner plus rapidement un chemin au lieu de modifier manuellement la liste. (J'étais trop paresseux pour programmer moi-même: P) Alors j'ai joué avec et j'ai ensuite découvert que je pouvais obtenir un meilleur score en modifiant la séquence des 3 dernières balles. J'ai eu un score autour de 10370. Jim a également créé un petit programme pour itérer sur les valeurs de la liste et les modifier légèrement pour essayer d’améliorer la valeur finale. C’est ainsi que j’ai obtenu mon score final.

Merci pour ce défi amusant!

1. C'est de nouveau Pavel qui remporte le défi, trônant sur son extraordinaire nuage de 10444 points !


Après m'être beaucoup amusé avec le mode interactif de ce simulateur de nuage magique sur ma Casio Graph 90+E, j'ai essayé de comprendre le code derrière ce jeu et j'ai trouvé que pour moi c'est beaucoup plus facile avec le code en Python pour la calculatrice NumWorks.

En analysant le code, j'ai remarqué les points suivants:
- un système de coordonnées polaires est utilisé pour le calcul de la position du nuage magique
- on ne contrôle que la coordonnée radiale
- la coordonnée angulaire est augmentée à chaque déplacement
- la vitesse angulaire a une composante aléatoire

Autrement dit, on pilote un nuage magique dans un cyclone.

Le calcul du score est assez simple:
- on gagne jusqu'à 1500 points pour chaque fragment trouvé
- il faut bien viser le centre des fragments pour maximiser les points
- on paie 500 points par unité de distance parcourue

Pour réaliser le meilleur score, j'ai découpé le problème en sous-problèmes suivants:
- trouver un plus court chemin qui visite chaque fragment et qui se termine au point de départ
- manoeuvrer le nuage magique en essayant de suivre ce chemin

Le premier sous-problème est le problème bien connu du voyageur de commerce.

En cherchant "salesman python" sur google, j'ai trouvé ce petit programme de dix lignes.

J'ai juste ajouté à ce programme les calculs des coordonnées des fragments. Voici le code et le chemin que j'ai obtenu:



La longueur de ce chemin est approximativement 6. On peut estimer que le score maximal devrait se situer quelque part autour de 10500 (9 * 1500 - 6 * 500).

Pour résoudre le deuxième sous-problème (manoeuvrer le nuage magique en essayant de suivre ce chemin), je l'ai aussi découpé en sous-sous-problèmes:
- trouver des instructions pour diriger le nouage magique d'un fragment au suivant
- optimiser ces instructions en utilisant une méthode d'optimisation stochastique
- répéter les deux étapes précédentes jusqu'à revenir au point de départ

Pour chaque déplacement entre deux fragments A et B, j'analyse les valeurs des instructions variant entre -1 et 1 et je choisis celle qui minimise l'angle entre la ligne AB et la ligne AN, ou N est la position du nuage magique:



S'il est possible d'atteindre un fragment après K ou K+1 instructions, je choisis les instructions qui maximisent le score.

Pour optimiser les instructions, je varie légèrement les valeurs une par une et je choisis les valeurs maximisant le score. Pour sortir d'un maximum local, j'applique une petite variation aléatoire aux plusieurs valeurs.

Cet algorithme fonctionne bien pour les 7 premiers fragments et il trouve automatiquement 81 instructions. Les deux dernières instructions sont ajoutées à la liste manuellement.

Après avoir ajusté différents paramètres de cet algorithme, j'ai réussi à trouver une solution à 10 444 points. Voici un lien vers la version finale de mon code.

Le mot de la fin

Bravo à tous les vaillants candidats qui ont affronté notre épreuve de courage !
Vous pouvez assister aux discussions sur l'annonce cousin sur TI-Planet.

Ceci clôt le triconcours de rentrée 2018 organisé par TI-Planet et Planète Casio. Merci à tous de vos participations, et si les constructeurs le permettent, à l'année prochaine !




Disperseur
En ligne
Membre
Points: 899
Défis: 0
Message
Dernier message de la page précédente :Posté le 02/12/2018 10:16 |
@Critor : je sais pas mais il me semble pas que Sentaro21 soit souvent dans les parages..
----------------------------------



Pages: Précédente | 1, 2, 3, 4 | Suivante

Critor
En ligne
Administrateur
Points: 989
Défis: 0
Message
Citer : Posté le 02/12/2018 10:38 | #
Sentaro21 c'est fait, merci.

Là, on attend après la réponse de Shadow15510 avant de passer au suivant :
https://tiplanet.org/forum/viewtopic.php?t=22022&p=237258#p237258
Sentaro21
En ligne
Membre
Points: 157
Défis: 0
Message
Citer : Posté le 02/12/2018 10:51 | #
Merci.
Je suis ici.
France-traduction du navigateur est parfois drôle.

There is not such a big contest in Japan.
I think that the French calculator situation is very splendid again.

Because I was CASIO fan, I put 90+E in a choice.
However,only one 90+E was left, I would choose other.
The one of reason why I chose HP-Prime is because it supports Japanese.

Thanks very much for all about this contest.


BTW,
I do not have import experience from Europe.
I'm worried about the postage to Japan.
Critor
En ligne
Administrateur
Points: 989
Défis: 0
Message
Citer : Posté le 02/12/2018 10:58 | #
Don't worry, it won't be the first time we ship a calculator to another continent.
You'll have tracking anyway.
Lephenixnoir
Hors ligne
Administrateur
Points: 13203
Défis: 136
Message
Citer : Posté le 02/12/2018 11:05 | #
We are really happy that our events can reach people so far away! Please come again!
----------------------------------
Rise.
Sentaro21
En ligne
Membre
Points: 157
Défis: 0
Message
Citer : Posté le 02/12/2018 11:26 | #
@Citor
Thanks very much for your kind consideration.

@Lephenixnoir
I felt that I'd like to participate in that again next chance.

Thanks very much for this great contest again.
Disperseur
En ligne
Membre
Points: 899
Défis: 0
Message
Citer : Posté le 02/12/2018 11:31 | #
Faut croire que je me suis trompé dans ce cas c'est que Sentaro21 est discret sur le site
----------------------------------
Sentaro21
En ligne
Membre
Points: 157
Défis: 0
Message
Citer : Posté le 02/12/2018 11:59 | #
Pas de problème.
Merci.
Shadow15510
Hors ligne
Administrateur
Points: 2220
Défis: 15
Message
Citer : Posté le 03/12/2018 10:09 | #
La Nspire est partie vers des horizons lointaines et nouvelles avec Aérostellar

J'ai tite question : Il faut compter combien de temps entre la fin de la répartition des lots et l'envoi des lots ?
----------------------------------
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Moral
   100%
Massena
Hors ligne
Community Manager
Points: 442
Défis: 3
Message
Citer : Posté le 03/12/2018 19:37 | #
Bon bah...
Je me retranche sur la numworks.
----------------------------------
La loi de Murphy a écrit :
La probabilité qu'un événement arrive est inversement proportionnelle à sa désirabilité.
Shadow15510
Hors ligne
Administrateur
Points: 2220
Défis: 15
Message
Citer : Posté le 03/12/2018 19:39 | #
Je pense que c'est une bonne idée mais elle est pas si mal : écran couleurs, programmation Python, des jeux de rôles comme Zelda compatibles et tout ! Avec Python tu pourra sans doute participer dans plusieurs catégories l'année prochaine...
----------------------------------
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Moral
   100%
Massena
Hors ligne
Community Manager
Points: 442
Défis: 3
Message
Citer : Posté le 03/12/2018 19:39 | #
AAAH Il reste une NumWork et une TI-83 !
Bon bah moi qui hésitait entre les deux, je vais pas avoir à choisir vu qu'il reste plus qu'une personne devant moi
----------------------------------
La loi de Murphy a écrit :
La probabilité qu'un événement arrive est inversement proportionnelle à sa désirabilité.
Critor
En ligne
Administrateur
Points: 989
Défis: 0
Message
Citer : Posté le 03/12/2018 19:47 | #
Plus qu'une personne oui, mais une personne qui a déjà choisi une calculatrice aux résultats du défi précédent.
Lephenixnoir
Hors ligne
Administrateur
Points: 13203
Défis: 136
Message
Citer : Posté le 03/12/2018 19:59 | #
Massena a écrit :
Bon bah...
Je me retranche sur la numworks.

C'est une machine cool et moderne !
----------------------------------
Rise.
Shadow15510
Hors ligne
Administrateur
Points: 2220
Défis: 15
Message
Citer : Posté le 03/12/2018 20:53 | #
@Massena : Tu as donc le choix de ta machine Numworks ou TI

@ Critor : Est-il possible de ne pas prendre le poster Casio (j'ai pris le poster mode examen parce qu'il fallait en prendre un) mais je préfère le laisser avec les goodies d'UnCurieux pour le dernier ou un prochain concours Merci !
----------------------------------
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Moral
   100%
Alexot
Hors ligne
Membre
Points: 264
Défis: 14
Message
Citer : Posté le 03/12/2018 22:24 | #
Critor a écrit :
Plus qu'une personne oui, mais une personne qui a déjà choisi une calculatrice aux résultats du défi précédent.

Héhéhé, ce qui me laisse donc le dernier lot avec calculatrice. Mon plan machiavélique d'arriver en 12ème place en prenant en compte les participants aux autres épreuves ayant aussi participé à la dernière épreuve m'a permis de tomber pile sur la place qui me permet de gagner une calculatrice *et* de ne pas être confronté au dilemme qu'est le fait de devoir choisir entre plusieurs calculatrices en fait j'aurais très bien pu arriver premier, j'ai juste fait exprès d'arriver 12ème par commodité.
----------------------------------
Cliquez pour découvrir
Cliquez pour recouvrir
2b 5b 2d 2d 2d 2d 2d 3e 2b 2b 2b 3c 5d 3e 2b 2e 2b 2b 2b 2b 2b 2b 2b 2b 2b 2b 2b 2b 2e 2e 2d 2d 2d 2d 2e 2b 2b 2b 2e 2b 5b 2d 2d 3e 2b 3c 5d 3e 2e 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2e 2e 2b 5b 2d 2d 3e 2b 2b 2b 2b 2b 3c 5d 3e 2b 2e 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2e 2b 2b 2b 2b 2b 2b 2e 2d 2e 2b 2e 2d 5b 2b 2b 3e 2d 2d 2d 3c 5d 3e 2e 2b 2b 2b 5b 2d 3e 2b 2b 3c 5d 3e 2e 2b 2b 2b 2e 5b 2d 3e 2b 2b 2b 3c 5d 3e 2e 5b 2d 2d 2d 3e 2b 3c 5d 3e 2d 2e 2d 5b 2d 3e 2b 2b 2b 2b 2b 2b 3c 5d 3e 2d 2e 2d 5b 2d 2d 3e 2b 2b 2b 3c 5d 3e 2d 2e 2b 5b 2b 2b 3e 2d 2d 2d 3c 5d 3e 2e 5b 2d 2d 2d 3e 2b 2b 3c 5d 3e 2d 2e 2d 5b 2d 2d 3e 2b 3c 5d 3e 2d 2d 2e 2b 5b 2d 2d 3e 2b 2b 2b 3c 5d 3e 2e 2b 2b 2b 5b 2d 3e 2b 2b 2b 2b 3c 5d 3e 2d 2e 3e 2b 5b 2d 2d 2d 3e 2b 2b 3c 5d 3e 2b 2b 2e 2b 2b 2b 2b 2b 2b 2b 2b 2b 2b 2b 2e 5b 2d 3e 2b 2b 2b 2b 2b 2b 3c 5d 3e 2d 2e
Critor
En ligne
Administrateur
Points: 989
Défis: 0
Message
Citer : Posté le 03/12/2018 22:29 | #
Shadow15510 a écrit :
@ Critor : Est-il possible de ne pas prendre le poster Casio (j'ai pris le poster mode examen parce qu'il fallait en prendre un) mais je préfère le laisser avec les goodies d'UnCurieux pour le dernier ou un prochain concours Merci !

Ok, c'est noté. Quelle abnégation cher collègue administrateur.
Shadow15510
Hors ligne
Administrateur
Points: 2220
Défis: 15
Message
Citer : Posté le 04/12/2018 06:48 | #
Critor je citerais UnCurieux : « je n’en ai pas usage »

Alexot : Ça m’arrange bien que tu es choisit la douxieme place plutôt que la première
----------------------------------
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Moral
   100%
Disperseur
En ligne
Membre
Points: 899
Défis: 0
Message
Citer : Posté le 04/12/2018 07:19 | #
Bon ben perso it's over pour une calto.. je m'y attendais. Le truc pas cool quand même c'est que j'ai mis en ligne ma dernière participation une semaine avant la fin.. on n'etait que 6 a avoir participé mais en une semaine pleins de fous sont arrivés (bravo à eux quand même ) et ont rehaussé le niveau vitesse grand V !
@Critor: je pense qu'il me reste des goodies non ?
----------------------------------
Shadow15510
Hors ligne
Administrateur
Points: 2220
Défis: 15
Message
Citer : Posté le 04/12/2018 08:34 | #
Tous le monde va gagner un truc sur cette épreuve
----------------------------------
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Moral
   100%
Massena
Hors ligne
Community Manager
Points: 442
Défis: 3
Message
Citer : Posté le 04/12/2018 18:09 | #
Il... me... reste... un... choix...
BLBLBLBLBLBLBLBLBLBLB
----------------------------------
La loi de Murphy a écrit :
La probabilité qu'un événement arrive est inversement proportionnelle à sa désirabilité.

Pages: Précédente | 1, 2, 3, 4 | Suivante

Index du Forum > Actualités > Résultats du triconcours : les plus courageux !

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2018 | Il y a 57 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire indépendant, géré bénévolement et n'est donc pas affilié à Casio | Toute reproduction de Planète Casio, même partielle, est interdite
Les fichiers, programmes et autres publications présents sur Planète Casio restent la propriété de leurs auteurs respectifs et peuvent être soumis à des licences ou des copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd