π
<-
Chat plein-écran
[^]

Concours de rentrée 2020 - défi Python de Xuanwu

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude critor » 20 Oct 2020, 09:47

So commandblockguy, what would you like ? :)

And what's your secret for achieving the best score ? ;)
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41468
Images: 14480
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude commandblockguy » 20 Oct 2020, 21:10

I'll take the Numworks calc (Sagittarius).

As for my strategy, I basically found a path through the maze by hand that had as few points as possible, without worrying about my score too much. I made sure to take a very shallow angle when exiting so that the path would be long enough to get the maximum score.

I then tested every single combination of angles and distances that would put me within some distance (if I remember correctly, about 1.5 tiles, though I changed it several times) of my original points, while still allowing me to get the maximum score. This was feasible because you get points off for each digit after the first decimal place, or before the units place, which means that there are only 100 angles and 100 distances to try for each point. The exception for this is the last point, which has to be more than 10 units away in order to meet the length requirement. This took a few hours to run in its entirety, and I was left with a few thousand paths. Prior to the scoring change, all of these paths would have left me with a score of 72, but after the scoring change it was now possible to get a fractional score.

Image
A "heatmap" of all the paths I found. The color of each point represents the last "target" point it was able to get to, with purple being the final point, outside of the maze.

The fractional part of the score was determined based on the sine of the sum of the angles and distances, which means that the input to sin() could be no more precise than to the tenths place. For the range of numbers that this sum could possibly be without adding a full point to my score, the tenth whose sine is closest to -1 is 11.0, and sin(11) is = -0.999990207.
Unfortunately, none of the few thousand paths that I had found added up to 11.0. However, I realized that I was only calling a_droite() in my path, and that if I replaced a_droite(x) with a_gauche(-x), x would be subtracted from the sum rather than added to it, without actually changing the validity of the path. I tried out every combination of a_droite and a_gauche calls for each of my few thousand paths, and found one that added up to 11.0, giving me a score of 71.0000097934493.

Here's the code that I used to find this path.

You'll notice that this is still very slightly off from my actual score - I realized that I could slightly decrease sin(sum) by slightly decreasing sum, and that I could slightly decrease sum by subtracting a tiny amount from each distance and angle. Normally, this would cause my score to increase by several full points because of the decimal places after the tenths place, but because the score is rounded to 5 decimal places before the length of the number is calculated, if the difference is less than 0.000005, you aren't penalized. So, I subtracted 0.0000049999... from each distance, to get a sum of 10.99991, a sine of -0.99999060081, and a final score of 71.00000939918644. I believe that this is within a floating-point error of the ideal solution.
Here's the solution that I submitted, for reference.

I actually tested all of this on a computer, as I didn't have my EP with me. I ported polycalc to use cv2 for drawing stuff.

I also tried to submit a few, uh, let's call them gimmicky, solutions. My first instinct was to try an integer overflow, but to my disappointment, Python doesn't actually have those. The numbers, they just keep going.
After that, I tried subclassing the float class so that it would return an empty string. Technically, this wasn't modifying the internal state of laby.py :p. I could have also returned a custom string class with a modified __len__ method, but in CPython __len__ must return a positive integer, which also gets converted into a regular integer, not one that I could subclass. Interestingly, MicroPython allows you to return a negative length for __len__, so I could have probably gotten a score of negative infinity if the admins didn't shut that idea down :p.

Finally, I also found a solution that's far better than the others that I decided not to submit since I was already in first. Here's the link if you want to give it a try for yourself.
Avatar de l’utilisateur
commandblockguyPremium
Niveau 2: MI2 (Membre Initié)
Niveau 2: MI2 (Membre Initié)
Prochain niv.: 46.7%
 
Messages: 7
Inscription: 26 Avr 2019, 23:08
Localisation: Texas
Genre: Homme
Calculatrice(s):
MyCalcs profile
GitHub: commandblockguy

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude critor » 20 Oct 2020, 23:44

Thanks for your reply and comprehensive details @commandblockguy. :)

Which NumWorks bag ?
130461304713048

Which NumWorks poster ?
1304013039130411304213034

And which Xcas goodies ?
T-shirt ? Hat ? Mousepad ? Sticker ?
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41468
Images: 14480
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude commandblockguy » 21 Oct 2020, 00:01

I'll take the third bag and the fourth poster, and a large shirt.
Avatar de l’utilisateur
commandblockguyPremium
Niveau 2: MI2 (Membre Initié)
Niveau 2: MI2 (Membre Initié)
Prochain niv.: 46.7%
 
Messages: 7
Inscription: 26 Avr 2019, 23:08
Localisation: Texas
Genre: Homme
Calculatrice(s):
MyCalcs profile
GitHub: commandblockguy

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude TIny_Hacker » 21 Oct 2020, 00:48

Very nice @commandblockguy, I remember you bragging about it and that (non-submitted) score is INSANELY lower than the others! Now I feel so dumb not going that path...
Avatar de l’utilisateur
TIny_HackerPremium
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 95.5%
 
Messages: 62
Inscription: 01 Oct 2020, 00:50
Localisation: USA
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: TIny_Hacker
Twitter/X: TIniestHacker
GitHub: TIny-Hacker

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude critor » 21 Oct 2020, 07:51

Thanks @commandblockguy.

Also I forgot, which TI-Planet sticker ?
11614
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41468
Images: 14480
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude critor » 21 Oct 2020, 07:58

Also to everybody, please make a post your details/explanations/secrets. :)

Aussi à tous, svp faites un post avec vos détails / explications / secrets. :)
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41468
Images: 14480
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude Pavel » 21 Oct 2020, 10:38

critor a écrit:Also to everybody, please make a post your details/explanations/secrets. :)

Aussi à tous, svp faites un post avec vos détails / explications / secrets. :)

Voici une explication de mon approche pour trouver une solution à ce défi.

J'ai commencé par essayer de comprendre comment la consommation est calculée. Voici les parties du code Python montrant tous les composants des calculs de consommation:
Code: Tout sélectionner
def fix_angle(a):
  return a * 2 * asin(1) / pi

def a_gauche(a):
  global state
  state[7] += a
  state[5] += 5 + cout(a)

def avancer(l):
  global state
  state[7] += l
  state[5] += 8 + cout(l)
  while(l > 0):
    l -= .25
    state[6] += (state[6] < 200)

def aller_selon(f):
  global state
  state = [0, .5, 0, 0, .5, 0, 0, 0]
  f()
  state[5] += sin(fix_angle(state[7])) - state[6] // 2
  print('Consommation : ' + str(state[5]))

Apparemment, la consommation se compose des trois éléments suivants:
Code: Tout sélectionner
state[5] = consommation de base
state[6] = distance totale parcourue multipliée par quatre
state[7] = angle total + distance totale

Ensuite, j'ai testé la fonction 'cout()' qui est utilisée dans les calculs de consommation:
Code: Tout sélectionner
>>> from laby import *
>>> cout(5)
3
>>> cout(0.5)
3
>>> cout(0.05)
4
>>> cout(5e-3)
5
>>> cout(5e-4)
6
>>> cout(5e-5)
7
>>> cout(5e-6)
3

Il semble donc que la consommation puisse être minimisée en combinant les éléments suivants:
  • minimiser la quantité de manoeuvres
  • minimiser 'sin(state[7])'
  • maximiser la distance totale parcourue
  • ne pas utiliser plus d'un chiffre décimal après la virgule décimale
  • essayer d'exploiter le faible coût du 'cout(5e-6)'
Pour minimiser 'sin(state[7])', j'ai utilisé le code Python suivant pour créer un tableau montrant les valeurs de la fonction 'sin()' pour différents angles avec un seul chiffre décimal après la virgule décimale:
Code: Tout sélectionner
from math import pi, sin

l = []

for i in range(-10, 11):
  a = round(-pi/2 + 2 * pi * i, 1)
  l.append((a, sin(a)))

l.sort(key=lambda e: e[1])

for e in l:
  print('a = %5.1f -> sin(a) = %f' % e)

Voici le résultat:
Code: Tout sélectionner
a = -64.4 -> sin(a) = -0.999996
a = -26.7 -> sin(a) = -0.999994
a =  11.0 -> sin(a) = -0.999990
a =  48.7 -> sin(a) = -0.999986
a =  42.4 -> sin(a) = -0.999934

De petites valeurs de 'state[7]' sont donc nécessaires pour une faible consommation. Vu que 'state[7]' est la somme des angles et des distances et que les distances ne peuvent pas être négatives, alors les valeurs des angles passés à la fonction 'a_gauche()' doivent être négatives.

Une fois que tout ça est devenu plus ou moins clair, j'ai modifié le code laby.py pour en faire une version qui peut être contrôlée comme un jeu vidéo avec les touches haut/bas/gauche/droite sur le clavier:
https://gitea.planet-casio.com/Pavel/labygui

En utilisant cette approche, j'ai obtenu la solution suivante:
Code: Tout sélectionner
from laby import *

def chemin():
  for e in [(-6.6, 2.3), (-7.3, 6.3), (-5.2, 4.6), (-4.8, 4.1), (-7.3, 6.3), (-8.3, 3.8), (-5.1, 3.8), (-2.3, 4.3), (9.1, 13.3)]:
    a_gauche(e[0])
    avancer(e[1])

aller_selon(chemin)

La consommation correspondant à cette solution est de 71.0000097934493.

À ce stade, je n'ai toujours pas exploité le faible coût du 'cout(5e-6)'. J'ai donc essayé d'ajouter ou de soustraire 5e-6 des distances et des angles. La solution qui m'a donné le score le plus bas (71.00000939918644) était la suivante:
Code: Tout sélectionner
from laby import *

def chemin():
  for e in [(-6.6, 2.3), (-7.3, 6.3), (-5.2, 4.6), (-4.8, 4.1), (-7.3, 6.3), (-8.3, 3.8), (-5.1, 3.8), (-2.3, 4.3), (9.1, 13.3)]:
    a_gauche(e[0] - 5e-6)
    avancer(e[1] - 5e-6)

aller_selon(chemin)

Au moment où j'ai trouvé cette solution, elle était déjà soumise par commandblockguy et j'ai dû trouver la deuxième meilleure solution (71.00000939918645) en ajoutant de très petites valeurs aux angles et aux distances:
Code: Tout sélectionner
from laby import *

def chemin():
  for e in [(-6.6, 2.3), (-7.3, 6.3), (-5.2, 4.6), (-4.8, 4.1), (-7.3, 6.3), (-8.3, 3.8), (-5.1, 3.8), (-2.3, 4.3), (9.1, 13.3)]:
    a_gauche(e[0] - 5e-6 + 1e-13)
    avancer(e[1] - 5e-6 + 1e-13)

aller_selon(chemin)
Dernière édition par Pavel le 21 Oct 2020, 10:57, édité 1 fois.
Avatar de l’utilisateur
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Prochain niv.: 83.6%
 
Messages: 107
Inscription: 19 Sep 2018, 10:50
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude cent20 » 21 Oct 2020, 10:50

Bravo pour ces explications d'une clarté lumineuse.

Je viens de comprendre que du coup, j'aurais pu fabriquer le score 71,00000939918646, oui enfin il fallait déjà arriver à faire l'intégralité du raisonnement pour cela.

Et merci pour le simulateur PC, une aide inestimable.
Image
Enseignant de mathématiques et d'informatique. Spécialité NSI : Des projets, des tutos, mais aussi de l'art
Calculatrice NumWorks : Des applications et des jeux, scripts, 📙 Découvrir la NumWorks
Avatar de l’utilisateur
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 45.9%
 
Messages: 1009
Images: 64
Inscription: 17 Mai 2012, 09:49
Localisation: Avignon
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: nsi_xyz

Re: Concours de rentrée 2020 - défi Python de Xuanwu

Message non lude critor » 21 Oct 2020, 15:43

critor a écrit:Thanks @commandblockguy.

Also I forgot, which TI-Planet sticker ?
11614

Ok, 1er autoccollant, merci. :)

@Pavel, merci pour ton explication et félicitations. Que nous prends-tu ? :bj:
  • 2 lots Capricorne ♑ : 1 calculatrice Casio Graph 90+E + 1 pack de goodies Casio + 1 goodie Xcas au choix + 1 pack de goodies TI-Planet & Planète Casio
  • 2 lots Bélier ♈ : 1 solution d'émulation Casio au choix + 1 CD de vidéos Casio fx-CG20 ou catalogue de produits Casio au choix + 1 pack de goodies Casio + 1 goodie Xcas au choix + 1 pack de goodies TI-Planet & Planète Casio
    Show/Hide spoilerAfficher/Masquer le spoiler
    CD de 54 vidéos pour plus de 8h par Jean-Michel Ferrard, pour fx-CG20 mais compatible Graph 90+E, pour Windows / Mac.

    Détail des solutions d'émulation Casio au choix :
    • clé USB 8 Go d'émulation permanente au choix, à jour avec 3 émulateurs pour Windows : fx-92+ Spéciale Collège + Graph 35+E II 3.30 + Graph 90+E 3.40
    • licence 3 ans utilisable pour l'installation de tout ou partie des logiciels d'émulation suivants :

    1161713022130231302513024
  • Lot Serpentaire ⛎ : 1 goodie HP au choix + 1 goodie Xcas au choix + 1 pack de goodies TI-Planète-Casio
    Show/Hide spoilerAfficher/Masquer le spoiler
    Poster HP : format 59,2×40 cm².

    Clé USB HP : 16 Go de capacité nominale.

    1303811654116539656
  • 1 lot Sagittaire ♐ : 1 calculatrice NumWorks N0110 + 1 pack de goodies NumWorks + 1 goodie Xcas au choix + 1 pack de goodies TI-Planet & Planète Casio
  • 2 lots Balance ♎ : 1 couvercle NumWorks + 1 autocollant NumWorks + 1 enveloppe NumWorks ou carte postale NumWorks ou carte de visite-énigme NumWorks au choix + 1 pack de goodies NumWorks + 1 goodie Xcas au choix + 1 pack de goodies TI-Planet & Planète Casio
    Show/Hide spoilerAfficher/Masquer le spoiler
    Couvercle NumWorks au nouveau format N0110 protégeant mieux l'écran contre les rayures, mais restant parfaitement utilisable sur l'ancien modèle N0100.

    11649130361303013026130271302813029


  • Lot Taureau ♉ : 1 calculatrice TI-Nspire CX II-T CAS + 1 licence logiciel TI-Nspire CAS élève + 1 pack de goodies TI + 1 goodie Xcas au choix + 1 pack de goodies TI-Planète-Casio
  • Lot Lion ♌ : 1 calculatrice TI-Nspire CX II-T + 1 licence logiciel TI-Nspire élève + 1 pack de goodies TI + 1 goodie Xcas au choix + 1 pack de goodies TI-Planète-Casio
  • Lot Gémeaux ♊ : 1 calculatrice TI-83 Premium CE Edition Python + 1 adaptateur USB + 1 clavier USB dédié + 1 pack de goodies TI + 1 pack de goodies TI-Planète-Casio
    Show/Hide spoilerAfficher/Masquer le spoiler
    Détail des calculatrices TI-Nspire CX II-T CAS au choix :
    • TI-Nspire CX II-T CAS sous blister version B
    • TI-Nspire CX II-T CAS sous blister version B avec autocollant sceau Comenius Edumedia 2019

    Détail des calculatrices TI-83 Premium CE Edition Python au choix :
    • TI-83 Premium CE Edition Python sous blister version E
    • TI-83 Premium CE Edition Python sous blister version E avec autocollant masquant sceau Approuvé par les familles 2019
1162413045116231182811827113251272411324130601305912281

[info]Détail des packs de goodies communs accompagnants les lots :
  • 1 manuel NumWorks au choix (N0100 ou N0110)
  • 1 cahier d'activités NumWorks SNT 2nde
  • 1 sac NumWorks au choix (N0100 versions 1.0-1.5, N0100 versions 1.6+, ou N0110)
  • 1 cahier NumWorks
  • 1 poster NumWorks au choix :
    • format A0 (118,9×84,1 cm²) : NumWorks N0100 - roulé
    • format A2 (42×59,4 cm²) :
      • NumWorks N0100 : Eduscol / Ministère de l'Education Nationale - roulé - brillant
      • NumWorks N0100 : Eduscol / Ministère de l'Education Nationale - roulé - mat
      • NumWorks N0100 : @Pims / @qabosse / @antalpilipili et ses collègues d'EPS - roulé
      • NumWorks N0100 : Xavier Andréani / TI-Planet - roulé - dédicacé
      • NumWorks N0110 : Comprendre le monde devient un jeu - plié
  • 1 stylo NumWorks
1303513031130461304713048130321306813037130401303913041130421303413033
  • 1 stylo TI au choix
  • 1 porte-documents TI
  • 1 poster TI plié au choix :
    • format ANSI-D (55,9×86,4 cm²) : TI-73 Explorer
    • format A1 (59,4×84,1 cm²) : TI-89 Titanium
    • format 55,75×83,5 cm² : TI-Nspire CX, TI-Nspire CX CAS
  • 1 clé USB TI au choix :
    • clé USB T3 France bleue - 2 Go de capacité nominale
    • clé USB TI-Primaire Plus - 4,01759 Go de capacité réelle
    • clé USB TI-Innovator Rover - 4,01813 Go de capacité réelle
    • clé USB TI-83 Premium CE avec lanière - 4,01811 Go de capacité réelle
    • clé USB TI-83 Premium CE avec chaînette - 4,01811 Go de capacité réelle
    • clé USB TI rouge - 1 Mo de capacité nominale (promotion TI-Primaire Plus défectueuse)
  • 1 autocollant TI ou décalcomanie TI ou pochette CD TI ou lunettes TI au choix
  • 1 cahier TI-83 Premium CE au choix

Aperçus de quelques cahiers d'activités TI-83 Premium CE Python au choix:
11782130651306613067130641306313062130611304913050130431304411533130561307413085130861308713088130811308213073130831308413077130781308313084130721306913070
1 t-shirt Xcas ou casquette Xcas ou tapis de souris Xcas ou autocollant Xcas
  • 1 autocollant TI-Planet au choix
  • 1 autocollant Planète Casio
  • 1 compte premium TI-Planet
1161411615
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.8%
 
Messages: 41468
Images: 14480
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

PrécédenteSuivante

Retourner vers News Divers

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 111 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
1211 utilisateurs:
>1195 invités
>11 membres
>5 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)