π
<-
Chat plein-écran
[^]

News 2017
Août (15)
Juillet (18)
Juin (1)
Mai (7)
Avril (4)
Mars (7)

News 2016
Août (17)
Juillet (16)
Juin (2)
Mai (2)
Avril (1)
Mars (5)

News 2015
Août (25)
Juin (4)
Mai (9)
Avril (4)
Mars (10)

News 2014
Août (4)
Juin (11)
Mai (12)
Avril (9)
Mars (12)
Janvier (13)

News 2013
Octobre (11)
Août (5)
Juin (9)
Mai (12)
Avril (10)
Mars (7)
Janvier (10)

News 2012
Août (12)
Juillet (10)
Juin (13)
Mai (22)
Avril (8)
Mars (5)

News 2011
Octobre (23)
Août (1)
Juin (29)
Mai (11)
Avril (5)
Mars (3)

News 2010
Août (2)
Juin (5)

News 2009
Août (1)
Juin (1)
Mai (1)
Avril (1)
Mars (1)

Fabrique un synthé avec la carte DSP TI-C5535 - #Épisode 2

Nouveau messagede Wistaro » 12 Déc 2017, 19:03

Il y a quelques semaines, nous te parlions d'une carte électronique programmable, fabriquée par
Texas instrument
, la
TMS320C5535 eZdsp
.
8206
Mais cette carte n'était pas une carte ordinaire, c'était une carte DSP, pour
Digital Signal Processing
.

Comme nous le disions, les possibilités offerte par cette carte étaient
nombreuses.




Aujourd'hui, après la théorie,
passons à la pratique!



Je vous propose de réaliser un premier projet tout au long de cet série d'articles: un
synthétiseur au clavier
.
Il s'agit en quelque sorte d'un piano virtuel. Vous appuyez sur des touches de votre clavier, et la carte DSP joue un son, différent pour chaque touche.
Tous les synthétiseurs utilisent ce principe! Une circuit détecte l'appui d'une touche
(par exemple, d'une touche au clavier s'il s'agit d'un piano électrique)
, et un autre circuit basé sur un ou plusieurs DSP se chargent de
générer le signal
.

Intéressant non?

Si vous êtes prêts, nous pouvons commencer.

Tout d'abord, il est important de définir notre
cahier des charges
, qui, dans un premier temps, vas être très simple! Nous serons peut-être amené à l'améliorer au fur et à mesure des épisodes de cette série. Aujourd'hui, nous ne nous imposons que très peu de limites!
En effet, nous voulons juste générer un son audible, à chaque appui d'une touche au clavier. Le programme devra tourner
en boucle
, pour pouvoir saisir autant de notes souhaitées. Nous pourrons ainsi créer une mélodie si nous sommes inspirés! :D

Nous voyons donc qu'il y a
2 parties majeures
dans ce projet:
  • Générer un signal audible
  • Détecter l'appui d'une touche au clavier


Je vais détailler chaque partie, et vous allez voir que même si cela semble peut-être un poil complexe, ce n'est en réalité par le cas!

Commençons par
la génération du son.



Un son, c'est quoi? C'est tout simplement
une vibration de l'air
. Ces vibrations se propagent un certain nombre de fois par seconde, c'est ce qu'on appelle
la fréquence
. Cela, vous savez ce que c'est. C'est en quelque sorte la "hauteur" du son: un son haute fréquence sera perçu aiguë, un son basse fréquence sera grave. Quand vous écoutez de la musique sur une enceinte, celle-ci va faire vibrer une
membrane
sous l'action d'une tension électrique, qui va faire vibrer les molécules d'air. Ces vibrations vont arriver jusqu'à
vos tympans
qui vont recevoir ces vibrations, et vous allez entendre quelque chose.
Enfin, normalement.

Mais comment la source
(votre téléphone, votre ordinateur...)
génère t-elle la tension qui arrive à faire bouger la membrane? En fait, rien de secret, c'est très simple! Lorsque la source envoie une
tension positive
, la membrane est poussée dans un sens, et lorsque la
tension est négative,
elle est poussée
dans l'autre sens
. La répétition de cette tension positive, puis négative, puis positive, etc. va alors faire
vibrer les molécules d'air
: c'est le but recherché. Notez que le temps entre ces répétitions est la période, soit l'inverse de la fréquence (
Pour être plus pointilleux, il s'agit de la demi-période! La période complète étant la temps entre 2 tensions de même signe!
).

Autrement dit, pour un son plus aiguë,
il va falloir être rapide!


Maintenant, quelle
fonction mathématique
possède des
alternances négatives et positive
au cours du temps? Il s'agit des fonction périodiques de valeur moyenne nulle. La plus simple d'entre-elle, est le
sinus.


OK, maintenant nous savons que notre carte doit générer un
signal sinusoïdal
d'une certaine fréquence.
Mais comment faire ça?
Notre carte ne traite que
les signaux binaires
, à priori.
Sauf que nous sommes sur une circuit DSP, et que le traitement des signaux, c'est son job.

Encore une fois, le principe va être simple. Nous allons lui donner en entrée un nombre, par exemple 42. Puis un petit composant va se charger de convertir ce nombre en
impulsion électrique
. Ce petit composant s'appelle un
Convertisseur Digital Analogique
, ou
DAC
en anglais.
Son but? Convertir un valeur en un signal électrique.
Ici, le DAC sur notre carte est un
AIC TI-3204
, qui échantillonne les signaux à
192kHz.



Il ne reste plus qu'à calculer les valeurs d'un sinus pour pouvoir ensuite les envoyer au DAC.

En réalité, c'est un peu plus complexe. Pour des raisons de
gestion de la mémoire
, il serait problématique de calculer à chaque fois tous les points du
signal sinusoïdal
. Il est préférable de le pré-calculer au lancement du programme, puis de s'en servir après. N'oubliez que pas que nous sommes sur un circuit DSP!
J'ai donc au préalable généré une sinusoïde sur
16bits signés
(capacité du DAC), c'est à dire qu'en sortie il y aura
$mathjax$2^{16}$mathjax$
niveaux de tension.

La configuration du DAC est un peu complexe, car il faut paramètrer beaucoup de choses sur l'AIC et les ports. Il est vivement recommandé de se baser sur la documentation de la carte!




Il ne reste plus qu'à envoyer le signal! Mais le problème est ici que nous ne pouvons pas jouer sur le fréquence, étant donné que nous avons pré-généré le sinus! J'ai donc bidouillé un peu le code pour que quand la variable fréquence varie, le son change. Par la suite, nous essayerons de faire quelque chose de plus propre! Mais pour le moment, ce n'est pas grave. Remarquez aussi que j'ai copié le signal 2 fois, car nous sommes sur un port stéréo.
Cela fonctionne très bien. Dans un prochain épisode, nous verrons comment générer un signal plus propre, certes, mais aussi différent d'un signal sinusoïdal. Chaque forme de signal a sa tonalité bien particulière. Par exemple, un signal carré fait beaucoup pensé aux synthétiseurs dans les musiques des années 80 :p Il sera également possible d'appliquer des
filtres
, des effets au signal pour le rendre
beaucoup, beaucoup plus cool
. Mais pour l'instant, occupons-nous de notre petit piano électrique!

Voilà la fin de la première partie!
Maintenant, il ne reste plus qu'a détecter les touches du clavier.
Vous savez peut-être que lorsque vous appuyez sur une touche, votre ordinateur reçoit une donnée correspondante à la touche envoyée. On appelle ça le code ascii. Et bien, grâce à un petit programme installé de base sous windows,
Hyperterminal
, il est possible d'envoyer cette donnée non pas à Windows, mais plutôt sur un port spécifique. Un port est globalement une entrée/sortie de l'ordinateur qui communique au moyen d'un liaison série: un fil sert pour émettre des données, et un autre pour les recevoir.



Et, ça tombe bien, notre carte TMSezDSPC5535 est connecté sur l'un de ces
ports séries
de notre ordinateur! I suffit donc de connecter
(virtuellement bien sûr!
) le fil d
'émission de l'ordinateur
sur le fil de
réception de la carte
, pour assurer une liaison entre les 2 deux. Ainsi, quand vous appuierez sur
"E"
, le carte DSP recevra
"E"
.
Mais cela n'est pas magique. Sur la carte, le composant qui réalise cela et un UART. Il fonctionne aussi bien en émission, qu'en réception. Ici, nous travaillons avec une fréquence de transmission de
115200
bits par seconde. Il faut donc que Hyperterminal reçoive aussi les données à cette fréquence, sinon il y a aura un gros problème!


Comme vous pouvez le voir à gauche, le code final est très simple. Dans une boucle infinie, je regarde en continu si je reçois un caractère. Si c'est le cas, alors je génère un signal pendant
1 seconde
, et je réinitialise tout. On peut remarque que la je passe en paramètre de ma fonction qui génère le signal la touche appuyée. En effet, je m'en sert pour que, à chaque touche soit associée un son différent!
Notez que le programme pourrait être bien plus optimisé, notamment en travaillant avec les interruptions! Nous verrons ça un peu plus tard.


Bon, en réalité, avec mes bidouillages, le signal est en sortie n'est pas très beau. Il est même assez loin du signal sinusoïdal. Voyez par vous-même :)
Image Image


En effet, si vous regardez mon code, vous voyez que je n'envois pas la totalité du sinus à chaque fois. Pour faire varier la fréquence, je n'envoie qu'une partie à chaque fois, et je répète cette partie. Le signal n'est donc pas sinusoïdal en sortie. D'ailleurs, c'est également bien visible sur le spectre, qui comporte quelques harmoniques.


Attention donc les oreilles :troll:
Nous sommes encore loin d'un beau synthétiseur, mais on s'approche :D

Voici une courte vidéo vous montrant le résultat :p



Le code source du projet est disponible gratuitement sur GitHub: https://github.com/Wistaro/DspSynthesizer


Et ensuite...?
Dans les prochains épisodes, comme je l'ai déjà dit, nous améliorerons ce projet, notamment avec ceci:
  • Génération de signaux plus propre
  • Génération de différents types de signaux
  • Ajout d'effet et filtres
  • Lecture d'une musique
  • Affichage d'un vu-mètre
  • Transformateur de voix
  • Reconnaissance vocale

Et bien plus encore! N'hésitez pas à me donner vos avis!

A bientôt!


Épisode précédant - Épisode suivant
Lien vers le sujet sur le forum: Fabrique un synthé avec la carte DSP TI-C5535 - #Épisode 2 (Commentaires: 0)

Résultats catégorie NumWorks concours Galactik rentrée 2017

Nouveau messagede critor » 10 Déc 2017, 22:15

Image

Après la publication du classement de la catégorie
HP
dans un article précédent, voici enfin aujourd'hui le classement catégorie
NumWorks
de notre concours de rentrée 2017
Galactik
! :bj:

Samuel V.
arrive
8ème
avec une disposition périphérique évaluée à .


Manu R.
quant à lui arrive à une disposition valant , se classant ainsi
7ème
.


Mention honorable pour
MMBC_Chris
qui passe à une disposition quadripolaire lui obtenant un score de après
2 participations
. Toutefois il a par la suite changé pour la catégorie
TI
.


Iamissam
arrive quant à lui à faire mieux après
3 participations
avec un unique amas d'étoiles central, terminant avec à la
6ème
place.


Mention honorable avec un amas d'étoiles un peu plus excentrée pour
Cyril S.
mais avec un peu plus d'ordre avec des dispositions remarquables en triangle et en carré, qui arrive ainsi à faire encore mieux avec . Il a par la suite opté pour la catégorie
HP
.

@Cyril, quel est ton secret ?

Cyril S. a écrit:Quand j’ai découvert le concours, pour des raisons de facilités, j’ai commencé à chercher dans la catégorie Numworks, où j’ai posté un premier score trouvé empiriquement. Bien qu’appréciant les calculatrices, je suis totalement novice dans la programmation sur calculatrice ou simplement le transfert de fichiers.
Puis j’ai chargé le programme pour ma Casio CP400 (que j’ai depuis deux mois), même si les lots ne m’intéressait pas vraiment. Après avoir essayé de déplacer fastidieusement les étoiles et pensé que soit j’avais mal fait l’importation, soit que le programme était bogué, j’ai chargé l’émulateur HP Prime, et j’ai vraiment commencé à être méthodique.
J’ai commencé par placer toutes les planètes en haut de l’écran, j’ai descendu la première, puis les autres une à une, afin d’établir un tableau répertoriant les différentes interactions avec des --, -, +, ++, tableau qui correspondra à la matrice G. Cela m’a permis de voir la distance 20 revenant pour les interactions positives.
J’ai ensuite copié le programme dans Notepad++, afin de l’indenter, et l’analyser en détail. J’ai découvert le fonctionnement du ranseed, puis compris comment le score était calculé. J’ai créé une liste avec les valeurs du ranseed(42) que j’ai exportée vers Excel, elle m’a permis de créer la matrice G.
Puisqu’il fallait placer les planètes avec une distance de 20, sur papier, j’ai disposé les planètes sur un maillage en formant des triangles équilatéraux en fonction des valeurs de G, en trouvant les coordonnées avec un peu de trigonométrie. Et j’ai obtenu un score aux alentours de 121 millions.
Pour essayer d’améliorer, j’ai repris Excel et créé une succession de matrices afin d’y calculer directement le score et d’utiliser les algorithmes du solveur. Que ce soit clair, il s’en sort peut être bien pour une fonction du second degré, mais là, il y a beaucoup trop d’extrema locaux, et globalement, il n’a presque jamais été en mesure d’améliorer la position initiale donnée, parfois quelques centièmes grappillés quand même.
J’ai fini par trouver à la main encore une réponse un peu meilleure avec 124,4 millions que je n’ai pas postée. Je comptais la garder pour revenir dans la catégorie HP, après avoir posté des résultats dans d’autres catégories, mais des vacances m’ont empêché de poursuivre mes recherches.
Je regrette quand même de ne pas avoir posté le score de 9,4 millions que j’avais trouvé sur CP400, puisqu’aucun score n’a été envoyé avec cette version du programme.

Ce concours était très intéressant, j’ai découvert la HP Prime via son émulateur, et je l’ai vraiment appréciée, la programmation y est compréhensible assez vite.
galactik HP Casio.xlsx
(43.6 Kio) Téléchargé 5 fois


En
5ème
position
Tom H.
scinde la constellation en 2 pôles mais ordonne intégralement l'un d'entre eux selon un quadrillage triangulaire, arrivant ainsi à atteindre un score de ,
3 participations
.


En reprenant cet ordonnancement triangulaire mais avec un unique amas d'étoiles, arrive à monter jusqu'à et donc à se classer
4ème
après avoir persévéré pendant
7 participations
.


Mention honorable avec une disposition partiellement triangulaire mais centrale pour
Lephenixnoir
, qui arrive ainsi à faire monter les enchères à . Il a toutefois la malchance d'être administrateur de
Planète Casio
et ne pouvait donc pas être classé.

@Lephenixnoir, comment t'y étais-tu pris pour disposer tes étoiles ?

Lephenixnoir a écrit:J'ai implémenté un pur algorithme génétique. Ce type d'algo consiste à prendre un population, ici un ensemble de solutions avec leurs scores. Il applique ensuite un cycle bien précis :

1. Évaluation : On calcule le score de chaque configuration
2. Sélection : On ne garde que les meilleures
3. Croisement : On croise les meilleures entre elles pour recréer de la population
4. Altération : On modifie aléatoirement quelques positions (pour éviter de stagner)
5. On recommence à l'étape 1.

Les deux premières étapes sont simples à s'imaginer. Pour la troisième, j'avais deux manières de croiser deux configurations. Dans chacune d'elles, je considérais pour chaque étoile, sa position dans la première configuration, puis dans la deuxième. La première méthode choisissait, pour placer cette étoile dans la configuration fille, une position au hasard sur le segment. La seconde aussi, mais elle se mettait au même endroit (au même rapport de distance, ie. le même barycentre) pour toutes les étoiles, ce qui donnait une sorte de rotation qui préservait bien le score.

Pour l'altération, je faisais vibrer toutes les étoiles sur une amplitude de λ autour de leur position. Tant que le score maximal de la population grandissait, λ restait fixe, mais s'il stagnait, λ devenait plus petit pour permettre de gagner de la précision. Si ça ne suffisant pas, λ devenait très grand pour tenter de débloquer la situation.

Je faisais tourner ça sur 65'000 à 4 millions de générations selon les cas (plus le score semblait prometteur et plus je faisais durer la simulation), en partant de configurations entièrement aléatoires. En le faisant tourner quelques minutes, je sortais plusieurs configurations à plus de 9 millions, mon meilleur score étant 9846814.67 sur Casio et 107711137.32 sur Numworks.

Comme ça ne suffisait pas pour rattraper les premiers, j'ai imaginé un autre système (que je n'ai malheureusement pas eu le temps d'implémenter). Ça consistait à traduire les relations entre les étoiles en forces et à appliquer de la mécanique sur le système. En gros, en combinant la somme de toutes les forces, le système aurait convergé naturellement vers un équilibre local. En plus de ça, j'aurais fait vibrer doucement toutes les planètes avec l'algorithme génétique pour éviter de stagner.
https://www.planet-casio.com/Fr/forums/lecture_sujet.php?id=14990#150945


Avec quelque chose de similaire,
Thomas M.
arrive à monter jusqu'à et à se classer
2nd
, si si, après avoir persévéré pendant
5 participations
.


Avec une disposition centrale intégralement ordonnée selon un quadrillage triangulaire,
Oakwood
arrivait initialement à faire mieux, .

Toutefois, il a volontairement envoyé par la suite une configuration moins optimale, expliquant tout à son honneur qu'il pouvait se payer la calculatrice
NumWorks
et préférait laisser leur chance à d'autres candidats, terminant ainsi
3ème
avec après un total de
7 participations
.


Toutes nos félicitations à
proghy_v2
. Avec une organisation triangulaire centrale, il culmine à et décroche ainsi la
1ère
place après
3 participations
.

@proghy_v2, explique-nous vite comment tu as fait ! :)

proghy_v2 a écrit:Déjà si vous me connaissez pas, c'est normal. Je m’intéressais aux calculatrices quand j'étais au lycée, j'ai posté quelques programmes z80 sur le site avant TI Planet, mais dès que j'ai eu un pc portable mon intérêt s'est détourné des calculatrices, donc je suis pas resté longtemps sur TI Planet.

Et puis la semaine dernière s'était Halloween, et je me disais que plus beaucoup de site changeaient de look pour l'occasion, alors je suis venu checker pour voir s'il y avait toujours des beaux artworks Halloween ici. Et je suis tombé sur la news qui annonçait la fin du concours, ça m'a trigger.

J'ai réinstallé wabbitemu pour tester le programme TI mais j'ai pas réussi, il me disait qu'il y avait pas assez de mémoire sur la calculatrice, wtf. Pas envie de me casser la tête, je suis parti sur la version Numworks en js. Comme je suis un quiche en js j'ai utilisé js2py pour convertir tout ça en python. J'ai juste réécris la fonction recalc() à la main pour qu'elle soit performante. Après j'ai testé a peu près tous les algos de la librairie scipy.optimize. Les algo de minimisation locale arrivaient à rien, la fonction est pas assez régulière / linéaire / différentiable que sais-je. Du coup je suis parti sur l'algo « differential evolution ». J'ai essayé pas mal de combinaisons de paramètres pour l'algo et rapidement j'arrivais dans les 106 millions, mais difficile de faire mieux.

Je me suis dit que j'avais plus le choix, qu'il fallait réfléchir. J'ai regardé le code et je me suis mis en tête d'exprimer la fonction avec la matrice de distance en entrée plutôt qu'avec des coordonnées de points. J'avais l'intuition que la fonction serait bien plus régulière et que les algo à descente de gradient pourraient converger. Et ils ont très bien convergé en effet : plus de 150 000 000 millions ! Alors j'ai essayé de placer des points dans le plan qui correspondaient à ces distance, mais c'était pas possible évidemment. J'ai alors ajouté aux problème de minimisation les contraintes pour que les distances vérifient les 3 inégalités triangulaires dans tous les triangles. Encore une fois ça converge bien, plus de 130 millions, je crois avoir touché au but. Mais non, la solution est toujours pas constructible en termes de points.

Je me suis dit qu'il manquaient encore des contraintes au niveau des quadrilatères. J'ai exprimé la longueur de la 6ème longueur en fonction des 5 autres. On se retrouve avec 2 cas :

cas convexe :
f^2=a^2+b^2-2*a*b*cos(arcos((a^2+e^2-c^2)/(2*a*e))-arcos((e^2+b^2-d^2)/(2*e*b)))

cas concave :
f^2=a^2+b^2-2*a*b*cos(arcos((a^2+e^2-c^2)/(2*a*e))+arcos((e^2+b^2-d^2)/(2*e*b)))

Je fais tourner mon algo avec ces contraintes... « math domain error » :/

Donc je prolonge ma fonction arcos pour qu'elle soit continue, pseudo-périodique parce que... je voyais pas quoi faire d'autre qui ait du sens.

Et l'algo a convergé vers un truc pourri, genre 80 millions. Je sas pas si c'est mes contraintes qui étaient trop fortes, ou la fonction pas assez comme il faut. J'ai ragequit, je suis retourné sur l'algo génétique, et au bout d'un moment j'ai trouvé des bon paramètres, ça me donnait dans les 113 millions, suffisant pour être premier.

Après j'ai essayé une autre lib de minimisation qui s'appelle pygmo. L'algo self adaptative differetial evolution arrivait à trouver dans les 110 millions sans se casser la tête à choisir les paramètres. L'algo CMA-ES a réussir à atteindre les 116 millions (fallait juste diviser la sortie de la fonction par un million sinon il stagnait dans les 108 millions). J'ai pas posté ce dernier résultat parce que c'était plus de minuit par contre ^^

Au final j'ai appris pas mal de trucs sur python et la algo de minimisation, c'était cool.
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&p=223473#p223473


Very honourable distinction for . With a similar but maybe more central constellation, he achieved . But he then moved to the
TI
category
.

@jacobly, how did you manage to achieve such a high score ?

jacobly a écrit:I used simulated annealing programmed in C to get all of my scores. Initially I assumed that I was restricted to integer coordinates which was difficult to optimize and didn't produce very good scores. Then I found out that other people were getting higher scores with fractional coordinates so I switched to a continuous algorithm. At some point I noticed that most of my good configurations had the stars near a "hexagonal" lattice of points where each point is 20 units away from 6 other points. I used this information to create another discrete implementation that only considered the points on this lattice. This let me find close to an optimal score fairly quickly, which I could then polish off by alternating two continuous algorithms. Since I was working with binary floats the whole time, I had no reasonable way to fully optimize the last digit when computed with decimal rounding error, and I ended finding a solution within an ulp of first place in 3 categories.
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&start=10#p223474



Merci à vous tous pour les efforts, mais aussi pour vos très nombreux messages positifs d'encouragements ou remerciements ayant accompagné vos participations ou comptes rendus de recherche, et qui nous ont fait bien chaud au coeur. :) En effet, ce concours a nécessité de notre part un investissement bénévole très conséquent ainsi qu'une forte abnégation puisque nous n'avons compté :
  • ni notre temps, avec littéralement 4 mois de préparation qui sont à rajouter aux 3 mois s'étant écoulés depuis son lancement
  • ni les goodies, nombre d'entre eux provenant de nos stocks personnels pour lesquels nous avons raclé jusqu'au fond des tiroirs, afin d'accompagner généreusement et équitablement un maximum de lots par catégorie
  • ni notre argent, avec des frais d'expédition atteignant déjà 3 chiffres alors que les envois ne sont même pas terminés
A bientôt. ;)
Lien vers le sujet sur le forum: Résultats catégorie NumWorks concours Galactik rentrée 2017 (Commentaires: 5)

Modèles non conformes en magasin, continue à être vigilant !

Nouveau messagede critor » 08 Déc 2017, 17:49

As-tu fait l'erreur de te prendre un modèle d'entrée de gamme qui t'handicapera en mode examen, comme la
Lexibook GC3000FR
dont nombre de possesseurs tentent déjà de se débarrasser tout en lui attribuant collectivement toutes les qualités du monde ? :p
(parfaite pour le lycée, le BAC, la Seconde, les séries non scientifiques, technologiques ou professionnelles et j'en passe...)
:troll:
Envie d'une meilleure calculatrice pour Noël ?
Il est en effet loin d'être trop tard et tu as encore largement le temps de la maîtriser même pour des examens ou concours cette année. :)

Tâche toutefois de ne pas te faire avoir une seconde fois. Car même si nombre de magasins ont enfin eu le respect pour cette rentrée 2017 de nettoyer leur rayon scolaire en en retirant tous les modèles non conformes, ce n'est hélas pas le cas partout. :'(

9034Ci-contre un magasin
Géant
, possiblement non représentatif de l'ensemble de la chaîne puisque nous avions pu remarquer les rentrées précédentes que les politiques d'affichage variaient grandement d'un magasin à un autre, mais qui continue quand même scandaleusement encore en 2017-2018 à tenter de te refiler ses
Casio Graph 35+ USB
et
Casio fx-CP400
non conformes, c'est-à-dire désormais inutilisables et non revendables. Autrement dit elles ne valent quasiment plus rien en France. Modèles affichés en rayon scolaire sans aucune mention de cette grave limitation
(manquement au devoir d'information du vendeur professionnel)
et sans aucune réduction, histoire en prime de te faire payer l'arnaque plein pot. :mj:

N'hésite pas à consulter la liste des modèles conformes ainsi que notre classement indépendant
QCC 2017
.
Lien vers le sujet sur le forum: Modèles non conformes en magasin, continue à être vigilant ! (Commentaires: 2)

Résultats catégorie HP concours Galactik rentrée 2017

Nouveau messagede critor » 03 Déc 2017, 13:01

Image

Après la publication du classement de la catégorie
Casio
dans un article précédent, voici aujourd'hui le classement catégorie
HP
de notre concours de rentrée 2017
Galactik
! :bj:

Erwin R.
arrive
8ème
avec une disposition en 4 pôles dont un central, évaluée à .


quant à lui arrive au bout de
7 participations
à une disposition tripolaire valant , se classant ainsi
7ème
.


Comme promis tous les participants précédents gagnent un compte
TI-Planet Premium
, et si ils en avaient déjà un il leur est parfaitement possible d'en faire don à une autre personne.

Voici maintenant les mentions honorables ainsi que les gagnants, pour ces derniers dans l'inverse de l'ordre dans lequel ils pourront puiser dans la dotation annoncée afin de composer leur lot.

Dubs
en
6ème
position reste sur une disposition tripolaire avec son score de

@Dubs, comment as-tu fait pour devenir multimillionnaire ?

Dubs a écrit:Je ne connaissais pas le langage de programmation de la HP Prime et le concours m'a donné un prétexte pour l'apprendre.
Je ne cherchais pas à obtenir le meilleur score, seulement apprendre le langage.
J'ai donc récupéré le source de l'appli Galactik et regardé comment il fonctionnait.

Ensuite je l'ai modifié pour qu'il cherche tout seul le meilleur score possible via force brute.
Je regroupe toutes les étoiles en haut à gauche et les déplace vers le bas/droite. je bouge une étoile d'un pixel, regarde le score et recommence jusqu'à ce qu'elle sorte de l'écran. Là je la replace en haut à gauche et bouge la seconde d'un pixel, etc.
Après une soirée passée à déplacer les étoiles pixel par pixel j'ai arrêté les frais, ça prendrait trop de temps par cette méthode.

Je l'ai améliorée un peu pour aller gagner en vitesse.
La position de départ est tirée aléatoirement, ensuite je bouge chaque étoile de quelques pixels vers un score plus élevé.
Ex: j'ai un score de 40, je bouge la première étoile vers la gauche d'un pixel pour un score de 39, vers la droite pour 40, vers le bas pour 41 et le haut 38.
Je déplace donc cette étoile vers le bas et passe au déplacement de la suivante. Je boucle sur toute les étoiles et retourne à la première jusqu'à ce que le score stagne.
Je sauve la positions des étoiles et le score obtenu.
Je repositionne les étoiles aléatoirement jusqu'à ce que leur position de départ dépasse le score actuel, puis les déplace pixel par pixel pour augmenter un peu le score.
Avec cette méthode et plusieurs heures de calcul j'avais obtenu un score dans les 104 millions.
Cool

Là je me suis dit que ce n'était pas très glorieux comme procédé et que j'allais plutôt essayer d'avoir un bon score en déplaçant les étoiles sans aide logicielle.
J'ai passé quelques soirées à déplacer les étoiles à la main, sans logique particulière, pour arriver à mon score final.

That's all.

Et au passage merci à TiPlanet pour ce concours !


Dimitri U.
arrive quant à lui à faire mieux après seulement
2 participations
avec un seul amas d'étoiles, terminant avec à la
5ème
place.

@Dimitri, comment as-tu fait pour accumuler autant de millions ?

Dimitri U. a écrit:Tout d'abord merci pour ce jeux bien sympathique. Au départ je voulais analyser l'algorithme mais faute de temps j'ai été au simple pour moi ; j'ai voulu faire confiance au hasard. J'ai modifié le programme pour que le déplacement et le changement d'étoile se fassent aléatoirement. J'ai laissé tourner sur mon PC le programme depuis la calculatrice virtuelle. Régulièrement je regardais le score obtenu. Après un certain temps, beaucoup de temps en fait, le meilleur score obtenu était catastrophique. En parallèle j'ai remarqué après quelques essais que j'obtenais mon meilleur score en regroupant dans une même zone toutes les étoiles. Quelques jours avant la fin du concours, je me suis résolu à ne plus faire confiance au hasard et essayer d'augmenter par moi-même mon score honorable, pour finir classer en 5ème position.


C'est en positionnant cet amas unique d'étoiles au centre que arrive à faire encore mieux après seulement
2 participations
avec et à finir ainsi
4ème
.

@TheMachine02, comment as-tu fait atteindre un aussi bon score ?

TheMachine02 a écrit:Alors globalement, j'ai commencé par refaire le programme de calcul des scores en C. Après j'ai essayé un premier bruteforce qui partait de positions aléatoires et tentait d'optimiser localement le système planétaire, en cherchant les meilleurs positions. Chose intéressante, j'ai pu créer des images de style heatmap, ce qui m'a permis de me rendre compte qu'on trouvait des distances optimales entre certains couples d'étoiles. Puis j'ai un peu tatonné directement sur émulateur afin de trouver la meilleur position en fonction des couples que j'avais trouvé. Et comme j'avais plus le temps, j'ai rien fait d'autre :p


En
3ème
position
Cyril S.
met un peu d'ordre en redisposant cet amas d'étoiles central selon un quadrillage triangulaire, arrivant ainsi à atteindre un score de .

@Cyril, quel est ton secret ?

Cyril S. a écrit:Quand j’ai découvert le concours, pour des raisons de facilités, j’ai commencé à chercher dans la catégorie Numworks, où j’ai posté un premier score trouvé empiriquement. Bien qu’appréciant les calculatrices, je suis totalement novice dans la programmation sur calculatrice ou simplement le transfert de fichiers.
Puis j’ai chargé le programme pour ma Casio CP400 (que j’ai depuis deux mois), même si les lots ne m’intéressait pas vraiment. Après avoir essayé de déplacer fastidieusement les étoiles et pensé que soit j’avais mal fait l’importation, soit que le programme était bogué, j’ai chargé l’émulateur HP Prime, et j’ai vraiment commencé à être méthodique.
J’ai commencé par placer toutes les planètes en haut de l’écran, j’ai descendu la première, puis les autres une à une, afin d’établir un tableau répertoriant les différentes interactions avec des --, -, +, ++, tableau qui correspondra à la matrice G. Cela m’a permis de voir la distance 20 revenant pour les interactions positives.
J’ai ensuite copié le programme dans Notepad++, afin de l’indenter, et l’analyser en détail. J’ai découvert le fonctionnement du ranseed, puis compris comment le score était calculé. J’ai créé une liste avec les valeurs du ranseed(42) que j’ai exportée vers Excel, elle m’a permis de créer la matrice G.
Puisqu’il fallait placer les planètes avec une distance de 20, sur papier, j’ai disposé les planètes sur un maillage en formant des triangles équilatéraux en fonction des valeurs de G, en trouvant les coordonnées avec un peu de trigonométrie. Et j’ai obtenu un score aux alentours de 121 millions.
Pour essayer d’améliorer, j’ai repris Excel et créé une succession de matrices afin d’y calculer directement le score et d’utiliser les algorithmes du solveur. Que ce soit clair, il s’en sort peut être bien pour une fonction du second degré, mais là, il y a beaucoup trop d’extrema locaux, et globalement, il n’a presque jamais été en mesure d’améliorer la position initiale donnée, parfois quelques centièmes grappillés quand même.
J’ai fini par trouver à la main encore une réponse un peu meilleure avec 124,4 millions que je n’ai pas postée. Je comptais la garder pour revenir dans la catégorie HP, après avoir posté des résultats dans d’autres catégories, mais des vacances m’ont empêché de poursuivre mes recherches.
Je regrette quand même de ne pas avoir posté le score de 9,4 millions que j’avais trouvé sur CP400, puisqu’aucun score n’a été envoyé avec cette version du programme.

Ce concours était très intéressant, j’ai découvert la HP Prime via son émulateur, et je l’ai vraiment appréciée, la programmation y est compréhensible assez vite.
galactik HP Casio.xlsx
(43.6 Kio) Téléchargé 9 fois


En permutant plusieurs étoiles sur ce quadrillage triangulaire, arrive à monter jusqu'à et donc à se classer
2nd
après avoir persévéré pendant
7 participations
.

@hpfx, comment t'y es-tu pris pour disposer tes étoiles ?

hpfx a écrit:Ha c’est ici qu’on raconte sa vie, je vai battre le record du post le plus long alors ;)
Je vais essayer de me rappeler, c’est déjà une histoire ancienne, vu que ça fait au moins 3 semaines que j’ai plus rien fait.

Chapitre 1 : le temps « soyons bourrin »

Au départ je suis parti sur un brute-force mais sans tester tous les pixels, je découpais en grille de 20 (ça donne rapidement des scores très honorables, et pour cause…)
Puis j’enchaine sur un petit algo «
pathfinding
» qui recherche à déplacer chacun des points d'abord dans les 4 directions à la recherche d’un minimum local. (puis plus de direction par la suite, [en diag, en cavalier/echec], puis même en sautant carrément plusieurs pixels :facteur 2,3,5…). Je crois que ça faisait en gros ~80 directions possibles.
Ensuite, J’essaie le déplacement deux à deux (2 étoiles au hasard, en testant toutes les combinaisons de déplacement possibles genre 80*80 cas), algo «
move2
»
Ensuite J’essaye alors de déplacer toutes les étoiles en même temps (anecdote pour la suite : et là je me rends compte que le meilleur placement possible est au centre), algo «
globalmove
»
Voilà donc dans un 1er temps, j’enchaine les algo
grid20
,
pathfind
,
move2
,
global-move
. (plusieurs tests avec des variantes etc…) Les résultats sont très bons . Les étoiles sont a peu prêt disposées en carré (normal vu le choix « grille » du départ)

Et dans ma lancée je me dis que je vais affiner avec une grille plus resserré, mais contrairement à mon attente il se trouve que ça n’améliore pas les résultats…

J’entame un nouvel algo de placement initial : placement aléatoire, puis déplacer les étoiles de manière récursive (pour les 80 directions), je déplace l’étoile même si le score est inférieur à sa position initiale, pour contrer le phénomène « minimum local ».
Je calcul en siècles le temps de faire tous les cas, je suis donc obligé d’implémenter un casseur de récursivité une fois arrivé à 500.000 tests (ce qui m’amène déjà à des profondeurs de récursivité 30). J’appelle cet algo «
tree
». c’est assez long car même si je casse après 500k, car il enchaine avec l’étoile suivante du 1er niveau, ça fait donc 500k * le nombre d’étoile.

Une fois mon meilleur arbre de déplacement trouvé pour un « run », je lui applique
pathfind, move2
, et
globalmove
. Et j’ai plus qu’à lancer plusieurs fois ce process.
Avec cet algo je serais 4eme de ma catégorie aujourd’hui avec 118 (pour info le meilleur score publié de l’époque était de 44). Les étoiles sont à peu près disposées en hexagone. C’est une réussite.
J’ai pas publié mon résultat, car je m’amusai alors à essayer de faire 100.000.000 tout rond pour le fun, en jouant avec les décimales des étoiles car on pouvait depuis peu avoir des nombres réels. Jusqu’à présent tous mes algo travaillent en entier. je ne suis pas arrivé à supprimer complètement les décimales, pour ça que non publié. J’ai bien remarqué le positionnement en hexagone, mais vu que je croyais être largement devant, que j’y avait passé des heures, je me contentai de 118 (je comptait passer 120 avec de petits ajustements...)
Alors que je travaillai juste à
réduire
mon score à 100... et bim, je vois qu’un concurrent publie à 140 « et là c’est le drame :) »

Chapitre 2 le temps « réfléchissons un peu pour changer »

Ok je modifie mon algo «
tree
» pour faire des déplacements « en étoile » à 30° pour voir, en quelques minutes je monte à 138. Pas mal, mais toujours inférieur à 140.
Et là j’ai
enfin
l’idée d’essayer de comprendre le calcul...
Très rapidement on voit bien que les points doivent être à une distance de 20 les uns des autres (car c’est « la valeur absolue de la distance moins 20 » qui compte dans le calcul), et que ça doit être centré, car on compare avec la première étoile qui est fixe et au centre.
Du coups depuis mon meilleur résultat (118) je repère en gros la position des étoiles, et je positionne « mathématiquement » les points sur la calto direct (sans algo) juste en modifiant les valeurs de la liste grâce à la notation exponentielle des complexes (par exemple point 1 = Z0 + 20*exp(i*pi/3)) et la direct 138 B-) Yes !
Je regarde les placements de tous mes bons scores (entre 110 et 118) et je remarque qu’il y a plusieurs configurations possibles en fait(ça donne de l’espoir), bon après coups j’ai compris que ce n’est pas vrai : il n’y a qu’une seul conf, il s’agit juste de symétrie ou rotations...

Sur cette base, et plein d'espoir, Hop un nouvel algo, au départ : tous les points confondus au centre, 6 déplacements possibles (à 20 pix) … en quelques secondes j’arrive enfin à 140, et je suis premier de quelques millièmes.

Chapitre 3 « j’ai compris »

Alors que Monsieur 140 me repasse devant le lendemain, je comprends qu’il n’y a qu’un seul bon placement, et qu’il faut jouer sur la rotation. En effet, la matrice ne régît que la position
relative
des points, mais en aucun cas leur placement absolu, on peut donc faire des rotations !
J’ai fait un petit algo qui fait tourner les points autour du centre. Merci la formule de la rotation des complexes : z* exp(i*angle), bon bien sûr il faut le faire par rapport au centre Z0 : (z-Z0)*exp(i*angle)+Z0
Ca marche ! B-)
Mais même avec un pas de rotation de pi/1000000 je ne peux pas faire mieux que décimale 0.223 (déjà pris), je publie donc 0.222 et voilà. Le lendemain un 3eme concurrent trouve aussi la méthode et publie 0.221. tout a été hyper vite.

Conclusion

Je me suis éclaté sur ce concours. un gros boulot d'algo (dont certain peu utilisé à la fin) puis clairement une réflexion mathématique.
Un grand merci aux organisateurs. c'était hyper fun.
au passage si critor m'a lu jusqu'ici, comme Zezombye, moi aussi je préfère que ça soit mon pseudo d'affiché.

Au passage,
Ce qui m’intrigue c’est le concurrent hp qui est à 121,
En effet j’ai eu des seuils difficiles à franchir en particulier 118, je serais curieux de savoir sa méthode/algo pour faire 121.
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&start=10#p223559


Honourable distinction for . By turning over and rotating the previous constellation, he achieved . But such participation couldn't be ranked, as the exact same score had already been submitted by someone else. He then managed to be accepted by slightly moving some stars and thus slightly lowering the score to the never submitted . This makes
4 participations
. But he finally moved to the TI category.

@jacobly, how did you manage to achieve such a high score ?

jacobly a écrit:I used simulated annealing programmed in C to get all of my scores. Initially I assumed that I was restricted to integer coordinates which was difficult to optimize and didn't produce very good scores. Then I found out that other people were getting higher scores with fractional coordinates so I switched to a continuous algorithm. At some point I noticed that most of my good configurations had the stars near a "hexagonal" lattice of points where each point is 20 units away from 6 other points. I used this information to create another discrete implementation that only considered the points on this lattice. This let me find close to an optimal score fairly quickly, which I could then polish off by alternating two continuous algorithms. Since I was working with binary floats the whole time, I had no reasonable way to fully optimize the last digit when computed with decimal rounding error, and I ended finding a solution within an ulp of first place in 3 categories.
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&start=10#p223474


By rotating this same constellation another time, ranks
1st
by improving the high score up to after submitting
3 participations
.

@Hooloovoo, we're waiting for your explanations.

Hooloovoo a écrit:The first step to solving Galactik was to understand how exactly the score is computed from L8.
I'm not going to go over the details of figuring out the dense HPPPL program, but I'll give a brief overview of how the score is computed.
Each point is stored as a complex number in L8. I think the easiest way to think of it is as a weighted complete graph. Basically, there is an operation computed between every pair of points, and the score is the sum of those operations.
There is a in pseudocode, the get_score(L8,weight_matrix) looks like:
There is also set up a list of weights between each edge
Code: Tout sélectionner
get_score(L8,weights):
    s=0
    for p from 2 up to N_PTS:
        for i from 1 to p-1:
            if i == 1 and weights[i][p]<0:
                score += weights[i][p] / (1 + abs(L8[i] - L8[p]))
            else:
                score += weights[i][p] / (1 + abs(20-abs(L8[i] - L8[p])))

a couple notes on that:
since L8 is a list of complex numbers, abs(L8[ i ]-L8[p]) finds the distance between them.
for each pair of points, the distance is evaluated once, and depending on the weight, things are evaluated differently: for positive weights, it is best if the distance is close to 20, and for negative weights, they should be far apart
There is a special case for the first point, such that it is best if all points are close to it, since those edges always have positive weight.
I used simulated annealing in python to figure out some optimal solutions. Once I had that I made it work on the calculator because I could. That got me to 129e6, but the points looked like they were exactly 20 away from one another when plotted, in a hexagonal grid. that shouldn't have surprised me, really.
I assumed that the points all lie on a triangular grid with spacing of 20. I modified the program so it would only check for solutions on that triangular/hex grid, and I got very near the final score, only a few fractions of a point away.
s solution was near the correct local minimum, but I didn't do any optimization on that. small deviations could change the score slightly.
Unfortunately, there is a huge difference between standard IEEE 754 floats and HP's floating point representation. I couldn't write up this next optimizer in python, because I didn't know how exactly the calculator does floating point math!
The next solution I posted, I think, was based on an SA approach running on the virtual Prime starting from the previous solution.
I found that starting the SA optimizer from different rotations of the same pattern (since the energy function doesn't care about rotation, mod weird FP effects) and even different random seeds, resulted in different final scores.
I'm not convinced that there is a general-purpose optimizer that I could use for this. There probably is.
I already had a SA optimizer coded up, and computers are fast, so I decided to use brute force. I started the optimizer from each successive starting location, rotating the original pattern by a small delta each time those until I couldn't get any better.



Merci à vous tous pour vos efforts, mais aussi pour vos très nombreux messages positifs d'encouragements ou remerciements ayant accompagné vos participations et comptes rendus de recherche. Nous allons donc dès maintenant commencer à travailler sur un nouveau sujet qui sera proposé aux partenaires et constructeurs pour l'année prochaine - à bientôt on espère. ;)
Et bien évidemment, remerciements au constructeur pour nous avoir fait confiance.

Lien vers le sujet sur le forum: Résultats catégorie HP concours Galactik rentrée 2017 (Commentaires: 18)

Connecteur batteries TI 2010-2014(Nspire, 84+C...) identifié

Nouveau messagede critor » 28 Nov 2017, 20:10

38117473Dans ses calculatrices fabriquées depuis avril 2014,
Texas Instruments
intègre des batteries que les menus de diagnostics appellent
Samsung
. On peut justement aisément les remplacer par les batteries
AB474350BU
ou
EB494353VU
prévues pour de vieux téléphones
Samsung
à clapet. Cela concerne les :
  • TI-83 Premium CE
  • TI-84 Plus CE
  • révisions matérielles O+ des
    TI-Nspire CX

Les modèles fabriqués antérieurement, de janvier 2010 à mars 2014, utilisaient une batterie différente munie d'un câble, appelée
Getac
par les menus de diagnostics. Cela concerne les :
  • TI-84 Plus C Silver Edition
  • révisions matérielles A-N des
    TI-Nspire CX
  • TI-Nspire CM
  • TI-Nspire TouchPad
  • TI-Nspire Lab cradle
  • TI-Nspire Navigator cradle v2

90269024Si tu es muni·e d'un de ces appareils et bien bonne nouvelle, car la connectique utilisée vient enfin d'être identifiée ! Il s'agit de
micro JST 4 broches au pas de 1.25mm
. :bj:
Te voilà donc enfin capable de récupérer les pièces aussi bien pour remplacer le connecteur ou la fiche en cas d'accident, que pour bricoler si tu veux t'amuser par exemple à caser une batterie haute capacité, à te fabriquer un adaptateur secteur ou encore pourquoi pas un chargeur de batterie dédié. ;)
Lien vers le sujet sur le forum: Connecteur batteries TI 2010-2014(Nspire, 84+C...) identifié (Commentaires: 0)

Résultats catégorie Casio concours Galactik rentrée 2017

Nouveau messagede critor » 25 Nov 2017, 23:40

Image

Après la publication du classement de la catégorie
TI
dans un article précédent, voici ce soir le classement catégorie
Casio
de notre concours de rentrée 2017
Galactik
! :bj:

C'est au bout de
3 participations
à l'aide de sa
Casio Graph 90+E
ou compatible qu'
Estéban S.
arrive
9ème
avec un score de .


Armé de sa
Casio Graph 90+E
, arrive au bout de
2 participations
à une disposition bipolaire évaluée à , se classant ainsi
8ème
.


Au bout de
4 participations
également,
Suruq Game
se place quant à lui
7ème
avec son score de mais obtenu à l'aide de sa
Casio Graph 35+E
ou compatible, avec des étoiles qui font la queue leu leu.


Toujours sur
Casio Graph 35+E
ou compatible, termine avec un score de à la
6ème
place, et nous remet une constellation bipolaire.


C'est quant à lui en explosant littéralement la constellation sur
Casio Graph 90+E
ou compatible que
Majdrab
arrive à faire mieux avec après
3 participations
, terminant ainsi
5ème
.


Comme promis tous les participants précédents gagnent un compte
TI-Planet Premium
, et si ils en avaient déjà un il leur est parfaitement possible d'en faire don à une autre personne.

Voici maintenant les mentions honorables ainsi que les gagnants, pour ces derniers dans l'inverse de l'ordre dans lequel ils pourront puiser dans la dotation annoncée afin de composer leur lot.

En
4ème
position, toutes nos félicitations à qui, muni d'une
Casio Graph 90+E
ou compatible nous sort une constellation linéaire avec une queue et une tête, arrivant ainsi à atteindre un score de après avoir persévéré pendant
2 participations
.

@Ne0tux, comment as-tu fait pour accumuler autant de millions ?

Ne0tux a écrit:Je vois que Zezombye et moi avons eu exactement le même raisonnement ! La seule différence est que j'ai fait une rotation du triangle (6,2,3) autour de 6 de -90 à 90° seulement, par soucis de temps. Si j'avais poussé les bornes plus loin j'aurais trouvé une solution analogue à la tienne. :waza:

J'ai tout fait à la main quasiment. Avec un papier et en regardant G, si on veut une distance de 20 dès que G est positif, on a qu'une seule possibilité :

Code: Tout sélectionner
      17----------2
     / |         |\
    /  |         | \
   5   |         |  3
    \  |         | /
     \ |         |/
       4----------6


J'ai vite compris avec les coefficients de G négatifs que le duo 1 et 7 devait se trouver le plus loin possible du reste donc je suis directement tombé sur cette configuration :

(c'est fou, j'avais fait une image quasiment identique !)

Le seul algo que j'ai utilisé effectuait 2 rotations, dont celle du triangle en effet.

J'ai quand même eu de la chance dans le sens où je suis tombé sur le seul modèle de calculatrice où l'on pouvait espérer trouver juste avec ses méninges (j'ai cru comprendre qu'il y avait plus d'étoiles dans d'autres catégories, ça corse les choses) ! ^^

C'était rigolo en tout cas. J'ai envisagé le bruteforce 10 secondes avant de me rendre compte que les 2 heures passées à la main seraient bien plus fructueuses qu'un algo qui prendrait des siècles. :lol:
https://www.planet-casio.com/Fr/forums/lecture_sujet.php?id=14990#150946


En redressant cette même constellation à la verticale,
Alix
se classe
3ème
et atteint directement un score de après avoir persévéré sur
Casio Graph 90+E
ou compatible pendant
3 participations
.

@Alix, comment t'y es-tu pris pour disposer tes étoiles ?

Alix a écrit:Bonsoir, merci à vous c'était un plaisirs de se creuser la tête sur un telle problème !!!

J'ai découvert ce concours par un ami.
En découvrant l'interface de jeu j'ai tout d'abord cherché à comprendre comment cela fonctionnait, juste en bougeant les étoiles avec les touches. Ça ne m'a mené à presque rien.

J'ai ensuite tenté de comprendre le code. Débutant dans le domaine ça m'a pris beaucoup de temps. Et il y a des détails qui m'ont échappé jusqu'à la fin.

La première grande découverte que j'ai faite c'est la matrice qui contenait les coefficients des scores entre les étoiles. J'ai juste désactivé le "clear" et je suis aller la consulté.

Ensuite il m'a fallu comprendre comment était calculé le score à partir de ça. Au début je me suis juste dis que c'était l'inverse de la distance entre les étoiles multiplié par le coefficient de ces deux étoiles.

Puis en regardant la liste j'ai compris comment les coordonnées des étoiles rentraient en compte. Et j'ai trouvé le point centrale "aimé" de toutes les étoiles.(le (189;93) qui ne bougeait jamais)

Avec ces connaissance j'ai bidouiller un peu étant donné que je connaissais la matrice et donc les étoiles contraire et jumelle.("-" = contraire et "+" = jumelle)


Ensuite tout c'est passé pendant les vacances.
Pour mieux comprendre le programme j'ai mis des "disp" entre les lignes de calcul du score. Ils me renvoyaient le P et le I, la distance, le coeff, le score engendré et le score total.

J'ai alors compris que mettre à une distance de 20 équivalait à coller. En réfléchissant avec la matrice sur mon brouillon, j'ai adopté (après plein d'essais) la formation en Y assez proche de ma solution finale.

Code: Tout sélectionner
R-----M
  \     /
    \  /
      C
       |
      V
       |
      J
       |
      B


(Avec 20 entre chaque étoiles)

Pour différentes distances : comme celle entre mon Y et le point (189;93). J'ai tracé des courbe du score en fonction de la distance. Et j'ai regardé le max. Ici le B ce retrouve alors sur le point (189;93)

J'ai aussi essayé des algos mais ça n'a pas marché.

Enfin, pour grappiller des points j'ai fait pivoter le triangle rouge, magenta, cyan (2,3,6) pour amener le vert plus proche du rouge que du magenta.

Durant tout le concours j'ai travaillé sur ma calculatrice et une feuille de brouillon sur ma table de nuit ;)


Mention honorable pour
Lephenixnoir
. En poursuivant la rotation et réorientant cette même constellation cette fois-ci en diagonale, il arrive à atteindre un score de après avoir cherché sur
Casio Graph 35+E
ou compatible et envoyé
2 participations
. Mais comme il est aussi administrateur de
Planète Casio
, il ne peut donc pas être classé.

@Lephenixnoir, comment t'y étais-tu pris pour disposer tes étoiles ?

Lephenixnoir a écrit:J'ai implémenté un pur algorithme génétique. Ce type d'algo consiste à prendre un population, ici un ensemble de solutions avec leurs scores. Il applique ensuite un cycle bien précis :

1. Évaluation : On calcule le score de chaque configuration
2. Sélection : On ne garde que les meilleures
3. Croisement : On croise les meilleures entre elles pour recréer de la population
4. Altération : On modifie aléatoirement quelques positions (pour éviter de stagner)
5. On recommence à l'étape 1.

Les deux premières étapes sont simples à s'imaginer. Pour la troisième, j'avais deux manières de croiser deux configurations. Dans chacune d'elles, je considérais pour chaque étoile, sa position dans la première configuration, puis dans la deuxième. La première méthode choisissait, pour placer cette étoile dans la configuration fille, une position au hasard sur le segment. La seconde aussi, mais elle se mettait au même endroit (au même rapport de distance, ie. le même barycentre) pour toutes les étoiles, ce qui donnait une sorte de rotation qui préservait bien le score.

Pour l'altération, je faisais vibrer toutes les étoiles sur une amplitude de λ autour de leur position. Tant que le score maximal de la population grandissait, λ restait fixe, mais s'il stagnait, λ devenait plus petit pour permettre de gagner de la précision. Si ça ne suffisant pas, λ devenait très grand pour tenter de débloquer la situation.

Je faisais tourner ça sur 65'000 à 4 millions de générations selon les cas (plus le score semblait prometteur et plus je faisais durer la simulation), en partant de configurations entièrement aléatoires. En le faisant tourner quelques minutes, je sortais plusieurs configurations à plus de 9 millions, mon meilleur score étant 9846814.67 sur Casio et 107711137.32 sur Numworks.

Comme ça ne suffisait pas pour rattraper les premiers, j'ai imaginé un autre système (que je n'ai malheureusement pas eu le temps d'implémenter). Ça consistait à traduire les relations entre les étoiles en forces et à appliquer de la mécanique sur le système. En gros, en combinant la somme de toutes les forces, le système aurait convergé naturellement vers un équilibre local. En plus de ça, j'aurais fait vibrer doucement toutes les planètes avec l'algorithme génétique pour éviter de stagner.
https://www.planet-casio.com/Fr/forums/lecture_sujet.php?id=14990#150945


C'est pour sa part en lui tordant le cou et lui coupant la queue, que se classe
2nd
en utilisant sa
Casio Graph 35+E
ou compatible pour améliorer le meilleur score jusqu'à .

@Nemhardy, comment as-tu fait pour atteindre un si bon score ?

Nemhardy a écrit:Personnellement, contrairement à Zezombye (mais sa méthode a le mérite de lui permettre réellement de s'approcher de la configuration optimale, en minimisant la «fenêtre de bruteforce», c'est assez joli, même si peut être assez peu viable sur plus d'étoiles… ^^), j'ai considéré le calcul du score comme une boîte noire d'une certaine manière, c'est à dire qu'une fois implémentée de mon côté pour me permettre de faire mes essais, je n'ai fait que m'en servir pour attribuer un score à des configurations, sans réflexions géométriques dessus.

L'idée que j'avais initialement était de laisser le système évoluer depuis un état quelconque, en essayant d'éviter les équilibres instables ; la nature est très forte pour minimiser de l'énergie d'un système semblable en suivant les mouvements imposées par les forces en jeu, et maximiser une énergie c'est globalement le même problème.

Mais étant un peu flemmard, j'ai d'abord commencé par une solution plus simple (et quand je dis simple, c'est vraiment le cas… x) ) : je pars d'une configuration aléatoire, puis choisis une étoile que je fais bouger d'un certain pas dans la direction maximisant l'augmentation du score ; si on ne trouve pas de direction qui augmente le score, on passe à une autre étoile, et une fois qu'on ne peut plus bouger aucune étoile, on diminue le pas (on le divisait par deux dans mon algo, mais c'est assez arbitraire) et on recommence jusqu'à ce qu'on soit passé sous un seuil arbitraire pour le pas, ou qu'on ait dépassé un nombre maximum d'itérations (arbitraire là encore). ^^

Je savais qu'il n'y avait aucune raison que ça donne une configuration optimale, ni même une bonne configuration en fait, car on peut imaginer des cas ou il faut bouger plus d'une étoile pour pouvoir débloquer la situation même sans diminuer le pas. Cependant, ayant fait tourner mon algo environ 13 minutes, j'ai eu ladite configuration qui m'a plassé provisoirement premier, donc c'était déjà pas mal. :waza:
(J'avais tout de même fait tourner quatre threads pendant ces 13 minutes, chacun ayant des paramètres correspondants à la fenêtre dans laquelle naissaient les configurations aléatoires, et le pas initial de déplacement initial différents, histoire de voir si il y avait certains de ces paramètres plus intéressants que les autres, mais de manière totalement empirique (même si on pouvait se douter qu'une fenêtre pas trop grande, centrée avec un pas pas trop exagéré allait sûrement donner de meilleurs résultats qu'un truc un peu délirant ! ^^)

J'en avais un peu en réserve en cas d'un petit dépassement par quelqu'un d'autre car j'ai fait un algo permettant d'améliorer une configuration pas trop mauvaise, en essayant de bouger cette fois ci plus d'une étoile par itération. Mais ça fait un truc un peu plus lourd à exécuter donc c'est viable sur des petits changement je pense mais pour les gros mouvements initiaux ça n'aurait pas été hyper intéressant, je crois ; donc je l'ai réservé à de l'amélioration de configuration, c'est à dire en travaillant directement sur du petit pas. Mais je n'ai pas vraiment eu à m'en servir, donc je n'ai pas vraiment vu jusqu'où on pouvait pousser la chose !

Et ensuite je n'ai plus vraiment eu le temps, mais j'ai trouvé le concours très sympa, et la dernière semaine (et sûrement avant, mais je m'y étais un peu moins plongé je dois dire…) a vu son lot de discussions intéressantes et de rebondissements, et ce sans trop de mauvais esprit du type «je balance mon super score une heure avant la fin», donc c'était cool ! :p
https://www.planet-casio.com/Fr/forums/lecture_sujet.php?id=14990#150943


Enfin reprend quant à lui la rotation, nous remettant la constellation à l'horizontale mais cette fois-ci tête au centre, terminant
1er
en améliorant encore le meilleur score jusqu'à à l'aide de sa
Casio Graph 35+E
ou compatible après seulement
4 participations
.

@Ruadh, peux-tu nous révéler ton secret ?

Ruadh a écrit:J’ai commencé par lire le programme fourni pour comprendre comment le score était calculé. J’ai découvert que si G(i,j)>0 (avec i et j différents de 1), alors la distance entre les étoiles i et j devait être de 20 pour avoir le score maximum. Si G(i,j)<0, il fallait espacer les étoiles i et j le plus possible. Enfin le score augmentait également en approchant chaque étoile du centre. J’ai donc placé les étoiles de la sorte et j’ai obtenu la disposition visible sur la figure 1.

Cependant, avec cette disposition, certaines étoiles sont très loin du centre, ce qui fait donc diminuer le score. J’ai remarqué que G(2,4) était très faible donc il n’est pas forcément utile d’éloigner les étoiles 2 et 4. Je les ai alors placées ensemble au centre et j’ai obtenu la disposition visible sur la figure 2.

Encore fallait-il déterminer l’angle α. Pour cela, j’ai tracé sur ma calculatrice une fonction qui donnait le score perdu dû aux distances d(3,5), d(3,7), d(6,5) et d(6,7). On peut exprimer ces distances en fonction de α.

d(3,5)=20*sqrt(2-2*cos(α))

d(3,7)=20*sqrt(5-4*cos(α))

d(6,5)=20*sqrt(2-2*cos(α+π/3))

d(6,7)=20*sqrt(5-4*cos(α+π/3))

La fonction est : f(α)=G(3,5)/(1+d(3,5))+G(3,7)/(1+d(3,7))+G(6,5)/(1+d(6,5))+G(6,7)/(1+d(6,7))

Une fois la fonction entrée dans la calculatrice, j’ai utilisé la recherche de maximum de la calculatrice pour obtenir l’angle qui maximise le score. Puis je me suis servi de cette valeur pour écrire la liste envoyée : {63+31i, 63+31i, 63+20*cos(α)+(31-20*sin(α))i, 63+31i, 83+31i, 63+20*cos(α+π/3)+(31-20*sin(α))i, 103+31i}.


Mention très honorable pour . Avec une disposition un peu plus centrale de cette même constellation, il améliore le meilleur score d'un cent-millionième avec à l'aide de sa
Casio Graph 35+E
ou compatible au bout de
4 participations
. Il ne peut toutefois être classe puisqu'ayant décidé au dernier moment de passer dans la catégorie
TI
.

@Zezombye, comment avais-tu fait ?

Zezombye a écrit:Le 17 septembre, je découvre la surprise dont parlaient les admins : le concours de rentrée.
J'ouvre le g1m, puis je me mets à décortiquer l'algorithme pour savoir comment est calculé le score.
On se rend compte rapidement que le calcul du score se fait dans cette boucle :
Code: Tout sélectionner
While K!=48 And K!=47 And K!=44
   If Abs Frac List 8[P] :Then
      
      Int List 8[P]->List 8[P]
      7->K
   Else
      
      GetKey->K
   IfEnd
   List 8[P]->Z
   If K=28 And ImP Z<Ymax-T Or K=27 And ReP Z<Xmax Or K=38 And ReP Z>Xmin Or K=37 And ImP Z>Ymin Or K=7 :Then
      
      Z+(K=27)-(K=38)+i((K=28)-(K=37))->List 8[P]
      For 1->I To P-1+(K!=7)(M-P+1)
         If I!=P :Then
            
            S+Mat G[I,P](1/(1+Abs ((Mat G[I,P]>0 And I>1)F-Abs (List 8[I]-List 8[P])))-(K!=7)/(1+Abs ((Mat G[I,P]>0 And I>1)F-Abs (List 8[I]-Z))))->S
         IfEnd
      Next
   IfEnd
   PlotOff ReP Z,ImP Z
   If K=78 Or K=77 Or K=7 :Then
      
      If K=77 :Then
         
         M-MOD(M-P+1,M-1)->P
      Else
         
         2+MOD(P-1,M-1)->P
      IfEnd
      PlotOff ReP List 8[P],ImP List 8[P]
      PlotOn ReP Z,ImP Z
   IfEnd
   PlotChg ReP List 8[P],ImP List 8[P]
   Text 1,1,S
WhileEnd


Plusieurs variables sont importantes ici :
- K pour Key, avec K=7 lors de l'initialisation
- S pour Score
- I pour Itérateur
- P pour Etoile (2 à 7, l'étoile 1 étant le centre de l'écran)
- F pour Distance (20, ne change pas).

On remarque que le code exécuté pour le recalcul du score est inutile ici, car on veut juste comprendre l'algo. Ainsi, on assume que K = 7 est toujours vrai.
En étudiant un peu plus l'algorithme, on remarque que la boucle While fonctionne ici comme un For qui itère sur P de 2 à 7. En pseudo-langage, ça donne :
Code: Tout sélectionner
for (int P = 2; P <= 7; P++) {

   for (int I = 1; I <= P-1; I++) {
                                    1      
      S+Mat G[I,P]*(--------------------------------------------------
                    1+|20(Mat G[I,P]>0 And I>1)-|List 8[I]-List 8[P]||
      
                          K != 7
      - -------------------------------------------) -> S
        1+|20*(Mat G[I,P]>0 And I>1)-|List 8[I]-Z||
   }            
}


Mais comme K = 7, alors K != 7 est faux, donc on peut directement enlever cette portion du code :
Code: Tout sélectionner
for (int P = 2; P <= 7; P++) {

   for (int I = 1; I <= P-1; I++) {
                                    1            
      S+Mat G[I,P]*(--------------------------------------------------)->S
                    1+|20(Mat G[I,P]>0 And I>1)-|List 8[I]-List 8[P]||
   }      
   
}


Tout de suite, c'est plus simple.
La matrice G vaut :
Code: Tout sélectionner
     1       2        3       4       5        6       7

1      0  485402   366483  895650   398681   246960  1062990
2            0    2603497  -18533 -3484358   386459  -768468
3                   0    -646585 -3156512  1487979 -2522960
4                           0     2602703   632508 -2423677
5                                 0    -1746276  1331355
6                                      0    -2905103
7                                          0

À noter que G[X,Y] = G[Y,X] (avec l'instruction Mat G+Trn Mat G->Mat G).

Pour avoir le meilleur score, il faut donc influer sur le dénominateur de la fraction : 1+|20(Mat G[I,P]>0 And I>1)-|List 8[ I ]-List 8[P]||.
Ici, |List 8[ I ]-List 8[P]| est la distance entre I et P. Deux cas sont possibles :
- Si Mat G[I,P] > 0 : dans ce cas il faut que le dénominateur soit le plus proche de 1. En étudiant bien le dénominateur, il faut que |20(Mat G[I,P]>0 And I>1)-|List 8[ I ]-List 8[P]|| = 0, ce qui signifie que la distance entre I et P doit être la plus proche de 20.
- Si Mat G[I,P] <= 0 ou que I = 1 (on calcule le score par rapport au centre), alors plus I sera proche de P, plus la fraction sera proche de 1. Cela veut dire que si Mat G[I,P] <= 0 alors il faut que I soit le plus éloigné possible de P, et si I = 1 alors il faut que I soit aux mêmes coordonnées que P.

Toutefois, mon cerveau a décidé pour une quelconque raison de lire la condition (Mat G[I,P]>0 And I>1) en tant que (Mat G[I,P]=0 And I>1), ce qui change tout. Cela veut dire que si Mat G[I,P] < 0, alors I doit être à une distance éloignée de 20 de P, donc I peut être aux mêmes coordonnées que P avec une perte de score minime ! (ce qui n'est pas le cas, mais c'est ce que je croyais au début).

J'ai donc tracé le graphe des liaisons entre les étoiles :

Puis, je me suis rendu compte qu'il n'y avait qu'une seule configuration possible pour qu'il n'y ait que des traits verts reliant les étoiles :


La seule modification ici était d'influer sur l'angle du triangle 6-2-3 (par rapport à l'horizontale), ce qui avait un impact car G[2,4] = -18533 alors que G[3,4] = -646585. Après un bruteforce, je trouve mon score de 9 843 347,30939981. Bizarrement, mon algorithme trouve un score de 9.6 millions (mais qui me donne 9.8M lorsque je transpose la liste sur la calculatrice), mais j'ai attribué ça à un changement de moteur de calcul.
Convaincu que le seul moyen de battre mon score n'était que de quelques millièmes en changeant un peu l'angle du triangle 6-2-3, je cherche sur TI et HP, mais n'arrive qu'à faire 46M et 123M, loin des premiers.

---
Un mois plus tard, le 28 octobre, Nemhardy me donne un coup de pied au cul en sortant un score de 9 966 747. Cela implique une toute nouvelle configuration, ce que je trouve bizarre : il n'y a pas de moyen évident d'arranger les étoiles autre que ma configuration.
En cherchant un peu, je trouve qu'en rompant la liaison 4-6 et en plaçant le 4 sur le 6, cela pourrait faire augmenter mon score :
- Rompre la liaison 4-6 me fait perdre 632k
- Placer le 4 sur le centre (avec le 7) me fait gagner 895k
- La pénalité de 4 et 7 est divisée par 21, ça me fait perdre 2423/21 ~= 120k.
Tout cela s'additionne pour me donner une amélioration d'environ 120k, ce qui correspond à peu près au delta de 123k entre mon score et celui de Nemhardy.

Je teste, et je trouve un score de... 7 millions ?! Bizarre. Je refais mes calculs : seuls les 3 paramètres cités varient. Je retélécharge Galactik au cas où j'aurais modifié le calcul du score dans un de mes tests : même chose. Je teste sur Graph 90+E (en devant en plus démarrer ma VM, car j'avais épuisé la période d'essai de l'émulateur) : même chose.
Aurais-je fait une erreur dans le recopiage de l'algorithme ? Je regarde, et je ne vois pas. Je remarque que le score de 7 millions était comme si la pénalité de la liaison 7-4 était appliquée sans être divisée par 20... il doit y avoir une erreur, car G[7,4] != 0 et I > 1 donc la condition devrait être vraie.
Je teste : P = 4, I = 7, Mat G[I,P] = -2M, alors pourquoi (Mat G[I,P] = 0 And I>1) retourne 0...
...
...Ah, c'est Mat G[I,P] > 0.

(oui, il m'a fallu jusqu'au dernier moment pour que mon cerveau corrige l'erreur)

Maintenant que je connais le vrai fonctionnement de l'algorithme, une nouvelle configuration semble logique : en effet, cela veut dire que pour des étoiles à 20 de distance, les liaisons négatives sont divisées par 21.
La liaison 4-2 n'imposant qu'une pénalité de -18k, je peux les superposer, ce qui me donne une amélioration de -1063k + 896k + 485k = 318k, et la configuration suivante :

L'amélioration n'est que de 147k en raison du rapprochement des liaisons 5-3, 3-4 et 5-6, qui font sentir leurs millions de pénalités.
Un autre bruteforce pour trouver l'angle du triangle 2-3-6 (et cette fois mon algo en java trouve le même score qu'affiché sur la calculatrice), et je trouve un score de 9 991 310, qui est d'ailleurs toujours premier de la catégorie casio.

---
Avec ces connaissances en plus, j'ai re-regardé mes configurations TI et HP, que je triturais pendant un mois (mais avec un algo faux). Je me suis aidé des images des matrices :

Sur HP, je n'ai pas réussi à bien améliorer mon score : 125M contre 123M... et de toute façon la catégorie était saturée, avec 3 participants différents étant tombés sur ce qui est visiblement le score maximal.

Sur TI, après un peu d'expérimentation, je suis tombé sur cette configuration :

Ce qui me donnait 48M... pas assez, mais suffisant pour être 2ème.
Pour modifier la configuration, il faut noter que le polygone 2-11-6-10-7 est inaltérable (car composé uniquement de triangles verts) ; impossible de déplacer n'importe laquelle de ces 5 étoiles sans baisser mon score.

J'ai essayé de relier la liaison 8-5, mais c'est impossible, car il fallait alors superposer des étoiles avec une liaison négative, ou casser des liaisons positives, ce qui baissait mon score (la liaison 8-5 ne m'apportant que 1.22M).

Mais, en mettant le 7 sur le 3, il est possible de changer la structure tout en gardant l'intégralité des liaisons vertes :

On voit que, tout comme casio, on peut influer sur l'angle de l'étoile 8 par rapport à l'étoile 10. Un petit bruteforce plus tard, j'ai un score de 49 942 613, ce qui me classe premier. Mais le participant n°23 avait soumis un score de 49 946k avant de se rabattre vers HP - il y avait donc une amélioration à faire.

Y a-t-il quelque chose qui pourrait bouger dans notre configuration ? On élimine tous les triangles, il reste donc le losange 9-5-7-4 dont on peut modifier la distance 5-4 afin d'améliorer le score.
Un peu de trigonométrie pour déterminer les coordonnées de 9 par rapport à l'angle de 4 par rapport à 7, et avec un bruteforce, je trouve 49 946k.
Mais étant donné qu'il y a 2 angles à modifier : l'angle de 4 par rapport à 7, et l'angle de 8 par rapport à 10, il faut bruteforcer les 2 afin de trouver la meilleure configuration.

Un premier bruteforce et je trouve 49 946 730.080507. Un bon début, mais il me reste 133 millionièmes.
En raffinant, je me rapproche : 509, 543, puis un score de 639, que je soumets.
45 mn plus tard, je trouve un score de... 641 ! J'obtiens alors la première place au classement TI, et y reste.
Durant les prochains jours, je tente de trouver un 642, sans succès. Mon bruteforce atteint les limites, et la différence de moteur de calcul se fait sentir : des scores supposés être supérieurs à mon 641 se traduisent par un 640, 639, ou pire, .073543 (7 millièmes de moins).

J'essaie donc le BigDecimal pour garder un moteur de calcul décimal, mais... c'est lent. 1 heure pour 10^6 combinaisons, alors que je peux faire 10^9 combinaisons (voire plus, je ne me souviens plus) en flottant. Et bruteforcer sur la TI-83, n'en parlons pas.
L'interpréteur Lua de la NSpire semble une bonne option... sauf qu'il calcule en flottant lui aussi, et non pas en décimal. Il fait donc les mêmes erreurs que mon algorithme Java.

Je décide d'en rester là, en me disant que, si quelqu'un trouve un 642, je reviendrai sur Casio... mais visiblement mon 641 était le maximum possible.

Voilà, et encore merci à Nemh qui m'a permis de me rendre compte du vrai algo - sinon je m'en serais rendu compte 4 jours plus tard, et ces 4 jours auraient pu être fatals x)
https://www.planet-casio.com/Fr/forums/lecture_sujet.php?id=14990
(avec en prime supports de recherche en pièce jointe)



Merci à vous tous pour vos efforts avec les diverses stratégies déployées et la persévérance jusqu'au bout du temps imparti et des décimales de la calculatrice ! :bj:

Lien vers le sujet sur le forum: Résultats catégorie Casio concours Galactik rentrée 2017 (Commentaires: 24)

Mise à jour TI-Innovator 1.2.0.18 : compatibilité TI-Rover

Nouveau messagede critor » 23 Nov 2017, 23:29

89619022La mise à jour
1.2
dédiée au périphérique
TI-Innovator Hub
pour
TI-83 Premium CE
et
TI-Nspire CX
est désormais disponible. Plus précisément, nous passons donc de la version
1.1.0.16
à la version
1.2.0.18
.

Bien que ce ne soit apparemment pas mentionné dans sa documentation, cette mise à jour est nécessaire pour les utilisateurs du robot
TI-Rover
, rajoutant apparemment la compatibilité avec ce dernier. En effet, sans cette mise à jour l'envoi comme déjà montré de la 1ère commande CONNECT RV génère une erreur INVALID OPTION.



Téléchargements
:
Lien vers le sujet sur le forum: Mise à jour TI-Innovator 1.2.0.18 : compatibilité TI-Rover (Commentaires: 0)

Résultats catégorie TI concours Galactik rentrée 2017

Nouveau messagede critor » 14 Nov 2017, 20:08

Image

Après la publication des participations dans un article précédent des participations anonymisées à notre concours de rentrée 2017
Galactik
, voici enfin ce soir la levée de l'anonymat avec le classement catégorie
TI
! :bj:

En
18ème
position, félicitons
Sébastien B.
qui a trouvé un score de à l'aide de sa
TI-83 Premium CE
ou compatible.


17ème
et toujours sur
TI-83 Premium CE
ou compatible, bravo à qui après
2 participations
a réussi à atteindre le score de .


A la
16ème
place c'est un chercheur
TI-Nspire
que nous accueillons, avec son score de .


qui se classe
15ème
décroche un score de après avoir cherché sur
TI-82 Advanced
ou compatible.


C'est à nouveau muni d'une
TI-83 Premium CE
ou compatible, que arrive
14ème
avec son score de .


13ème
, a choisi quant à lui de chercher le problème sur
TI-Nspire
et arrive à faire un score de après
2 participations
.


A la
12ème
place, bravo à
Thimoté L.
qui, muni de sa
TI-83 Premium CE
ou compatible, arrive à monter jusqu'à un score de .


Toujours à l'aide d'une
TI-83 Premium CE
ou compatible,
Mohammad G.
se classe
11ème
avec son score de .


avec sa
TI-Nspire
arrive à nous décrocher la
10ème
place avec un score de après avoir persévéré pendant
5 participations
.


C'est quant à lui au bout de
4 participations
à l'aide de sa
TI-83 Premium CE
ou compatible que arrive
9ème
avec un score de . Remarquons qu'il s'agit du premier candidat à utiliser des coordonnées avec une partie décimale non nulle.


Armé de sa fidèle
TI-Nspire
, arrive au bout de
4 participations
à une disposition évaluée à , se classant ainsi
8ème
. Remarquons qu'il s'agit de la première configuration géométriquement remarquable, avec une disposition en quadrillage.


Après
2 participations
avec sa
TI-82 Advanced
ou compatible,
Guillaume S.
se place quant à lui
7ème
avec son score de .


Toujours fidèle à ses
TI-Nspire
, termine avec un score de à la
6ème
place au bout de
3 participations
.


C'est également sur
TI-Nspire
que
Yassine E.
arrive à faire légèrement mieux avec après seulement
2 participations
, terminant ainsi
5ème
.


Comme promis tous les participants précédents gagnent un compte
TI-Planet Premium
, et si ils en avaient déjà un il leur est parfaitement possible d'en faire don à une autre personne.

Voici maintenant, dans l'inverse de l'ordre dans lequel ils pourront puiser dans la dotation annoncée afin de composer leur lot, les 4 meilleurs participants.

En
4ème
position, toutes nos félicitations à qui, muni d'une simple
TI-82 Advanced
ou compatible, arrive à atteindre un score de après avoir persévéré pendant
7 participations
. Remarquons ici aussi une disposition géométriquement remarquable, selon un quadrillage triangulaire.

@LaTaupe, comment as-tu fait pour accumuler autant de millions ?

LaTaupe a écrit:Dans un premier temps, j'ai décidé de créer un algorithme en python utilisant le principe de la programmation génétique. Apres avoir fait tourner mon PC pendant quelques nuits, je n'ai obtenu qu'un score de 43 millions dans ma catégorie TI. Par conséquent, j'ai changé de méthode en écrivant un algorithme testant des configurations se basant sur une structure hexagonale. En effet, pour maximiser le score entre deux étoiles, il faut que ces dernières soient à une distance de 20 ou éloignées le plus possible l'une de l'autre. La structure hexagonale permet ainsi d'optimiser les distances entres les étoiles pour avoir le plus d'écart de 20. C'est ainsi que j'ai pu obtenir ma quatrième place dans la catégorie TI à 820 près. (encore désolé pour le participant 16)


Se classant
3ème
, tout notre respect à qui atteint directement un score de après avoir cherché sur
TI-83 Premium CE
ou compatible. Nous avons ici encore une disposition selon un quadrillage en triangle, et l'on peut noter qu'il reste quelques traces de son raisonnement dans la liste fournie avec quelques valeurs exactes.

@Disconnected59, comment t'y es-tu pris pour disposer tes étoiles ?

Disconnected59 a écrit:Pour le concours, je suis tombé sur le concours lorsque je venais chercher des informations sur ma Ti 83CE et l’application dont j’avais besoin pour pouvoir le faire communiquer avec mon ordinateur.
Et pour le score, j’ai passé beaucoup de temps à essayer de réussir, j’ai même essayé plusieurs méthodes avec quelque algorithme pour m’aider, je suis alors tombé sur une liste me rapprochant de 49 millions et ensuite j’ai fait un Brut-force localisé sur la liste pour forcer le passage et ainsi me retrouver avec ce score.


Congratulations to who ranked
2nd
using his
TI-83 Premium CE
or compatible to improve the high score by 2 millionth up to after submitting only
2 entries
.

@jacobly, how did you achieve such a high score ?

jacobly a écrit:I used simulated annealing programmed in C to get all of my scores. Initially I assumed that I was restricted to integer coordinates which was difficult to optimize and didn't produce very good scores. Then I found out that other people were getting higher scores with fractional coordinates so I switched to a continuous algorithm. At some point I noticed that most of my good configurations had the stars near a "hexagonal" lattice of points where each point is 20 units away from 6 other points. I used this information to create another discrete implementation that only considered the points on this lattice. This let me find close to an optimal score fairly quickly, which I could then polish off by alternating two continuous algorithms. Since I was working with binary floats the whole time, I had no reasonable way to fully optimize the last digit when computed with decimal rounding error, and I ended finding a solution within an ulp of first place in 3 categories.
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&start=10#p223474


Enfin, nous avons qui termine
1er
en améliorant encore le meilleur score d'un millionième jusqu'à à l'aide de sa
TI-83 Premium CE
ou compatible après seulement
2 participations
. Nous retrouvons ici aussi une disposition remarquable selon un quadrillage triangulaire, ainsi que quelques traces de recherche avec quelques valeurs exactes dans la liste.

@Zezombye, le monde entier attend de connaître ton secret.

Zezombye a écrit:Le 17 septembre, je découvre la surprise dont parlaient les admins : le concours de rentrée.
J'ouvre le g1m, puis je me mets à décortiquer l'algorithme pour savoir comment est calculé le score.
On se rend compte rapidement que le calcul du score se fait dans cette boucle :
Code: Tout sélectionner
While K!=48 And K!=47 And K!=44
   If Abs Frac List 8[P] :Then
      
      Int List 8[P]->List 8[P]
      7->K
   Else
      
      GetKey->K
   IfEnd
   List 8[P]->Z
   If K=28 And ImP Z<Ymax-T Or K=27 And ReP Z<Xmax Or K=38 And ReP Z>Xmin Or K=37 And ImP Z>Ymin Or K=7 :Then
      
      Z+(K=27)-(K=38)+i((K=28)-(K=37))->List 8[P]
      For 1->I To P-1+(K!=7)(M-P+1)
         If I!=P :Then
            
            S+Mat G[I,P](1/(1+Abs ((Mat G[I,P]>0 And I>1)F-Abs (List 8[I]-List 8[P])))-(K!=7)/(1+Abs ((Mat G[I,P]>0 And I>1)F-Abs (List 8[I]-Z))))->S
         IfEnd
      Next
   IfEnd
   PlotOff ReP Z,ImP Z
   If K=78 Or K=77 Or K=7 :Then
      
      If K=77 :Then
         
         M-MOD(M-P+1,M-1)->P
      Else
         
         2+MOD(P-1,M-1)->P
      IfEnd
      PlotOff ReP List 8[P],ImP List 8[P]
      PlotOn ReP Z,ImP Z
   IfEnd
   PlotChg ReP List 8[P],ImP List 8[P]
   Text 1,1,S
WhileEnd


Plusieurs variables sont importantes ici :
- K pour Key, avec K=7 lors de l'initialisation
- S pour Score
- I pour Itérateur
- P pour Etoile (2 à 7, l'étoile 1 étant le centre de l'écran)
- F pour Distance (20, ne change pas).

On remarque que le code exécuté pour le recalcul du score est inutile ici, car on veut juste comprendre l'algo. Ainsi, on assume que K = 7 est toujours vrai.
En étudiant un peu plus l'algorithme, on remarque que la boucle While fonctionne ici comme un For qui itère sur P de 2 à 7. En pseudo-langage, ça donne :
Code: Tout sélectionner
for (int P = 2; P <= 7; P++) {

   for (int I = 1; I <= P-1; I++) {
                                    1      
      S+Mat G[I,P]*(--------------------------------------------------
                    1+|20(Mat G[I,P]>0 And I>1)-|List 8[I]-List 8[P]||
      
                          K != 7
      - -------------------------------------------) -> S
        1+|20*(Mat G[I,P]>0 And I>1)-|List 8[I]-Z||
   }            
}


Mais comme K = 7, alors K != 7 est faux, donc on peut directement enlever cette portion du code :
Code: Tout sélectionner
for (int P = 2; P <= 7; P++) {

   for (int I = 1; I <= P-1; I++) {
                                    1            
      S+Mat G[I,P]*(--------------------------------------------------)->S
                    1+|20(Mat G[I,P]>0 And I>1)-|List 8[I]-List 8[P]||
   }      
   
}


Tout de suite, c'est plus simple.
La matrice G vaut :
Code: Tout sélectionner
     1       2        3       4       5        6       7

1      0  485402   366483  895650   398681   246960  1062990
2            0    2603497  -18533 -3484358   386459  -768468
3                   0    -646585 -3156512  1487979 -2522960
4                           0     2602703   632508 -2423677
5                                 0    -1746276  1331355
6                                      0    -2905103
7                                          0

À noter que G[X,Y] = G[Y,X] (avec l'instruction Mat G+Trn Mat G->Mat G).

Pour avoir le meilleur score, il faut donc influer sur le dénominateur de la fraction : 1+|20(Mat G[I,P]>0 And I>1)-|List 8[ I ]-List 8[P]||.
Ici, |List 8[ I ]-List 8[P]| est la distance entre I et P. Deux cas sont possibles :
- Si Mat G[I,P] > 0 : dans ce cas il faut que le dénominateur soit le plus proche de 1. En étudiant bien le dénominateur, il faut que |20(Mat G[I,P]>0 And I>1)-|List 8[ I ]-List 8[P]|| = 0, ce qui signifie que la distance entre I et P doit être la plus proche de 20.
- Si Mat G[I,P] <= 0 ou que I = 1 (on calcule le score par rapport au centre), alors plus I sera proche de P, plus la fraction sera proche de 1. Cela veut dire que si Mat G[I,P] <= 0 alors il faut que I soit le plus éloigné possible de P, et si I = 1 alors il faut que I soit aux mêmes coordonnées que P.

Toutefois, mon cerveau a décidé pour une quelconque raison de lire la condition (Mat G[I,P]>0 And I>1) en tant que (Mat G[I,P]=0 And I>1), ce qui change tout. Cela veut dire que si Mat G[I,P] < 0, alors I doit être à une distance éloignée de 20 de P, donc I peut être aux mêmes coordonnées que P avec une perte de score minime ! (ce qui n'est pas le cas, mais c'est ce que je croyais au début).

J'ai donc tracé le graphe des liaisons entre les étoiles :

Puis, je me suis rendu compte qu'il n'y avait qu'une seule configuration possible pour qu'il n'y ait que des traits verts reliant les étoiles :


La seule modification ici était d'influer sur l'angle du triangle 6-2-3 (par rapport à l'horizontale), ce qui avait un impact car G[2,4] = -18533 alors que G[3,4] = -646585. Après un bruteforce, je trouve mon score de 9 843 347,30939981. Bizarrement, mon algorithme trouve un score de 9.6 millions (mais qui me donne 9.8M lorsque je transpose la liste sur la calculatrice), mais j'ai attribué ça à un changement de moteur de calcul.
Convaincu que le seul moyen de battre mon score n'était que de quelques millièmes en changeant un peu l'angle du triangle 6-2-3, je cherche sur TI et HP, mais n'arrive qu'à faire 46M et 123M, loin des premiers.

---
Un mois plus tard, le 28 octobre, Nemhardy me donne un coup de pied au cul en sortant un score de 9 966 747. Cela implique une toute nouvelle configuration, ce que je trouve bizarre : il n'y a pas de moyen évident d'arranger les étoiles autre que ma configuration.
En cherchant un peu, je trouve qu'en rompant la liaison 4-6 et en plaçant le 4 sur le 6, cela pourrait faire augmenter mon score :
- Rompre la liaison 4-6 me fait perdre 632k
- Placer le 4 sur le centre (avec le 7) me fait gagner 895k
- La pénalité de 4 et 7 est divisée par 21, ça me fait perdre 2423/21 ~= 120k.
Tout cela s'additionne pour me donner une amélioration d'environ 120k, ce qui correspond à peu près au delta de 123k entre mon score et celui de Nemhardy.

Je teste, et je trouve un score de... 7 millions ?! Bizarre. Je refais mes calculs : seuls les 3 paramètres cités varient. Je retélécharge Galactik au cas où j'aurais modifié le calcul du score dans un de mes tests : même chose. Je teste sur Graph 90+E (en devant en plus démarrer ma VM, car j'avais épuisé la période d'essai de l'émulateur) : même chose.
Aurais-je fait une erreur dans le recopiage de l'algorithme ? Je regarde, et je ne vois pas. Je remarque que le score de 7 millions était comme si la pénalité de la liaison 7-4 était appliquée sans être divisée par 20... il doit y avoir une erreur, car G[7,4] != 0 et I > 1 donc la condition devrait être vraie.
Je teste : P = 4, I = 7, Mat G[I,P] = -2M, alors pourquoi (Mat G[I,P] = 0 And I>1) retourne 0...
...
...Ah, c'est Mat G[I,P] > 0.

(oui, il m'a fallu jusqu'au dernier moment pour que mon cerveau corrige l'erreur)

Maintenant que je connais le vrai fonctionnement de l'algorithme, une nouvelle configuration semble logique : en effet, cela veut dire que pour des étoiles à 20 de distance, les liaisons négatives sont divisées par 21.
La liaison 4-2 n'imposant qu'une pénalité de -18k, je peux les superposer, ce qui me donne une amélioration de -1063k + 896k + 485k = 318k, et la configuration suivante :

L'amélioration n'est que de 147k en raison du rapprochement des liaisons 5-3, 3-4 et 5-6, qui font sentir leurs millions de pénalités.
Un autre bruteforce pour trouver l'angle du triangle 2-3-6 (et cette fois mon algo en java trouve le même score qu'affiché sur la calculatrice), et je trouve un score de 9 991 310, qui est d'ailleurs toujours premier de la catégorie casio.

---
Avec ces connaissances en plus, j'ai re-regardé mes configurations TI et HP, que je triturais pendant un mois (mais avec un algo faux). Je me suis aidé des images des matrices :

Sur HP, je n'ai pas réussi à bien améliorer mon score : 125M contre 123M... et de toute façon la catégorie était saturée, avec 3 participants différents étant tombés sur ce qui est visiblement le score maximal.

Sur TI, après un peu d'expérimentation, je suis tombé sur cette configuration :

Ce qui me donnait 48M... pas assez, mais suffisant pour être 2ème.
Pour modifier la configuration, il faut noter que le polygone 2-11-6-10-7 est inaltérable (car composé uniquement de triangles verts) ; impossible de déplacer n'importe laquelle de ces 5 étoiles sans baisser mon score.

J'ai essayé de relier la liaison 8-5, mais c'est impossible, car il fallait alors superposer des étoiles avec une liaison négative, ou casser des liaisons positives, ce qui baissait mon score (la liaison 8-5 ne m'apportant que 1.22M).

Mais, en mettant le 7 sur le 3, il est possible de changer la structure tout en gardant l'intégralité des liaisons vertes :

On voit que, tout comme casio, on peut influer sur l'angle de l'étoile 8 par rapport à l'étoile 10. Un petit bruteforce plus tard, j'ai un score de 49 942 613, ce qui me classe premier. Mais le participant n°23 avait soumis un score de 49 946k avant de se rabattre vers HP - il y avait donc une amélioration à faire.

Y a-t-il quelque chose qui pourrait bouger dans notre configuration ? On élimine tous les triangles, il reste donc le losange 9-5-7-4 dont on peut modifier la distance 5-4 afin d'améliorer le score.
Un peu de trigonométrie pour déterminer les coordonnées de 9 par rapport à l'angle de 4 par rapport à 7, et avec un bruteforce, je trouve 49 946k.
Mais étant donné qu'il y a 2 angles à modifier : l'angle de 4 par rapport à 7, et l'angle de 8 par rapport à 10, il faut bruteforcer les 2 afin de trouver la meilleure configuration.

Un premier bruteforce et je trouve 49 946 730.080507. Un bon début, mais il me reste 133 millionièmes.
En raffinant, je me rapproche : 509, 543, puis un score de 639, que je soumets.
45 mn plus tard, je trouve un score de... 641 ! J'obtiens alors la première place au classement TI, et y reste.
Durant les prochains jours, je tente de trouver un 642, sans succès. Mon bruteforce atteint les limites, et la différence de moteur de calcul se fait sentir : des scores supposés être supérieurs à mon 641 se traduisent par un 640, 639, ou pire, .073543 (7 millièmes de moins).

J'essaie donc le BigDecimal pour garder un moteur de calcul décimal, mais... c'est lent. 1 heure pour 10^6 combinaisons, alors que je peux faire 10^9 combinaisons (voire plus, je ne me souviens plus) en flottant. Et bruteforcer sur la TI-83, n'en parlons pas.
L'interpréteur Lua de la NSpire semble une bonne option... sauf qu'il calcule en flottant lui aussi, et non pas en décimal. Il fait donc les mêmes erreurs que mon algorithme Java.

Je décide d'en rester là, en me disant que, si quelqu'un trouve un 642, je reviendrai sur Casio... mais visiblement mon 641 était le maximum possible.

Voilà, et encore merci à Nemh qui m'a permis de me rendre compte du vrai algo - sinon je m'en serais rendu compte 4 jours plus tard, et ces 4 jours auraient pu être fatals x)
https://www.planet-casio.com/Fr/forums/lecture_sujet.php?id=14990
(avec en prime supports de recherche en pièce jointe)


Merci à vous tous pour vos efforts avec les diverses stratégies déployées et la persévérance jusqu'au bout du temps imparti et des décimales de la calculatrice ! :bj:

Lien vers le sujet sur le forum: Résultats catégorie TI concours Galactik rentrée 2017 (Commentaires: 50)

-
Rechercher
-
Sujets à la une
"NumWorks++": Challenge de modification matérielle pour rajouter une puce de mémoire Flash !
Offre TI-Planet/Jarrety pour avoir la TI-83 Premium CE avec son chargeur pour 79,79€ port inclus !
Offre TI-Planet/Jarrety pour avoir la TI-Nspire CX CAS à seulement 130€ TTC port inclus!
Jailbreake ta TI-Nspire avec Ndless et profite des meilleurs jeux et applications !
Transforme ta TI-Nspire CX en console Game Boy Advance!
12345
-
Donations/Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
PayPal : paiement en ligne sécurisé - secure online payments
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


-
Sélections fichiers
Partenaires et pub
Notre partenaire Jarrety 
-
Stats.
304 utilisateurs:
>224 invités
>74 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)