Echauffement pour l'IOCCC [Concours de code] - C - Programmation
Marsh Posté le 07-12-2005 à 17:39:27
Code :
|
j'ai gagné
Marsh Posté le 07-12-2005 à 17:40:42
petit malin, mais : "Le code ne doit pas fonctionner uniquement avec l'exemple.", faut lire jusqu'a la fin . de plus il manque les argc et argv dans le main et le retour. Suivant !
Marsh Posté le 07-12-2005 à 17:49:20
Tsss, le proto sans argc / argv est légal, et le return y est : il renvoie printf, et j'aurai du l'enlever:
http://www.comeaucomputing.com/techtalk/c99/#return0
Bon, version corrigée qui marche pour d'autres exemples:
Code :
|
La solution est passée en premier paramètre.
Bon ok ok, je sors. Mais que veux-tu, je suis désavantagé : j'ai beau me forcer, je suis incapable de concevoir un code illisible
Marsh Posté le 07-12-2005 à 17:54:50
Bon ok ok je modifie le argc/argv (je pensais que c'était obligatoire) mais le but n'est non plus de pourrir le topic...
Marsh Posté le 07-12-2005 à 18:12:28
ton codage du plateau est assez laid, pour tester plus proprement,
le programme devrait lire stdin avec un format du genre
Code :
|
Marsh Posté le 07-12-2005 à 18:40:16
Ah ouais c'est beaucoup plus propre comme ça tout d'un coup...
()
Et brusquement vachement plus facile à parser
()
D'ailleurs t'as ptet pas remarqué, mais avec ton super format ultra facile à parser, fournir les tailles du labyrinthe c'est redondant.
()
Marsh Posté le 07-12-2005 à 18:47:14
masklinn a écrit : Ah ouais c'est beaucoup plus propre comme ça tout d'un coup... |
Son format ( a base de x et de . ) est le format standard des entrainements prologins il me semble
Marsh Posté le 07-12-2005 à 18:50:30
J'crois pas que ce soit le but de l'exercice là
Marsh Posté le 07-12-2005 à 18:54:13
Bha d'un autre coté, intégrer le labyrinthe au code c'est pas top, ca demande de recompiler pour avoir la solution d'un autre labyrinthe. Bon ca permet de résoudre le pb uniquemnent à base de préprocesseur ( bonne chance ) mais ca fait du programme finit kkchose de pas très utilisable quand même
Marsh Posté le 07-12-2005 à 22:51:14
Donc la qualite du chemin propose (longueur, fait qu'on revinnent parfois sur ses pas...) n'intervient absolument dans la "notation" du programe ? Ni la beaute de l'algorithme utilise ? Seulement la taille du programme ?
Marsh Posté le 07-12-2005 à 22:54:35
matafan a écrit : Donc la qualite du chemin propose (longueur, fait qu'on revinnent parfois sur ses pas...) n'intervient absolument dans la "notation" du programe ? Ni la beaute de l'algorithme utilise ? Seulement la taille du programme ? |
C'est vrai que si y'a pas de notion de qualité du chemin, spa génial un simple algo de "je colle au mur de droite sauf quand je suis deja passé par la" peut faire l'affaire
Marsh Posté le 07-12-2005 à 23:19:57
matafan a écrit : Donc la qualite du chemin propose (longueur, fait qu'on revinnent parfois sur ses pas...) n'intervient absolument dans la "notation" du programe ? Ni la beaute de l'algorithme utilise ? Seulement la taille du programme ? |
Non la qualité du chemin n'importe pas, il faut juste que le chemin soit cohérent, c-à-d que chaque point donné soit contigue au précédent et commence au point de départ et finit au point d'arrivé.
Le but ultime est de minimiser le nombre de caractère (par l'utilisation de macro, de décalage de bit ou autre..)!
Marsh Posté le 08-12-2005 à 01:12:28
Bon voila ma solution, surement pas optimale mais j'aurais l'honneur d'avoir posté le 1er ^^ :
|
[edit]
j'ai pas eu l'occasion de le tester avec différents laby ( flemme de coder un générateur ), si kkun arrive à le prendre en défaut ca m'étonnerait pas j'ai fait ca vitefait ^^
Marsh Posté le 08-12-2005 à 01:27:08
sympa,
dans le style drunken master
Code :
|
ce programme ne perd jamais espoir ...
(edit petit lapin & mise en page, mdr le Vi)
ps :j'ai surement inversé I & J
Marsh Posté le 08-12-2005 à 01:57:26
fra0 a écrit : sympa,
|
Si j'ai bien compris le dessin en haut, par les trous au milieu de chaque bords on peut passer, et si j'ai bien compris ton code, il le gère pas non ?
Marsh Posté le 08-12-2005 à 01:59:38
"On ne peut pas sortir du labyrinthe sans autorisation préalable."
voui, j'ai pas compris à qui il fallait demander l'autorisation
Marsh Posté le 08-12-2005 à 02:01:16
sans aucun doute, t'es devant et tu pourrais encore gagner quelques octets
avec d>>=1
et tes houuuu
Marsh Posté le 08-12-2005 à 02:10:30
Voui je gagne un peu avec quelques optims :
|
[edit]
J'ai refait un peu la présentation
Marsh Posté le 08-12-2005 à 06:45:05
Je propose la première solution déterministe, avec une bête recherche en profondeur par récursion :
Code :
|
L'utilisation d'unsigned permet d'économiser la comparaison à 0 de i et j.
Si j'ai bien compté on a pour l'instant 0x90 à 386 caractères, moi à 419 et fra0 à 431.
Edit : j'inverse les points de départ et d'arrivée pour obtenir un affichage à l'endroit.
Marsh Posté le 08-12-2005 à 08:48:56
matafan >
J'ai quelques erreurs avec ton code (gcc 3.2.3) :
include/stdio.h:206: parse error before "size_t"
peut-être dû à l'utilisation de macros..
Marsh Posté le 08-12-2005 à 09:11:01
J'ai ajouté deux clause pour clarifier certains points :
Marsh Posté le 08-12-2005 à 09:22:32
Simplement pour compliquer un petit peu et obliger à gérer le cas ou l'on sort du tableau (se balader aléatoirement dans la mémoire ).
Marsh Posté le 08-12-2005 à 09:23:39
Bon je propose mon code :
Code :
|
Il sort ca :
(0,0) |
Il retourne 0 si pas de solution
Marsh Posté le 08-12-2005 à 10:31:54
Code :
|
moi, j'aimes pas quand il y a plusieurs lignes dans une fonction.
396 caracteres pour une sortie identique a Ummon.
Marsh Posté le 08-12-2005 à 11:28:15
On peut utiliser un fichier XML pour le labyrinthe ? On pourrait alors faire une validation avec un XSD
J'peux faire ça en PHP ?
En JavaScript ?
Y'a quoi comme compilo C pour être sur qu'on est valide C99 ?
Marsh Posté le 08-12-2005 à 11:35:32
Alors c'est uniquement en 'C99' ... mais bon si cela t'amuses tu peux le faire dans un autre langage.
Pour le labyrinthe en xml, bein c'est pas en accord avec la donnée.
Sinon pour le compilo tu peux prendre 'gcc' par exemple.
Marsh Posté le 08-12-2005 à 11:37:33
FlorentG a écrit : On peut utiliser un fichier XML pour le labyrinthe ? On pourrait alors faire une validation avec un XSD |
Et valider quoi d'abord, que le labyrinthe a une solution
Marsh Posté le 08-12-2005 à 11:39:14
gcc c'est linusqusse, non ?
Nan bon, j'vais essayer si je trouve le temps, ça me fera travailler l'algoritmique et l'obfuscation
Marsh Posté le 08-12-2005 à 11:40:23
masklinn a écrit : Et valider quoi d'abord, que le labyrinthe a une solution |
Que le labyrinthe est correctement structuré
Marsh Posté le 08-12-2005 à 11:42:56
FlorentG a écrit : On peut utiliser un fichier XML pour le labyrinthe ? On pourrait alors faire une validation avec un XSD |
lol, ur teh bloatman
Marsh Posté le 08-12-2005 à 11:44:23
ReplyMarsh Posté le 08-12-2005 à 11:47:07
FlorentG a écrit : gcc c'est linusqusse, non ? |
Ya des ports sous winwin
FlorentG a écrit : Que le labyrinthe est correctement structuré |
haha lol
FlorentG a écrit : I'm teh modernman u 0ld-monk3y |
Non, retourne faire du java
Marsh Posté le 08-12-2005 à 11:47:21
shitz0r, its because of moron like u taht cant do sh*t in less than 3gb that we need 5ghz pc to run a stupid not3p4d
Marsh Posté le 08-12-2005 à 11:50:12
masklinn a écrit : Ya des ports sous winwin |
Je sais, je sais. Au pire j'ai un cygwin où doit y avoir un gcc.
masklinn a écrit : haha lol |
hihihi lol
masklinn a écrit : Non, retourne faire du java |
Merci, mais j'ai arrêté
chrisbk a écrit : shitz0r, its because of moron like u taht cant do sh*t in less than 3gb that we need 5ghz pc to run a stupid not3p4d |
My bloat-stuff is so optimised, it's waaay faster than ur vintage prog style
Marsh Posté le 08-12-2005 à 12:04:14
FlorentG a écrit : gcc c'est linusqusse, non ? |
Pas forcément. Sous Windows, il y a cygwin et mingw.
Voir Code::Blocks, par exemple... (IDE sur mingw)
http://www.codeblocks.org/
Marsh Posté le 08-12-2005 à 12:07:03
Justement, j'ai déjà cygwin d'installouillé, donc c'est bon Y'a un gcc 3.4.4 avec
Marsh Posté le 08-12-2005 à 14:31:49
J'viens de remarquer un truc marrant: avec ce format de labyrinthes on peut créer des passages à un seul sens
Marsh Posté le 07-12-2005 à 17:09:33
Vous ! oui Vous qui ne faîtes rien qu'a glander sur BlaBla@Programmation en attendant l'heure de la pause, Vous qu'on sous-exploite alors que Linus Torvalds (celui qui dit que les goto c'est bien) ne vous arrive même pas à la cheville. Exprimez votre besoin de liberté en participant à notre grand concours "Toi aussi fait du code pourri qui marche (défois)".
Le but est de réaliser un programme permettant de résoudre un labyrinthe et afficher le chemin d'un point A à un point B.
Le défit ultime est de pondre un code source le plus petit possible (le moins de caractère), les espaces, tabulations et retour à la ligne (<cr><lf> et/ou <lf> ) ne seront pas compté (tous les caractères non-imprimables de façon général).
Données
Voici le code qui devra obligatoirement se trouver au début de votre code source et qui ne devra en aucun cas être modifié (pour que tout le monde ait les même bases) :
H est la hauteur du labyrinthe
W est la largeur du labyrinthe
DI, DJ sont les coordonnées du point de départ
AI, AJ sont les coordonnées du point d'arrivé
l est le labyrinthe, chaque case est codé comme suit (les bit sont décrit en partant de celui ayant le poids le plus faible):
1er bit = 1 signifie qu'il y a un mur en haut
2ieme bit = 1 signifie qu'il y a un mur à gauche
3ieme bit = 1 signifie qu'il y a un mur en bas
4ieme bit = 1 signifie qu'il y a un mur à droite
5ième-8ième bits : non-utilisés.
exemples :
0xa : mur à gauche et à droite
0x3 : mur en haut et à gauche
Quelques labyrinthes que le programme doit pouvoir résoudre (bleu = départ, rouge = arrivée) :
a) b) c)
a) Le labyrinthe de l'exemple fournit
b)
#define H 5
#define W 5
#define DI 2
#define DJ 2
#define AI 0
#define AJ 4
static char l[H][W] =
{{0x0, 0x0, 0x0, 0x0, 0x0},
{0x0, 0x0, 0x4, 0x0, 0x0},
{0x0, 0x8, 0xb, 0x2, 0x0},
{0x0, 0x0, 0x0, 0x0, 0x0},
{0x0, 0x0, 0x0, 0x0, 0x0}};
c) Pour ce cas ci le programme ne doit pas tourner indéfiniment
#define H 5
#define W 5
#define DI 2
#define DJ 2
#define AI 0
#define AJ 3
static char l[H][W] =
{{0x3, 0x9, 0x7, 0x5, 0xd},
{0xa, 0x2, 0x1, 0x9, 0xb},
{0xa, 0x2, 0x0, 0x8, 0xa},
{0xa, 0x6, 0x4, 0xc, 0xa},
{0x6, 0x5, 0x5, 0x5, 0xc}};
Resultat
Le résultat doit obligatoirement ressembler à un truc comme ça (pour le labyrinthe fournit). Le chemin peut également être fournit dans l'ordre inverse :
(0,0)
(0,1)
(0,2)
(1,2)
(1,3)
(2,3)
(2,2)
(3,2)
(3,1)
(4,1)
(4,2)
(4,3)
(3,3)
Prescriptions générales
Scores à battre (nb de caractère)
Message édité par Ummon le 19-09-2008 à 11:26:40