I'm now blogging in English on blog.a3nm.net. The main reason for the move is that I want to manage my blog on my own computer rather than through a web interface. I'm unsure about the fate of this old blog, though.

Cela dit, je ne suis plus vraiment satisfait par le système du blog tel que je l'ai mis en place. Déjà, les billets s'éditent avec une interface web, alors que je préférerais le faire en ligne de commande. Ensuite, il serait bien d'automatiser les choses entre mon gros dépôt Subversion qui contient mon travail et le blog, pour éviter d'avoir à tout mettre à jour à la main. Pire encore, j'aimerais me débarrasser de Subversion pour passer à autre chose... mais à quoi ? VCS décentralisé ? Peut-être, mais...

Donc, il n'est pas dit que ce blog en tant que tel continue à être mis à jour... je vais plutôt essayer de mettre en place un nouveau système. Si j'y arrive, évidemment, ce sera indiqué ici. L'idéal serait de migrer le contenu de ce blog vers le nouveau pour assurer la compatibilité descendante et éviter de continuer à trimballer celui-là, mais ça n'est pas gagné.

Prépa's over, so I should resume updating this blog. I'll be going to Normale Sup' next year, and I'm quite happy about it. :-)

However, I'm not really satisfied anymore by the system I set up to write this blog. First, posts are written through a web interface, whereas I'd rather edit them in my terminal. Second, it'd be better to design some scripts to update the blog automatically from my big Subversion repository without having to upload everything by hand. Worse still, I'd prefer to dump Subversion and start using something else... but I don't know what. A decentralised VCS, maybe.

It's therefore quite unsure that this blog per se will go on... I'll rather try to set up another system. If I manage to do that, I'll blog about it here, of course. The best thing to do would be to move this blog's content to the new system in order to ensure backward compatibility and avoid keeping this one running, but it's not that simple to do...

I am working hard to prepare the entrance exams for the grandes écoles, and will not be able to update this blog for several months.

Comme l'an dernier, c'était absolument génial. Comme l'an dernier, le sujet était absolument délirant (diriger un hamster pour s'emparer de pommes plus vite que l'adversaire, en planifiant ses déplacements trois par trois). Contrairement à l'an dernier, toutefois, j'ai fini premier (j'étais 44e en 2007). Ça m'a beaucoup et agréablement surpris. Certes, je savais mieux comment gérer mon temps, et le sujet m'a paru beaucoup plus abordable (l'an dernier, il fallait gérer des messages entre collègues, et collaborer avec l'ennemi tout en le trahissant, ce qui n'était pas simple). Mais quand même.

Comme l'an dernier, je mets mon code source à disposition ici (sous licence GNU GPL, si quelqu'un souhaite l'utiliser). Le code est raisonnablement bien documenté (même s'il manque le fichier README.TXT principal), j'ai passé ma dernière heure à faire ça (et quelques minutes de plus auraient été bien utiles). Le code ne montre pas non plus une petite bidouille que j'avais utilisée, et qui a été bien pratique (sans doute un facteur non négligeable pour expliquer ma première place) : une interface à Stechec (utilisant wget, avec des paramètres POST et les cookies de Firefox) pour lancer de manière automatique plusieurs centaines de matches. Grâce à la fonction de score proposée par Stechec pour chaque IA uploadée, cela me permettait de comparer très facilement les versions entre elles pour mesurer les améliorations et identifier les régressions. (Il n'y avait pas encore de feedback, toutefois ; le script ne parsait pas le HTML de Stechec pour aller lire les scores. Il serait rigolo d'essayer d'optimiser chacune des constantes numériques du code de façon automatisée avec un système un peu plus évolué... peut-être le ferai-je l'an prochain, si les concours me laissent le temps de participer...)

• amarillia.tgz (13 Kio), archive TGZ du champion soumise à Stechec, modifiée seulement en ajoutant un fichier COPYING et en rangeant les fichiers dans un dossier "finale" (licences GNU GPL version 2 ou ultérieure, et Creative Commons BY-SA version 2.0 ou ultérieure).

Mes conseils aux futurs participants à Prologin, pour éviter de tomber dans les pièges classiques (s'il y en a que ça intéresse) :

• Qualifiez-vous pour la demi-finale. C'est super important. Pour ce faire, remplissez le QCM de sélection. Il est d'une difficulté très raisonnable, la plupart des réponses aux questions pouvant être obtenues à l'aide d'un moteur de recherche. Les programmes à écrire sont aussi d'une difficulté raisonnable : rédigez-les proprement, commentez-les soigneusement (ils sont lus par des humains), et surtout, assurez-vous qu'ils fonctionnent correctement sur des données de test avant de les soumettre (c'est la moindre des choses). Le plus difficile est sans doute de trouver le temps de rédiger les programmes parce qu'on n'est pas sûr que ça en vaille la peine (si j'ai participé en 2007, c'est en très grande partie parce que je suis tombé sur le concours un soir où je n'avais pas grand-chose d'autre à faire), mais croyez-moi, le jeu en vaut la chandelle.
• Qualifiez-vous pour la finale. C'est super important aussi. (Si l'épreuve machine de la demi-finale peut sembler fun, la finale l'est encore beaucoup plus.) L'épreuve papier est sans doute la partie la plus "scolaire" de Prologin (même si le sujet est rédigé avec humour) : des connaissances en algorithmique et en informatique théorique sont sans doute utiles, mais si, comme moi, vous en avez peu, savoir programmer devrait suffire. L'entretien n'est pas très difficile : on vous demandera grosso modo ce que vous avez fait ces derniers temps qui ait trait à l'informatique, pour s'assurer que vous pratiquez. L'épreuve machine est très sympathique ; les programmes à rédiger sont de difficulté croissante (normalement), il faut en écrire le plus possible. Il est facile de perdre plusieurs dizaines de minutes pour traquer une ânerie qui empêche votre code de fonctionner ; si vous en avez marre, n'hésitez pas à demander l'aide d'un organisateur.
• Assurez-vous d'avoir bien compris le sujet de la finale. Cela va de soi : inutile de commencer à coder si vous avez encore des doutes. Étant donné que les sujets de finale sont en règle générale bien tordus, dissiper les confusions peut prendre un certain temps.
• Faites quelque chose de simple qui marche à peu près, puis améliorez-le progressivement. Il est très difficile de gérer son temps (trente-six heures, c'est à la fois très long et très court), et il vaut mieux être sûr de rendre quelque chose de primitif, plutôt que de s'embarquer dans un projet pharaonique qui ne sera pas fini à la fin du temps et qui ne fonctionnera pas.
• En première approximation, oubliez que l'ennemi est présent (si c'est possible). Tant qu'il n'est pas possible d'affronter d'autres IA sur Stechec, inutile de partir dans de complexes pronostics sur les stratégies adverses possibles. Faites une IA qui répond à peu près à la question posée, seule, sans se soucier des éventuelles perturbations que l'ennemi pourrait provoquer. (Bien entendu, si tout cela a un sens par rapport au sujet posé, mais en général c'est le cas).
• Par contre, dès que possible, battez-vous sur Stechec. Vu que c'est Stechec qui va être utilisé pour noter votre IA, c'est la référence pour que vous puissiez juger de sa performance. Si vous perdez systématiquement contre une autre IA, il peut être utile de visionner le match pour identifier d'où proviennent vos échecs (c'est comme ça que, vers le début, j'ai compris que si je passais mon temps à transporter des pommes de la zone neutre à ma base ; comme l'ennemi passait le sien à transporter des pommes de ma zone à la sienne, j'étais mal parti). Par contre, essayez aussi de ne pas perdre trop de temps à faire ça : au bout d'un moment, il faut essayer d'améliorer son IA par rapport à sa capacité à battre les autres en moyenne, même si elle perd de temps en temps.
• Gardez les tâches faciles pour la fin. Par exemple, la documentation (même si écrire du code propre dès le départ est préférable, car il n'est pas exclu qu'en commentant, vous supprimiez accidentellement un point critique de votre code...). À quelques heures de la fin, essayez d'avoir une version stable à laquelle vous ne touchez plus. Si vous essayez encore de l'améliorer, vérifiez sur Stechec que tout fonctionne encore correctement.
• Utilisez un gestionnaire de versions. Ou, au moins, faites des copies de sauvegarde. Et n'hésitez pas à revenir en arrière, vous aurez parfois des surprises. (Vers la fin, certaines corrections de bug (du genre, ne pas tirer sur un hamster s'il y a un rocher dans le chemin) ou améliorations (par exemple, utilisation du turbo) rendaient en fait l'IA moins efficace, pour des raisons mystérieuses.)
• Ne passez pas tout votre temps à coder. Bon, j'y ai quand même passé le plus clair de mon temps, mais prendre du recul par rapport à ce que vous faites peut vous aider à comprendre quelques points essentiels. Par exemple, ce n'est que vers le deuxième soir que j'ai compris que l'histoire de la planification à trois tours m'obligeait à récrire dans mon code une partie du code du serveur pour anticiper correctement ce qui arriverait à mes hamsters (sans compter l'ennemi).

Pour terminer ce billet, je voudrais remercier l'équipe de Prologin. Ils font vraiment un travail remarquable. En particulier, merci pour la stabilité du serveur cette année. Ce n'est pas une blague ; alors que, l'an dernier, les règles du jeu changeaient en cours de route et que le serveur n'acceptait qu'un match sur trois (quand il ne plantait pas), tout a fonctionné (presque) parfaitement cette année, et le serveur a accepté sans broncher les milliers de matches que mon script a lancés. Du beau boulot !

Bien que j'utilise des systèmes *nix depuis plus de deux ans, c'est seulement il y a quelques mois que j'ai commencé à utiliser SSH. Au début, je me demandais ce que ça pouvait bien être, mais j'ai vite compris que c'était un outil extrêmement utile, et une découverte récente de ma part fait que je le classe maintenant au rang des outils indispensables.

SSH basics

SSH is a tool for secure remote use of a machine. To use a computer remotely, you first install the SSH server software on this computer: aptitude install openssh-server should be enough on Debian-based distros. Then, using another machine, you can log in remotely with the command: ssh login@server where "login" is your login name and "server" is the domain name (or IP address) of the server. You then give your password and voilà: you are connected to the remote machine and can enter commands as if you were in front of a physical terminal for this machine.

SSH est un outil permettant d'utiliser une machine à distance de façon sécurisée. Pour ce faire, il faut d'abord installer le serveur SSH sur la machine que vous voulez contrôler : aptitude install openssh-server devrait suffire pour les distributions dérivées de Debian. Une fois que cela est fait, vous pouvez vous connecter à distance depuis une autre machine avec la commande ssh login@server où "login" est votre nom d'utilisateur et "serveur" le nom de domaine (ou l'adresse IP) du serveur. Vous donnez alors votre mot de passe, et vous êtes connecté à la machine distante : vous pouvez entrer des commandes comme si vous étiez en face d'un terminal physique pour cette machine.

Security

Unlike Telnet, SSH has a very strong focus on security. (OpenSSH is developed by the OpenBSD team.) First, your actual password is never sent in plaintext to the host. It works more or less like this: the server asks you to encrypt some random data using your password. Only the encrypted data (which is not sufficient to recover your password) is sent by your machine. The server check if it matches what it got using your actual password. If the two match, you are given access. Second, all further exchanges between you and the server are encrypted. This means that you can log in using SSH over any kind of connection, no matter how insecure. (Open Wifi networks are a good example.)

SSH, au contraire de Telnet, est très orienté sécurité. (OpenSSH est développé par l'équipe de OpenBSD.) Premièrement, votre mot de passe n'est jamais envoyé en clair à l'hôte. Cela fonctionne à peu près comme ça : le serveur vous demande de chiffrer des données aléatoires à l'aide de votre mot de passe. Seules les données chiffrées (qui ne suffisent pas pour reconstituer votre mot de passe) sont envoyées par votre machine. Le serveur vérifie si ça correspond à ce que lui obtient avec votre mot de passe réel. Si les deux correspondent, il vous donne accès à votre compte. Deuxièmement, toutes les communications ultérieures entre vous et le serveur sont chiffrées. Cela signifie que vous pouvez vous connecter en utilisant SSH via n'importe quel type de connexion, même si elles sont peu sécurisées (par exemple, des réseaux Wifi ouverts.)

SFTP

SSH can also be used as a way to transmit files between two machines (in a FTP-like way). You can directly use the sftp program on the command line, or use graphical FTP clients which support SFTP (such as Filezilla or gFTP); you can even pseudo-mount it using Gnome and KDE. The Gnome integration sometimes refuses to work, but when it works, if the bandwidth is large enough, you can use Totem to play some files from the remote server on your machine. Last but not least, you can use a program called rsync for automatic synchronisation of folders between the client and host. Rsync optimises the transfer rates using diff algos and on-the-fly compression.

SSH peut aussi être utilisé pour transmettre des fichiers entre deux machines (d'une manière semblable à FTP). Depius la ligne de commande, vous pouvez utiliser directement le programme sftp ; vous pouvez aussi utiliser des clients FTP graphiques avec support SFTP (comme Filezilla ou gFTP), ou même le pseudo-monter depuis Gnome ou KDE. L'intégration avec Gnome ne fonctionne pas toujours, mais quand cela fonctionne, si la bande passante est suffisante, vous pouvez utiliser Totem pour jouer des fichiers audio sur votre machine depuis le serveur. Une autre possibilité (et non des moindres) est d'utiliser un programme nommé rsync pour synchroniser automatiquement des répertoires entre le serveur et le client. Rsync optimise les taux de transfert à l'aide d'algorithmes fondés sur diff, et en compressant les transferts à la volée.

Key-based authentication

Entering your password each time you login to a remote host can be a pain. Worse still, it makes it very difficult to script connections to an SSH server for backups or anything. There is no -password switch for SSH; there are obscure ways to work around this, but it is discouraged. It is much better to generate a key used to authentify your machine. You first run the program ssh-keygen to create a key (do not enter any passphrase), and then you log in to the remote host using ssh-copy-id (you might have to pass the path to the *.pub key file in your .ssh folder using the -i switch). Your key is then added to the remote host's allowed keys list, so that you can log in to it (only for your session, of course :)) using the key file (automatically sent by SSH) instead of a password. (If it doesn't work, it might be because SSH thinks the permissions of your home directory, .ssh folder and stuff aren't restrictive enough; search the web for details about how to set up permissions.) Of course, since the key file is sufficient to connect to the server, make sure to keep it private.

Il peut être pénible d'entrer votre mot de passe à chaque fois que vous vous connectez à une machine distante. Pire encore, cela rend très difficile la connexion à un serveur SSH avec des scripts, pour faire des backups ou quoi que ce soit d'autre. Il n'y a pas d'option -password pour SSH; il y a des moyens obscurs de contourner cela, mais ce n'est pas recommandé. Il est de loin préférable de générer une clé permettant d'authentifier votre machine. Vous lancez d'abord le programme ssh-keygen pour créer une clé (ne paramétrez pas de phrase de passe), et puis vous vous connectez à l'hôte distant en utilisant ssh-copy-id (il faudra peut-être passer en paramètre le chemin vers le fichier de clé *.pub dans votre répertoire .ssh avec l'option -i). Votre clé est alors ajoutée à la liste des clés autorisées par l'hôte distant, de sorte que vous pouvez vous y connecter (seulement avec votre session, bien sûr :)) en utilisant le fichier de clé (envoyé automatiquement par SSH) au lieu d'un mot de passe. (Si ça ne fonctionne pas, c'est peut-être parce que SSH a décidé que les permissions de votre répertoire utilisateur, dossier .ssh et autres ne sont pas assez restrictives; cherchez sur Internet pour savoir quelles sont les permissions qu'il faut mettre.) Bien sûr, vu que le fichier de clé est suffisant pour se connecter au serveur, faites en sorte de la garder en sécurité.

Using X

The command line is nice, but perhaps would you prefer to use X applications. SSH also allows you to do that. Just pass the -X switch to SSH on the command line, and run any graphical application you like on the terminal (e.g. "firefox"). It should then appear on your screen, running from the remote host (and once again going through a secure channel). A few caveats, however. First, unless you are on a very low-latency high-speed network (such as a LAN), everything will probably feel quite sluggish. This can be improved a bit with the -C switch (which tells SSH to compress all traffic on-the-fly). Second, this can not be used (as far as I know) to monitor the status of existing applications, only to run new ones: if you want to see what the remote host is displaying (with the desktop and all), you'll be better off with something like VNC. Third, X11 forwarding does not forward the sound. There might be some workarounnds but I don't know any simple one. The sound will be played on the remote machine instead, with potentially unexpected effects on anybody who happens to be nearby... So keep all of this in mind, and stick to the command line whenever possible ;).

La ligne de commande, c'est bien joli, mais peut-être préféreriez-vous utiliser des applications X. SSH vous permet de le faire. Passez juste le paramètre -X à SSH sur la ligne de commande, et lancez l'application graphique de votre choix depuis le terminal (par exemple "firefox"). Elle devrait alors apparaître sur votre écran, en étant exécutée sur la machine distante (et à nouveau au travers d'un canal sécurisé). Il y a quelques limitations, cependant. Premièrement, à moins d'être sur un réseau à très faible latence et à très grande vitesse (un réseau local, par exemple), tout sera probablement très lent. On peut un peu l'améliorer avec l'option -C (qui demande à SSH de compresser tout le trafic à la volée). Deuxièmement, on ne peut pas se servir de l'option -X (enfin, pas que je sache) pour suivre l'exécution d'applications déjà lancées ; on peut juste en lancer de nouvelles. Si vous voulez voir précisément ce que l'hôte distant affiche (avec le bureau et tout), vous feriez mieux d'utiliser quelque chose comme VNC. Troisièmement, le forwarding X11 ne permet pas d'avoir du son. Il y a peut-être une manière de l'avoir, mais je n'en connais aucune qui soit simple. Le son sera en fait joué sur la machine distante, ce qui peut avoir des effets imprévus sur les personnes qui sont à proximité... Donc, gardez tout cela en tête, et tenez-vous-en à la ligne de commande dans la mesure du possible. ;)

Tunnels

Tunnels are a very useful tool which I just discovered. Say you're on holiday with no connection except an open Wifi network, and you want to check your e-mail. If you can use a protocol which is already secure (such as HTTPS for a webmail) then you're fine. However, if the protocol isn't secure, it is not a very good idea to broadcast your passwords in plaintext for anybody to sniff and reuse. If you've understood everything I said up to now, you might be tempted to use SSH to log in to a machine with a trusted web connection and then check your mail, so that your passwords first go through SSH (encrypted) over the Wifi connection and then in plaintext from the trusted machine to the server on the secure connection. A better option is to create a tunnel (in fact, creating a SOCKS server is an even better option, I'll present it in the next paragraph). Tunnels are created by passing to SSH the -L switch with something like 123:mailserver.org:456. If you run this, pointing a program to port 123 on your machine will cause SSH to forward its input to the host you connected to, which will in turn redirect the traffic to port 456 of mailserver.org. Another use case is to reach a machine within a LAN from the outside world: use ssh machine_a 123:machine_b:123 with "machine_a" one of the machines in the LAN which can be reached from the WAN, and "machine_b" the target LAN machine identified by its LAN address. When you request something on port 123 of your machine, everything will happen as if you were machine_a trying to access machine_b on port 123.

Les tunnels sont un outil très pratique que j'ai découvert récemment. Par exemple, disons que vous êtes en vacances avec pour seule connexion un réseau Wifi ouvert, et que vous voulez relever votre courriel. Si vous utilisez un protocole qui est déjà sécurisé (par exemple, HTTPS pour accéder à un webmail), vous êtes tranquille. Par contre, si le protocole n'est pas sécurisé, vous n'avez probablement pas envie d'émettre vos mots de passe en clair pour que n'importe qui puisse les intercepter et s'en servir. Si vous avez compris ce que j'ai écrit jusqu'à maintenant, vous avez peut-être envie d'utiliser SSH pour vous connecter à une machine avec une connexion sécurisée à Internet et de relever votre courriel à partir de là, de sorte que vos mots de passe transitent d'abord sous forme chiffrée avec SSH via la connexion Wifi, et puis en clair depuis la machine de confiance jusqu'au serveur via la connexion sécurisée. Il y a une meilleure manière de faire, c'est d'utiliser des tunnels (en fait, créer un serveur SOCKS est encore plus pratique, j'en parlerai dans le prochain paragraphe). Pour créer un tunnel, il faut passer à SSH l'option -L avec un paramètre comme 123:mailserver.org:456. Cela signifie que si un programme se connecte au port 123 sur votre machine, SSH transmettra la connexion à l'hôte auquel vous vous êtes connecté, qui redirigera à son tour le trafic au port 456 de mailserver.org. Une autre utilisation possible est d'atteindre depuis le monde extérieur une machine à l'intérieur d'un réseau local : utilisez ssh machine_a 123:machine_b:123 où "machine_a" est une des machines du réseau local accessible depuis l'extérieur, et "machine_b" la machine cible du identifiée par son adresse dans le réseau local. Quand vous accéderez au port 123 de votre machine, tout se passera comme si vous étiez la machine_a en train d'essayer d'accéder à machine_b sur le port 123.

SOCKS

A better solution for the Wifi use case above is to create a SOCKS server. Creating a tunnel is fine, but suppose that you want to use the secure tunnel on several ports, to visit several websites... You won't use a tunnel for every connection you want to secure. Instead, you'll use the -D switch and pass a port number (say 9999). This will create a SOCKS server on your machine, port 9999, which will redirect its input to the trusted machine you connected to using SSH and then use it. What you will do is instruct your OS and/or whatever application you're using (e.g. Ubuntu has a system-wide setting but Firefox and Thunderbird have their own options and will override it) to use the SOCKS proxy at 127.0.0.1 port 9999. When these applications want to use Internet, they will send their queries through the SOCKS proxy (no matter whom they connect to, no matter which port), and SSH will redirect them to the trusted machine who will perform the query. This enables you to do anything you wish on an untrusted connection in a quite straightforward way, and can also be used for other things (e.g. circumvent IP blocks on the machine you're using by appearing to the outside world as the trusted machine...). The only downside, as with everything to do with tunneling, is higher ping (instead of going directly to the remote host, you have to pass through the trusted machine), and smaller rates (the slowest member of the chain will limit the speed; for instance, if you download a file from the web through a tunnel involving a trusted machine on a home connection, chances are that the web server has a decent upload speed but that your trusted machine hasn't and will slow the whole thing down).

Une meilleure solution, si vous n'avez qu'une connexion Wifi non sécurisée à portée, est de créer un serveur SOCKS. Créer un tunnel est déjà bien, mais si vous voulez utiliser différents ports et différents sites web, vous n'aller pas créer un tunnel pour chaque connexion. Vous allez plutôt utiliser le paramètre -D et passer en paramètre un port, par exemple 9999. Ceci va créer un serveur SOCKS sur votre machine (sur le port 9999) qui va rediriger tout ce qu'il reçoit à la machine de confiance (à laquelle vous vous êtes connecté avec SSH) qui va ensuite l'exécuter. Il faudra juste dire à votre système d'exploitation et/ou aux applications que vous utilisez (par exemple, Ubuntu a un paramètre pour cela mais Firefox et Thunderbird ne suivent pas le réglage système et ont leur propres options) d'utiliser le proxy SOCKS à l'adresse 127.0.0.1 port 9999. Quand ces applications voudront utiliser Internet, elles enverront leurs requêtes au serveur SOCKS (peu importe à qui elles se connectent, peu importe le port), et SSH les redirigera à la machine de confiance qui effectuera la requête. Cela vous permet de faire ce que vous voulez sur la connexion non sécurisée sans trop se prendre la tête, et peut être utilisé pour toutes sortes d'autres choses (par exemple, contourner des blocages d'IP sur la machine que vous utilisez, en apparaissant comme la machine de confiance pour le monde extérieur...). Le seul inconvénient, qui s'applique à toute cette histoire de tunneling, est que vous allez avoir un ping plus élevé (au lieu de vous connecter directement à la machine distante, il faut passer par la machine de confiance) et des débits plus bas (le maillon le plus lent de la chaîne sera limitant ; par exemple, si vous téléchargez un fichier depuis le web via un tunnel passant par une machine de confiance avec un fournisseur d'accès standard, il est probable que le serveur web a une vitesse d'upload bien supérieure à votre machine de confiance, qui va tout ralentir).

Over HTTP

It seems that you can (quite) easily embed SSH traffic in HTTP to work around stringent firewall policies. I haven't had the occasion to try it yet (but I'll probably do it soon). See this explanation.

Il semblerait qu'il soit (assez) facile d'inclure du trafic SSH dans du HTTP pour contourner des pare-feux restrictifs. Je n'ai pas encore eu l'occasion d'essayer, mais je le ferai sans doute bientôt. Voir ces explications.

• main.pdf (125,1 Kio), fichier PDF ;
• main.tex (44,1 Kio), fichier source LaTeX.

Désolé pour l'absence de mises à jour ; je suis toujours là, malgré tout. Je devrais bientôt poster une dissertation du Concours Général et configurer Subversion pour publier mes commits ici, patience...

Résolution de Sudoku avec Maple

Il s'agissait d'une réécriture hâtive de mon programme Sudokusc pour Maple. Je précise que je n'apprécie pas vraiment Maple (c'est une litote), qui est un logiciel à la fois propriétaire et de très mauvaise qualité, mais c'est malheureusement ce que nous utilisons en prépa (honte sur l'Éducation Nationale), et c'était donc le seul langage que tous mes camarades de classe comprenaient.

Comparé à mon autre présentation du même logiciel, celle-ci visait à présenter le fonctionnement du programme plus que la programmation en général. L'ensemble du programme était peu à peu écrit au tableau, et mes auditeurs devaient en théorie comprendre ce qu'il faisait. Je ne disposais pas d'un rétroprojecteur, aussi n'avais-je qu'un plan de cours et non un diaporama. Je n'ai pas non plus écrit de résumé pour les auditeurs, par manque de temps mais aussi parce que le plan est posté ici et que le résumé n'en aurait été qu'une copie.

Je mets également à disposition le code du programme Sudokusc écrit en Maple, accompagné d'une grille d'exemple (la résolution prend quelques dizaines de secondes, à comparer aux quelques dizaines de millisecondes nécessaires avec la version en C). La fonction à exécuter est sksolve ; la fonction sksolve_global n'a pas été testé mais devrait être plus performante si elle fonctionne.

Fichiers :

• main.pdf (41,9 Kio), plan de la présentation au format PDF ;
• main.tex (2,7 Kio), sources du plan de la présentation au format LaTeX ;
• sumaple.txt (3,2 Kio), programme Maple avec grille d'exemple ;
• grid_c.txt (163 octets), grille d'exemple à fournir en entrée à la version en C pour comparaison des performances.

Zapping informatique : présentation rapide de concepts fondamentaux

(C'est le titre indiqué sur le document, mais je n'en suis pas satisfait, aussi ne l'ai-je pas donné lors de la présentation.)

Cette présentation (à mon avis bien plus intéressante) a été construite à partir de l'article Huit concepts qu'il faudrait faire connaître aux utilisateurs Windows déjà publié sur ce blog. À ces huit thèmes s'ajoutent une brève présentation de SSH (que j'ai découvert depuis lors) et une présentation rapide de la sécurité informatique (que je comptais rédiger sous la forme d'un billet pour ce blog, je le ferai peut-être si j'ai le temps).

Faute de temps, tout ce qui est indiqué sur le plan n'a pas forcément été traité. Une version vaguement retouchée de l'article original est incluse, elle n'a pas été mise à jour de manière satisfaisante pour intégrer tout ce que mentionne la présentation.

J'ai profité de la présentation pour faire une petite blague à mes chers camarades. Sous le prétexte d'expliquer ce qu'était le social engineering, j'ai fait mine de leur montrer quelque chose sur ordinateur. J'ai alors demandé que quelqu'un me "prête" sa session parce que la mienne ne fonctionnait pas pour ce que je voulais illustrer. Dans les deux groupes, quelqu'un s'est généreusement proposé et m'a donné son identifiant et son mot de passe, sur un plateau d'argent. J'ai alors expliqué où je voulais en venir : c'était en fait du social engineering récursif, ou méta-social-engineering. Si les deux victimes se souviennent au moins qu'il ne faut pas donner son mot de passe à quiconque, ce sera déjà une bonne chose. (Sans rancune ? ;-))

Fichiers :

• main.pdf (48,0 Kio), plan de la présentation au format PDF ;
• main.tex (8,2 Kio), sources du plan de la présentation au format LaTeX ;
• main.txt (34,9 Kio), version peu modifiée de l'article original.

Pour ceux qui ne le savent pas, Prologin est le concours national d'informatique français. Il est ouvert aux personnes de moins de 20 ans, et la participation est gratuite. Une première sélection est effectuée sur la base d'un QCM et de quatre petits programmes à rédiger, que vous pouvez allez rendre en ligne dès maintenant. Les 300 meilleurs (environ) sont retenus pour participer aux demi-finales qui comportent de l'informatique, de l'algorithmique et un entretien, et qui se déroulent sur une journée dans les principales villes de France. Les 100 meilleurs sont retenus pour participer à la finale qui dure quelques jours et a lieu à Paris, et où l'épreuve est 36 (trente-six) heures de programmation non-stop. Vous devez coder une intelligence artificielle pour un jeu dont les règles vous ont été données. Les programmes s'affrontent au terme du concours, et les dix meilleurs candidats sont départagés par entretiens individuels et reçoivent des (très jolis) cadeaux.

J'ai participé à la finale de l'année dernière, et je peux vous dire que l'expression "concours national d'informatique" est extrêmement réductrice. Il serait plus juste de parler de "formation accélérée aux logiciels libres", de "paradis pour informaticiens", ou de "réunion de jeunes geeks".

Croyez-moi, ça en vaut vraiment, vraiment la peine. À titre illustratif, voici quelques informations concernant la finale :

Liste des activités organisées (non exhaustive)

• Banquet ;
• Barbe à papa ;
• Bataille d'eau ;
• Concerts ;
• Demos ;
• Discussions entre geeks ;
• DJ ;
• Feu d'artifice ;
• Formation au logiciel libre ;
• Jonglage ;
• Karaoké ;
• LAN ;
• Lasers ;
• Présentations ;
• Programmation ;
• Réveils en fanfare ;
• Surprises ;
• Tetris ;
• Très peu de sommeil.

Diagramme de mes activités

Quelques perles de code

Manque de temps, manque de sommeil... cela favorise l'apparition de certaines perles lors de la correction du code. Faute d'avoir gagné un prix, j'aurai au moins fait rigoler (ou pleurer) les correcteurs. Toutes ces perles sont tirées de la version finale du programme, que j'ai rendue. (Du moins, si je me souviens bien de quelle version j'ai rendue...)

Pour embrouiller le relecteur...

/* FIXME2: à utiliser */
#define MENACE_ALLIE_MALUS_ATTAQUE_CELLULE_SAINE 50

À comprendre...

#define SCORE_VIRUS_PHAGO 20.0
#define SCORE_CELL_PHAGO 20.0
#define SCORE_LEUCO_PHAGO 200.0 /* NB c'est un coefficient */

Bien la peine...

/* Distance max à considérer dans l'exploration des distances (en Manhattan) */
#define MAX_RANGE 1

Bon courage...

/* Coefficient d'incertitude au cours du temps pour chaque type.
   (à la puissance du nombre de jours pour aboutir à un pourcentage) */
const float certainty = {1, 1, 0.2, 0.9, 0.7, 0.2} ;

Ce serait bête, hein ?

/* Pour ne pas s'agglutiner bêtement */

#define PERIMETRE 1
#define PENALTY_POW 3000
#define PENALTY_ENNEMY_NEAR 10;

Ça devrait valoir 1...

/* Ratio des menaces pour priorités d'attaque, le total devrait valoir 1, allie virus bactérie */

#define MENACE_ALLIE 0
#define MENACE_VIRUS 1
#define MENACE_BACTERIE 2

Vanité...

/*
  Notre algorithme de chiffrement des messages révolutionnaire est réputé incassable.

Flemmard...

} else {
  /* Ne nous fatiguons pas, ce n'est pas le travail de cette fonction */
  return BAD_ARGUMENT;

Dommage !

if (consistent() == SUCCESS)
{
  /* Les données sont cohérentes après vérification, c'est donc un message au format privé */
  /* On lui accorde donc la validation */
  _typep = VALID;
  return SUCCESS;
} else {
  /* Non ? Tant pis, dommage */
  return BAD_ARGUMENT;
}

Fonction essentielle.

int thirdparty_parse_message(int id)
{
  /* Fonction de gestion des messages dans un format privé inconnu */

  /* Tentatives élémentaires de décodage */
  /* Gestion de la cohérence, des menaces etc */
  /* FIXME4 */

  return BAD_ARGUMENT;
}

OSEF !

case COM_WHITEFLAG:

  /* On s'en moque :-) */

  break;

Evil mastermind !

case INVALID:
     
  /*
    Le message est une tentative maladroite et pitoyable de nous induire en erreur.
    De fait, les informations qu'il renferme sont très probablement fausses.
    Cela veut dire qu'on ne peut plus avoir confiance en ses alliés !
    On divise par deux la confiance accordée aux messages d'info adverse.
    FIXME4 : crédit négatif aux infos du message
  */
  
  credibilite_allie /= 2;

OSEF toujours.

case COM_WHITEFLAG:

  /* On s'en moque aussi :-) */

  break;

Désespoir...

 printf("failed.\n");

/* Tant pis, que voulez-vous ! */
/* On arrête là, et on doit quand même retourner SUCCESS
   (quelle vie !) */
return SUCCESS;

Programmeur fou...

/* Maintenant que le message sous sa forme intelligible nous attend bien au chaud
   dans des variables globales, on fait le travail d'interprétation proprement dit */

Technique astucieuse...

/* Mesure de prudence... */
while (init_competences() != SUCCESS)
  ;

Hem...

} else {
  return 0; /* There be dragons... */
}

Mes plus belles pièces (1).

int allies_contigus()
{
  if (
      (regarde(position_leucocyte_x(mon_identifiant()),
       position_leucocyte_y(mon_identifiant()) + 1)
        == WHITE_CELL
       && equipe(identifiant_leucocyte(position_leucocyte_x(mon_identifiant()),
                                       position_leucocyte_y(mon_identifiant())+ 1))
        != mon_equipe())
     || (regarde(position_leucocyte_x(mon_identifiant()),
                 position_leucocyte_y(mon_identifiant()) - 1)
        == WHITE_CELL
       && equipe(identifiant_leucocyte(position_leucocyte_x(mon_identifiant()),
                                       position_leucocyte_y(mon_identifiant())- 1))
        != mon_equipe())
     || (regarde(position_leucocyte_x(mon_identifiant()) + 1,
                 position_leucocyte_y(mon_identifiant()))
        == WHITE_CELL
       && equipe(identifiant_leucocyte(position_leucocyte_x(mon_identifiant()) + 1,
                                         position_leucocyte_y(mon_identifiant())))
       != mon_equipe())
     || (regarde(position_leucocyte_x(mon_identifiant()) - 1,
                 position_leucocyte_y(mon_identifiant()))
        == WHITE_CELL
       && equipe(identifiant_leucocyte(position_leucocyte_x(mon_identifiant()) - 1,
                                         position_leucocyte_y(mon_identifiant()))
        != mon_equipe()))
     )
  { return 1; } else { return 0; }
}

Mes plus belles pièces (2).

int agresseur()
{
  int t, x, y;

  if (\(regarde((x = position_leucocyte_x(mon_identifiant())),
               (y = position_leucocyte_y(mon_identifiant())) + 1)
      == WHITE_CELL)
      && (equipe(t = identifiant_leucocyte(x, y+1)) != mon_equipe())
      && (etat_leucocyte(t) == STATE_PHAGOCYTOSING))
    { return t; }

  if ((regarde(x, y-1) == WHITE_CELL)
      && (equipe(t = identifiant_leucocyte(x, y-1)) != mon_equipe())
      && (etat_leucocyte(t) == STATE_PHAGOCYTOSING))
    { return t; }

  if ((regarde(x+1, y) == WHITE_CELL)
      && (equipe(t = identifiant_leucocyte(x+1, y)) != mon_equipe())
      && (etat_leucocyte(t) == STATE_PHAGOCYTOSING))
    { return t; }

  if ((regarde(x-1, y) == WHITE_CELL)
      && (equipe(t = identifiant_leucocyte(x-1, y)) != mon_equipe())
      && (etat_leucocyte(t) == STATE_PHAGOCYTOSING))
    { return t; }
  return INVALID_COMMAND;

}

Tristesse...

case CELL_STATE_DEAD:
 
/* Que peut-on en faire, sinon pleurer sur le sort de cette pauvre
   cellule innocente morte pour la bonne cause ? */

return -1; // (Ouin ouin)

Pessimisme.

case VIRUS:

  /* FIXME1: Oui mais, ce n'est guère subtil et n'est peut-être pas optimal */
  /* FIXME1: (utilisation d'anticorps, astuces pour trahir etc.) */

  return mult_p * menaceMENACE_VIRUS*SCORE_VIRUS_PHAGO;

  break;

Prudence.

}

/* Euh... normalement rien, mais sait-on jamais... */

printf("@Une action est passée entre les mailles du filet de traitement.");

return 0;

Pour rien...

{
  /* On cherche à phagocyter un virus,
     on est pile à une case en diagonale,
     on n'a pas de traîtres potentiels aux basques.
     Donc : on ne fait rien. */

Conditionnel génial

if (1) // inutile de filtrer sur le type de terrain, c'est potentiellement intéressant partout
  {

Vengeance !

if(etat_leucocyte(mon_identifiant()) == STATE_BEING_PHAGOCYTED)
{
  /* Hein ! Mais ... On nous attaque ! Jamais possible d'avoir la paix */

  update_menace(MENACE_ALLIE, MALUS_AGRESSION); // Et vlan !

Mon code

Pour ceux que ça intéresserait, vous pouvez télécharger l'ensemble de mon code. Je vous le déconseille instamment, toutefois. Il est buggé, illisible (voir plus haut), peu performant (je n'ai fini que 44ème, soit parmi les derniers de ceux qui avaient un programme qui marchait), et issu d'une gestion du temps tout à fait pathétique (mais je compte faire mieux cette année, si je suis pris à nouveau). Si vous le voulez quand même :

• prologin_2007.tar.gz (12,8 Ko), archive des sources.

Participez !

C'est là un conseil que je vous donne. Ça ne prend pas longtemps et ça en vaut la peine. L'an dernier, je l'ai fait un soir, comme ça, juste pour voir, et j'ai été retenu. (Mais bon, si vous ne participez pas, tant pis pour vous. Ça me fera plus de chances de me qualifier :-)).