Forum de Ti-Gen.org, le site francophone des TI

Bienvenue Invité ! Se connecter Mes sujets	Administrer
Utilisateurs actifs : Aucun membre + 1 visiteur

Avant de poster sur le forum, il y a des régles de bases à respecter pour une bonne entente et un respect de tous.
Veuillez lire la charte du forum.

:: Index » Concours - Contests » Concours FireProg » Quatrième Concours FireProg (81 réponse(s))

./POST DE DEPART (post n°0) Marquer comme non lu.

Dari

Ecrit le: Lundi 21 février 2005 à 11:16

Membre privilégié

Messages: 968

Membre n°203

Inscrit le 18 avril 2004

Là c'est de l'algorithmique pure : Vous commencez au pixel de coordonnée (1, 1), et l'arrivée est au point de coordonnées (157,75). Entre les deux, un labyrinthe. Il est entouré par une ligne qui fait le tour.
Votre programme doit trouver la sortie et dessiner le chemin qu'il a fait pour y arriver.
Mon programme est à 41min 14s.
Bonne chance !!! (je vous avais dit que ça serait sadique).
Bien sûr, si votre programme dépasse trois heures, je laisserais tomber. Le labyrinthe est déjà fait, il est sadique. La résolution est de 1 pixel (les cases font un pixel).
GO !

"iPod, therefore, I am."

http://media.laquadrature.net/Quadrature_black-out_HADOPI_468x60px.gif

./Post n°1 Marquer comme non lu.

LionelA

Ecrit le: Lundi 21 février 2005 à 11:39

Modérateur général

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 947

Membre n°206

Inscrit le 19 avril 2004

Je veux participer, mais ca serait plus sympa si on avait un screenshot du labyrinthe ou alors un autre qui servirait d'exemple et de test pour developper l'algo

Merci

Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/

./Post n°2 Marquer comme non lu.

bobti89

Ecrit le: Lundi 21 février 2005 à 12:14

Membre: Maître Ultime

Messages: 2494

Membre n°45

Inscrit le 09 février 2004

Ok, ca c'est intéressant, je vais participer

bob ou bob, vous ne voyez pas la différence. Pourtant il y en a une fondamentale, l'un est écrit à l'endroit, l'autre à l'envers.

Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

./Post n°3 Marquer comme non lu.

bobti89

Ecrit le: Lundi 21 février 2005 à 12:54

Membre: Maître Ultime

Messages: 2494

Membre n°45

Inscrit le 09 février 2004

C'est vrai qu'il faudrait qu'on travaille tous sur le même laby afin de pouvoir comparer nos progs !
Je propose que tu nous donnes un laby (différent de celui avec lequel tu vérifieras).

bob ou bob, vous ne voyez pas la différence. Pourtant il y en a une fondamentale, l'un est écrit à l'endroit, l'autre à l'envers.

Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

./Post n°4 Marquer comme non lu.

Pollux

Ecrit le: Lundi 21 février 2005 à 16:35

Membre: Vétéran

Messages: 95

Membre n°306

Inscrit le 11 juin 2004

tiens, un sujet intéressant ? mais qu'est-ce qui se passe ? #confus#

sinon oui c'est indispensable que tu fasses 1 ou 2 labyrinthes qui aient un peu les mêmes caractéristiques que celui sur lequel tu vas tester... selon qu'il y a ou pas de grandes zones blanches, selon la taille des zones noires, selon la forme du labyrinthe, le meilleur algorithme sera très différent

ah, et autre chose : c'est un peu n'importe quoi la façon dont vous comptez les points, si qqun fait un programme qui met 2h, il n'y aura presque aucune différence au niveau des points entre un programme qui met 5 minutes et un programme qui met 10 minutes, et finalement tout se jouera sur la taille du programme #sick#

quelque chose de plus équitable (et qui ne privilégie pas trop la taille sur la vitesse ou inversement), ce serait de prendre le prog le plus rapide, lui donner 10 points, donner 7 points au 2è, 5 points au 3è, 3 points au 4è, 2 points au 5è, 1 point au 6è (par exemple), et faire pareil pour la taille

./Post n°5 Marquer comme non lu.

Dari

Ecrit le: Lundi 21 février 2005 à 16:36

Membre privilégié

Messages: 968

Membre n°203

Inscrit le 18 avril 2004

Euh, j'ai passé trois jours à le faire, pas le temps d'en faire un autre désolé.
Ca ressemble à ça :

+----+---------------------------------------------
| | |
| +- |
|
+--
|
|
|
|
|
|

"iPod, therefore, I am."

./Post n°6 Marquer comme non lu.

Dari

Ecrit le: Lundi 21 février 2005 à 16:40

Membre privilégié

Messages: 968

Membre n°203

Inscrit le 18 avril 2004

Pollux> Mais non !
Si ton prog fait 2h (le plus long), tu auras 1 en vitesse.
S'il fait 10 min tu auras : 10/120 = 0,0833333.
S'il fait 5 min : 0,04166666.
Comme ça, c'est adapté à chacun. On peut comparer le programme selon ce que tout le monde a fait. Si tout le monde fait des trucs merdiques, le meilleur aura tout de même une meilleure note (mias je doute que vous fassiez des trucs merdiques).
Je vous posterai mon programme à la fin du concours.

"iPod, therefore, I am."

./Post n°7 Marquer comme non lu.

Pollux

Ecrit le: Lundi 21 février 2005 à 16:40

Membre: Vétéran

Messages: 95

Membre n°306

Inscrit le 11 juin 2004

euh c'est pas très parlant ton dessin

sinon au pire tu peux soit :
* nous donner juste un quart du labyrinthe, tel que la solution optimale de ce quart de labyrinthe n'ait pas grand-chose à voir avec la solution optimale du labyrinthe complet -- donc on pourra pas s'en servir
* modifier légèrement ton labyrinthe pour que la meilleure solution ne soit pas la même

Je pense pas que tu révèles grand-chose en donnant un quart du labyrinthe, non ?

./Post n°8 Marquer comme non lu.

Pollux

Ecrit le: Lundi 21 février 2005 à 16:50

Membre: Vétéran

Messages: 95

Membre n°306

Inscrit le 11 juin 2004

Dari :
Pollux> Mais non !
Si ton prog fait 2h (le plus long), tu auras 1 en vitesse.
S'il fait 10 min tu auras : 10/120 = 0,0833333.
S'il fait 5 min : 0,04166666.
Comme ça, c'est adapté à chacun.

Euh, je crois que tu n'as pas bien compris ma critique.
Ce que je dis, c'est que si j'ai :

Newbie : 120 min, 1800 octets
Kevin_taille : 10 min, 1200 octets
Kevin_vitesse : 5 min, 1300 octets

Alors les scores vont être :
Newbie : 1 vitesse, 1 taille
Kevin_taille : 0.083 vitesse, 0.667 taille
Kevin_vitesse : 0.042 vitesse, 0.722 taille

Soit au total :
Newbie : 2
Kevin_taille : 0.750
Kevin_vitesse : 0.764

Ca veut dire que même si Kevin_vitesse a fait un truc 2x plus rapide, le fait que ça soit même pas 10% plus gros va le faire perdre ! Dans ces conditions, ça veut dire que l'optimisation en taille va être de loin le facteur le plus important, si on peut se permettre un prog 2x plus lent pour gagner 10% en taille.

On peut comparer le programme selon ce que tout le monde a fait. Si tout le monde fait des trucs merdiques, le meilleur aura tout de même une meilleure note (mias je doute que vous fassiez des trucs merdiques).

Tu noteras que la seule chose que je critique, c'est que la répartition entre taille et vitesse ne sera pas équilibrée du tout... (pas le fait que si c'est globalement merdique, tout le monde aura une bonne note : ça c'est pas un pb)

Si c'est le fait que ma proposition fait que qqun peut avoir 0 quand il y a plus de 7 personnes qui te gêne, on peut corriger ça en faisant :
* score_vitesse = 0.7^rang_vitesse
* score_taille = 0.7^rang_taille
* score_total = score_vitesse + score_taille

./Post n°9 Marquer comme non lu.

Kevin Kofler

Ecrit le: Lundi 21 février 2005 à 17:03

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4814

Membre n°40

Inscrit le 08 février 2004

Peut-être que la bonne solution à ce problème serait de travailler en pourcentage de la meilleure solution plutôt qu'en pourcentage de la plus mauvaise solution. C'est-à-dire qu'un programme pourrait avoir au maximum 200 points (100 en taille et 100 en vitesse), que plus de points il a, mieux c'est, et que l'existence d'entrées pourries n'influence pas le score des entrées potentiellement gagnantes (un effet qui est clairement paradoxal et indésirable).
-Edité le Lundi 21 février 2005 à 17:03 par Kevin Kofler-

Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!

./Post n°10 Marquer comme non lu.

Pollux

Ecrit le: Lundi 21 février 2005 à 17:10

Membre: Vétéran

Messages: 95

Membre n°306

Inscrit le 11 juin 2004

Tout à fait

Mais je pense que travailler en pourcentage risque pour le coup plus de privilégier la vitesse que la taille (parce qu'en général, une optimisation en vitesse veut dire gagner genre 30%, alors que gagner 30% en taille, ça peut être difficile quand on est déjà relativement proche de la solution optimale), alors que quand on fait seulement par rapport au *classement*, on est sûr de ne privilégier ni la taille, ni la vitesse.

./Post n°11 Marquer comme non lu.

Dari

Ecrit le: Lundi 21 février 2005 à 17:21

Membre privilégié

Messages: 968

Membre n°203

Inscrit le 18 avril 2004

Ce topic n'est pas fait pour parler de ça. Je prends note de tout ça.

"iPod, therefore, I am."

./Post n°12 Marquer comme non lu.

Pollux

Ecrit le: Lundi 21 février 2005 à 18:06

Membre: Vétéran

Messages: 95

Membre n°306

Inscrit le 11 juin 2004

ok, et pour le post 7 ?

et sinon, est-ce que :

X
X
X

est censé être un chemin ou est-ce qu'il faut faire

XX
XX
X

?

et il n'y a évidemment aucune contrainte d'optimalité du chemin, mais j'imagine qu'on n'a pas le droit de passer 2x par un même point, non ?

./Post n°13 Marquer comme non lu.

Jfg

Ecrit le: Lundi 21 février 2005 à 18:21

Administrateur

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 1260

Membre n°60

Inscrit le 23 février 2004

Il est excellent ton sujet Dari.

Kill Mario

./Post n°14 Marquer comme non lu.

bobti89

Ecrit le: Lundi 21 février 2005 à 18:55

Membre: Maître Ultime

Messages: 2494

Membre n°45

Inscrit le 09 février 2004

Je viens d'essayer un algo, mais qu'est ce que c'est lent le basic !!!
Bon j'attends un laby pour le tester sur l'ecran entier !

bob ou bob, vous ne voyez pas la différence. Pourtant il y en a une fondamentale, l'un est écrit à l'endroit, l'autre à l'envers.

Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

./Post n°15 Marquer comme non lu.

LionelA

Ecrit le: Lundi 21 février 2005 à 20:17

Modérateur général

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 947

Membre n°206

Inscrit le 19 avril 2004

J'ai généré ça tout à l'heure (random) :

http://anton.lionel.free.fr/TI68k/fireprog/LAB.gif

notez qu'il y a une solution (j'ai fait un remplissage avec un logiciel de retouche de photos)

Vu le manque de spécif qu'on a sur le labyrinthe, j'aimerais savoir si il correspond ? et si il y a d'autre truc possibles (couloirs de plus d'une cases de large, ...)

Pour les autres voilà le fichier v2i si vous voulez travailler sur le meme laby que moi

http://anton.lionel.free.fr/TI68k/fireprog/main.lab.v2i

./Post n°16 Marquer comme non lu.

Dari

Ecrit le: Mardi 22 février 2005 à 10:35

Membre privilégié

Messages: 968

Membre n°203

Inscrit le 18 avril 2004

Ton labyrinthe corresponf esxactement au mien. Les couloirs font une case et les murs aussi (résolution de 1).
Il est évident que le chemin va du départ à l'arrivée, mais après vous faites ce que vous voulez (je vous rappelle amicalement que plus vous dessinez, plus vous perdez de temps.

"iPod, therefore, I am."

./Post n°17 Marquer comme non lu.

bobti89

Ecrit le: Mardi 22 février 2005 à 10:58

Membre: Maître Ultime

Messages: 2494

Membre n°45

Inscrit le 09 février 2004

Lionel> Tu pourrais en créer un pour ti89 stp ?
Merci d'avance

bob ou bob, vous ne voyez pas la différence. Pourtant il y en a une fondamentale, l'un est écrit à l'endroit, l'autre à l'envers.

Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

./Post n°18 Marquer comme non lu.

LionelA

Ecrit le: Mardi 22 février 2005 à 11:15

Modérateur général

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 947

Membre n°206

Inscrit le 19 avril 2004

ben le fichier v2i marche sur les 89 (d'ailleurs je viens de tester mon algo sur VTI 89 à 1300% (c'est plus simple pour tester)

./Post n°19 Marquer comme non lu.

bobti89

Ecrit le: Mardi 22 février 2005 à 11:26

Membre: Maître Ultime

Messages: 2494

Membre n°45

Inscrit le 09 février 2004

Bon bah je vais essayer

bob ou bob, vous ne voyez pas la différence. Pourtant il y en a une fondamentale, l'un est écrit à l'endroit, l'autre à l'envers.

Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici