J'ai découvert l'énoncé avec 4 jours de retard et j'ai commencé mes recherches sur la ressource
NumWorks avec le
Workshop officiel.
J'ai placé des commandes
modifier_vol(n1, n2, n3) en tatonant, jusqu'à avoir une solution convenable.
J'ai alors 22 étapes et une consommation à 3567.5.
Par exemple, la longue ligne droite entre le premier et le deuxième stalactite est coupée en 4 segments mis bout à bout... inutilement.
Puis, j’ai fait un deuxième essai à 2034.5 et ensuite un troisième à 1964.5 et un à 1666 avant d'arriver à mon essai à 1054.5 que j’ai décidé d'envoyer.
Après plusieurs essais et 9 scores plus tard, j'arrive à 541.5 et je décide de passer (enfin !) par un algorithme pour optimiser tout ça.
J'ai repris la ressource proposée pour la
NumWorks (version
Workshop officiel) et j'en ai supprimé la partie graphique (faute de savoir comment l'adapter sur ordi, en utilisant
tkinter plutôt que
kandindky pour le module graphique) et j'ai ajouté quelques lignes pour créer 3 listes d'initialisation
coord1init,
coord2init et
coord3init qui contiennent respectivement : les valeurs utilisées comme 1er paramètre, celles utilisées comme 2ème paramètre et celles utilisées comme 3ème paramètre. Et maintenant, avec un peu de recul, je me demande s'il n'aurait pas été plus pertinent de créer des triplets de nombres (un triplet pour chaque commande
modifier_vol(n1, n2, n3) plutôt que 3 listes. En fait NON, car sauvegarder puis récupérer régulièrement plein de triplets c'est plus compliqué que de sauvegarder 3 listes.
Dans le script j'ai également créé une variable
scoremax qui contiendra mon meilleur score. J'ai également créé 3 listes
coord1,
coord2 et
coord3 qui sont les listes de paramètres sur lesquelles je vais travailler (et qui sont en lien avec les 3 listes d'initialisation). Je modifie aléatoirement une valeur d'une ou de plusieurs de ces 3 listes et je calcule la consommation obtenue. Concrètement, je tire un nombre aléatoire compris entre 0 et la longueur de coord1 - 1. Je stocke ce nombre dans la variable
rang1. Ensuite, je modifie
coord1[rang1] en lui ajoutant ou en lui retirant une certaine valeur ou en ne la modifiant pas, avec l'instruction
coord1[rang1]+=0.01*(randint(0,2)-1) qui ajoute ou retire 0.01 ou ne fait rien. Je fais de même avec
coord2 et
coord3. Ensuite, je compare la consommation obtenue, donc
state[4], avec mon
scoremax. Si le score obtenu est meilleur (donc plus petit), alors je copie les 3 listes
coord1,
coord2 et
coord3 dans mes listes d'initialisation/sauvegarde
coord1init et ses consœurs et je stocke mon nouveau meilleur score dans
scoremax. Ensuite, au tour de boucle suivant, je modifie de nouveau une valeur dans une ou plusieurs des 3 listes et je compare le score obtenu avec mon meilleur score et ainsi de suite. Tous les 3 tours de boucle, donc tous les 3 changements (qui sont successifs), je récupère la valeur de
coord1init et ses deux voisines pour les copier dans
coord1,
coord2 et
coord3. C'est une sorte de réinitialisation de mes 3 listes de travail aux paramètres du dernier meilleur score obtenu.
J'ai parfois adapté ce nombre de boucles à parcourir avant cette réinitialisation, suivant si je voulais permettre un grand nombre de changements ou au contraire rester proche de mon actuelle meilleure solution (finalement 3 boucles était un bon choix).
J'ai également adapté la précision des valeurs que je souhaitais pour les 3 paramètres. Le dernier paramètre semble être toujours un entier (mettre une valeur non entière donne le même le score que mettre uniquement la partie entière).
Avec la publication du classement et des solutions de chacune et chacun des gagnants du premier défi, j'ai vu qu'il pouvait y avoir une histoire de nombre de décimales. J'ai donc tenté de réduire le nombre de décimales de mes paramètres (par exemple, je remplace un 2.42 par 2.4 dans la liste
coord1init et je relance mon algorithme jusqu'à obtenir de nouveau mon meilleur score, les autres valeurs ayant alors été légèrement modifiées pour compenser l'écart entre 2.42 et 2.4, et je recopie alors ces autres valeurs qui ont été renvoyées avec mon 2.4 ; si avec 2.4 ça ne me renvoie pas une nouvelle solution avec mon meilleur score, alors je teste avec 2.41, en étant moins exigeant, puis ensuite avec 2.4).
Mon premier score obtenu avec mon algorithme était 537.5 (le 11/10). Je passe sous la barre des 500 le même jour, puis sous la barre des 400 le 16/10 et enfin sous la barre des 300 le 17/10 et je suis finalement arrivé à 265.325 le 21/10. Ensuite, rien. Le néant. Plus aucune amélioration pendant 2 jours.
LeGmask, que je remercie
grandement ici pour son aide, m'a entendu me plaindre de cette stagnation de mon score sur le chat et m'a donné quelques conseils, en particulier celui d'utiliser l'interface graphique proposée par
Pavel - que je remercie
grandement ici pour son script généreusement partagé dans les commentaires (page 3).
LeGmask m'a proposé une version améliorée par ses soins, qui m'a aidé à comprendre l'importance et l'influence des 3 paramètres et de la variable
state[2]. Avant d'utiliser cette interface graphique, j'avais compris qu'on pouvait tracer un segment (droit) avec un triplet de la forme
(0, 0, n) avec
n un entier. J'avais également compris que le dernier paramètre influait sur la longueur du morceau de courbe placé et que le premier paramètre modifiait l'inclinaison ou la hauteur d'arrivée. Le 2ème paramètre restait assez flou pour moi et j'ai laissé mon algorithme choisir la valeur la plus adaptée pour obtenir un bon score. En suivant les conseils de
LeGmask et avec l'interface graphique de
Pavel, j'ai compris que le 2ème paramètre modifiait la valeur de
state[2] et que la consommation de chaque morceau de courbe placé était bien moindre lorsque
state[2] avait pour valeur 0.5 (ce qu'on peut retrouver en lisant le code du script donné pour le défi, à l'endroit du calcul du score, donc de
state[4], et ça concerne en particulier la variable
dapi qui sanctionne tout écart de
state[2] avec la valeur 0.5). Une solution simple serait de modifier le 2ème paramètre de la 1ère commande
modifier_vol(n1, n2, n3) afin de mettre la variable
state[2] à 0.5 et de ne plus modifier cette valeur. Le problème est que
state[2] joue sur l'épaisseur du tracé et qu'il est nécessaire de modifier cette valeur pour réduire l'épaisseur du trait pour passer certains passages étroits de la cave sans toucher les bords (en fait : le passage sous chacun des 3 stalactites). Il faut donc momentanément s'éloigner de cette fameuse valeur 0.5 le temps de passer sous les stalactites pour y revenir aussi vite que possible en modifiant le 2ème paramètre du premier morceau de courbe placé après un passage étroit.
Une observation grandement facilitée par l'utilisation de l'interface graphique m'a permis de comprendre que
state[0] contient la position horizontale à la fin du dernier morceau de courbe placé (la cave est en fait divisée en 128 "tranches verticales" qui donnent une abscisse comprise entre 0 et 127, stockée dans
state[0]), de même
state[1] contient la position verticale,
state[2] contient un paramètre toujours compris entre 0 et 1 et qu'il vaut mieux conserver à 0.5 lorsque c'est possible (c'est le 2ème paramètre des commandes
modifier_vol(n1, n2, n3) qui modifie la valeur de
state[2]) et
state[4] contient la consommation totale (donc le score). Pour
state[3], je ne sais pas... J'ai également observé l'évolution de la consommation suivant la valeur prise par
state[2]. Si
state[2] vaut 0.5, alors chaque nouveau morceau de courbe placé (et qui conserve le fait que
state[2] vaut 0.5) consomme 10 s'il est droit (1er paramètre égal à 0) et 20 s'il est courbé (1er paramètre non nul) et ce peu importe sa longueur (donnée par le 3ème paramètre). Si
state[2] ne vaut pas 0.5, alors le calcul est différent et la consommation d'un morceau de courbe placé augmente de 3 lorsque sa longueur (3ème paramètre) augmente de 1. L'utilisation de l'interface graphique m'a permis de comprendre que le 2ème argument pouvait se contenter de prendre pour valeur 0.5 ou -0.5, en effet les valeurs strictement comprises entre -0.5 et 0.5 ne sont pas très productives et les valeurs en-dehors de cet intervalle ne changent rien du tout par rapport à un -0.5 ou un 0.5) ce qui a grandement augmenté l'efficacité de mon algorithme de recherche puisque la partie
coord2[rang2]+=0.01*(int(0,2)-1) est devenue
coord2[rang2]=0.5*(int(0,2)-1) avec seulement 3 valeurs possibles pour chaque 2ème argument.
Donc, pour minimiser la consommation globale, il faut essayer de garder
state[2] à 0.5 en modifiant la valeur du 2ème paramètre, ou revenir à ce 0.5 dès que possible. Il faut également minimiser le nombre de commandes
modifier_vol(n1, n2, n3) car chaque nouvelle commande a un coût fixe. Il faut donc favoriser de longs morceaux (traversant le plus grand nombre possible de "tranches verticales", peu importe la position verticale (
state[1]) de départ et d'arrivée), si possible en ligne droite.
Un dernier point : les collisions. Chaque collision consomme 7 ou 14 (ou plus). Il faut donc à tout prix réduire le nombre de collisions. Il est possible de parcourir la grotte sans collision à l'exception du passage sous le 3ème stalactite. Ce passage entraîne 4 ou 5 collisions dans la plupart des cas. En fait, j'ai modifié mon algorithme de recherche pour l'orienter sur l'optimisation de ce nombre de collisions et surtout j'en ai demandé l'affichage. Le nombre de collisions est calculé deux fois dans chaque "tranche verticale" de cave et prend la forme d'un nombre entier compris entre 0 et 12, inclus. J'ai créé une liste (
colli) qui contient ces nombres de collisions et ça donne une liste de 255 entiers compris entre 0 et 12, inclus.
Une de mes tactiques pour améliorer mon score a été de minimiser ma consommation sans prendre en compte le nombre de collisions, puis de modifier mes 3 listes de coordonnées pour réduire le nombre de collisions lors du passage sous le 3ème stalactite puis de réduire le nombre de collisions après le 3ème stalactite. N'ayant d'abord pas utilisé l'interface graphique de Pavel, j'ai tenté d'optimiser le début du parcours (quitte à casser la suite du parcours), puis le passage sous le 3ème stalactite (quitte à casser la suite du parcours) puis de corriger la fin du parcours, et tout ça en jouant sur les valeurs de la liste
colli qui contient le nombre de collisions tout au long du chemin parcouru. J'ai ainsi créé un 2ème algorithme ayant pour seul but de réduire le nombre de collisions sous le 3ème stalactite. En fait, dans la liste
colli, le passage sous le 3ème stalactite correspond aux 169 et 170ème valeurs (donc d'indices 168 et 169). Dans l'idée, j'ai lancé mon script en mettant comme condition de réussite/affichage le fait d'avoir les 168 premières valeurs égales à 0, donc avec aucune collision avant le passage critique, puis comme condition d'avoir la somme
colli[168]+colli[169] (écrite sous la forme
sum(colli(168:170]) dans mon script) égale à 4 (en fait 2+2), puis comme condition d'avoir les derniers termes de la liste
colli tous égaux à 0.
J'ai tenté à de très nombreuses reprises d'avoir strictement moins de 4 collisions sur le parcours complet, mais rien n'y a fait, ni avec mon algorithme de recherche, ni avec la version adaptée pour la réduction du nombre de collisions, ni avec l'interface graphique de
Pavel améliorée par
LeGmask je n'ai réussi à réduire le nombre de collisions strictement en-dessous de 4.
Le 26/10 j'ai finalement obtenu 220.0 avec 4 collisions en tout, puis 221.0 mais avec 5 collisions. En supprimant cette 5ème collision, j'ai finalement obtenu 214. Le 27/10
Pavel envoie un score à 211 que j'ai réussi à obtenir quelques heures plus tard en imitant son trajet, sauf pour la fin. (On peut en effet remplacer deux segments droits qui coûtent 10 et 10 lorsque
state[2] vaut 0.5 par un morceau courbé qui coûte 10+10 directement). En partant du trajet à 214.0, il restait une optimisation à faire, qu'il a faite avant moi. Bien joué ! J'ai passé de longues heures à essayer de réduire encore le score, pour éventuellement passer à 208 en raccourcissant un morceau courbé dans un passage étroit (donc sans avoir
state[2]=0.5) et en rallongeant un segment droit, mais sans succès. J'ai également essayé de réduire le nombre de morceaux (-10 ou -20) tout en ayant une collision supplémentaire (+7 ou +14) mais sans y parvenir. 211.0 est peut-être le meilleur score possible, après tout...
En dégradant ce 211.0 j'ai obtenu 213.98 puis 213.56 puis 213.5 (justement en modifiant le 2ème paramètre du morceau qui contient la portion en rouge et en le mettant à 0.25 plutôt qu'à 0.5, le trait est moins fin mais donne toujours 4 collisions et la consommation globale est alors de 213.5). Il m'a semblé impossible d'obtenir un score strictement compris entre 211.0 et 213.5 et mon algorithme n'a pas trouvé non plus. Le participant qui est juste derrière moi a obtenu 213.501 et le suivant 213.502. En fait, il est possible d'obtenir des scores compris entre 213.500 et 213.501. Par exemple, en mettant 0.2501 plutôt que 0.25 au 2ème paramètre du morceau de courbe qui contient la zone en rouge, on obtient un score à 213.5002
et en mettant 0.25001 on obtient 213.50002
Cette explication était vraiment beaucoup trop longue ! Je vous mets les dernières versions de mes deux scripts en pièces jointes.
Je remercie
grandement les organisateurs de ce concours, qui proposent une fois encore un concours original, enthousiasmant et organisé avec soin et avec une quantité impressionnante de super lots ! <3
critor wrote:Cher @
Afyu alors, comment as-tu fait et que nous prends-tu ?
Je prendrais bien :
1 lot Sagittaire ♐ : 1
calculatrice NumWorks N0110 + 1
pack de goodies NumWorks + 1
goodie Xcas + 1
pack de goodies TI-Planet & Planète Casio You do not have the required permissions to view the files attached to this post.
by 
[
) and it has been quite enjoyable! Also, thank you Pavel for your GUI and Afyu for the helpful tips!
