Code Golfing

Publié il y a 3 ans par Quentin

Un conseil qu'on vous donne quand vous voulez vous faire un profil de développeur sur internet est de participer sur Stack Overflow.

Pour sûr, Stack Overflow vous note lorsque vous répondez à des questions et le site vous attribue un score de réputation en retour.

C'est intéressant pour les développeurs qui n'ont pas de gros projets open source dans leurs dépôts github et qui cherche à prouver leur valeur.

Il y a quand même un problème. Stack Overflow étant une référence chez les développeurs, la plupart des questions "faciles" sont éculées. La majorité des questions récentes sont des questions sur des technos toutes nouvelles ou juste des gens qui vous demandent de déboguer leur code. De plus la concurrence est de plus en plus rude sur les réponses. Il est devenu très difficile de se faire une réputation sur Stack Overflow directement.

Par contre, Stack Exchange, le réseau dont fait parti Stack Overflow, contient un autre site nommé CodeGolf.

Codegolf utilise le système de questions/réponses afin de faire des compétitions de code. Le principe est simple : quelqu'un pose un problème de programmation simple et toutes les réponses montrent comment le faire dans un langage le plus rapidement possible. Comme le golf, il faut atteindre le but en le moins de coups possibles.

Les problèmes posés sont de tout ordre : de faire un "Hello World" le plus court possible à faire des programmes qui produisent leur propre code en passant par le fameux "FooBarBazz". Les réponses données sont souvent impressionnantes et complètement incompréhensible au premier regard.

Laissez-moi vous montrer un exemple.

Le problème est de faire un programme ou une fonction qui prends en entrée une chaîne de caractère, inverse l'ordre des bits de chaque caractères, inverse chaque bit et sort le résultat. C'est relativement inutile mais ça permet de faire des opérations intéressantes.

Résumons plus simplement l'algorithme :

  • Une chaine de caractères ASCII est fournie en entrée
  • Pour chaque caractères, l'ordre des bits est inversé (10000000 devient 00000001)
  • Pour chaque caractères, la valeur des bits est modifiée (00000001 devient 11111110)
  • Les nouveaux caractères ASCII résultants sont donnés en sortie

Dans le cadre d'un code standard(non-codegolfé), on aurait surement quelquechose comme ça :

Ouf ! Ça fait beaucoup de code tout ça. Essayons de réduire le plus possible ce code pour qu'il soit plus court. Première étape, rassembler les opérations sur une même variable en une seule chaine. Profitons-en aussi pour retirer les commentaires qui prennent de la place pour "rien".

Javascript est relativement intelligent et sait faire des conversions tout seuls si on lui donne une chaine bien formattée. En ECMAScript6, nous pouvons utiliser "0b" au début d'une chaine de caractères pour indiquer un nombre binaire. Du coup on peut faire ça :

On peut aussi retirer les variables char et binary en remplaçant leurs usages :

La fonction d'inversion de bit peut être réduite en utilisant les arrow functions d'ECMAScript 6 :

De plus l'inversion de bit peut se faire plus rapidement avec l'opérateur XOR binaire : ^ :

Finalement, on peut renommer la variable pour gagner 4 caractères :

Si nous traitons l'entrée comme un tableau plutot qu'une chaine de caractères, on pourrait alors se passer de la variable output :

Finalement, vu que notre fonction n'utilise qu'un seul return, nous pouvons la passer en arrow function, pareil pour la fonction dans le map :

On a plus qu'à réduire les noms de variables et retirer les espaces inutiles :

À partir de là, on a un code golfé de 125 bytes (ou caractères). Je vous laisse comparer avec la première version de la fonction qui elle faisait 425 caractères sans les commentaires. Il existe un grand nombre d'astuces pour gagner des caractères en javascript. Typiquement, on peut en gagner encore plus en remplaçant le premier split par un appel de la fonction map d'un tableau bindée sur la chaine :

Bref, vous l'aurez compris, le but du code golf c'est d'utiliser toutes les astuces et structures d'un langage pour rendre un code le plus court possible. Si vous aimez faire des one liners, c'est une discipline pour vous.

En code golfant, on apprend surtout à faire des algorithmes et à utiliser de nouveaux concepts d'un langage. On y apprend à gérer la priorités des opérateurs ou la portée des variables afin de gagner quelques bytes.

Le code golf, c'est aussi le moment pour vous d'expliquer comment vous faites certains algorithmes ou d'apprendre de nouveaux concepts de programmation ou mathématiques (J'ai appris hier ce qu'étais un programme "pristine" hier par exemple).

Bref, si vous cherchez un petit casse-tête de code ou simplement à montrer une partie de vos compétences sur internet en code, je vous conseille chaudement le code golfing.