Résultats du triconcours : les plus forts !
Posté le 18/11/2018 19:31
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
, 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
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.
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)…
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)
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.
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 !
Citer : Posté le 18/11/2018 20:00 | #
Merci à tous !
Citer : Posté le 18/11/2018 20:21 | #
J'ai corrigé une erreur de lien vers TI-Planet.
Bravo à tous les participants, il est très intéressant de voir vos approches du problème !
Citer : Posté le 18/11/2018 20:23 | #
Vraiment intéressant bravo à tout les participants
Citer : Posté le 18/11/2018 20:37 | #
Donc Pavel si tu nous lis, tu as fait preuve d'une force divine, tu es premier, à toi l'honneur !
Attention, dans ton cas tu as participé aux 3 défis, et n'as rien pris aux résultats du 1er défi.
Tu peux donc cette fois-ci :
- prendre un lot sans calculatrice physique et te réserver ainsi le choix d'un lot avec calculatrice physique pour les résultats du prochain défi
- prendre un lot avec calculatrice physique et te réserver ainsi le choix d'un lot sans calculatrice physique pour les résultats du prochain défi
Alors, tu nous choisis quel lot ?
Le détail illustré est sur le post TIP : https://tiplanet.org/forum/viewtopic.php?t=21986&p=236958#p236962
Ajouté le 20/11/2018 à 22:17 :
C'est fait pour Pavel et Ne0tuX.
J'appelle maintenant @Nemhardy pour le choix de son lot :
https://tiplanet.org/forum/viewtopic.php?f=49&t=21986&p=237032#p237032
Ajouté le 22/11/2018 à 17:45 :
Merci @Nemhardy.
@Hackcell, c'est ton tour !
https://tiplanet.org/forum/viewtopic.php?f=49&t=21986&p=237067#p237067
Citer : Posté le 22/11/2018 18:08 | #
Un pack Émeraude, s'il te plaît.
Avec le troisième stylo,
La clé USB fx-92 collège
Et un poster graph 25/35/90+E
Est-ce bon? J''ai plus trop les neurones en place actuellement
Citer : Posté le 22/11/2018 18:37 | #
Merci, ça m'a l'air bon.
Ajouté le 22/11/2018 à 18:45 :
@Zezombye, à toi :
https://tiplanet.org/forum/viewtopic.php?f=49&t=21986&p=237070#p237070
Citer : Posté le 22/11/2018 19:52 | #
@Critor: ou en est-tu dans la distribution des lots... j'ai du mal a suivre ?
-Planétarium 2
Citer : Posté le 23/11/2018 07:57 | #
Épreuve de force, 8eme position me semble t'il...
Du coup c'est pas tout de suite pour l'épreuve de courage
Citer : Posté le 23/11/2018 11:26 | #
Bon, on va tacher d'être patient
-Planétarium 2
Citer : Posté le 23/11/2018 18:30 | #
Ais-je le droit d'avouer que j'ai hâte de voir les résultats du Courage ?
Quand je vois le peu d'engouement que suscite la Graph 90, je me dis que j'ai une chance de l'avoir un jour...
Citer : Posté le 23/11/2018 18:39 | #
Elles sont parties quand même, mais pas en premier effectivement.
Ce sont pourtant d'excellentes machines et de plus ici superbement accompagnées.
Citer : Posté le 23/11/2018 18:41 | #
Du coup, toi qui est connaisseur, tu penses qu'arrivant en 7ème position pour le Courage, j'ai une chance de remporter une CG90+E ou pas ?
Citer : Posté le 23/11/2018 18:44 | #
Je ne peux pas te le garantir.
Mais deux personnes devant toi au défi de Courage visent un lot TI je pense.
Parce que sinon... elles auraient déjà pris une calculatrice au défi de Force plutôt que des goodies.
Citer : Posté le 23/11/2018 18:59 | #
Si tu n'en gagnes pas, tu pourrais toujours développer sur une de CreativeCalc !
Citer : Posté le 23/11/2018 19:11 | #
Je suppose qu'une personne devant moi va ne pas choisir une calto. Ce qui m'en laisse une (j'espère !)
Je me contenterais des miettes, tant que j'ai une nouvelle calc x)
Citer : Posté le 23/11/2018 19:14 | #
Regarde déjà si parmi les gagnants, certains n'auraient pas déjà choisi une calculatrice à un défi précédent !
Citer : Posté le 23/11/2018 20:01 | #
Si je n'en gagne pas, j'aurais une TI CE-premium un modèle plus intéressant que ma Graph35++ donc même si je suis "perdant" je suis gagnant !
Citer : Posté le 23/11/2018 22:32 | #
Du coup, toi qui est connaisseur, tu penses qu'arrivant en 7ème position pour le Courage, j'ai une chance de remporter une CG90+E ou pas ?
J'ai finis 7 ème, et même si j'ai pris la peluche Ti-Planet ♥, il restait toujours des CG90+E
Citer : Posté le 26/11/2018 12:54 | #
Sont partis ce midi les lots de :
- Jacobly
- Ne0tuX
- Nemhardy
- Anonyte
Bonne réception à vous.
Il manque Alexmaster350 dont l'emballage n'est pas terminé.
Et pour les autres, ce sera traité une fois que l'on aura leur choix aux résultats du 3ème défi.