This page presents some little funny projects to code, for the bored ones. They constitute some sort of brainteasers for geeks. Who said procrastination ??

If you have propositions to enrich my collection of coding brainteasers, please contact me.

External Sources of Procrastination

Light Bot and Light Bot 2 are two flash games for programmers. I like it a lot, even if the first one is a bit short and the second one is a bit hard.
Robozzle is similar to Light Bot yet different. If you liked one, you'll like the other one. It's kinda playable in javascript although I've been told that the SilverLight version is much more usable.
There is also some funny and challenging exercises in the PLM. In particular, check the maze and lightbot lessons.
Online exercisers: these sites list a whole load of algorithmic problems. Pick a problem, solve it, submit your solution, and the robot will evaluate the correction of your program instantly. Unfortunately, the problem lists are long and uneven. I must be prefectionits, but I'd prefer some more editorial work from their maintainers.
- CodinGame The best players will get interesting job offers.
- Sphere Online Judge
- Programming Challenge The editorial work is a bit better here, with less exercises.
Programming Contests: There is several sites that organize some sort of programming contests. In general, they are intended to select the best programmer from the participant, and are thus quite difficult to achieve. Another result of this premise is that no or little help is given to improve your solution if you fail. I must confess that I didn't really tryied them out, but you may like them.
- GoogleJam is an annual coding contest.
- TopCoder is another similar system, but more restrictive on the languages you may use (only Java, C++ or C#).
- ICFP contest is certainly the king of all programming contests. It is also rather difficult, definitely far from the "gentle coding brainteasers" category listed below
- A larger collection of Programming Contests maintained by Pascal Lafourcade.
Small games that could maybe be implemented for fun:
- Pen and paper games
- Rich maths activities
- Full collection by Pascal Lafourcade.
If you liked these links and if you speak French, you probably should stop by interstices, too. That's a really nice website.

TODO: Translate in english

Le radoteur (machine à inventer des mots)

[Le "radoteur" a été imaginé par Claude Shannon puis exploré et baptisé (en 1975) par Roland Moreno (lire Théorie du bordel ambiant, chapitre 6, Belfond, 1990)].

Le radoteur fabrique des mots nouveaux à partir d'une liste de mots. Il découpe des groupes de lettres dans les mots de la liste et les colle bout-à-bout. Il assemble par exemple le début d'un mot avec la fin d'un autre. Il n'y a aucune "invention". Le résultat a toujours un air de famille avec les mots de départ... tout en étant différent. Par exemple, lorsqu'on lui donne une liste de pays, il en fabrique de nouveaux : palombie syldavie bordurie kafiristan lizbékistan...

Algorithme

Choisir une lettre au hasard dans la liste de mot et l'écrire dans le mot en construction.
Chercher la prochaine occurence de cette lettre dans la liste de mot.
Considérons la lettre juste après celle cherchée. On l'ajoute au mot en construction, et cela devient le nouveau motif à chercher en retournant à l'étape 2. On s'arrête quand on a trouvé un espace.

Voilà, c'est tout. Donc, pour le coder, il faut savoir allouer un tableau de chaînes, puis chacune des chaînes. Ensuite, il faut ouvrir le fichier passé en argument et lire chaque ligne avec getline(3), par exemple. A partir de là, le reste est enfantin.

Listes de mots

Voici quelques exemples. Si vous avez d'autres listes ou si vous avez des exemples de listes manquantes, envoyez les moi s'il vous plaît.

Liste de pays ; animaux ; fleurs ; plantes ; médicaments ; injures ; prénoms... On peut bien évidement mélanger différentes listes (fleurs et injures ?).

Variantes

La première est assez simple et la seconde ajoute vraiment ajoute du piquant, alors n'hésitez pas.

Faire varier la similitude

Au lieu d'utiliser un motif de taille 1 (ie, chercher une lettre seule), on peut chercher plusieurs lettres à la fois. Ce nombre de lettres est le paramètre Avant. De même, au lieu de prendre une seule lettre après, on peut en prendre plusieurs (paramètre Après). Quand ces paramètres augmentent, la similitude des mots crées avec ceux de la liste donnée augmente. Expérimentalement, Avant=Après=2 donne de bons résultats.

Note: il y a des algorithmes très bien pour la recherche de motif. Si vous ne savez pas faire, utilisez strstr(3).

Créer des phrases entières et d'autres choses

On peut jouer sur des proverbes (Après la pluie, rien d'impossible ; L'union vient en mangeant ; veni, vedi, j'y reste) ou des petites annonces (Etudiant ch. dame sensible avec remorque). Moreno propose même de créer de la musique de la sorte en mélangeant du Bach et du Brel. Une autre idée est de travailler avec l'alphabet phonétique au lieu d'utiliser les lettres habituelles. Si quelqu'un me propose une implémentation, je suis naturellement preneur...

Nombres auto-digitaux

(idée honteusement volée dans "le virus informatique", mais en même temps, il serait dommage de laisser cette idée tomber dans les limbes de l'oubli sous prétexte que ce bon journal n'existe plus).

On dira d'un nombre qu'il est autodigital parfait s'il peut être calculé en utilisant tous les chiffres qui le compose dans leur ordre d'apparition (de gauche à droite). Si l'ordre d'apparition n'est pas respecté, on le dira imparfait. Un exemple valant mieux qu'un long discours :

36 = 3! * 6
127 = -1 + 2⁷
660 = 6! - 60

Ces trois nombres sont des autodigitaux parfaits. Le dernier nombre met en évidence qu'on accepte aussi, arbitrairement, d'utiliser des groupes de chiffres. Attention, on n'accepte pas d'utiliser le groupe formé de tous les chiffres, i.e. le nombre recherché lui-même, car cela manquerait un peu d'intérêt de constater que, par exemple, 660 = 660, non ? Le deuxième exemple montre que l'opérateur de soustraction peut-être utilisé comme opérateur unaire (s'appliquant à une seule opérande), ce qui revient à dire qu'on accepte les nombres négatifs. Dans le cadre de ce problème, on se limitera aux opérateurs suivant (que l'on pourra combiner autant que nécessaire) :

les quatres opérations de base : +, -, /, * (on accepte le "-" comme opérateur et comme signe)
l'élévation à la puissance : ^
la factorielle : ! [qui se définit par 0! = 1 ; 1! = 1 ; n! = 1 * 2 * ... * n (pour n > 1)
la racine carrée
les parenthèses : ( )

La question est bien évidement de trouver tous les nombres autodigitaux parfaits ou non entre 0 et ... ben, jusqu'où vous pouvez. Personellement, j'ai aussi fait quelques recherches...

tranche	# parfaits	# imparfaits
0-999	39	29
1000-1999	36	127

Si vous vous ennuyez, vous pouvez ajouter d'autres opérations, telles que la sommielle (pendant de la factorielle pour l'addition), ou le changement de base.

Indice: Pour faire ce projet en C, manipuler des pointeurs sur fonction peut aider. D'autres langages (comme CAML) me semblent plus simple, mais ça peut être personnel.

Ce problème a été assez intensivement étudié par un mathématicien américan nommé Erich Friedman. À la lecture de sa page web, j'aime bien cette personne et je vous conseille d'aller lui rendre visite. Sa collection de puzzles est très intéressante pour qui veut faire de petits défis de programmation.