News
La Revue des Projets - 132
Bonjour à tous !
Ce soir une mini revue des projet express et en retard pour éviter des suicides ! Une RdP petite, soit, mais une RdP quand même, ce soir, un article de Massena.


Massena que nous avions quitté avec une calculatrice au contenu à moitié effacé et un autre projet en cours nous éblouit avec un troisième projet qui arrive, laissons-lui la place !

Massena a écrit :
Coucou ! (Sorry pour le retard)

Puisque le Triconcours de PC et TIP est fini, je n'ai plus aucune excuse pour glander ne pas me remettre à la programmation.

Donc, chers villageois de Thiercelieux, j'ai besoin de votre avis. Je suis actuellement sur 3 projets de programmations, et je ne pourrais PAS DU TOUT les faire en même temps. Il va falloir faire un choix. Je hais les choix. C'est là que j'ai besoin de vous.

Mesdames et messieurs, je vais demander votre participation. J'aimerais que vous choisissiez deux projets sur les trois, selon 2 critères :
- Le jeu en lui-même ( Est-il bien ? Vous plaît-il ? )
- La possibilité de réalisation ( Pensez-vous qu'il est réalisable en Basic Casio ? )

Maintenant, que vous connaissez les critères, je vais vous dévoiler les trois projets, vous en connaissez tout de même 2 sur les trois...

Premier projet
Evocalc !
Vous connaissez sûrement ce projet, qui a été abandonné à cause d'un malheureux incident.

Pour ceux qui ne savent pas de quoi je parle, c'est une adaptation du RPG Evoland. Vous trouverez le trailer ici.

L'idée serait de reprendre le concept évolutif du jeu, mais de cette fois décrire l'évolution des commandes en Basic Casio. Passage du Locate() au Text(), mais aussi du jeu textuel à l'aventure RPG.







Dans une RdP précédente, j'annonçais la reprise de ce projet, mais maintenant qu'entre temps j'eu à programmer mon deuxième projet, qui est maintenant plutôt avancé, j'hésite un peu.


Deuxième projet
Picross for casio
Celui-ci, j'ai été assez discret dessus. Pas de screen, juste une annonce.

Durant ma dépresssion dû à Evocalc le triconcours de rentrée, j'ai eu l'idée de programmer un picross. Le déclic est venu lors de la sortie du dernier opus sur switch. Voici une image du jeu :


La grille a une dimension de 8*8, ce qui donne, sachant qu'il y a noir/blanc à chaque case... euuuh... je vous laisse calculer --'


Troisième projet
Professeur Layton et [insérer une relique ancienne]
Vous connaissez sûrement la saga du professeur Layton.

Pour les incultes, les ermites ou les joueurs de Call of Duty, c'est un jeu où l'on doit résoudre une enquête (incarné par le professeur Layton), et des énigmes. J'explique très mal. Ça ne vous dit toujours rien ? Vous savez, le mec qui a des petits pois à la place des yeux et un grand chapeau ?



C'est le mec le plus inexpressif au mond... Ah nan au fait :



BREF je n'ai jamais annoncé ce projet. Les graphismes sont même pas fait, ni le moteur de jeu, j'ai juste quelques images qui rendent vraiment bien sur calto. Je sais comment je pourrais développer ce jeu, et je suis assez motivé vu que, après Zelda, c'est une de mes saga préférées.


Bon, maintenant vous avez toute les cartes en main. Donnez-moi vos avis en commentaire, la semaine prochaine je publierais les résultats du vote, et des screens des jeux sélectionnés.

Bonne soirée !
Massénou

Bonne soirée à tous, et à la semaine prochaine !

On continue cette soirée avec les résultats du vote du jeu du mois de novembre 2018 :

Parmi les 8 pogrammes de ce vote, Poképix s'est distingué le premier fonçant vers ses deux points, suivi de près par Candy-Crush qui le rejoint en tête !
Très vite Poképix continue avec 5 points et Pixel part avec deux points !
Nous avons donc Poképix en première place !
Puis Candy-Crush et Pixel ex aequo en seconde position !

Bravo à tous ! Ceux qui n'ont pas eu de notes, ne désespérez pas : essayer d'améliorer votre com' autour de votre jeu : plusieurs topic existent à ce sujet et l'équipe de Planète-Casio est là pour vous aider à réalise vos projets !
Un grand merci à tous pour vos programmes ou vos votes, voire les deux ! Et au moins prochain.



Après ces résultats attendu, passons à la suite :

Cette semaine, 8 programmes ont été postés !

Partition de Manolo un programme qui permet de lire et d'écrire une partition.
Graphique de Mastermokeko un programme pour Fx-CP 400 qui permet de tracer des graphes.
Dessin du même auteur, et toujours pour la Fx-CP 400 permet de dessiner via l'écran tactile de la calculatrice !
1er Degré du Underhead un programme qui résout les équation du premier degré. Dans la même collection : Inéquation Sup, Equation IEquation Inf et Identités remarquables
Pong de Thoricelli un jeu de ping-pong en BASIC.

Nous terminons ici cette RdP, à la semaine prochaine !

Lire la RDP précédente : La revue des projets - 131
Participez à la Revue des Projets : Proposez un article

Commentez cette news ! (20)
écrit par Shadow15510 le 09/12/2018 19:25 Voir toutes les news

Gagne une Graph 90+E au puzzle de l'Avent 2018 !
Grâce à la générosité de Casio France, notre événement de l'Avent 2018 devient un concours.

Nous aurons en effet le plaisir de récompenser la première personne à résoudre l'énigme finale avec un superbe cadeau de Noël, la rolls des Casio Graph, j'ai nommé la superbe calculatrice graphique couleur Graph 90+E !
Calculatrice qui rappelons-le inclut l'interpréteur MicroPython 1.9.4 une fois mise à jour en version 3.20 si jamais la machine venait préchargée d'une version antérieure.

Pour consulter l'ensemble des indices et énigmes intermédiaires quotidiennes destinés à te mettre sur la bonne voie, c'est par ici.

Merci Casio, et bon Avent 2018 à toutes et à tous sur Planète Casio !

Commentez cette news ! (6)
écrit par Critor le 06/12/2018 18:53 Voir toutes les news

TDM n°10 – Promouvoir son jeu ! (Partie 1)
Le Tuto Du Mercredi [TDM] est une idée qui fut proposée par Ne0tux. Un mercredi sur deux, nous postons un tutoriel sur l'Utilisation de la calculatrice, le Transfert, les Graphismes, la Programmation, ou encore la Conception de jeux. En voici la dixième édition, dans un format plus léger ! Champagne !

Comment valoriser mon projet de jeu ?

Niveau : ★ ★ ☆ ☆ ☆

Tags : Jeux, Projet, Communauté

Il n'est pas toujours facile de se faire remarquer, de montrer ses jeux et de donner envie aux membres de la communauté d'y jouer. Ce tutoriel a pour but de vous donner quelques astuces pour promouvoir votre projet de jeu auprès de la communauté de Planète Casio, lui donner de la visibilité, et d'avoir du feedback sur ce que vous faites.

Partie I – La section « Projets » du forum :

Projet UnderCasio par Lepianoteur.

Sans doute la saviez-vous déjà, mais le forum se divise en plusieurs catégories. L'une d'entre elle s'intitule « Projets de Programmation » : il s'agit de la section du forum dédiée aux projets des membres de la communauté. C'est ici que vous pouvez ouvrir un topic pour présenter votre projet de jeu et en parler. Il y a plusieurs intérêts à faire cela, et en voici une liste :
— Parler de votre projet de jeu pendant son développement et générer une attente autour du projet
— Recevoir des conseils lorsque vous en avez besoin
— Regrouper vos avancées et voir votre propre projet se développer
— Montrer des images en avant-première de votre jeu et donner envie aux gens d'y jouer
— Avoir un gain de motivation pour progresser dans le projet
— Générer de l'activité sur le site

Vous l'aurez compris, les avantages sont nombreux ! Seulement, qu'est-ce qu'il faut mettre dans un topic de projet ? Comment entretenir un tel topic ? Pas de panique, je vous propose de regarder quelques topics sur des projets par des membres de la communauté. Certains projets sont énormes, d'autres plus modestes, mais ils présentent tous des intérêts. Cliquez et regardez à quoi ça ressemble :
Windmill de Ninestars. Un excellent topic. Il y a de nombreux visuels, la description du projet est concise et on comprend vite de quoi il s'agit.
Plague.inc de Shadow15510.Il n'y a pas d'images, mais il y a toutefois une description et des indications claires sur l'avancée du projet.
Casio Ware de Kikoodx. Cette page est soigneusement présentée, et les informations sont hiérarchisées.
Sword Burst Zero, de Redeyes. La page du topic est pleine d'images du jeu, de dessins qui accompagnent le tout, et est assez riche. Un historique des avancées vient indiquer où en est le projet. Les détails techniques sont dans des spoilers.


Arena, un jeu développé par Lephenixnoir avec Gint.

De manière générale, on remarque qu'on retrouve ces éléments qui sont, à mes yeux, tous très importants pour promouvoir votre projet de programmation :
Une description du projet, ou bien de l'idée de projet en cours qui a encore besoin de se construire. Cette description doit être plutôt concise, il n'est pas nécessaire d'écrire des blocs de texte énormes – donc ne faites pas comme moi.
— Des visuels : screenshots du jeu, dessins, ou encore des vidéos de démonstration pour les projets qui prennent forme. On aime voir des images ! Si le lecteur ne lit pas forcément tout le contenu, il est fortement susceptible de regarder les images et donc de s'intéresser au projet.
— Une idée de l'avancée du projet. Cela se fait au fur et à mesure et se met à jour : ce qui a été fait et ce qui reste à faire, voir aussi la partie suivante à ce sujet.
— Éventuellement, ce dont vous avez besoin : la communauté de Planète Casio peut vous apporter de l'aide sur des problèmes techniques, ou bien vous avez peut-être envie d'entamer un projet de groupe.

Enfin, je rajouterais ce commentaire de Ninestars pour compléter le tout :
Ninestars a écrit :
Je pense qu'il faut aussi faire vivre son projet, surtout dans la section "projet de programmation". Le plus simple est de poster régulièrement les avancées, même les petites choses, et surtout faire part de ses difficultés, et comment, ou pas, elles se sont concluent.


Partie II – La Revue des Projets :

La Revue des Projets (RDP) est une revue hebdomadaire qui existe depuis plusieurs années déjà, et qui est faite pour vous ! Tous les membres de la communauté, tous, peuvent soumettre un article pour la RDP, et ainsi faire paraître leur projet en page d'accueil ! C'est un excellent moyen pour faire parler de votre projet et pour lui donner de la visibilité. Le top, c'est d'y ajouter des images. Un rédacteur ou un administrateur se charge ensuite de rédiger la revue et y intègre tous les articles qui ont été publiés dans la semaine.

Voici des exemples de RDP bien fournies, et qui donnent envie !
La RDP 119, une RDP bien fat comme on les aime.
La RDP 116, avec son bon paquet de visuels.
La RDP 127, plus textuelle.
— etc.

N'hésitez donc pas à écrire pour la RDP, car cela génère également de l'activité sur le site. En général, on y écrit pour présenter un nouveau projet, ou bien pour montrer ses avancées et montrer qu'on continue d'avancer. C'est aussi l'idéal pour avoir des retours bienveillants sur votre travail acharné !!!


C'est tout pour cette fois ! Dans la partie suivante, nous verrons d'autres manières encore de mettre en valeur votre jeu. Portez-vous bien !

Liens utiles :
Promouvoir son jeu sur les réseaux sociaux auprès du Community Manager.
La section projets du forum
TDM précédent : Gérer les collisions !

Consulter l'ensemble des TDM


Commentez cette news ! (6)
écrit par Drak le 05/12/2018 18:00 Voir toutes les news

Le puzzle de l'Avent 2018
C'est la période de l'Avent ! Planète Casio vous propose un calendrier aux 24 énigmes pour aiguiser votre sens critique. Parviendrez-vous à trouver la solution de notre puzzle ?

Notre jeu de l'Avent est un jeu de piste. Chaque jour, nous délivrerons sur ce topic divers indices vous menant à la solution du problème. Pour pimenter la recherche, nous vous donnerons toutes les clés de l'énigme bien avant le jour de Noël, mais sans vous dire quand. Êtes-vous prêts à vous mesurer à notre mystère ?

CASIO Education a doté cet événement d'une Graph 90+E ! Le premier à mettre la main sur la solution de l'énigme remportera la machine pour Noël. N'hésitez plus !



Règles du jeu

Le puzzle de l'avent est un jeu de piste constituté de plusieurs énigmes en succession. Vous devrez résoudres dans l'ordre toutes les énigmes pour atteindre la solution. Des indices et des informations sont donnés tous les jours pour vous y aider.

Règle 1. La solution du puzzle comprend deux éléments :
* La reconstitution de l'image dont les pièces sont donnés chaque jour jusqu'à Noël.
* La phrase-mystère.


Règle 2. Le premier membre inscrit qui poste l'image reconsituée et la phrase-mystère, et peut prouver qu'il a suivi toutes les étapes du parcours, remporte le jeu de piste.

En pratique, si vous postez la réponse, nous vous demanderons par MP comment vous avez fait. Si votre méthode est très incomplète ou que vous avez triché, nous changerons légèrement la conclusion du puzzle pour que les autres participants puissent continuer.

Règle 3. Si vous découvrez une suite de 6 lettres et chiffres, gardez-la pour vous.

Ce sont des indices ou des codes importants qui permettent de progresser dans l'énigme. En les révélant, vous permettriez aux autres candidats de griller des étapes.


Liste des indices et pièces de l'image

1er Décembre


2 Décembre


Indice n°1 :
- Les jeunes mammifères boivent mon 1er
- Mon 2nd est une négation à répétition
- Mon 3ème est la cinquième consonne
- La vache fait mon 4ème
- Mon tout en est une

3 Décembre


Indice n°2 :
- Il ne faut pas tomber dans mon 1er
- Mon 2nd exprime un désir solide à la troisième personne du singulier
- Mon tout fait plaisir

4 Décembre


Indice n°3 :
Je peux être sage, ou incarner la violence.
Pour qui sait, je suis source d’information.
Trafiquée je peux mentir, mais véridique je montre la vérité sans détour…

Indice n°4 : Une symétrie en vaut deux...
Indice n°5 : Une pièce peut en cacher une autre...

5 Décembre

Indice n°6 : Quel est le point commun entre un téléphone et une fx-92+ Spéciale Collège ?

6 Décembre


Indice n°7 :
- Mon 1er peut avoir 20 faces, mais rarement plus
- Mon 2nd est en forme
- Mon tout peut être beau et va vous aider à trouver un précédent indice

7 Décembre


Indice n°8 :
- Mon 1er est un vêtement féminin
- Mon 2nd est une exclamation traduisant la peur
- Mon 3ème est « l’aller » anglais
- Mon 4ème est un tiers de cheminée
- Mon tout va vous aider un peu

Indice n°9 : Êtes vous sûr que cette surface est unie ?

8 Décembre


9 Décembre

Indice n°10 : ♫ 0x51, 0x52, f-x 9-2 ♫

10 Décembre

Indice n°11 : La boîte de texte en cache plus que vous ne le croyez.

11 Décembre

Indice n°12 : Papillons et -codes !

Commentez cette news ! (123)
écrit par Lephenixnoir le 01/12/2018 17:47 Voir toutes les news

Le vote du Jeu du Mois de Novembre 2018
Bonjour à tous !
On se retrouve juste avant une période de festivité bien remplie pour notre rendez-vous mensuel qui dure depuis maintenant 5 mois, le vote du Jeu du Mois ! Et ce mois-ci ça va être serré puisque nous avons 8 programme à départager !


Alors le principe et tout bête, nous allons vous soumettre une liste de jeu récemment publiés sur le site. Le but est que dans vos commentaires, vous votiez pour votre jeu préféré. Un classement sera établi dans une semaine pour déterminer le meilleur jeu du mois ! On se dépêche de lire les règles et on y va !

Règles

On ne peut voter qu'une seule fois
Le Top 3 peut contenir des lacunes : vous pouvez ne mettre aucun programme en face des notes.
On ne peut pas voter pour soi-même (Tout vote pour soi est considéré invalide et remplacé par une lacune.)

Exemple de classement : Nous avons les jeux Sony, Mario, Starwars, Zelda, Pizza. J'aime beaucoup Pizza, j'ai bien aimé joué à Mario, sans plus et je n'ai pas aimé les autres :
1-Pizza (3pts)
2-
3-Mario (1pt)
Si j'ai bien aimé Sony mais pas les autres et que je pense que Sony aurait pût être mieux ce vote serait approprié:
1-
2-Sony (2pts)
3-

Si j'ai adoré Mario, Sony et Zelda, mais que je préfère Mario aux deux autres et que je trouve que la prestation de Zelda est bâclée alors mon vote va ressembler à ça :
1-Mario (3pts)
2-Sony (2pts)
3-Zelda (1pt)

Depuis le temps... Faudrait que j'ai le courage de modifier au moins les noms des jeux... non ?

Voici la liste (les jeux sont classés par ordre alphabétique) :


On commence en douceur avec Shadow15510 et son adaptation :
Candy-Crush Alignez 4 items identique pour vider votre ligne. Saurez-vous faire le meilleur score en un minimum de coups ?

On continue avec Thoricelli et son jeu d'action :
Invaders est une reprise du célèbre jeu où les extra-terrestres débarquent. Sauvez la terre !

On arrive à notre 3ème jeu développer par Matcul :
Pixel, une sorte de labyrinthe, un départ, une arrivée, vous, et... des dizianes de pièges à chaque mouvements... Un jeu qui vous fera sursauter en maths !

Un jeu de Lepianoteur à présent :
Poképix où vous devez battre votre adversaire en hot seat : une première en BASIC !

Arrive ensuite un jeu de réflexion créé par Captainluigi :
Slotgame Vous avez une impression de déjà vu ? Quelle mémoire ! Ce jeu est une re-make de Calcpoke du même auteur où le but et de jouer à des jeux d'argents sans argent...

Nous avons ensuite un jeu Tituya :
Stick Hero est un jeu de sport réalisé par Dragonbleu il y a longtemps, depuis, Tituya a repris le concept et vous présente la dernière version du jeu : nouveau personnages, systèmes de score de bau tout neuf : un vrai coup de chiffon sur un vieux projet !

Encore un jeu, c'est génial : celui-ci est de Aziogs :
TLOZ FOG Le tout dernier opus de Zelda débarque sur vos caltos ! Il est encore en développement mais est déjà avancé...

Nous terminons cette liste avec Math680 :
Zelda GAME une adaptation BASIC de Zelda pour les CG90+E, graphismes et animations sont au rendez-vous !

Voila... Nous souhaitons une bonne chance à nos programmeurs en herbe ainsi qu'au plus expérimentés ! Un grand merci à tous les participants et à nos futurs votants qui vont se déchaîner pendant une semaine ! Eh oui, le vote prendra fin le Samedi 8 Décembre en attendant : bon vote !

Commentez cette news ! (5)
écrit par Shadow15510 le 01/12/2018 10:00 Voir toutes les news

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 !


Commentez cette news ! (61)
écrit par Lephenixnoir le 28/11/2018 21:37 Voir toutes les news

La Revue des Projets – 131
En ce moment, profitez avec ivresse de notre offre spéciale Black Friday chez Planète Casio ! Au menu, vos projets favoris se montrent sans complexe !

Et oui, c'est aussi la saison des achats furieux chez Planète Casio ! Si vous aussi, vous avez des blagues douteuses – par « douteuses » j'entends « racistes » – à faire part rapport au Black friday, alors je vous invite à ne pas les dire !

Sans tarder, voici notre première offre très spéciale – par « spéciale », j'entends « spécialement ordinaire » – qui porte sur un grand projet qui mobilise toute une équipe au sein de la communauté ! Il s'agit du projet intitulé « L'Odyssée, la plus grande aventure du siècle sur vos écrans de 128×64 pixels qui vous fera flotter d'euphorie dans le 7ème cosmos » !

…*toussote*

Oh, pardonnez mon enthousiasme. J'ai simplement ajouté une pointe de fantaisie au nom du projet pour vous forcer à consommer. Sans plus attendre, en voici le contenu !

L'équipe de l'Odyssée a écrit :
Coucou tous le monde !

On a un peu avancé notre projet : le cahier des charges commence à se remplir...
:
Présentation du projet
Nom : Odyssée
Langage : C (reprise du projet BASIC)
Modèles de calculatrice visées : Graph 35++/75/85/95 (SD) (+CG90+ ?)
Technologie utilisée : Non définie (à choisir entre Gint, le Fx-SDK, et le Prizm SDK)
Taille : Non définie (mais sans doute vers les 150-200 Ko max)

Les tâches
Les Sprites : Se mettre d'accord pour la taille, les faire, ainsi que les fichiers Sprites.c et le header correspondant
Le moteur Graphique : Gestion et création du design des maps et agencement des éléments dans la carte via la matrice (inclura sans doute la gestion de la mini-map)
Le moteur Physique : va gérer le moteur Graphique avec les collisions. Inclut les lieux d'interactions et l'affichage
Le moteur de Combat : Gestion du temps réel dans les combats avec les attaques via le pavé numérique, la partie théorique des combats est ok
Le moteur de Jeu est le plus important : il regroupe les mécanismes indispensables au jeu, à savoir, la partie scénario, les interactions, la gestion du clavier, la gestion du temps fictif du jeu, les systèmes de niveau du jeu et l'intégration du narrateur
Gestion IA et PnJ : dialogues mouvements, action, et interactions avec le joueur
Le moteur des Dialogues rejoint les intaractions et les PnJ, comprend la partie vente de jeu : objets, armes,...
Gestion des sauvegardes : les variables indispensable à l'avancée du jeu

Bon... Je pense avoir balayer les différents aspect du projets... On le modifiera au besoin. On peut commencer à travailler !

Les Sprites :
Taille : 16*16 ? (+ mini-map)
Couleurs : ? (sans doute monochrome au début)
Dessins déjà fait (monochromes) :
Personnages
Arbres (x2)
Buissons
Design extérieur (mur, portes, fenêtres)
Design toits (x2)
Interrupteur (On/Off) + Levier (3 postions : Gauche, milieu, droite)
petit caillou
Interface joueur "in game" (texte, clafs, vies, rubis, gemmes)
Petit objets divers : rubis, gemmes, vies (coeur), drapeau, fanion, fioles (vide, 1/2, pleine)

Dessins à faire :
Design éléments interne : porte, fenêtre
Design pièce
Meubles : lit, armoire, coffre, bar, chaise, table

On a pas mal ratisser les éléments principaux du jeu. On pensait aussi revoir le système de monnaie : plutôt que d'avoir des Drachmes de Diamant, d'Or, d'Argent, et de Bronze on optera sans doute pour un système à deux niveaux : il y aurait donc des Rubis et des Gemmes et c'est tout ! Le système de Drachmes a l'inconvénient d'être dure à gérer en cas d'achat...

C'est tout pour cette fois mais on espère avoir de neuf sous peu, bientôt les premiers sprites seront sur le Git, on vous donne des images dès que possible !

Eh bien, voila un cahier des charges bien rédigé ! Avec de telles directives, on peut vous assurer, chère clientèle, que le projet ne tardera pas à prendre corps !

Notre deuxième offre est une offre également très spéciale – par « très spéciale », j'entends… oh, laissez tomber. Il s'agit d'un jeu dores et déjà disponible dans nos rayons, j'ai nommé Aventura, le Royaume Poudingue ! Profitez d'une réduction de - 85% sur le téléchargement gratuit de ce dernier ! Tout de suite, un mot de l'auteur de ce jeu super spécial, qui exprime son amour et sa gratitude ! Come on, Darling !

Drak a écrit :
Hello everyone!

J'écris ce petit article pour en revenir sur mon projet de jeu majeur ; Aventura, le Royaume Poudingue. Je voulais vous faire un retour par rapport à ce projet, maintenant que cela fait deux mois que le jeu a été posté dans sa première version !



J'ai donc reçu de nombreux feedbacks de votre part, ainsi qu'un total de 4 notes pour une moyenne de 9.05/10 ! Pas mal, pour un jeu encore bugué. Ce jeu a aussi été élu jeu du mois de Septembre 2018, ce qui est pour moi une grande fierté ! J'avais aussi en tête de demander à ce que le jeu puisse obtenir le label de qualité, mais je ne formulerai pas cette demande officiellement tant que le jeu sera dans cet état...

En effet, à ce jour, la version actuelle ne trace que la moitié de l'histoire, la moitié des terrains à explorer, ne fait pas ressentir les conflits qui traversent le royaume Poudingue, et présente quelques bugs vraiment gênants. L'un d'eux empêche même la progression dans l'histoire !

J'écris donc cet article pour vous signaler que ce projet n'est pas fini. Bien que je sois pleinement occupé par mes études, je pense bientôt tenter d'accorder un peu de temps à ce projet, ne serait-ce que pour corriger les bugs majeurs et faire quelques petites implémentations.

Et, pour le fun, quelques citations :

« Ce jeu est génial ! J'ai joué ( loin d'avoir fini, puisque je me fais defoncer par le rat du sous sol ) et aucun bug à signaler ! », Lightmare

« Je suis tombé sur Massena dans le jeu ! C'est excellent !! », Shadow15510

« Oh... Bordel. Pourquoi j'ai peur ? », Réaction de Massena au commentaire de Shadow15510 ci-dessus.

« Je passe mon temps à me servir du sort 99 enfer cataclysmique, il est époustouflant ! », Redeyes

« Les combats sont vraiment bien, très dynamiques, le principe des couleurs est bien, surtout le fait d’avoir des neutres. Il y a de nombreux sort différents et aussi de nombreux monstres, c’est vraiment génial. », Ninestars

« Ah le royaume Poudingue c'est entre deux méandres d'intestin grêle ? Blague à part je trouve la mappemonde magnifique, bien que le format m'intrigue. », Ne0tux

Si je mets quelques citations, ce n'est pas seulement pour faire de la « pub » pour mon jeu, mais c'est surtout pour vous remercier : tous vos retours m'ont touché et m'ont prouvé que j'étais capable de faire un jeu original qui plaise ! Ce qu'il me reste à faire, c'est de prendre en compte tout ce que vous m'avez dit dans chacun de vos commentaires et tenter d'améliorer le jeu, en sortir une nouvelle version, et répéter le processus… Bref, je vous tiendrai au courant lorsque j'aurais décidé de me remettre au travail sur ce beau projet ! Encore un grand merci à vous !

Et maintenant, sortez votre porte-feuille !

Si vous n'êtes pas encore fauché, il nous reste une petite sélection de programmes tous frais ci-dessous ! Oh my, nous sommes presque en rupture de stock ! Battez-vous !

Cette semaine 1 programme a été posté.
Invaders de Thoricelli, un jeu en Basic pour calculatrices monochromes. Une adaptation simple de Space Invaders, avec un réglage de la difficulté. En solde !

Bénéficiez d'offres spéciales sur la rédaction de vos articles pour la RDP !

- 30% sur la lecture de la RDP précédente : RDP 130

Commentez cette news ! (30)
écrit par Drak le 25/11/2018 18:00 Voir toutes les news

TDM n°9 – Gérer les collisions !
Le Tuto Du Mercredi [TDM] est une idée qui fut proposée par Ne0tux. Un mercredi sur deux, nous postons un tutoriel sur l'Utilisation de la calculatrice, le Transfert, les Graphismes, la Programmation, ou encore la Conception de jeu. Ce TDM-ci en explique un point important et des fois compliqué ! Mention spéciale à Ninestars qui a rédigé le contenu de cette édition.

TDM n°9 – Comment gérer les collisions d'un personnage ?

Niveau : ★ ★ ★ ★ ☆

Tags : Basic Casio, Jeux, Collision, Personnage

Comment faire un système qui permet de gérer les collisions d'un personnage avec le décor, ou avec tout autre chose ? Nous allons détailler plusieurs méthodes possibles dans ce TDM.

Hypothèses : Nous nous plaçons dans le cas d'un jeu vu de haut, avec un personnage qui peut se déplacer selon deux axes. On suppose également que la carte dans laquelle se déplace le joueur est composée de tiles – tuiles en français. On parle souvent de Zelda-like.

Le personnage que déplace le joueur est positionné grâce à deux variables : U et V, respectivement l'abscisse et l'ordonnée. On suppose que le coin inférieur bas est l'origine du repère, c'est-à-dire que U et V valent 0 à cet endroit.

Plan d'action :

Dans la boucle principale du jeu, il faut réaliser ces actions dans un ordre précis :
1) L'action du joueur sur son clavier va modifier la valeur de ces variables
2) On vérifie si le joueur sort de la carte
3) On vérifie si la position souhaitée est bloquée
4) On vérifie si la position souhaitée déclenche une action
5) Si oui, déplacer le joueur ou déclencher l'action


Partie I – Que veut faire le joueur ?

La meilleure méthode pour gérer l'action du joueur est d'utiliser des variables intermédiaires enregistrant la position souhaitée ; nous utiliserons donc I et J. Ensuite il y aura un tas de conditions à remplir, et si tout va bien, la position souhaitée deviendra la position du joueur.

Début de l'exemple :

5->U
3->V
...
Do // début de boucle
U->I
V->J //On initialise I et J
While 1 // Sous-boucle, qui nous sert de raccourci avec la commande Break
Do
GetKey->G
LpWhile Not G //la boucle tourne tant que le joueur n'actionne pas de commande
G=37⇒Dsz J //↓
G=38⇒Dsz I //←
G=27⇒Isz I //→
G=28⇒Isz J //↑
If I≠U Or J≠V //Si le joueur a appuyé sur une touche directionnelle
Then
// la suite en partie II
IfEnd
I->U
J->V
WhileEnd
LpWhile 1 // fin de boucle

I et J donnent la position désirée par le joueur. En plus on peut savoir si le joueur a souhaité se déplacer en vérifiant que I≠U ou J≠V. Il est plutôt important d'utiliser cette condition pour éviter de vérifier les collisions, donc avoir un jeu plus fluide, et éviter le clignotement de l'écran. En effet pas besoin de redessiner l'écran si rien ne change !


Partie II – Le joueur sort-il de la carte ?

Pour cela, il suffit de vérifier si la position souhaitée est en dehors de la carte. Soit une carte de dimensions W (width ; la largeur) et H (height ; la hauteur) :
If I<0 Or I>W Or J<0 Or J>H // Si le personnage sort de la carte
Then
// Alors on apporte les modifications nécessaires...
Break //On sort de la sous-boucle
Else
// Sinon, le personnage reste dans la carte
// la suite en partie III
IfEnd

En fonction du jeu, soit on bloque le joueur, soit on change la carte.
Pour bloquer le joueur, il suffit de sauter avec un Break qui nous amène à la fin du code (juste après le WhileEnd) : le changement des coordonnées du personnage est donc sauté. Il reste alors à sa place.


Partie III – La position souhaitée est-elle atteignable ?

À partir de maintenant, tout va dépendre de la façon dont l'information de la carte est enregistrée.
Il existe plusieurs méthodes, certaines très efficaces, d'autre moins.

Première méthode : La matrice
C'est la méthode triviale ; il suffit d'enregistrer de façon naturelle la position des objets sur la carte, dans une matrice de la taille de la carte. Dans cet exemple, la matrice Mat A fait 16×8 cases et par défaut est remplie de 0.


Les autres nombres correspondent à des objets sur la carte : ce peut être un personnage, une rivière, un arbre, un mur, une maison, un coffre... La valeur indique la nature de l'objet.

Ici il suffit de vérifier que la valeur est 0 :
If Mat A[I,J]=0 //s'écrit aussi If Not Mat A[I,J
Then
// dans ce cas rien ne bloque le joueur
// la suite partie V
IfEnd



Partie IV – Déclencher une action ?

Juste à la suite, on peut ajouter des conditions sur la nature de l'objet, et exécuter du code à ce moment là.
If Mat A[I,J]=3
Then // action
IfEnd

Il peut y avoir des subtilités, par exemple si un objet est présent (donc la case de la matrice est différente de 0) mais que le joueur peut passer au travers. Dans ce cas, il suffit de gérer l'exception :
If Mat A[I,J]=7
Then
// le joueur peut passer au travers
// la suite partie V
// action
IfEnd

Une méthode autre serait d'identifier les éléments que le joueur peut traverser (herbes, escaliers, etc.) par une valeur négative et ceux qu'il ne peut pas traverser (murs, arbres, rivières, etc.) par une valeur positive, plutôt que de gérer plein d'exceptions :
If 0<Mat[I,J //Si la valeur est strictement positive
Then Break //Le joueur est bloqué, on sort de la sous-boucle
Else //Sinon, c'est que la valeur est nulle ou négative : on peut passer !
//On gère ici les exceptions, les éventuelles actions en fonction de l'objet traversé
IfEnd



Partie V – Déplacer le joueur :

Dans tous les cas, si le joueur peut aller où c'est possible, il suffit de faire I->U:J->V pour que la position souhaitée du joueur deviennent la position réelle.
I->U
J->V


Code final avec indentation :
5->U //début de programme
3->V
...
Do // Boucle principale
    U->I
    V->J
    While 1 // Sous-boucle, qui nous sert de raccourci
        Do
            GetKey->G
        LpWhile Not G
        G=37⇒Dsz J //↓
        G=38⇒Dsz I //←
        G=27⇒Isz I //→
        G=28⇒Isz J //↑

        If I≠U Or J≠V //Si le joueur a appuyé sur une touche directionnelle
        Then
            If I<0 Or I>W Or J<0 Or J>H // Si le personnage sort de la carte
            Then
                // Alors on apporte les modifications nécessaires...
                // Par exemple, on change I et J et on entre dans un sous-programme pour gérer cela.
                Break //On sort de la boucle
            Else
                // Sinon, le personnage reste dans la carte
                If 0<Mat[I,J] //Si on ne peut pas passer
                Then
                    Break //On sort de la sous-boucle ; U et V ne sont pas modifiées
                Else
                    If Mat[I,J]<0 //Si la valeur est négative
                    Then //On gère les éventuelles exceptions
                    IfEnd
                IfEnd
            IfEnd
        IfEnd //La fin de nos quatre If
        I->U
        J->V
    WhileEnd
LpWhile 1


Code final sans commentaire :

5->U
3->V
...
Do
U->I
V->J
While 1
Do
GetKey->G
LpWhile Not G
G=37⇒Dsz J
G=38⇒Dsz I
G=27⇒Isz I
G=28⇒Isz J
If I≠U Or J≠V
Then
If I<0 Or I>W Or J<0 Or J>H
Then ...
Break
Else
If 0<Mat[I,J
Then Break
Else If 0>Mat[I,J
Then ...
IfEnd:IfEnd:IfEnd:IfEnd
I->U
J->V
WhileEnd
LpWhile 1


Méthodes alternatives

Ces méthodes ne sont pas forcement plus rapides, ou plus simples. D'ailleurs certaines ne sont pas adaptées au Basic.

Méthode par recherche :

La méthode des matrices est simple, rapide, mais la carte est très granuleuse et sa taille est vite limitée par une consommation de mémoire excessive. En effet, une grande carte sera en majorité remplie de 0, c'est du gâchis.
La méthode par recherche consiste à enregistrer dans une Matrice Mat en Basic, ou un tableau de structures en C, l'ensemble des objets présents sur la carte, ainsi que leurs coordonnées. Puis quand le joueur souhaite se déplacer, rechercher dans l'ensemble de ce tableau si un objet à les mêmes coordonnées que la position souhaitée.


0->F
For 0->K To Nombre d'objets
If I=Mat A[K,1] And J=Mat A[K,2]
Then
// collision avec l'objet ID Mat A[K,3]
1->F
// passer à la partie IV
IfEnd
Next
If F=0
Then I->U:J->V
IfEnd

F est un flag servant à savoir s'il y a eu une collision avec au moins un objet. Si F=0 alors il n'y a pas eu de collision et on déplace le joueur.

De cette manière, il est même possible de définir la largeur et la hauteur des objets, il suffit de modifier la condition pour que I et J ne soit plus strictement égaux, mais compris dans les intervalles.

Cette méthode est assez peu adaptée au Basic vu quelle nécessite plus calcul. Néanmoins le calcul listique peut accélérer la recherche. En C, cette méthode est très efficace, et les performances de la calculatrice sont (vraiment) largement suffisantes, même pour 300 objets.

Méthode par équation :

Cette méthode est plutôt utilisée pour des collisions d'objets avec des formes complexes, et pas forcement alignées sur le repère.
Supposons qu'un mur soit défini par deux points A et B. Des calculs permettent de savoir si le personnage de coordonnées (U;V) est à gauche ou à droite de la droite. Si il passe de gauche à droite, ou de droite à gauche, c'est que le joueur croise le mur, donc il y a collision.

Ce test peut être réalisé avec l'équation paramétrique de la droite, ou avec le signe du produit scalaire. Ces segments peuvent être mis bout-à-bout pour former une forme complexe, ouverte comme fermée. Plus d'informations sur les technique de calcul de collision en fin de page parmi les liens utiles.


C'est ainsi que se finit le neuvième TDM, dense et assez spécial puisque Ninestars en a rédigé le contenu ! Je tenais à m'excuser auprès de lui pour les quelques légères modifications que j'ai apporté à son code : je préfère ne pas avoir de Lbl !

Liens utiles :

En apprendre davantage sur les différentes méthodes de collisions sur le Site du Zéro !
Consulter l'ensemble des TDM disponibles.
Soumettre des suggestions de TDM sur cette page !

Commentez cette news ! (24)
écrit par Drak le 21/11/2018 18:00 Voir toutes les news

Résultats du triconcours : les plus forts !
Nous sommes de retour pour les résultats de la seconde épreuve du triconcours, l'épreuve de force !

Il y a eu 15 participants en tout, sensiblement comme à la première épreuve, mais cette fois 120 soumissions ! La bataille a été dure pour allumer les bons potentiomètres aves les bons niveaux, clé à molette en main. Étonamment, vous avez presque tous utilisé la NumWorks pour cette épreuve. Est-ce pour son émulateur en ligne ? Dites-nous tout !

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

Le classement des participants

13. On a d'abord Extra44, qui allume 215 lampes et récolte 188.1 points et la 13ème place du classement.


12. Vient ensuite Email address, replace the 【arobase】 with a @ and ▶ with a . : ggauny【arobase】live▶fr, l'un des seuls à avoir utilisé une HP Prime pour résoudre cette épreuve en allumant 236 lampes et 210.9 points : il atteint la 12ème place.


11. nicodu95 atteint la 11ème place avec sa solution à 216.4 points en 239 lampes.


Les grands gagnants : les plus forts !

10. Alexmaster350 se hisse dans le classement en illuminant 242 lampes pour un total de 217.7 points.


9. La 9ème place revient à Anonyte pour ses 243 lampes (quel sapin de Noël !) qui lui concèdent 219 points.


Les participants suivants nous ont même donné des explications ! Alors, comment ont-ils faits pour atteindre ces scores records ?

8. À la huitième place, Zezombye exploite un algorithme glouton lancé sur des configurations aléatoires pour atteindre 221.3 points au moyen de 244 lampes allumées. [#159394]


Zezombye a écrit :
Moi pareil : j'ai fait des entiers de 0 à 93 au lieu d'utiliser des fractions.

J'ai tout d'abord essayé une approche avec peu de potentiomètres : essayer toutes les combinaisons de 1, 2, 3, 4 potentiomètres et regarder laquelle allume plus d'ampoules. Mais si je me souviens bien, on peut allumer un maximum de 212 ampoules avec 4 potentiomètres (et mon bruteforce allait pas au delà) : comme le score peut pas être supérieur au nombre d'ampoules allumées, il fallait forcément alimenter tous les potentiomètres.

Du coup après j'ai essayé (comme le disait hackcell) en mettant tous les potentiomètres à une valeur : un peu de bruteforce et on trouve que le score atteint un sommet pour 8 ou 9 (fractions de 93). Du coup je fais un bruteforce pour mettre tous les potentiomètres à 8 ou 9 : j'atteins 215 maximum, pas assez...

Après j'ai fait une fonction "convergeuse" qui prend une combinaison (celle générée avec les 8 et 9) et diminue un potentiomètre de 1, en choisissant ce potentiomètre de telle sorte à ce qu'il fasse perdre le moins de score (ou gagner le plus). Avec ça je crois que je suis allé dans les 217/218.

Enfin, j'ai fait une boucle infinie qui prend des valeurs aléatoires pour chaque potentiomètre entre 7 et 12, avec ensuite ma fonction convergeuse qui traite chaque combinaison. Là je suis allé facilement dans les 220, avec un score à 221.274 (mon final) après quelques dizaines de minutes (mais j'ai été chanceux).

Sur les conseils de DS, j'ai fait un algo pseudo-génétique qui génère 100 combinaisons, prend les 30 meilleures et change quelques valeurs : j'atteins 221.3, mais toujours pas assez. (si je m'y étais pas pris le jour même, j'aurais peut être pu le laisser tourner un peu plus longtemps )

Par contre pavel : j'ai hâte de voir ton algo pour la 3ème épreuve, ça m'a l'air assez dur à algorithmiser ça...


7. Plus redoutable encore, Hackcell allume 244 ampoules mais sans en griller aucune autre, s'attribuant un score de 221.6 points ! [#158330]


Bon, le miracle attendu n'a pas eu lieu (j'ai gagné environ 0.2 point).

J'avais pour intention de bricoler un autre algorithme de recherche de maximum basé sur une sorte de gradient à 30 dimensions, mais je me suis arrêtée 5 minutes pour regarder la suggestion de DS, un algorithme génétique, résultat, j'en ai codé un en une bonne heure, la page Wikipédia qui explique comment réaliser un telle algorithme est plutôt bien faite, donc au final j'ai pas eu tant besoin de réfléchir, j'ai pas eu besoin de café, en revanche, j'aurais sans doute besoins de chance

Donc merci DS pour ta suggestion.

Pour être plus précis, voici les paramétrés de mon algo:
— Population : 100 individus
— Génome : 30 chiffre de 0 à 1
— Système de score : Celui de base pour le concours
— Sélection : Trie des individus par score en commençant par le meilleur, choix des accouplements via un (np.random.random()*10)**2 (pas optimal, je pourrais gérer ça de manière plus souple, mais ça ira pour l'instant). Je réalise 49 accouplements, puis j'ajoute le meilleur de la génération précédente s'il ne s'est pas reproduit et complète avec des individus aléatoires.
— Empattement : 70%
— Mutation : 1% (Avec du recul, je devrai l'augmenter un poil)

Et puis c'est tout, pour l'instant ça grimpe gentiment et j'en suis à 210,7 points

[Plus tard]
L'algorithme commence à sortir des maximum, sauf qu'il a un peu de mal a s'extraire de ces maximum locaux, il est temps de tourner les boutons pour voir ce que ça fait

6. La 6ème position revient à Erwin R., notre deuxième utilisateur de HP Prime qui prouve qu'avec 243 lampes on peut atteindre 221.8 points et battre des configurations à 244 lampes ! Il a publié un article sur son blog à ce sujet.


From what I can say from the description indicates that you control 30 potentiometers with weird interconnections, with the goal of lighting the maximum amount of lights. Playing the game in your calculator goes like this:

1. Run the app
2. Type pot(number,value)
3. See results/score
4. Go to step 2

Of course it goes really slow. So the optimal solution is descramble the app code to understand the function they are using… but this is a lot of work! so I just decided to use bruteforce, starting with a random seed and iterating per potentiometer in increments of 1/34:

The script dumps the best combinations as .txt files. It was very exciting to check the new scores every morning. Like scratching a lottery ticket.

This is also slow, but is not THAT slow if you use multiples machines with multiple instances of the script running. You can even use your cluster made of old laptops that nobody wants in your office, laptops in beautiful racks made of cardboard.

My score was not the best or near the first places, in fact was #6, but I had a lot of fun. Next time I will try to use less brute-force.

Even when my solutions were lazy and poorly executed, I think this is the real nature behind the love for the calculators. Having doses of entertainment in a restricted environment.

It is so special to be in 2018 and still have contest like these french ones. I am happy for that today.


Mention honorable pour Dark Storm, qui ne peut pas participer au concours car il était Administrateur lors de sa préparation, mais qui atteint 222.9 points avec ses 245 lampes ! [#159786]


Pour ma part, je suis parti sur un algo génétique assez "brut", dont je pouvais faire varier les paramètres en live à chaque génération, pour introduire de grosses modifications du génome, ajouter des configurations intéressantes, ou bien recentrer autour d'un point.

Ça a tourné sur le VPS pendant deux ou trois jours, j'arrive à un score de 225 et des poussières.

Les derniers rapports générés sont dispo sur mon VPS : https://files.darks.fr/concours/
Je mettrais aussi le code dans le même dossier une fois chez moi.

5. De retour dans la compétition, Nemhardy rafle la 5ème place en activant 247 lampes et 225.7 jetons de score ! [#159282]


(Après avoir tapé un peu trop d'une traite, je me rends compte que c'est peut-être un poil long, pour pas grand chose non plus… mais je voulais présenter un peu toute ma démarche, qui peut rester intéressante si vous n'avez jamais entendu parler de programmation linéaire, ou d'utilisation de glpk… Ne serait-ce que pour voir comment ça peut servir… On va dire que ça va dans le sens de PC qui peut servir à introduire à différents concepts autour de l'informatique ! Un jour je mettrai ce genre de post trop long dans un blog qui n'existe pas encore… )

Donc, personnellement, j'ai atteint un score de 225,699.

Mon approche a été encore une fois (comme l'an dernier déjà… ) pas d'une extrême intelligence d'analyse de l'instance qui nous était donnée, mais c'était un premier jet et je voulais voir jusqu'où on pouvait aller avec, avant de passer à autre chose… ce que je n'ai pas fait par une lecture trop peu lucide des modalités du concours… Enfin, passons là dessus !

Déjà pour ceux qui connaissent, l'intitulé rappelle bien vite le problème Illumination dispo sur www.primers.xyz, où le but est aussi d'allumer un maximum d'interrupteurs à l'aide d'un ensemble d'interrupteurs branchés en va-et-vient ; ici la nuance c'est l'aspect continu dans l'actionnement des interupteurs, puisqu'on passe de boutons dans Illumination à des potentiomètres ici.

Même s'il semble que ça peut rendre le problème plus compliqué (l'espace des configurations augmentant alors de manière assez incontrolée), il s'avère que pas mal de problèmes sont en fait plus facile à résoudre lorsqu'on vit dans un espace continu (typiquement dans un tel espace, on peut «glisser» d'une configuration l'autre sans soucis, et, avec un peu de chance, avoir notre fonction objectif continue le long du glissement, nous ouvrant alors la voie à de l'optimisation en glissant de manière maligne parmi les configurations, là où dans un espace certes plus réduit, mais discontinu, il est plus difficile de lier deux configurations différentes, puisque ça revient à faire des sauts, et un peu tout comme n'importe quoi peut se passer lors de ces sauts).

Dans un premier temps j'ai essayé de résoudre des versions simplifiées du problème, pour voir les scores qu'on peut tout de même en tirer. En lisant l'analyse faite par Hackcell plus haut (encore une fois, c'était chouette de partager ça ! ), un problème simplifié qui vient à l'esprit peut être le suivant :

On cherche à allumer toutes les ampoules (ie. à faire passer
la valeur des ampoules au dessus de 1, chacune), tout en minimisant la
somme des valeurs des interrupteurs (ça peut paraître un premier moyen
de limiter le gaspillage).

On n'a aucune garantie que ce problème simplifié va donner quoi que ce soit de bon vis à vis du problème initial, mais ça me semblait un bon début pour prendre le tout en main.

Si on étudie un peu le fonctionnement des ampoules et de leurs potentiomètres, on s'apperçoit que la valeur de chaque ampoule n'est autre que la somme des valeurs des potentiomètres qui la commandent, en particulier c'est une combinaison linéaire de ces valeurs. La fonction que l'on cherche à minimiser l'est aussi : bingo ! On a en fait là un programme linéaire à résoudre, et ça, et bien on sait bien faire ! Des solveurs efficaces existent déjà, et normalement on n'a plus qu'à encoder notre problème pour un de ces solveurs et voir ce qu'il nous sort. C'est ce que j'ai fait pour ce premier problème simplifié, en utilisant le solveur glpk. Mon encodage du problème en MathProg ressemble à ça :


set potentiometres := (0 .. 29);
var pot{p in potentiometres};

set ampoules := (0 .. 251);
var amp{a in ampoules};

param amp_vers_pot{a in ampoules, p in potentiometres};

minimize consommation: sum{p in potentiometres} pot[p];
    s.t. reseau{a in ampoules}:
        amp[a] = sum{p in potentiometres} amp_vers_pot[a,p]*pot[p];
    s.t. allume{a in ampoules}:
        amp[a] >= 1;
    s.t. plage_potentiometre{p in potentiometres}:
        0 <= pot[p] <= 1;
solve;

printf 'config = [';
printf '%.3f', pot[0];
for {p in (1..29)}
    printf ', %.3f', pot[p];
printf ']\n';

data;

param amp_vers_pot: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 :=
    0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1
    2 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 1
    3 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0
    4 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0
    5 0 0 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0
    6 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1
    7 0 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1
    8 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1
    9 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0
    10 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0
    11 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1
    12 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 1
    13 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0
    14 0 0 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0
    15 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0
    16 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0
    17 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0
    18 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 0
    19 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1
    20 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1
    21 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1
    22 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 1
    23 0 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0
    24 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1
    25 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0
    26 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1
    27 1 1 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0
    28 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0
    29 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0
    30 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0
    31 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0
    32 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 0 0 0 0
    33 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1
    34 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 1
    35 1 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1
    36 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1
    37 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1
    38 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1
    39 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0
    40 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0
    41 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0
    42 0 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0
    43 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1
    44 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0
    45 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0
    46 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1
    47 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0
    48 1 1 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 1 0
    49 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0
    50 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0
    51 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0
    52 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1
    53 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1
    54 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0
    55 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 1 1 1
    56 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0
    57 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 1
    58 1 0 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0
    59 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1
    60 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1
    61 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0
    62 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1
    63 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
    64 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0
    65 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1
    66 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0
    67 1 0 0 0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1
    68 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 1 1
    69 0 1 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0
    70 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0
    71 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0
    72 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1
    73 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1 0
    74 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0
    75 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1
    76 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 0 1
    77 1 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0
    78 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1
    79 1 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0
    80 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1
    81 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0
    82 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1
    83 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 1
    84 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0
    85 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0
    86 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1
    87 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0
    88 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1
    89 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0
    90 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1
    91 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1
    92 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1
    93 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1
    94 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1
    95 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
    96 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0
    97 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 0 1 0
    98 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0
    99 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0
    100 0 0 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1
    101 0 1 1 1 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1
    102 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0
    103 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0
    104 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0
    105 0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0
    106 1 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 1 0 1
    107 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0
    108 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0
    109 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1
    110 1 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
    111 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0
    112 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0
    113 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0
    114 0 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0
    115 1 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0
    116 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1
    117 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1
    118 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0
    119 0 1 1 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0
    120 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 1
    121 0 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 1
    122 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
    123 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0
    124 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0
    125 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1
    126 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0
    127 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0
    128 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1
    129 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0
    130 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0
    131 0 1 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 0
    132 1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0
    133 0 1 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 1
    134 1 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0
    135 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0
    136 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1
    137 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0
    138 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 1
    139 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1
    140 0 1 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1
    141 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0
    142 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 0
    143 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0
    144 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0
    145 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 1 0 1 0 0
    146 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 1 1 1 1
    147 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 1
    148 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1
    149 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1
    150 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 1 0
    151 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0
    152 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0
    153 1 1 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0
    154 0 0 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0
    155 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0
    156 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0
    157 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0
    158 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0
    159 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1
    160 0 0 1 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 0
    161 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0
    162 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0
    163 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1
    164 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0
    165 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1
    166 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 1 1
    167 0 1 1 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1
    168 1 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1
    169 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0
    170 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1
    171 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0
    172 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1
    173 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1
    174 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 1 1
    175 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0
    176 1 1 0 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 1
    177 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1
    178 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1
    179 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0
    180 0 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1
    181 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1
    182 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1
    183 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0
    184 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0
    185 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 0
    186 0 1 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1
    187 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0
    188 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1
    189 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 0
    190 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1
    191 0 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0
    192 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0
    193 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0
    194 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1
    195 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 0
    196 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1
    197 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1
    198 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0
    199 1 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1
    200 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1
    201 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 0
    202 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 0 1 1 1 0
    203 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0
    204 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1
    205 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0
    206 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1
    207 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1
    208 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0
    209 1 0 0 0 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0
    210 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 0 0
    211 1 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1
    212 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0
    213 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1
    214 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1
    215 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0
    216 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1
    217 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1
    218 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0
    219 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1
    220 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 0
    221 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0
    222 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0
    223 1 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1
    224 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1
    225 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1
    226 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 0 0
    227 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1
    228 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0
    229 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0
    230 0 1 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 1 0
    231 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 1 1 0
    232 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 1
    233 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1
    234 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 1
    235 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1
    236 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0
    237 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1
    238 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0
    239 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1
    240 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0
    241 0 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0
    242 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1
    243 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1
    244 0 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 0
    245 0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1
    246 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1
    247 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0
    248 0 1 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 0
    249 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1
    250 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0
    251 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 0 0 0 0;

end;


Je détaille rapidement ce qu'il se passe là, je me dis que ça peut toujours servir à quelqu'un qui aurait un bout de programme linéaire à encoder et résoudre un jour.

Donc, sans détailler trop la syntaxe, on déclare là les tableaux potentiometres et ampoules qui contiennent juste la liste des indices des ampoules et potentiomètres en jeu dans le problème, qui vont permettre d'itérer avoir à hardcoder les plages (0 .. 29) et (0 .. 251) à chaque fois… question de bon goût juste ! Ensuite on déclare les variables pot et amp, qui sont en fait des familles de variables respectivement indexées par potentiometres et ampoules, et qui vont permettre d'encoder la valeur à laquelle on règle chaque potentiomètres et les valeurs correspondantes des ampoules. On ajoute aussi un gros tableau de paramètres qui permet de lier chaque ampoule aux interrupteurs qui la contrôlent (à bien sûr ne pas taper à la main, mais bidouiller un peu le script forcecas.py pour le générer ). Ne reste plus alors qu'à décrire le programme linéaire que l'on veut résoudre :


minimize consommation: sum{p in potentiometres} pot[p];
    s.t. plage_potentiometre{p in potentiometres}:
        0 <= pot[p] <= 1;
    s.t. reseau{a in ampoules}:
        amp[a] = sum{p in potentiometres} amp_vers_pot[a,p]*pot[p];
    s.t. allume{a in ampoules}:
        amp[a] >= 1;
solve;


Comme on l'a dit plus tôt, on veut minimiser l'intensité totale en sortie des potentiomètres, c'est ce qu'indique la première ligne : on minimise la somme des pot[p] pour p qui décrit potentiometres. On indique ensuite les contraintes qui spécifient notre problème (les s.t. sont à lire comme such that, c'est à dire tel que en français) : on veut que chaque potentiomètre ait une valeur entre 0 et 1 (ce sont les contraintes plage_potentiometre{p}, on a une telle contrainte par potentiomètre), que chaque ampoule ait la valeur qui lui soit attribuée par le réseau de potentiomètres (contrainte reseau, on utilise à cet endroit notre gros tableau de correspondance et calcule simplement la bonne combinaison linéaire des valeurs des potentiomètres) et enfin que chaque ampoule soit allumée (donc de valeur supérieure ou égale à 1) (ce sont les contraintes allume{a}). L'important est que toutes nos contraintes ainsi que ce que l'on veut maximiser ou minimiser soit linéaire en les variables que l'on a déclarées.

Je ne sais si c'est très clair ou utile à toustes tout ça, mais je voulais montrer un peu la tête d'un fichier en MathProg, je trouvais ça sympa !

Les quelques lignes restantes sont juste là pour formater la sortie du programme (je voulais récuperer une ligne que je n'avais plus qu'à coller dans un fichier python et qui spécifierait les valeurs de chaque interrupteurs) et ne sont pas très intéressantes.

Il ne reste plus qu'à lancer le solveur sur notre programme avec glpsol --math programme_simple.mathprog. On obtient instantanément la ligne

config = [0.023, 0.223, 0.023, 0.000, 0.164, 0.132, 0.139, 0.191, 0.115, 0.146, 0.081, 0.094, 0.359, 0.083, 0.038, 0.159, 0.000, 0.000, 0.000, 0.001, 0.242, 0.158, 0.064, 0.156, 0.078, 0.105, 0.000, 0.000, 0.123, 0.068]

Là tout content on se décide à tester cette solution du problème simplifié comme solution du problème initial et là, déception… On obtient un score d'à peine un peu plus de 204. Plus en détail, on a :


All+Grill:232+20/252
Alimentat:2.989247311827957
Pertes   :0.0
Gaspillag:123.46236559139786


On constate que l'on allume bien toutes les ampoules, comme prévu, enfin en tout cas elles sont toutes à une valeur plus grande que 1, mais certaines sont grillées (on pouvait s'y attendre, vu qu'on a jamais dit à notre programme de faire attention à ça). En plus, malgré notre minimisation de la valeur totale en sortie des interrupteurs, le gaspillage reste significatif : c'est normal, puisque le gaspillage dépend de ce que font les ampoules du courant en sortie, et non simplement de la valeur de la sortie. Il va falloir raffiner.

Premier raffinement assez intuitif qui vient à l'esprit : éviter de griller des ampoules. Pour ce faire, il suffit a priori juste de changer s.t. allume{a in ampoules}: amp[a] >= 1; en s.t. allume{a in ampoules}: 1 <= amp[a] <= 2;. On relance le solveur, et obtient là la sortie suivante LP HAS NO PRIMAL FEASIBLE SOLUTION. Bon. En gros, ça nous apprend qu'il n'existe aucune configuration de potentiomètre telle qu'ont puisse allumer les 252 ampoules en même temps sans en griller aucune, même si ça ne nous avance pas vraiment, je trouve intéressant qu'on puisse obtenir ce genre d'information aussi facilement.

À partir de là, on peut penser à plusieurs pistes : on peut essayer de déterminer le nombre minimal d'ampoule que l'on accepte de griller tel qu'on puisse allumer toutes les autres. On sait que ce nombre est plus grand que 0, et inférieur à 20 (on a trouvé qu'on pouvait tout allumer en en grillant 20, avec notre premier programme). Si ce nombre est entre 1 et 5, on peut espérer le trouver relativement rapidement en bruteforcant les cas possibles (c'est à dire en testant toutes les configurations où on autorise explicitement telle et telle ampoule à être grillées), mais s'il est plus grand, ça me paraît plus délicat en passant par un bruteforce du genre. Je n'ai pas fait cette analyse comme ça, mais je me dis a posteriori que ça doit être intéressant !

J'ai plutôt petit à petit intégré les aspects du problème initial dans mon problème réduit. Je ne vais pas tout détailler, mais notamment si on regarde un peu plus en détail, le problème initial n'est pas non plus si continu (et donc pas si linéaire…) que ça, le score étant calculé différemment selon des paliers de valeurs pour les ampoules (entre 0 et 1, entre 1 et 2 puis entre 2 et l'au-delà). En fait on peut ruser un peu pour encoder ce genre de notions dans le programme linéaire : en MathProg, on peut forcer certaines variables à valoir soit 0 soit 1, par exemple avec var est_allume{a in ampoules}, binary;. Il faut toujours se rappeler que l'on a pas le droit d'utiliser des conditions ou des fonctions comme min ou max ou autre dans un programme linéaire, ou tout doit être… et bien linéaire ! On peut ruser comme je le disais : si vous maximisez la somme des est_allume[⋅], avec les contraintes est_allume[a] <= amp[a], lorsque amp[a] sera supérieure à 1 (donc l'ampoule allumée), et bien comme on cherche à ce que la somme des est_allume[⋅] soit maximale, on aura tout intérêt à mettre toutes les variables correspondant à des ampoules allumés à une valeur la plus grande possible, ici 1. En revanche lorsque l'ampoule est éteinte, c'est que amp[a] est inférieure strictement à 1, et donc est_allume[a] ne pourra pas prendre d'autre valeur que 0. En revanche abuser de telles valeurs booléennes tend à augmenter la complexité du problème, pour les raisons décrites plus tôt (le solveur doit encaisser les «sauts», ce qui revient globalement à énumérer des possibilités, même s'il est assez malin pour pouvoir faire ça assez vite dans pas mal de cas, il ne peut pas tout faire, en particulier pas résoudre des problèmes NP-complets plus vite que la musique ! )

Le programme qui m'a permis d'atteindre la solution que j'ai soumise est le suivant (je ne l'ai pas trop nettoyé, donc il est peut-être pas très très lisible, mais bon, il reprend grosso modo les idées décrites plus tôt), avec quelques trucs hardcodés parce-que sur le moment ça me semblait intéressant… sûrement… x)


set switches := (0 .. 29);

var s{k in switches};

set bulbs := (0 .. 251);

param b2s{i in bulbs, k in switches};

var b{i in bulbs};
var sig{i in bulbs}, binary;

var alpha{i in bulbs};

maximize score: sum{i in bulbs}sig[i] - sum{i in switches}alpha[i];#s[i];
    s.t. alp{i in bulbs}: alpha[i] >= 0;
    s.t. alpi{i in bulbs}: alpha[i] >= b[i]-1.66;
    s.t. foo{i in bulbs}: b[i] = sum{k in switches} b2s[i,k]*s[k];
    s.t. lit{i in bulbs}: b[i] >= sig[i];
    s.t. still{i in bulbs}: b[i] <= 1.9;
    s.t. rest{k in switches}: 0 <= s[k] <= 1;
solve;

printf 'aff = [';
printf '%.3f', s[0];
for {k in (1..29)}
    printf ', %.3f', s[k];
printf ']\n';

data;

param b2s: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 :=
    0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1
    2 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 1
    3 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0
    4 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0
    5 0 0 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0
    6 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1
    …
    …
    …
    248 0 1 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 0
    249 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1
    250 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0
    251 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 0 0 0 0;

end;



Le score 225,699 que l'on obtient n'est pas trop mal, et on l'obtient en quelques secondes, mais il faut savoir qu'il y a quelques soucis qui font que l'approche que j'ai développée jusque là ne permettrait pas je pense de faire bien mieux. Déjà le côté continu des potentiomètres est en fait discutable puisque, notamment pour les raisons qu'a bien et gentiment décrites Critor plus tôt, ceux-ci prennent en fait leurs valeurs dans une plage de 94 valeurs possibles, ça peut sembler suffisant pour approximer du continu, mais cela adjoint aux paliers pose un soucis : globalement on va essayer de faire coller les valeurs des ampoules le plus possibles à la valeur 1.0, le truc c'est que lorsqu'on ajoute des arrondis, et bien on peut avoir tendance à passer très légèrement en dessous de 1.0, et même si c'est peu, c'est suffisant pour changer de palier (l'ampoule n'est plus allumée, et donc le calcul du score erroné). Si on voulait tout de même tout encoder on s'approcherait de plus en plus de la résolution d'un problème vraiment NP-Complet, encodé dans un programme linéaire, et donc un truc qui prend beaucoup trop de temps, en tout cas on ne gagne pas grand chose à passer par un solveur linéaire.

Je me suis amusé à lancer une version plus précise sur une grosse machine pendant un week-end, pas grand chose n'a eu le temps d'en sortir, sinon de la RAM occupée…


Comment ça je squatte la RAM du serveur ?


Enfin voilà, sans tous les petits détails, c'était globalement mon approche, je suis curieux de voir ce qu'on pu faire les autres, surtout que le score optimal semble être bien approché (puisqu'on a deux soumissions à 227,647 par deux personnes différentes)…

4. On arrive à la 4ème place avec Ruadh, qui encaisse 225.9 points avec 245 lampes, une autre preuve que le développement durable est une voie judicieuse !


En lisant le programme, j'ai compris que chaque potentiomètre pouvait avoir 94 valeurs distinctes, qui sont les entiers de 0 à 93 divisés par 93. J'ai donc utilisé les nombres entiers par la suite. J'ai ensuite cherché quel est l'entier qui permettait d'avoir le meilleur score si tous les potentiomètres avaient la même valeur, il s'agissait de 8. J'ai utilisé un programme qui modifiait légèrement les valeurs de chaque potentiomètre autour de cette valeur et j'ai finalement réalisé un score de plus de 218.
Voyant que je ne parviendrai pas à monter plus haut avec cette méthode, j'ai utilisé un algorithme génétique assez basique. J'ai supposé que les potentiomètres ne pouvaient pas avoir une valeur supérieure à 20, en effet, les ampoules ont tendance à griller au-delà. Cela a permis à mon algorithme de converger très rapidement vers mon dernier score de presque 226.

3. La 3ème place est pour le fort Ne0tux dont la configuration à 245 lampes est encore plus efficace que celle de son prédécesseur. Il table sur 226.3 points !


Pour ma part j'ai eu la même approche que Hackcell : les Algorithmes Génétiques. Je n'y connais pas grand chose dans ce domaine, puisque je n'en avais jusqu'alors jamais développé (J'en avais juste parlé lors d'un pitch pour une application qui devait faire de la réalité augmentée). De ce que j'en avais compris les AG permettent de trouver 'une' solution pas trop mauvaise (mais pas LA solution, à moins d'avoir de la chance) en un temps raisonnable. Ce qui m'a lancé c'est le fait que le nombre d'entrées et de sorties était connu et lui aussi raisonnable.

Bref j'ai lu la page Wikipédia et... c'est tout. J'ai pondu un code, je ne sais pas trop ce que ça vaut. J'avoue que la partie qui chamboule la population si l'algorithme est bloqué dans un maximum local est du pur bricolage. Si quelqu'un connait une méthode robuste pour gérer ça je suis preneur. J'ai vu sur la page Wikipédia qu'il était question du recuit simulé en alternative, mais je ne connais pas du tout : ce sera l'occasion d'apprendre une prochaine fois !

A toute fin utile je vous mets mon code en Pyhton en PJ. Je prends toutes vos remarques si vous en avez, comme je disais je suis néo(tux)phyte.

(Fichier joint: AG_Potars.py)


2. On continue en seconde place avec jacobly, qui avait atteint 227.7 points mais avec la même configuration que le prochain au classement. Il opte donc pour un autre tableau électrique vendu 227.6 points qui affiche 247 lampes. Impressionnant !


I just used the same simulated annealing program that I had used for Galaktik, but between the search space being discrete and therefore minuscule in comparison and the maximization function being much more well behaved, I had the global maximum within 6 hours of finding out about the contest. In the end I had a ~140 line program that can find the best score with no starting information in under 4 minutes with a maybe a 5-10% probability. The only thing of note that I did was I scaled the score function so that it could be computed using only integer math which meant that I didn't have to worry about floating point error.

1. Et le maître incontesté de cette épreuve, le plus fort d'entre vous, c'est Pavel, qui atteint le score astronomique de 227.7 points por 247 lampes avec des méthodes d'optimisation algorithmique ! Chapeau bas ! [#159391]


Bonjour,

Je vais essayer d'expliquer comment j'ai obtenu 227,647 points.

J'ai commencé par légèrement simplifier le code. J'ai modifié la fonction pot() pour qu'elle marche avec les valeurs entières de 0 à 93 et j'ai ajouté une fonction (score()) pour calculer les points. Voici un lien vers le code après ces modifications.

En jouant avec ce code, j'ai remarqué deux comportements de ce problème potentiellement utiles pour trouver une solution:

1. En tournant les potentiomètres un par un de 0 à 93, il est possible de trouver quelque chose qui ressemble à un maximum local:


for j in range(30):
  pot(j, 8 + j % 2)

print(score())

while True:
  smax = score()
  kmax = -1
  vmax = -1
  for k in range(30):
    backup = ls[k]
    for v in range(94):
      pot(k, v)
      s = score()
      if smax < s:
        smax = s
        kmax = k
        vmax = v
    pot(k, backup)
  if kmax >= 0:
    pot(kmax, vmax)
    print(smax)
  else:
    break


2. Pour sortir d'un maximum local, il suffit de tourner juste un tout petit peu quelques potentiomètres:


for k in range(30):
  v = ls[k] + mrandint(-1, 1)
  if v < 0: v = 0
  if v > 93: v = 93
  pot(k, v)


Ensuite, j'ai fait un peu de lecture sur des méthodes d'optimisation stochastiques et j'ai essayé quelques méthodes de ce livre.

Le recuit simulé a donné les meilleurs résultats en moins de temps par rapport aux autres méthodes.

Enfin, voici un lien vers le code en C qui converge à la solution en quelques heures.


Lot mot de la fin

Voici qui conclut la seconde épreuve de notre triconcours de rentrée ! Bravo à tous les participants N'oubliez pas de consulter également les commentaires de l'annonce sur TI-Planet.

À très bientôt pour les résultats de la dernière épreuve du triconcours !


Commentez cette news ! (19)
écrit par Lephenixnoir le 18/11/2018 19:31 Voir toutes les news

La Revue des Projets - 130
Bonjour à tous !
Ce soir cher casionautes, une nonne bouvelle,... euh... une bonne nouvelle ! Lepianoteur (celui dont je confond régulièrement le pseudo avec Lephe...) nous parle de son tout dernier projet en C ! Mais ce soir nous accueillons également Zezombye qui fait avancer sont projet de Python !


Depuis quelques temps on voit régulièrement un nom de topic, et aujourd'hui on voit du concret ! Juste ces superbes graphiques et cette maîtrise parfaites des collisions : Voici le tout dernier né des projets en C qui signe un retour aux Add-ins !
Lepianoteur a écrit :
Bonjour à tous, je vous présente mon projet UnderCasio
Ce projet consiste à refaire le jeu Undertale
Le jeu est en C c'est mon 1er jeu en C donc je prend pas mal de temps à comprendre les bases mais le projet avance bien je trouve et je pense arriver à avoir un résultat pas mauvais à la fin

Pour l'instant le personnage peut se déplacer et avoir des collisions avec la map, j'essaye bien sûr de reproduire la map du jeu au mieux pour être fidèle mais c'est compliqué.

Je met une petite vidéo pour montrer le résultat




Je m'excuse pour la qualité mais je n'ai pas réussi à screen seulement la fenêtre du jeu Mais bon ça donne quand même une idée du résultat c'est le principal
Pour l'avancement du projet vous pouvez aller voir ici Actuellement je suis entrain de voir comment faire pour afficher la boite de dialogue

Voilà c'est tout ce que j'ai à vous dire pour le projet UnderCasio

Voila cher casionautes ! N'oubliez de jeter un œil au topic dédié ! En cas de questions ou de problème tu sais où nous trouver Lepianoteur

On continue ce soir avec Zezombye et son Casio Python. Bientôt les Graphs monochromes auront aussi Python !
Zezombye a écrit :
CasioPython a énormément avancé (en moins de temps que je ne l'avais prévu) :

- 32 ko de mémoire dispo (au lieu de 2 ko)
- Entiers "infinis"
- Support des floats et complexes
- Ajout des modules math, cmath et urandom (renommé en random)
- Un shell digne de ce nom !





Comme vous pouvez le voir, j'ai affiché le caractère "saut de ligne" (principalement pour du débug), du coup petit sondage : est ce que je le laisse, ou non ? Sachant que le shell fait du wrapping (pas de débordement sur le côté droit de l'écran).

Le shell comporte à l'heure d'écriture :
- un curseur digne de ce nom (on peut se déplacer dans la ligne actuelle, aller au début/fin avec shift+flèche gauche/droite)
- un historique (flèche haut/bas)
- un retour arrière (suppr) qui marche visuellement

D'ici la publication de cette RDP j'espère pouvoir également implémenter le scrolling (page up/down).

Du coup j'ai besoin de votre aide pour m'aider à débugger tout ça :
- Expérimentez avec les floats, complexes et entiers, dites s'il y a des opérations, fonctions, etc qui provoquent un crash système
- Expérimentez surtout avec le shell : j'ai mis l'historique à 200 octets (bien entendu s'il y a pas de bugs il sera après à 2 ko), ceci pour mieux expérimenter sur la rotation (quand il arrive à la fin du buffer de 200 octets, il supprime la 1ère ligne et déplace le texte pour libérer de la mémoire). Il y a un nombre en haut à droite du shell (le nombre d'octets du buffer), il ne devrait jamais dépasser 200. Du coup expérimentez lorsque ce nombre est proche de 200, par exemple insérer 2 caractères de suite (avec la touche "^").

On applaudit bien Zezombye pour son travail ! N'oubliez pas que vous pouvez vous tenir au courant via le topic dédié et que vous pouvez contribuer à améliorer Casio Python en l'essayant dès maintenant !

Cette semaine 7 programmes ont été postés
TLOZ FOG de Aziogs le tout dernier-né des jeux de rôles en BASIC
Pupitre un programme de Shadow15510 qui permet de lire les tablatures de guitare sur votre calculatrice
Stick Hero de Tiyuba Une amélioration de ce programme avec plus de perso et une gestion des records !
Stats Calc de Loky974 Ce programme permet de calculer les intervalles de confiance d'une série statistique et autre calculs statistiques...
Pixel de Matcul un jeu d'action où vous devez... survivre ! Une tâche qui s'avère plus complexe que prévue.
Candy-Crush de Shadow15510 l'adaptation en BASIC du jeu du même nom.
Emprunt de Fabcvlr qui signe avec cet utilitaire de maths financières son 64ème programme !!

On se retrouve la semaine prochaine !
En attendant vous avez de nouveaux jeux à tester...
Lire la RdP précédente : La Revue des Projets - 129
Vous, oui vous lecteur, aussi pouvez participer à la Revue des Projet !

L'heure de publication est volontairement avancée car d'autre articles sont à attendre en début de soirée, donc restez connectés !

Commentez cette news ! (14)
écrit par Shadow15510 le 18/11/2018 17:08 Voir toutes les news

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2018 | Il y a 24 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