[Concours de code]Echauffement pour l'IOCCC

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 3 4 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [Concours de code]Echauffement pour l'IOCCC

Ummon

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) :

Code :

#define H 5
#define W 5
#define DI 0
#define DJ 0
#define AI 3
#define AJ 3
static char l[H][W] =
{{0x7, 0x5, 0x0, 0x5, 0x9},
{0x3, 0x1, 0x4, 0x9, 0xa},
{0x0, 0xc, 0x3, 0x4, 0x0},
{0xa, 0x3, 0xc, 0xb, 0xa},
{0xe, 0x6, 0x1, 0xc, 0xe}};

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

Le code ne doit pas fonctionner uniquement avec l'exemple mais également avec des labyrinthes de tailles différentes ayant ou non une solution.
Dans le cas d'un labyrinthe sans solution, le programme de doit pas tourner en boucle.
On ne peut pas sortir du labyrinthe (les sorties ne peuvent pas être impruntées).
Pour compter le nombre de caractère vous pouvez utiliser ce petit utilitaire : version windows, version linux.
Le code doit être à la norme iso C99 (je test avec >gcc -std=c99 source.c).
Aucun warning doit être levé à la compilation.
Un seul fichier pour le code source
Les macros et les gotos sont vos amis .
Les drogues ne sont en aucun cas interdits.

Scores à battre (nb de caractère)

386 0x90 (invalide : tourne en boucle lorsqu'il n'y a pas de solution et utilise les sorties pour faire des sauts) -> voir
389 fra0 (dépend de la taille de la pile) -> voir
390 matafan (dépend de la taille de la pile) -> http://forum.hardware.fr/hardwaref [...] 62282]voir
393 0x90 (ne fonctionne pas d'après ce post (j'ai effectivement pu vérifier))-> voir
394 PowerKiki (dépend de la taille de la pile) -> voir
397 Ummon(dépend de la taille de la pile) -> voir
410 Ummon (dépend de la taille de la pile) -> voir
419 matafan (dépend de la taille de la pile) -> voir
431 fra0 (invalide : tourne en boucle lorsqu'il n'y a pas de solution) -> voir

Message édité par Ummon le 19-09-2008 à 11:26:40

Publicité

black_lord

Truth speaks from peacefulness

torvalds

HelloWorld

Salut tout le monde!

Code :

#include <stdio.h>
int main(){return printf("(0,0)\n(0,1)\n(0,2)\n(1,2)\n(1,3)\n(2,3)\n(2,2)\n(3,1)\n(3,2)\n(4,1)\n(4,2)\n(4,3)\n(3,3)\n" );}

j'ai gagné

---------------
FAQ fclc++ - FAQ C++ - C++ FAQ Lite

Ummon

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 !

Message édité par Ummon le 07-12-2005 à 17:41:52

HelloWorld

Salut tout le monde!

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 :

#include <stdio.h>
int main(int argc, char**argv){printf(argv[1]);}

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 :spamafote:

---------------
FAQ fclc++ - FAQ C++ - C++ FAQ Lite

Ummon

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

fra0

ton codage du plateau est assez laid, pour tester plus proprement,
le programme devrait lire stdin avec un format du genre

Code :

9
7
xxxxxxxxx
xD...x..x
xxx..x..x
x.x...x.x
x...x...x
x...x..Ax
xxxxxxxxx

masklinn

í dag viðrar vel til loftárása

Ah ouais c'est beaucoup plus propre comme ça tout d'un coup...
( [:pingouino] )

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

Message cité 1 fois
Message édité par masklinn le 07-12-2005 à 18:42:34

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

0x90

→

masklinn a écrit :

Son format ( a base de x et de . ) est le format standard des entrainements prologins il me semble [:spamafote]

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

masklinn

í dag viðrar vel til loftárása

J'crois pas que ce soit le but de l'exercice là [:dawa]

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

Publicité

0x90

→

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

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

matafan

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 ?

Message cité 2 fois

0x90

→

matafan a écrit :

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

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

Ummon

matafan a écrit :

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

Message édité par Ummon le 07-12-2005 à 23:20:39

0x90

→

Bon voila ma solution, surement pas optimale mais j'aurais l'honneur d'avoir posté le 1er ^^ :

#define DJ 0
#define AI 3
#define AJ 3
static char l[H][W] =
{{0x7, 0x5, 0x0, 0x5, 0x9},
{0x3, 0x1, 0x4, 0x9, 0xa},
{0x0, 0xc, 0x3, 0x4, 0x0},
{0xa, 0x3, 0xc, 0xb, 0xa},
{0xe, 0x6, 0x1, 0xc, 0xe}};

#include <stdio.h>
#include <stdlib.h>
int x=DI,y=DJ,d=4; int
main(void){while(x-AI||y
-AJ){while(l[y][x]&d||rand
()%2||!printf("(%i,%i)\n",
y,x)){(d>>=1)||(d=8);}(d
&1)?y+=H-1:(d&2)?x+=W-
1:(d&4)?y++:x++;y%=H
;x%=W ;}return 0;}

[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 ^^

Message édité par 0x90 le 08-12-2005 à 01:13:38

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

fra0

sympa,
dans le style drunken master

Code :

#define H 5
#define W 5
#define DI 0
#define DJ 0
#define AI 3
#define AJ 3
static char l[H][W] =
{{0x7, 0x5, 0x0, 0x5, 0x9},
{0x3, 0x1, 0x4, 0x9, 0xa},
{0x0, 0xc, 0x3, 0x4, 0x0},
{0xa, 0x3, 0xc, 0xb, 0xa},
{0xe, 0x6, 0x1, 0xc, 0xe}};
#include<stdio.h>
#include<stdlib.h>
#define l(n,p,k)case n:if(!((l[y][x]>>n)&1)&&p)k;else goto _;break;
int main(){int x=DJ,y=DI;while(
printf("(%d,%d)\n",y,x)&&x-AJ|y
-AI)_:switch(rand()&3){l(0,y>0,
--y)l(1,x>0,--x)l(2,y<H-1,++y)l
(3,x<W-1,++x)}return 0;}

ce programme ne perd jamais espoir ...
(edit petit lapin & mise en page, mdr le Vi)
ps :j'ai surement inversé I & J

Message cité 1 fois
Message édité par fra0 le 08-12-2005 à 03:27:32

0x90

→

fra0 a écrit :

sympa,
dans le style drunken master

Code :

#include<stdio.h>
#include<stdlib.h>
#define l(n,p,k) case n:if(!((l[y][x]>>n)&1)&&p)k;else goto _;break;
int main(){int x=DJ,y=DI;while(x-AJ|y-AI&&printf("(%d,%d)\n",y,x))
_:switch(rand()&3){l(0,y>0,--y)l(1,x>0,--x)l(2,y<H-1,++y)l(3,x<W-1,++x)}
return 0;}

ce programme ne perd jamais espoir ...

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 ?

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

fra0

"On ne peut pas sortir du labyrinthe sans autorisation préalable."

voui, j'ai pas compris à qui il fallait demander l'autorisation

fra0

sans aucun doute, t'es devant et tu pourrais encore gagner quelques octets
avec d>>=1
et tes houuuu

0x90

→

Voui je gagne un peu avec quelques optims :

#define H 5
#define W 5
#define DI 0
#define DJ 0
#define AI 3
#define AJ 3
static char l[H][W] =
{{0x7, 0x5, 0x0, 0x5, 0x9},
{0x3, 0x1, 0x4, 0x9, 0xa},
{0x0, 0xc, 0x3, 0x4, 0x0},
{0xa, 0x3, 0xc, 0xb, 0xa},
{0xe, 0x6, 0x1, 0xc, 0xe}};

#include <stdio.h>
#include <stdlib.h>
int main () {int d=
4,e=DJ,a =DI ;while (
a-AI||e- AJ){while(
l[e][a]& d||rand()& 1||
!printf( "(%i,%i)\n" ,e,
a))(d/=2 )||(d=8); (d&
1)?e+=H-1:(d&2)? a+=
W-1:(d&4)?e++: ++a
;e%=H ;a%=W; } }

[edit]
J'ai refait un peu la présentation :whistle:

Message édité par 0x90 le 08-12-2005 à 02:46:17

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

matafan

Je propose la première solution déterministe, avec une bête recherche en profondeur par récursion :

Code :

#define H 5
#define W 5
#define DI 0
#define DJ 0
#define AI 3
#define AJ 3
static char l[H][W] =
{{0x7, 0x5, 0x0, 0x5, 0x9},
{0x3, 0x1, 0x4, 0x9, 0xa},
{0x0, 0xc, 0x3, 0x4, 0x0},
{0xa, 0x3, 0xc, 0xb, 0xa},
{0xe, 0x6, 0x1, 0xc, 0xe}};
#include <stdio.h>
#define u unsigned
#define r return
u f(u i, u j)
{
u c = ~l[i][j];
if (i<H && j<W && c&16) {
l[i][j] |= 16;
if (i==DI && j==DJ
|| c&1 && f(i-1,j)
|| c&2 && f(i,j-1)
|| c&4 && f(i+1,j)
|| c&8 && f(i,j+1))
{
printf("(%u,%u)\n", i, j);
r 1;
}
}
r 0;
}
int main()
{
r f(AI,AJ);
}

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.

Message édité par matafan le 08-12-2005 à 07:07:30

Ummon

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

Message cité 1 fois
Message édité par Ummon le 08-12-2005 à 08:49:44

Ummon

J'ai ajouté deux clause pour clarifier certains points :

Dans le cas d'un labyrinthe sans solution, le programme de doit pas tourner en boucle.
On ne peut pas sortir du labyrinthe (les sorties ne peuvent pas être impruntées).

chrisbk

bin alors pourquoi y'a des sorties ?

Ummon

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

Ummon

Bon je propose mon code :

Code :

#define H 5
#define W 5
#define DI 0
#define DJ 0
#define AI 3
#define AJ 3
static char l[H][W] =
{{0x7, 0x5, 0x0, 0x5, 0x9},
{0x3, 0x1, 0x4, 0x9, 0xa},
{0x0, 0xc, 0x3, 0x4, 0x0},
{0xa, 0x3, 0xc, 0xb, 0xa},
{0xe, 0x6, 0x1, 0xc, 0xe}};
#include<stdio.h>
#define I [i][j]
#define Q(A) &&~l I&A&&p(i
#define R return
int p(int i,int j)
{
if(l I&16
)R 0 ;l I
|=16 ;R (
i == DI&&
j == DJ||
i Q( 1)-1
,j ) || j
Q(2) ,j-1
)||i <H-1
Q(4) +1,j
)||j <W-1
Q(8),j+1))&&
printf("(%i,%i)\n",i,j);
}
int main()
{
R p(AI,AJ);
}

Il sort ca :

(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)

Il retourne 0 si pas de solution

Message édité par Ummon le 08-12-2005 à 10:09:08

PowerKiKi

Code :

#define H 5
#define W 5
#define DI 0
#define DJ 0
#define AI 3
#define AJ 3
static char l[H][W] =
{{0x7, 0x5, 0x0, 0x5, 0x9},
{0x3, 0x1, 0x4, 0x9, 0xa},
{0x0, 0xc, 0x3, 0x4, 0x0},
{0xa, 0x3, 0xc, 0xb, 0xa},
{0xe, 0x6, 0x1, 0xc, 0xe}};
#include <stdio.h>
#define L l[i][j]
#define E(c, x) )|| c && ~L & x && r(i
int r(int i, int j)
{
return ~L &16?L |=16,(i==DI && j==DJ( E(i, 1) -1,j E(j, 2) ,j-1 E(i<H-1, 4) +1,j E(j<W-1, 8) ,j+1)) && printf("(%d,%d)\n",i,j):0;
}
int main()
{
r(AI, AJ);
}

moi, j'aimes pas quand il y a plusieurs lignes dans une fonction.

396 caracteres pour une sortie identique a Ummon.

Message édité par PowerKiKi le 08-12-2005 à 11:01:55

FlorentG

On peut utiliser un fichier XML pour le labyrinthe ? On pourrait alors faire une validation avec un XSD [:dawa]

J'peux faire ça en PHP ?

En JavaScript ?

Y'a quoi comme compilo C pour être sur qu'on est valide C99 ?

Message cité 2 fois

Ummon

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.

masklinn

í dag viðrar vel til loftárása

FlorentG a écrit :

On peut utiliser un fichier XML pour le labyrinthe ? On pourrait alors faire une validation avec un XSD [:dawa]

[:moule_bite]

Et valider quoi d'abord, que le labyrinthe a une solution [:petrus dei]

Message cité 1 fois
Message édité par masklinn le 08-12-2005 à 11:37:52

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

FlorentG

gcc c'est linusqusse, non ? [:petrus75]

Nan bon, j'vais essayer si je trouve le temps, ça me fera travailler l'algoritmique et l'obfuscation [:kbchris]

Message cité 2 fois

FlorentG

masklinn a écrit :

Et valider quoi d'abord, que le labyrinthe a une solution [:petrus dei]

Que le labyrinthe est correctement structuré [:moule_bite]

Message cité 1 fois

chrisbk

FlorentG a écrit :

lol, ur teh bloatman

Message cité 1 fois

FlorentG

chrisbk a écrit :

lol, ur teh bloatman

I'm teh modernman u 0ld-monk3y

Message cité 1 fois

masklinn

í dag viðrar vel til loftárása

FlorentG a écrit :

gcc c'est linusqusse, non ? [:petrus75]

Ya des ports sous winwin

FlorentG a écrit :

Que le labyrinthe est correctement structuré [:moule_bite]

haha lol [:moule_bite]

FlorentG a écrit :

I'm teh modernman u 0ld-monk3y

Non, retourne faire du java [:bistou tt]

Message cité 1 fois

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

chrisbk

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

Message cité 1 fois

FlorentG

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 [:moule_bite]

hihihi lol

masklinn a écrit :

Non, retourne faire du java [:bistou tt]

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

Message édité par FlorentG le 08-12-2005 à 11:50:24

Emmanuel Delahaye

C is a sharp tool

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/

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

FlorentG

Justement, j'ai déjà cygwin d'installouillé, donc c'est bon Y'a un gcc 3.4.4 avec

masklinn

í dag viðrar vel til loftárása

J'viens de remarquer un truc marrant: avec ce format de labyrinthes on peut créer des passages à un seul sens [:atsuko]

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

Publicité

Page : 1 2 3 4

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

[Concours de code]Echauffement pour l'IOCCC

Sujets relatifs
Problème de lecture .wmv dans le code HTML	Comment on code des bretelles en ada ?
récupérer le code source page Web https..(dhtml, javascript) avec vba?	Code VBA permettant de supprimer un faux message d'erreur
Code de retour d'un batch windows	j'ai du code vbscript que j'aimerais transformer en vb6
[VBA-EXCEL 2003] SaveCopyAs mais sans le code VBA ou macro	j'ai le code source des page html qui s'affiche en local
Fonction pour pour convertir le code HTML	Pb code php : page de connexion
Plus de sujets relatifs à : [Concours de code]Echauffement pour l'IOCCC

Page générée en 0.150 secondes