π
<-

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

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

So , what would you like ?

And what's your secret for achieving the best score ?

Niveau 19: CU (Créateur Universel)
Level up: 9.7%

Posts: 36270
Images: 9889
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender:
Calculator(s):
Class: Lycée
GitHub: critor

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

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.

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 . 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 .

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.

Niveau 0: MI (Membre Inactif)
Level up: 20%

Posts: 3
Joined: 26 Apr 2019, 23:08
Location: Texas
Gender:
Calculator(s):
GitHub: commandblockguy

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

Thanks for your reply and comprehensive details @commandblockguy.

Which NumWorks bag ?

Which NumWorks poster ?

And which Xcas goodies ?
T-shirt ? Hat ? Mousepad ? Sticker ?

Niveau 19: CU (Créateur Universel)
Level up: 9.7%

Posts: 36270
Images: 9889
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender:
Calculator(s):
Class: Lycée
GitHub: critor

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

I'll take the third bag and the fourth poster, and a large shirt.

Niveau 0: MI (Membre Inactif)
Level up: 20%

Posts: 3
Joined: 26 Apr 2019, 23:08
Location: Texas
Gender:
Calculator(s):
GitHub: commandblockguy

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

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...

TIny_Hacker

Niveau 7: EP (Espèce Protégée: geek)
Level up: 18%

Posts: 24
Joined: 01 Oct 2020, 00:50
Gender:
Calculator(s):

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

Thanks @commandblockguy.

Also I forgot, which TI-Planet sticker ?

Niveau 19: CU (Créateur Universel)
Level up: 9.7%

Posts: 36270
Images: 9889
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender:
Calculator(s):
Class: Lycée
GitHub: critor

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

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

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

Niveau 19: CU (Créateur Universel)
Level up: 9.7%

Posts: 36270
Images: 9889
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender:
Calculator(s):
Class: Lycée
GitHub: critor

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

critor wrote: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: Select all
def fix_angle(a):  return a * 2 * asin(1) / pidef 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: Select all
state[5] = consommation de basestate[6] = distance totale parcourue multipliée par quatrestate[7] = angle total + distance totale

Ensuite, j'ai testé la fonction 'cout()' qui est utilisée dans les calculs de consommation:
Code: Select all
>>> 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: Select all
from math import pi, sinl = []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: Select all
a = -64.4 -> sin(a) = -0.999996a = -26.7 -> sin(a) = -0.999994a =  11.0 -> sin(a) = -0.999990a =  48.7 -> sin(a) = -0.999986a =  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: Select all
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: Select all
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: Select all
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)
Last edited by Pavel on 21 Oct 2020, 10:57, edited 1 time in total.

Niveau 2: MI2 (Membre Initié)
Level up: 53.3%

Posts: 70
Joined: 19 Sep 2018, 10:50
Gender:
Calculator(s):

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

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.

Enseignant de mathématiques et de spécialité NSI ( projets, tutos ...)
NumWork, Python : démineur, snake, tétris

Niveau 13: CU (Calculateur Universel)
Level up: 39.1%

Posts: 524
Images: 38
Joined: 17 May 2012, 09:49
Location: Avignon
Gender:
Calculator(s):

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

critor wrote:Thanks @commandblockguy.

Also I forgot, which TI-Planet sticker ?

Ok, 1er autoccollant, merci.

@Pavel, merci pour ton explication et félicitations. Que nous prends-tu ?
• 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

CD
de
54
vidéos pour plus de
8h
par , 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 :

• Lot
Serpentaire ⛎
:
1
goodie
HP
au choix + 1
goodie
Xcas
au choix + 1
pack de goodies
TI-Planète-Casio

Poster
HP
: format
59,2×40 cm²
.

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

• 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

Couvercle
NumWorks
au nouveau format
N0110
protégeant mieux l'écran contre les rayures, mais restant parfaitement utilisable sur l'ancien modèle
N0100
.

• 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
USB
+ 1
clavier
USB
dédié + 1
pack de goodies
TI
+ 1
pack de goodies
TI-Planète-Casio

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

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

[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
• 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
avec lanière -
4,01811 Go
de capacité réelle
• clé USB
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
au choix

Aperçus de quelques
cahiers d'activités
TI-83 Premium CE Python
au choix:
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
TI-Planet

Niveau 19: CU (Créateur Universel)
Level up: 9.7%

Posts: 36270
Images: 9889
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender:
Calculator(s):
Class: Lycée
GitHub: critor

PreviousNext

### Who is online

Users browsing this forum: Tituya and 8 guests

-
Search
-
Featured topics
1234
-
For more contests, prizes, reviews, helping us pay the server and domains...

Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !

-
Stats.
616 utilisateurs:
>597 invités
>12 membres
>7 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
(English / Français)
Banque de programmes TI
ticalc.org
(English)
La communauté TI-82
tout82.free.fr
(Français)