Licence CC BY-SA

Petits Défis Acidulé

Défis absurde , mais une manière comme une autre de se creuser un peu la tête et renforcer ses connaissances sur le C.

Pré en bulles

Bonjour à tous ! Je transfers quelques-uns de mes défis et regrouper dans plusieurs billets certains défis que j’ai déjà proposé par le passé.(j’en proposerai de nouveaux par la suite.)

Le but est de s’amuser, de se creuser un peu la tête et sortir des sentiers battus. (même si le code n’est ou ne peut pas être propre, tant que ça valide les contraintes, c’est bon !)

Pour ce premier défis, je vais vous proposer (de nouveau pour certains) un défis simple comme bonjour … ou presque.

Le défis

Ecrire une fonction qui permet de vérifier si un entier (sur un long) est premier.

  • Si le nombre est premier => retourner 1
  • Si le nombre n’est pas premier (1 n’est pas premer) => retourner 0
  • Si le nombre est strictement inferieur à 1, retourner une valeur négative.

Bref rien de bien compliqué, c’est même un cas très scolaire lors de l’apprentissage de n’importe quel langage.

Mais on va le pimenter en rajoutant quelques contraintes de rien du tout.

  1. Un code en C (le défis peut se faire dans d’autres langage mais il faudrait sans doute d’autres contraintes spécifiques)
  2. Interdiction à toutes librairies non standard.
  3. Seul la fonction standard printf est autorisée
  4. Interdiction au #define et #pragma
  5. Interdiction d’utiliser les mots asm,for,goto,neuneu,while,if,switch (3 fois rien)
  6. Interdiction d’utiliser ?
  7. Interdiction aux opérateurs arithmétiques (donc pas de +,-,*,/,%)
  8. Seul l’opérateur d’affectation = est autorisé (pas de ++,--,+=,*=,etc…)
  9. Tout ce qui n’est pas interdit est autorisé.

et même après avoir enlever une grosse partie du langage… c’est toujours possible et il y a même plusieurs solutions différentes pour y parvenir ! (ce qui signifie que l’on peut encore rajouter de nouvelles contraintes ! )

Et pas de spoil de préférence hein :) ?

Bonne chance à tous !



21 commentaires

\ Joke

Comment ça peut être acidulé si j’ai pas le droit au + de H+\text{H}^+ … J’y comprend rien.


Par contre en logique pure et dure, j’ai aucune idée comment ça peut marcher, car la division est l’un des tests pour trouver un nombre premier. ça à bien l’air coton cette affaire.

+1 -0

On peut coder des fonctions pour faire la division et les autres opérateurs arithmétiques, et ensuite c’est quasiment fini. :)

+0 -0

Par contre en logique pure et dure, j’ai aucune idée comment ça peut marcher, car la division est l’un des tests pour trouver un nombre premier. ça à bien l’air coton cette affaire.

Heureusement on peut utiliser les opérateurs de bits.

+0 -0

Bonsoir,

Pour les opérateurs mathématiques, je vois bien des alternatives possibles. Pour les boucles for/while aussi…. c’est ch#### mais faisable…
Par contre sans if…. j’ai du mal à voir comment on peut faire sans que ça soit horriblement lourd et illisible.

ET la performance du machin on en parle ?

+0 -0

Utiliser une fonction récursive et des opérateurs autorisés marche aussi.

+0 -0

Utiliser une fonction récursive et des opérateurs autorisés marche aussi.

Oui, la récursivité de toute façon on n’a pas le choix si on veut faire des boucles sans utiliser les mots-clés for, while et goto.

Avec des tableaux. Du coup, oui, c’est vite lourd et illisible. ^^"

Je pensais précisément à des tableaux de pointeurs de fonction. Le truc dont on ne se sert que très rarement sauf si on est un peu fou quoi.


Enfin bref, l’interdiction des structures de contrôle c’est un peu too much je trouve. C’est juste… inutilement emm######; et donc pas très pédagogique.

Par contre utiliser les opérateurs de bit à la place des opérateurs arithmétiques c’est pas mal comme restriction, ça permet de découvrir des vrais algorithmes qui ont une vraie utilité dans certains contextes.

Par contre en quoi est-il utile d’autoriser printf ?

IL faut bien pouvoir afficher le résultat à un moment donné non ?

+0 -0

Comme il n’est question que d’une fonction qui renvoie un entier je dirais que non.

JE vois mal comment on peut utiliser printf autrement que pour afficher quelque chose. Sauf si on autorise aussi sprintf ? Ou alors il faut print du '\b’, c’est moche et ça sert à rien, de nouveau.

ET puis même, ça ne retourne que le nombre de caractères imprimés. Refaire strlen c’est facile à faire, je ne vois pas l’intérêt.

+0 -0

Je ne pensais pas avoir autant de réponse d’un coup !

Si on enlève pas mal de fonctionalité assez pratique à un langage, doit-on s’attendre tout de même à un code propre ou performant ? Il n’y a aucune contraintes là dessus. (9) Tout ce qui n’est pas interdit est autorisé.

Par contre en logique pure et dure, j’ai aucune idée comment ça peut marcher, car la division est l’un des tests pour trouver un nombre premier. ça à bien l’air coton cette affaire.

Heureusement on peut utiliser les opérateurs de bits.

Renault

Oui, ils ne sont pas interdits (donc autorisé). Mais il existe d’autres manières de résoudre ce problème sans y avoir recours. Oui, je suis généreux.

On peut aussi se passer de pointeur de fonction.

Par contre en quoi est-il utile d’autoriser printf ?

entwanne

;)

Enfin bref, l’interdiction des structures de contrôle c’est un peu too much je trouve. C’est juste… inutilement emm######; et donc pas très pédagogique.

Source: QuentinC

Mais quelle dureté :D !

Je suis assez d’accord que ce défis n’est pas très pédagogique. Et ce n’est pas son but ;)

+0 -0

C’est une excellente question. Et je n’ai pas de réponse objective sur ce point.

Je considère comme du C valide, ce qui est conforme à la norme C11 au moment où j’écrits ces lignes.

Une extension , comme les fonctions imbriquées (supportées par gcc de mémoire) ne sont pas valide par la dernière norme en date, et je considérerai ça comme une hérésie ;)

A discuter !

Bon, voici ma solution:

int isPrime(const int n) {
  // Some precomputed data. Nothing to look at.
  unsigned char data[] = {0x85, 0xff, 0x7e, 0x27, 0x31, 0xc9, 0x83, 0xff, 0x01,
                          0x74, 0x25, 0x83, 0xff, 0x03, 0x7c, 0x14, 0xbe, 0x02,
                          0x00, 0x00, 0x00, 0x89, 0xf8, 0x99, 0xf7, 0xfe, 0x85,
                          0xd2, 0x74, 0x12, 0xff, 0xc6, 0x39, 0xf7, 0x75, 0xf1,
                          0xb9, 0x01, 0x00, 0x00, 0x00, 0xeb, 0x05, 0xb9, 0xff,
                          0xff, 0xff, 0xff, 0x89, 0xc8, 0xc3, 0x31, 0xc0, 0xc3};
  // Wait, that's illigal!
  return ((int (*)(int))data)(n);
}

C’est pas forcément parfaitement portable, mais ça devrait tourner sur la majorité des systèmes x86_64. Il est possible qu’il faille ajouter un -z execstack à la commande de compilation si votre système empêche effectivement d’executer la mémoire utilisé pour la stack.

Je propose la version suivante, pas optimisée pour un sou.

int id2(int a, int _b) {
  return a;
}

int add(int a, int b) {
  int carry;
  int (*f[2])(int, int) = {add, id2};
  carry = a & b;
  return f[carry==0](a ^ b, carry << 1);
}

int sub(int a, int b) {
  return add(a, add(~b, 1));
}

int divisible(int a, int b) {
  int c;
  int x[3] = {1, 0, a};
  int (*f1[2])(int, int) = {id2, sub};
  int (*f2[2])(int, int) = {id2, divisible};
  c = x[add(a >= b, a != 0)];
  c = f1[a >= b](c, b);
  return f2[a >= b](c, b);
}

int is_prime_aux2(int n, int i);

int is_prime_aux(int n, int i) {
  int x[3] = {n, 1, -1};
  int (*f[2])(int, int) = {is_prime_aux2, id2};
  f[i >= n](x[add(i > n, i >= n)], i);
}

int is_prime_aux2(int n, int i) {
  int d = divisible(n, i);
  int x[2] = {n, 0};
  int (*f[2])(int, int) = {is_prime_aux, id2};
  f[d](x[d], add(i, 1));
}

int is_prime(int n) {
  return is_prime_aux(n, 2);
}

@Berdes Ta solution est validée ;) ( et j’ai un gros doute d’obtenir le même résultat si l’endianess change, mais bon , il y a un cas d’environnement qui fonctionne , c’est suffisant !)

neuneutrinos

Étant donné que x86_64 est little endian et que ma version n’a en gros aucune chance de fonctionner sur un autre système, l’endianness n’est pas un problème en sois.

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

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