À l’occasion des Google RISE Awards qui ont tout récemment récompensé l’association Prologin pour son engagement dans la promotion de l’algorithmique chez les jeunes, j’aimerais rappeler en quoi consiste ce concours.

L’association Prologin organise le concours national d’informatique, ouvert aux jeunes de 20 ans et moins. Celui-ci se déroule en trois parties :

• En octobre, un questionnaire de culture informatique et d’algorithmique.
• En février et mars, des épreuves régionales dans diverses villes de France et de Belgique.
• En mai, une finale de 36 heures non stop à l’EPITA à Paris, sur un projet d’IA.

Le concours est entièrement gratuit et les dix meilleurs reçoivent un prix (un ordinateur portable, une console, mais aussi parfois des lots plus exotiques comme une caméra GoPro ou un kit Arduino).

Le questionnaire de sélection

Pour exemple, le sujet de 2011 s’intéressait à un logiciel minimaliste (ProloGIMP) de traitement d’images représentées par des matrices de 0 et de 1.

Les questions allaient de la simple écriture d’une fonction pour inverser les bits d’une image jusqu’à des questions plus difficiles telles que : à partir d’une image initialisée à 0 et d’un pinceau de curseur en forme de + qui inverse les bits sur lesquels on l’applique, est-il possible de dessiner une certaine image ? Notez que ce problème est identique au jeu Lights Off (merci Alexis Comte !) où il faut éteindre toutes les lampes sachant que les interrupteurs sont interdépendants.

Si vous voulez essayer ces exercices, en vous inscrivant vous pourrez tester vos algorithmes sur le serveur d’entraînement.

Les épreuves régionales

L’épreuve régionale se déroule un samedi dans un centre d’examen. Le matin une épreuve écrite, l’après-midi une épreuve machine. Le déjeuner est offert par l’association.

Un sujet écrit d’algorithmique

Le samedi 17 mars 2012 vers neuf heures, la vidéo suivante a été diffusée dans un amphithéâtre à l’École polytechnique juste avant la distribution des sujets de l’épreuve écrite.

(Activez les sous-titres, cela nécessitera peut-être de passer par la version Flash, hélas.)

Et voici le sujet correspondant, qui contenait une grille semblable à celle dont il est question dans la vidéo avec l’ensemble des candidats à l’épreuve écrite en haut et « finaliste » ou « non finaliste » en bas. La première question du sujet était d’ailleurs :

Question 1. Alors ? Êtes-vous sélectionné en finale ?

Ces grilles, nommées amidakuji, sont très répandues au Japon : c’est effectivement un moyen très simple de créer une permutation aléatoire.

Aussi, savez-vous comment on dit « une machine à deux anneaux » en anglais ?

Un sujet machine de programmation

Voici un exemple d’exercice que j’aime beaucoup : Épiphanie.

C’est l’épiphanie, Joseph Marchand doit se couper une part de gâteau des rois. En fait, la brioche ne l’a jamais intéressé ; non, ce qu’il aime, ce sont les fruits confits. Tradition familiale oblige, il va se servir une part de gâteau. Déterminer les endroits où couper de sorte à ce que Joseph obtienne la plus petite part contenant au moins une fois chaque fruit confit.

On pourrait certes tester toutes les parts, mais cette approche pour 1 000 fruits confits réaliserait 1 000 000 opérations, ce qui dépasserait la limite de temps. Il existe en réalité une approche qui n’explore que 2 000 parts.

La finale

La dernière épreuve rassemble les 100 meilleurs candidats à l’EPITA pendant trente-six heures au cours desquelles la restauration et l’hébergement sont entièrement pris en charge par l’association. En 2006, les candidats pouvaient découvrir les premières lignes du sujet (de 24 pages !) :

Bonjour à toi, vainqueur de l’édition 2006 de Prologin ! Ce fut une belle finale, et ce marathon de programmation aura été serré. Mais fort heureusement, tu t’en es bien sorti. Reste à savoir qui tu es, puisque autour de toi les autres candidats lisent précisément le même texte. Car c’est toi — ou plutôt moi — qui as écrit ce sujet, à la différence que moi, j’ai participé à la finale, et toi pas encore.

Ce métasujet, inspiré de Retour vers le futur décrivait les règles du jeu et les différentes fonctions utilisables par les programmes des candidats. Le but : contrôler des joueurs sur une carte pour récupérer le fameux almanach et la DeLorean afin de parier dans des casinos dans le passé pour gagner le plus d’argent possible. Comme chaque année, chaque candidat devait programmer une intelligence artificielle nommée champion qui jouait au jeu et des tournois étaient organisés entre les différents champions pour déterminer un classement.

Après la présentation du sujet, en sortant dans la cour pour accéder à la salle machine, on pouvait découvrir une véritable DeLorean.

Car en plus de concevoir les règles du sujet et d’établir l’infrastructure de la finale, les orgas travaillent la déco. Et à l’issue des trente-six heures, d’une courte nuit et des oraux pour les dix premiers du classement devant un jury, à l’ouverture de la remise des prix, une vidéo est projetée retraçant l’événement. L’équipe EPTV avait donc travaillé d’arrache-pied la dernière nuit pour nous offrir le spectacle suivant :

Et pour la vidéo de la finale 2013, c’est ici. Bon code à tous !

Le musée de Grenoble a fêté ses 20 ans ce week-end, avec actuellement Sigmar Polke à l’honneur. L’une de ses œuvres s’intitule « Carrés magiques I-VII (Saturne, Jupiter, Mars, Soleil, Vénus, Mercure, Lune) », et se compose de figures obtenues en reliant les nombres d’un carré magique d’ordre N dans l’ordre croissant, et ce pour N variant de 3 à 9 :

On peut alors s’intéresser à la génération de carrés magiques d’ordre N. Apparemment, il existe une méthode simple pour le cas N impair, si simple qu’il en existe une implémentation en une ligne de Python :

n=5
print [[(i+j-1+n/2)%n*n+(i+2*j-2)%n+1 for j in range(n)] for i in range(n)]

La page Wikipédia associée présente diverses méthodes plus ou moins compliquées pour le cas N pair, notamment une solution pour N multiple de 4 et une autre solution pour le cas général.

Mais heureusement, l’implémentation des carrés magiques dans le logiciel de calcul numérique Octave est succincte.

Study the magic.m (Figure 2) code and appreciate the wisdom inside this succinct script.

Il existe également une version Python de cette implémentation que l’on peut utiliser pour refaire les dessins de Polke en TikZ. Le code est sur Bitbucket.

À noter qu’il existe aussi un package en R, qui permet de générer des hypercubes magiques de dimension quelconque.

Update 24/09/2020 : Yasutaka Tsutsui a été récemment adapté en l’anime Millionaire Detective et moins récemment le pastiche Nihon Igai Zenbu Chinbotsu (“Everything other than Japan sinks”).

Aujourd’hui, si vous parlez de La Traversée du temps (時をかける少女) à un Japonais, il est fort probable qu’il connaisse cette œuvre. L’histoire a été déclinée en une dizaine de films et drama, et des remakes sont régulièrement réalisés. Mais la nouvelle originale date de 1967, et le texte (disponible en français) n’a pas pris une ride.

Vous avez peut-être entendu parler du (apparemment critiqué) film Superstar (2012) avec Kad Merad, où un homme découvre à son insu qu’il est une célébrité. Oui, mais avant ça, il y avait Omni-Visibilis (2010), une BD de Lewis Trondheim (dessinée par Matthieu Bonhomme) sur un homme dont tout le monde peut lire dans les pensées. Oui, mais avant ça, il existait le manga Transparent (2001) sur des êtres dont les pensées se diffusent dans l’atmosphère. Mais avant ça, il existait Rumors about me (おれに関する噂), une nouvelle de Yasutaka Tsutsui publiée en 1974 où des événements anodins du quotidien d’un citoyen ordinaire deviennent le sujet d’un reportage à l’échelle nationale. Cette nouvelle fait partie de ce que Takayuki Tatsumi appelle la première vague de Tsutsui (années 60-70), où il s’est attaché à détruire les pseudo-événements (notion de Daniel Boorstin, 1962) : des faits « planifiés, semés ou incités dans l’optique immédiate d’être signalés ou reproduits » (avec Twitter, on est en plein dedans), dont « la relation à la réalité sous-jacente est ambiguë » et dont « l’intérêt repose essentiellement sur cette ambiguïté ». Boorstin avait remarqué que la société américaine était de plus en plus dominée par de tels pseudo-événements.

Puis, Tsutsui s’est intéressé à la métafiction. L’une de ses rares œuvres disponibles en français, Les Cours particuliers du professeur Tadano (1990), relate les péripéties d’un professeur de critique littéraire tout en constituant une satire du système universitaire japonais. Chaque chapitre du livre se termine par un cours particulier du professeur Tadano, dont celui sur le structuralisme mentionne Les Cours particuliers du professeur Tadano comme ouvrage de métafiction :

Il faut aussi mentionner la voix. elle concerne le moment du récit : est-il raconté en même temps que progresse l’histoire, juste après que celle-ci s’est achevée, assez longtemps après. Enfin, vous avez les questions de niveau, assez délicates : celui qui raconte se situe-t-il au-dessus du récit où à l’intérieur de celui-ci, ou bien encore, s’agit-il d’un récit qui raconte un récit, c’est-à-dire que l’on aurait affaire à un métarécit ? Tenez, prenons un exemple : c’est Yasutaka Tsutsui qui écrit le roman Les Cours particuliers du professeur Tadano. Il suffit que je cite son nom pour que, aussitôt, il fasse partie de ce roman, et on passe alors à du métarécit. Il est à un niveau supérieur au nôtre, mais en tant que narrateur, il est descendu d’un niveau. Il s’agit là de métalepse, quand l’auteur fait soudain irruption dans son œuvre.

Dans les années 90, Tsutsui s’est mis à explorer les possibilités du support électronique et les relations complexes entre fiction littéraire, simulation par ordinateur et le monde réel hypermédiatisé (c’est à cette occasion qu’il a écrit Paprika (パプリカ) en 1993, dont je persiste à croire que ne pas en avoir vu l’adaptation en film est une faute grave). Une autre œuvre représentative de cette période, moins connue, a vu le jour en 1992 : dans le magazine Asahi Shimbun, pour présenter aux lecteurs son premier roman-feuilleton Gaspard of the Morning, Tsutsui a posé la question : « Que puis-je faire justement avec une limite quotidienne de 3 pages ? » La réponse étant d’être capable d’incorporer les retours de ses lecteurs (courrier au magazine et forum web) dans le feuilleton¹. « J’aimerais vous faire remarquer que cette note fait partie du roman. En d’autres termes, la fiction Gaspard of the Morning a déjà commencé. »

Quelques jours après cette introduction, le récit commence avec un escadron de soldats japonais mené par un certain Commandant Fukae situé sur une planète déserte, incertain quant aux raisons liées à son envoi en mission et appréhendant des attaques d’aliens. Tsutsui précise :

Tous leurs visages, y compris celui de Fukae, avaient un air de ressemblance. Ils avaient certes chacun un visage exprimant clairement leur personnalité, donc d’un certain côté leurs faciès n’étaient pas les mêmes. Mais les contours de leurs visages faisaient penser à des personnages de films d’action… Parfois Fukae se disait que cela devait être l’influence génétique des générations de Japonais fans d’anime.

À compter du troisième chapitre, on découvre que Fukae et sa troupe étaient en réalité les personnages d’un jeu vidéo intitulé L’Escadron fantôme, joué par un nouveau protagoniste : un homme d’affaires appelé Kinohara Seizō (on comprend alors que l’« influence génétique » était plus littérale qu’il n’y paraissait), dont la femme Satoko s’endette via un jeu de bourse à travers un « service en ligne de portfolio financier ». Mais Seizō est trop absorbé par son jeu pour remarquer la crise imminente. Pour rendre la narration encore plus cocasse, le récit est ponctué par l’intrusion de l’« auteur » Kunugizawa, ainsi que l’« éditeur » Origuchi, qui font des métacommentaires sur le récit et les réactions sur le forum. Alors que Tsutsui lui-même est un membre actif sur le forum, Kunugizama se réfère aux lecteurs comme « the Internet science-fiction idiots » (インターネットのＳＦバカ, intaanetto no SF baka). L’expérience a battu son plein lorsque Tsutsui a réussi à mettre en lumière le conflit d’intérêt entre auteur et lecteur (des lecteurs se plaignaient du trop grand nombre de personnages secondes, Tsutsui-Kunugizawa les a tous faits exploser d’un coup, à la manière d’un dictateur parano), et en attirant l’attention sur les dangers liés au pouvoir de contrôler la parole dans les environnements médiatiques émergents. Au final, Gaspard of the Morning, que Tsutsui aimait appeler « un roman critiquant les romans » (en fait, une fiction interactive critiquant les fictions interactives), a obtenu le Japanese Science Fiction Grand Prize en 1992.

Je vais brièvement² finir sur une note que je développerai sans doute plus tard : le succès de Paprika alors considéré comme une œuvre maîtresse va être progressivement voilé par un événement concernant une œuvre de Tsutsui publiée en 1965 : Robot Police (無人警察). L’histoire : dans une société futuriste, l’ordre est maintenu par des robots policiers, ayant une telle faculté d’analyse des données qu’ils peuvent par exemple repérer des épileptiques au volant et leur confisquer leur permis de conduire³. Les choses ont commencé à se gâter lorsque Robot Police a été sélectionné pour faire partie des manuels scolaires au lycée. La Japanese Epilepsy Association (JEA) a alors adressé une lettre de protestation à l’éditeur, prétendant que cela ne ferait que propager de l’incompréhension et du préjudice envers les épileptiques. Tsutsui ayant lui-même la faculté de déceler du méta partout, il a perçu d’autant plus mal cet épisode que cela lui remémorait la société future décrite dans cette même œuvre, où même les pensées inconscientes sont criminalisées et où tous les suspects doivent se livrer d’eux-mêmes aux autorités. Même si au final, Robot Police est resté dans les manuels, Tsutsui, particulièrement déçu de la manière dont la presse avait relaté l’épisode, a décidé de ne plus rien imprimer, de « rompre la déclaration du pinceau » (dampitsu sengen). Il disait alors :

To keep not writing is for me the way to express myself literally.

Inutile de mentionner que sa notoriété n’en a que grossi ; en fait, un livre d’essais à propos de la controverse s’est même mieux vendu que Paprika et Tsutsui s’était amusé à dire qu’il risquait d’être traité de profiteur. 3 ans plus tard, il s’est remis à publier des travaux sur sa page Web, et a renoué avec l’impression en 1997.

Je tenais à vous faire part de cet auteur quasiment inconnu hors Japon⁴ aux travaux d’une clarté et d’une richesse rare ; je ne connaissais rien à la critique littéraire, mais Les Cours particuliers du professeur Tadano ne nécessite pas de prérequis ; on sent d’ailleurs que Tsutsui a apprécié les écrits de Roland Barthes qui me semble-t-il est aussi connu pour sa capacité à s’adresser à tous.

Joyeux anniversaire !

J’étais à Feurs, j’avais un train pour Saint-Étienne à 17 h 31 pour prendre à 18 h 13 un TGV pour Paris.

17 h 31. Je monte dans le train et m’assois.
17 h 40. Le contrôleur passe et me fait remarquer que je me suis trompé de train. (C’est pas de chance, il n’y a que deux voies à Feurs, et il y avait deux trains sur ces deux voies à la même heure.)
17 h 42. J’envoie un mail à Capitaine Train leur demandant s’ils peuvent annuler la deuxième partie de mon billet.
18 h 06. J’arrive à Roanne et fonce au guichet, en demandant à annuler mon billet. Le guichetier me dit : « Ah, il a déjà été annulé à 17 h 52.
— Wow.
— Ils sont efficaces. Je suis impressionné. »
Effectivement, à 17 h 55 j’avais reçu une réponse à mon mail de Capitaine Train, indiquant que mon billet avait été annulé et qu’il fallait que je retourne mon billet pour le remboursement.
Le guichetier m’a ensuite fait remarquer qu’il ne restait plus qu’une place en seconde classe pour Paris depuis Le Creusot (je dois être cocu, c’est pas possible) et au final, ma connerie ne m’aura coûté que 5 euros en tout.

Update 22 h 39. En fait, au Creusot, le TGV a eu une heure de retard. Donc ma connerie m’aura même fait gagner de l’argent !

Bref, j’ai l’impression de régulièrement tester le système Capitaine Train dans les moindres cas foireux et, presque toujours¹, ils s’en sont sortis à merveille.

L’avantage principal, c’est qu’il est possible d’inscrire des profils pour chacun des voyageurs (carte 12-25, etc.), ensuite il n’y a plus qu’à cocher les passagers d’un trajet pour réserver les billets ; plus besoin de retaper les codes de carte de fidélité de chacun. Pratique pour Prologin par exemple, où un sous-ensemble des membres de l’association se rend chaque semaine dans des villes différentes pour organiser les épreuves régionales.

Vous faites comment pour aller de Porte d’Italie (Prologin) à Paris-Gare de Lyon, vous ? Moi, je fais M7 → Place d’Italie, M6 → Bercy, M14 → Gare de Lyon.

Du coup, pour aller au MK2 Bibliothèque, je comptais faire M7 → Place d’Italie, M6 → Bercy, M14 → Bibliothèque François-Mitterrand. Mais c’était idiot.

La séance était à 21 h, le film sort le 9 octobre.

20 h 46. Le prochain M7 est dans 9 minutes. Je laisse tomber, de toute façon je n’ai pas de place.
20 h 48. Je décide d’y aller en courant.
20 h 53. Tolbiac.
21 h 04. Avenue de France.
21 h 05. MK2 Bibliothèque. 50 personnes font la queue, un festivalier dit qu’il reste 12 places.
21 h 06. Il y a deux jeunes derrière moi (par commodité, nous les appellerons Pif et Hercule), Pif essaie de gruger à une deuxième caisse, qui lui dit gentiment qu’il faut qu’il fasse la queue comme tout le monde.
21 h 11. En fait, il reste 53 places. WOW.
21 h 12. Je prends 2 places avec ma carte UGC Illimité pour 2. J’en offre une à Hercule.
21 h 13. Hercule ne me suit pas. Je lui fais signe, il me fait comprendre que Pif n’a pas eu de place.
21 h 14. Moi. — Qui veut une place pour La Vie d’Adèle ?
Un billetier. — La fille en blanc, là-bas !
Moi. — Hé, vous voulez une place pour La Vie d’Adèle ? (Je vois son copain.) mais je n’en ai qu’une.
The Girl in White. — Ah non mais on fait tout à deux !
21 h 15. Un gars intéressé se manifeste.
21 h 17. Le film a commencé, on est une vingtaine debout dans la salle éteinte.
21 h 19. Ah non, je suis assis en fait.
00 h 06. Le film s’achève, sans générique de fin (il fait 2 h 59) et le copyright final sort de l’écran.
00 h 07. Jill-Jênn (à ma voisine). — Ah oui, je me rappelle qu’ils étaient tellement à l’arrache qu’il n’y avait pas de générique de fin, mais quand même, ça fait bizarre !
Ma voisine. — Oui, j’avais lu ça aussi. J’ai bien aimé le côté éducation¹, ça m’a rappelé quand je voulais devenir institutrice, c’était exactement ça. Si vous avez aimé ce film, vous aimerez sûrement un autre film de Kechiche.
— La Graine et le Mulet ?
— Non, L’Esquive.
— Ah, ça tombe bien, j’adore Sara Forestier !
00 h 08. Je regarde vite fait dans la salle s’il y a des gens que je connais ; personne. Je me retourne.
00 h 08 et 1 seconde. On me tape dans le dos :
Léa. — Salut !
Jill-Jênn. — Ah ben, forcément !
— Ben ouais, forcément.
— *se rend compte de l’ambiguïté²* Non, je voulais dire, forcément, je vais te rencontrer ici³ !
— Ouais ouais, j’ai très bien compris.

… Ah euh, sinon, le film était cool.

Moralité : si un dimanche soir tu n’as pas de place pour une avant-première de Palme d’Or à 2,6 km de là 14 minutes plus tard, essaie quand même, si jamais ça marche, tu pourras le tweeter et peut-être même que @Linka_fk t’ajoutera à ses favoris.