Concours de rentrée 2021 - La Geste d'Alrys

[SlyVTT]

Du coup j'ai mis une mise à jour pour éviter le spoil
Même qu'il s'agissait d'un vieux chemin pas optimisé, visiblement il y avait qq infos intéressantes.

Voila qui devra forcer les moins rapides à réfléchir par eux même
Merci Dubs et Pavel de m'avoir signalé.

Ciao
Sly

[Afyu]

Bonjour tout le monde !

Alors qu'il reste moins d'une semaine avant la fin du concours, je partage quelques scripts d'optimisation ou de recollement que j'ai utilisés.
Les scripts alrys-opti_ et ses variantes v3, v3+, v4 et v4+ sont assez proches.
L'idée est de prendre la liste des angles et déplacements qui constitue le trajet que l'on suit et de modifier une ou plusieurs valeurs de la liste, puis de tester pour voir si la nouvelle liste donne un meilleur score que la précédente. La nouvelle liste est affichée, avec son score associé, si elle est meilleure que la liste initiale (ou que la meilleure liste obtenue après optimisations).

C'est ce que fait le script alrys-opti_.py.
La version 3 stocke la meilleure liste obtenue dans un fichier score.txt et lis le contenu de la liste score.txt lorsqu'on l'exécute. Ainsi, il n'y a plus besoin de copier la meilleure liste obtenue après optimisation et affichée dans la console pour la coller dans le script et le relancer, tout est automatiquement actualisé et lu. Il y a 3 lignes du script à dé-commenter pour copier la liste initiale dans le fichier score.txt, au premier lancement

La version 4 est similaire à la version 3 mais utilise l'algorithme de recollement de morceaux (présent également dans le script recollement.py) et modifie une seule valeur de la liste et recalcule l'angle et la distance qui permettent de retomber sur le point suivant

Les versions 3+ et 4+ stockent le meilleur score dans un fichier scoremaxi.txt, ce qui permet de lancer plusieurs fois le script simultanément tout en s'assurant que chaque nouvelle meilleure liste stockée dans le fichier score.txt est meilleure que la précédente meilleure liste stockée dans ce fichier.

Dans ces 5 scripts, on peut régler certaines choses, comme l'écart que l'on applique aux valeurs de la liste, avec diff, ou encore le rang du premier et du dernier point de la liste qu'on s'autorise à modifier avec a=randint(début,fin), ou encore le nombre de modifications que l'on s'autorise à faire à notre liste avant de reprendre la meilleure liste obtenue pour de nouveau tester des changements.

Le script recollement.py permet de recoller un début de parcours optimisé (par exemple avec un des 5 autres scripts donnés) avec un parcours complet (ou pas !) mais moins optimisé. Si le morceau que vous avez optimisé comporte moins de segments que son équivalent dans la liste pas optimisée, alors il faut penser à ajouter des segments de longueur 0 (donc des morceaux en [1, 0, 0, 0] pour chaque segment à ajouter, à la fin du début optimisé (puis les retirer dans la liste de sortie affichée dans la console). À l'inverse, il faudra en ajouter au bon endroit dans la liste pas optimisée s'il y en a plus dans le début optimisé que dans le morceau équivalent dans la liste pas optimisée. J'espère que c'est clair... :s
Ce script m'a souvent sauvé lorsque les premières versions du programme de Dubs donnait parfois une liste qui ne passait pas dans Python.

Si vous avez des questions, n'hésitez pas !

[SlyVTT]

Bon alors pour ceux qui comme moi galèrent ou ont galéré à installer la version PC des scripts voici la procédure que j'ai suivi pour que cela fonctionne sous Win10 (j'avais une install sous linux qui a été super simple, mais sous Win c'est une horreur !!!).

1/ installer Python en le téléchargeant ici et en l'installant (suivre les indications de l'installeur)
https://www.python.org/downloads/windows/ et prendre la dernière release (à l'heure de l'écriture de ce post, c'est la version 3.10.0)

2/ ouvrir un terminal et taper (il faut avoir une connexion internet, car on va télécharger et installer un paquet) :

Code: Select all

pip install PySDL2

3/ En théorie, la librairie PySDL2 est installée, mais visiblement parfois il en manque des morceaux.
Ouvrez un terminal, allez dans le répertoire où vous avez copié vos scripts de Alrys et tapez :

Code: Select all

python alrys.py

si une fenêtre "Polycalc SDL2" s'ouvre, c'est tout bon cela est fonctionnel, donc ça marche, vous pouvez allez jouer à Alrys

... sinon passez à la suite ...

4/ Bon, si vous lisez cette partie, c'est que tout comme chez moi, ça n'a pas fonctionné. En fait, il faut donc terminer l'installation à la main si comme moi ça ne fonctionne pas, car la DLL de SDL2 n'est pas incluse dans le paquet de PySDL2. On va donc remédier à cela.

5/ Allez sur le site SDL.org https://www.libsdl.org/download-2.0.php et téléchargez l'archive du "Runtime Binaries" pour windows (x64 a priori).

6/ ouvrez le fichier ZIP que vous venez de télécharger. A l'intérieur se trouve un fichier .dll qu'il faudra copier dans le répertoire :
"C:\Users\ xxx__xxx \AppData\Local\Programs\Python\Python310\Lib\site-packages\sdl2"
en remplaçant le xxx___xxx par votre nom d'utilisateur

7/ la touche finale : pour fonctionner, PySDL2 a besoin de savoir où le fichier DLL est installé, il faut donc lui préciser par une variable d'environnement:
dans la barre de recherche vers le bouton démarrer (bouton avec la loupe) : taper "Système" et valider sur "Systeme - Panneau de configuration)
- une fenêtre s'affiche alors, et sur la partie droite un lien indique "Paramètres avancés du système" : cliquer dessus
- une nouvelle fenêtre "Propriétés système" s'ouvre. Cliquer sur le bouton "Variables d'environnement..."
- cliquez sur le bouton "Nouvelle..." du haut (pour l'utilisateur XXX)
- dans "nom de la variable : " taper PYSDL2_DLL_PATH
et dans Valeur de la variable :" le chemin d'installation du fichier dll : C:\Users\ xxx__xxx \AppData\Local\Programs\Python\Python310\Lib\site-packages\sdl2
en remplaçant encore une fois le xxx___xxx par votre nom d'utilisateur (je pense que vous aviez compris

8/ On valide 3 fois par OK et fermer les fenêtres ouvertes et a priori cette fois cela devrait fonctionner, vous pouvez vérifier en reprenant l'étape 3.

Et miracle, la fameuse fenêtre "Polycalc SDL2" doit apparaître comme par enchantement.

En espérant que cela fonctionne chez vous aussi.

@+

Sly

PS : cela fonctionne aussi pour SynchroDonjon

[critor]

Bon, il faut que l'on parle des NumWorks.

On m'a donc donnée aux journées APMEP 2 NumWorks en révision matérielle 3.43 (la dernière), mais qui sont déjà à jour en version 16.
Ce sont des machines de démonstration/formation, venant avec l'emballage complet et tous les acessoires. L'emballage n'est pas scellé, donc techniquement elles ne sont plus neuves, mais elles n'ont quasiment pas servi.

Donc déjà, je vais vous en démonter une des deux, aussi proprement que possible, puisque j'avais demandé des photos du nouveau matériel vu que plein de nouveaux utilisateurs en ont récupéré pour cette rentrée 2021, et qu'à ma connaissance personne n'a rien partagé en ce sens.

Mais il nous faut garder 1-2 NumWorks N0110 déverrouillées pour pouvoir tester Khi+KhiCAS de temps en temps ainsi que d'éventuels autres firmwares, et vous informer de l'actualité à leur sujet.
Je suppose aussi qu'il serait pertinent de garder 1 N0110 r3.43 également.

Bref, on ne sait pas trop encore ce que l'on va vous envoyer.
On va regarder toutes les NumWorks que nous avons, et une fois mises de côté les machines que nous souhaitons garder ainsi que celles qui ne seraient pas en état nickel, on vous proposera de choisir parmi les autres, tout en vous informant bien sur l'historique de chacune.
Si vous voulez des machines non verrouillées, je crains qu'il n'y ait pas beaucoup de choix.

[critor]

Merci à vous tous, l'aventure Alrys fut absolument fantastique.

29 candidats ayant produit 326 participations, toutes différentes, je suis heureux de voir que le sujet vous a intéressés et passionnés.

Une très belle compétition, félicitations à tous et toutes !

L'anonymat est levé ; les itinéraires et listes associées sont dès maintenant librement consultables :
https://tiplanet.org/concours_alrys2021 ... =0&infos=1

Pour au moins les 12 premiers (+ tous les suivants qui le souhaitent), on aimerait bien avoir quelques lignes de votre part, ici ou par courriel : comment vous avez procédé, et si vous avez quelque chose à dire ce que vous avez pensé du sujet ou encore des lots disponibles. Merci.

Vous pouvez dès maintenant choisir vos lots en répondant ici (ou par courriel) à tour de rôle.
@Pavel, tu commences.

[Pavel]

Tout d'abord, je tiens à remercier les organisateurs et les constructeurs de calculatrices pour ce magnifique concours. Les organisateurs se sont encore surpassés et ont proposé des défis très intéressants et difficiles. Je suis très impressionné par les défis proposés cette année. Je n'aurais jamais pensé que cela était possible en Python sur une calculatrice.

Je remercie également Dubs et SlyVTT pour le partage de leurs programmes et idées. C'était une grande source d'inspiration pour moi. Le programme de Dubs m'a aidé à commencer à comprendre ce qui se passe dans ce défi et la vidéo de SlyVTT m'a stimulé à faire quelques lectures sur les algorithmes RRT* et A* et à essayer de les utiliser. C'est bien l'algorithme A* que j'ai utilisé pour trouver des solutions dans les deux défis.

Voici comment j'ai abordé ce défi:

• Tout d'abord, je suis passé des coordonnées polaires relatives aux coordonnées orthogonales absolues pour mieux comprendre ce qui se passe dans ce défi.
• J'ai remarqué que, lors de l'optimisation, de nombreuses coordonnées se dirigeaient vers des valeurs entières ou des valeurs entières plus/moins une très petite valeur (
  $mathjax$10^{-14}$mathjax$
  ).
• Pour l'algorithme A*, j'ai défini l'espace de recherche comme une grille qui comprend:
  
  • coordonnées entières (coins de toutes les cases)
  • coordonnées entières plus/moins une très petite valeur (
    $mathjax$10^{-14}$mathjax$
    )
  
• J'ai utilisé l'algorithme A* avec 58080 (241*241-1) voisins pour trouver les chemins entre les donjons et les villages. C'est en effet la combinaison des coordonnées entières plus/moins
  $mathjax$10^{-14}$mathjax$
  et de l'algorithme A* qui m'a permis de trouver quelques passages secrets.
• J'ai utilisé une méthode d'optimisation stochastique (recuit simulé) et j'ai essayé de supprimer/ajouter des tranches de chemin à la main afin d'obtenir des chemins bien optimisés.
• J'ai essayé plusieurs séquences de donjon et de village et la meilleure séquence que j'ai trouvé m'a donné 1820,7 points. Ensuite, c'est la séquence que j'ai trouvé dans le code de SlyVTT qui m'a permis d'obtenir mon meilleur score.

Tout le code que j'ai utilisé pour ce défi se trouve dans ce dépôt. L'algorithme A* est dans le fichier search.cpp. L'optimisation stochastique se trouve dans les fichiers explore.c, finalize.c, optimize.sh.

[Pavel]

Vous pouvez dès maintenant choisir vos lots en répondant ici (ou par courriel) à tour de rôle.
@Pavel, tu commences.

J'aimerais beaucoup un lot 83PCE avec

• calculatrice TI-83 Premium CE Edition Python sans gravure
• housse Wyngs noir
• stylo CALCUSO
• clé USB 4 Go rouge
• sac STEM
• cahier Enseignement de spécialité Mathématiques (1ère et Tle)
• aimantin TI-Planet

[critor]

Merci @Pavel.

@CrimsonDeus, à toi.

[Lephe]

Il me semble que le compte-rendu est dans le message du dessus ?

[Pavel]

Merci @Pavel.
N'oublie pas ton compte-rendu de recherche, stp.

Je pense que je l'ai déjà posté:
viewtopic.php?f=49&t=25201&p=264996#p264994