Challenges de programmation

Venez résoudre différents problèmes de programmation en C !

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut les agrumes ! :)

Aujourd'hui je vous apporte des petits défis de programmation à résoudre en C.

Pourquoi avoir choisi le C ?

A la base, j'avais rédigé ces défis pour un futur défi de Clem mais après avoir eu quelques retours et sur une décision personnelle, j'ai transformé ce défi en atelier car il était déjà trop orienté vers le C (or les défis de Clem se veulent neutre en langage), et je préfère réaliser un bon atelier plutôt qu'un défi médiocre à cause d'un choix de langage. D'autant plus, je ne pense pas que se limiter à un seul langage soit une mauvaise chose (cf le Javaquarium qui était au départ uniquement pour le Java), et au contraire un mélange entre choix du langage et langage spécifique permet d'explorer bien des idées.

Maintenant, place aux différents challenges qui sont présentés par ordre de difficulté.

Qui a la plus petite … solution ?!

Le sujet est simple, il faut réaliser un programme qui prend en entrée un nombre $N$ de lignes, $M$ de colonnes et qui affiche en sortie un rectangle de dimension $N \times M$ avec chaque ligne constituée soit de X (sur une ligne paire), soit de O (sur une ligne impaire).

Exemple

Entrée : 3 4
Sortie :
OOOO
XXXX
OOOO

Là où réside le véritable challenge est qu'il faut coder ce programme en utilisant le moins de caractères possible (absolument tout compte) ! On appelle cette pratique le code golf pour ceux que ça intéressent. ;)

Akinator

Le but de ce deuxième défi est d'expliquer la sortie de ce programme, c'est-à-dire de deviner ce qu'il va afficher mais surtout pourquoi il va le faire. Cependant, il y a quelques contraintes :

  • Interdit de copier/coller le code dans un éditeur.
  • Interdit de compiler le code.
  • Vous devez uniquement le lire ici.

On a dit pas de copier/coller !

NSA

Jusqu'à quel point pouvez-vous exploiter ce code comportant une (ou plusieurs ?) faille(s) de sécurité ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <string.h>

#define TAILLE_MAX 256

int main(int argc, char **argv)
{
   char buffer[TAILLE_MAX + 1];
   int top_secret = 0;

   if(argc <= 1) {
      printf("Veuillez indiquer une chaine en argument du programme !\n");
      return -1;
   }

   strcpy(buffer, argv[1]);

   printf("Vous avez entre : \n");
   printf(buffer);
   printf("\n\n");

   if(!strcmp(buffer, "code_secret"))
      top_secret = 1;

   if(top_secret)
      printf("Vous etes rentre dans la partie top secrete du programme !\n");

   return 0;
}

L'idée ici est, dans un premier temps, de repérer la/les faille(s), puis de chercher à l'/les exploiter pour créer des comportements non voulus (par exemple rentrer dans la partie secrète du programme, mais pas que !).

A vous de faire vos propres recherches sur la manière d'aborder le sujet. Mais pour ceux qui sont totalement perdus, je vous conseille une certain approche en lisant ces quelques articles qui vous aideront grandement à commencer :

Si vous avez réussi à trouver une faille facilement, essayez d'en chercher d'autres. Cela peut toujours être intéressant…

This is madness !

J'ai peut-être "un peu" forcé sur ce challenge…

Le défi est de comprendre comment fonctionne ce programme et donc d'expliquer comment il affiche sa sortie (je vous laisse l'exécuter pour voir le résultat) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
char*main(int l,char*s,char*_,int r,int t){
return(l==7)?0:l==1&&r!=1?main(l,"wzqzmv{*##bv/{}qzv=*\
|v|:;r/az~v=*|ve*&#;r/m|#vbm*|#evb#evez@zm~v=*|;r/tbnzv=*\
|v$m=;r/@b=v{**e`=z;r/~zaavbva}zvb#ev'|m~v=*|lr/","r~{nb@:\
#wmq;*=&z`'$}t|vlea\ntgkaspnNrv,oywebhcimu !dl",1,t):r>1?
t>=3?*s=='/'?8:main(l,s,_,r,-9)?main(l,++s,_,r,3):
-4:t<0?*s==*_?putchar(*(_+26)):main(l,s,++_,r,-7):
!l?s:*s=='/'?main(++l,++s,_,r,2):main(l,++s,_,r,1):
r?main(0,main(0,s,"mqk@]0",2,1),_,2,12),
main(-l,main(-l,s,"qkK~z@",2,2),_,2,27),main(++l,s,_,r,t):8;}

Oui, ceci est un programme écrit entièrement en C (il est dit obfusqué), et non ce programme n'est pas dangereux. Je précise que pour compiler ce code sans soucis, il faut utiliser gcc sans aucun flags :

1
2
3
4
# Compile le programme
gcc code.c -o code
# Execute le programme
./code

Il se peut que je donne des indices si je vois que les recherches sur ce code n'avancent pas assez, en tout cas j'autorise à chercher à plusieurs pour celui-là ! :p


Le but de cet atelier n'est pas de tout réussir, mais de vous faire découvrir de nouvelles choses intéressantes à propos du C (que ce soit par vous-même ou avec les solutions des autres). N'hésitez pas à poster vos avancées, vos découvertes, vos recherches et réflexions mais veillez à bien utiliser les balises secrètes pour éviter tout spoil.

J'espère que les quatre challenges vous plairont, et bonne chance à tous ! :)

+6 -0

Pour Akinator : bien sûr, la réponse est qu'il y a un problème dans la multiplication. Le fix se fait en 4 caractères, je laisse le mystère pour ceux qui veulent chercher =) .

Saroupille

Pour bien faire les choses il en faudrait 6 ;)

Le préprocesseur fait un simple remplacement, donc en utilisant la version non protégée #define mul(a, b) a*b, mul(1+2, 3+4) devient 1+2*3+4, soit 11 au lieu de 3*7=21 comme attendu. Et oui, la multiplication est prioritaire.

Il faut donc protéger les arguments et l'ensemble de la macro, comme ceci :

1
#define mul(a, b) ((a)*(b))


une question, c'est permis de mettre plus de deux arguments dans la fonction main (faut croire que oui), et dans ce cas, ils servent à quoi?

joseph

Le troisième arguement de la fonction main en C, char *envp[], est un pointeur vers un tableau de char*, contenant les variables d'environnement. C'est plus ou moins permis, plus d'infos ici (en) ou ici (fr).

Édité par Nodraak

http://nodraak.fr/ – Dictateur bienveillant de l'iTeam, logiciel libre et sécurité à l'ECE Paris

+0 -0
Auteur du sujet

une question, c'est permis de mettre plus de deux arguments dans la fonction main (faut croire que oui), et dans ce cas, ils servent à quoi?

joseph

C'est en rapport avec un challenge en particulier ? Sinon, main reste une fonction donc je peux lui faire prendre autant d'arguments que je souhaite. ;)

Pour bien faire les choses il en faudrait 6 ;)

Nodraak

N'allez pas trop vite dans la lecture :)

Édité par napnac

+0 -0

Le 1er m'a amusé. On peut encore gagner la ligne de l'include, au prix d'un warning. Notez que je ne suis plus à ça près.

1
2
3
4
5
#include <stdio.h>
main(){int N,M,m;
scanf("%d%d",&N,&M);
while(N--){for(m=M;m--;)putchar(N%2?88:79);puts("");}
}

Je n'ai pas tout mis sur une ligne, mais vous voyez l'idée. Il doit y avoir moyen de faire plus pourri.

PS: sizeof(char) == 1 par définition.

Édité par lmghs

+1 -0
Auteur du sujet

Merci de ta participation lmghs !

On peut encore gagner la ligne de l'include, au prix d'un warning. Notez que je ne suis plus à ça près.

lmghs

C'est le but non ? :D Tant que ton code compile avec gcc (ce que requiert l'IOCCC, même si ici c'est pas de l'obfuscation) ça me va.

Sinon tu peux encore le raccourcir de ce que j'ai rapidement vu :

Tu peux effectivement virer le include, mais tu peux aussi jouer astucieusement sur la déclaration des variables pour gagner de la place. Tu peux déclarer N dans les paramètres de ton main (pour gagner une virgule), et mettre M et m en global afin de ne pas avoir à donner de type explicite int.

+0 -0

Le 1er m'a amusé. On peut encore gagner la ligne de l'include, au prix d'un warning. Notez que je ne suis plus à ça près.

lmghs

La règle des lignes paires/impaires n'est pas respectée. Il y a bien alternance des O et X mais elles ne correspondent pas à la parité du n° de ligne.

Auteur du sujet

Le 1er m'a amusé. On peut encore gagner la ligne de l'include, au prix d'un warning. Notez que je ne suis plus à ça près.

lmghs

La règle des lignes paires/impaires n'est pas respectée. Il y a bien alternance des O et X mais elles ne correspondent pas à la parité du n° de ligne.

entwanne

Hm non il respecte bien la règle (si on commence à compter à partir de 1 et pas 0) :

1
2
3
4
5
6
7
8
$ gcc test.c -o test ; ./test
test.c:2:1: attention : return type defaults to ‘int’ [-Wimplicit-int]
 main(){int N,M,m;
 ^
3 4
OOOO
XXXX
OOOO
+0 -0

Non il ne la respecte pas. J'ai rencontré le même problème et n'ai pas eu envie de le corriger, ça me faisait trop de caractères en plus.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
$ ./a.out                                                                                                   [0]
4 3
XXX
OOO
XXX
OOO
$ ./a.out                                                                                                   [0]
5 3
OOO
XXX
OOO
XXX
OOO

Dans le premier cas, la première ligne est constituée de X, dans le second de O.

Édité par entwanne

Auteur du sujet

Bien vu ! Excuse moi, j'ai testé trop rapidement.

J'ai rencontré le même problème et n'ai pas eu envie de le corriger, ça me faisait trop de caractères en plus.

entwanne

Hm après tout je n'ai jamais dit que c'était facile le code golf :p Tu peux poster ton code en secret tout de même ?

+0 -0
Auteur du sujet

Quelques remarques :

La solution évidente serait d'utiliser une deuxième boucle for à la place du while. Tu dis que ça prend trop de caractères, mais y a pas mal de choses que tu peux raccourcir dans ton code, ce qui fait qu'au final si tu fais quelques modifs, même avec l'ajout d'une deuxième boucle for le code est plus court que celui actuel. Déjà l'entrée, je ne sais pas trop pourquoi tu veux utiliser les arguments alors qu'un scanf est plus court, surtout que tu peux déclarer en variable globale x et laisser y sans int dans le main. Sinon j'aime bien ta manière de choisir le caractère à afficher ! (même si ça n'économise qu'un caractère par rapport à une solution du style de lmghs, l'idée est sympa).

Après ce que tu peux faire si tu ne veux pas de la deuxième boucle for, c'est de chercher un moyen de tout faire en une seule boucle, ou alors de trouver une formule mathématiques pas trop longue pour contrer ton problème actuel avec le while. A toi de voir :p

+0 -0
Auteur du sujet

N'hésitez pas à poster vos avancées, vos découvertes, vos recherches et réflexions mais veillez à bien utiliser les balises secrètes pour éviter tout spoil.

napnac

;)

napnac

Tu n'as plus d'excuses Zérotisme !

Édité par napnac

+0 -0

Déjà l'entrée, je ne sais pas trop pourquoi tu veux utiliser les arguments alors qu'un scanf est plus court

napnac

Parce que quand je lis que c'est ce que le programme prend en entrée, il me paraît plus logique qu'il s'agisse de paramètres de la ligne de commande, et non de lire une ligne sur l'entrée standard.

1
i;main(int x,int**y){x=atoi(y[2]);for(i=atoi(y[1])*x;i--;i%x?:puts(""))putchar(79+i/x%2*9);}

Édité par entwanne

Voilà pour le 1er, on peut certainement faire mieux

1
i;main(n,m){scanf("%d%d",&n,&m);for(m++;i++<n*m;putchar(i%m?i/m%2?88:79:10));}

Le résultat

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
$ gcc test1.c
test1.c:1: warning: data definition has no type or storage class
test1.c: In function 'main':
test1.c:1: warning: incompatible implicit declaration of built-in function 'scanf'
$ ./a.exe
3
4
OOOO
XXXX
OOOO
$ ./a.exe
2
2
OO
XX

Édité par fromvega

+1 -0
Auteur du sujet

Déjà l'entrée, je ne sais pas trop pourquoi tu veux utiliser les arguments alors qu'un scanf est plus court

napnac

Parce que quand je lis que c'est ce que le programme prend en entrée, il me paraît plus logique qu'il s'agisse de paramètres de la ligne de commande, et non de lire une ligne sur l'entrée standard.

entwanne

Les deux méthodes sont autorisées, mais clairement l'entrée standard est plus favorable car elle prend moins de place. ;)

Merci fromvega pour ta solution !

Du coup, le challenge 2 a encore un secret non trouvé (mais je vous préviens, je peux être très fourbe parfois :p). Pour ceux qui veulent encore chercher, voici ce qu'affiche le programme en sortie :

Probleme d'allocation memoire !
Probleme de multiplication !
Tout va bien !

Personne ne s'attaque au challenge 3 (encore pour le 4 il est peut être un peu tôt) ? Il y a des failles assez basiques à exploiter. ;)

+0 -0

Pour ceux qui doutaient encore du fait que le pre-processing de C sent la mort.

Édité par Ksass`Peuk

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte