Un escargot à Manhattan

China Post : échecs cuisants répétés

J’ai voulu envoyer un colis en Chine1, le lot du Mangaki Data Challenge. Pour compliquer la chose, il fallait que j’envoie : un livre, un CD et une lettre.

On m’avait conseillé de l’envoyer depuis la Chine plutôt que depuis le Japon, pour que ce soit moins cher.

Préambule

À un certain moment du voyage, je demande à George : « Tiens mais c’est marrant, d’un côté tu as Jinmen 金门 (portail d’or),
et de l’autre Xiamen 厦门. Mais du coup ça veut dire quoi le Xia de Xiamen ?
— Ça ne veut rien dire, c’est un nom propre.
— Mais pourtant ça ressemble à 夏 (été) ?
— Oui mais le caractère est complètement différent.
— Bah y a juste 厂 en plus quoi.
— Oui mais c’est complètement différent. 厦 ça veut dire building. Mais c’est un nom propre.
— D’accord. »

Essai 1, à l’hôtel

L’adresse en poche, je demande à mon hôtel de l’envoyer.

L’hôtellière parvient avec peine (et Baidu) à déchiffrer l’adresse écrite en caractères latins. Puis elle me demande : « Au fait, vous avez le numéro du destinataire ?
— Euh non.
— Ah ben c’est pas possible alors. »

Échec. Je demande au gagnant son numéro de téléphone.

(Elle a jeté un œil au colis et a dit : “あ、日本語が喋れる!” (« Ah, vous parlez japonais ! ») bref, elle aurait préféré communiquer en japonais plutôt qu’en anglais.)

Essai 2, près de l’aéroport

« Un CD ? Non, vous n’allez jamais pouvoir envoyer ça.
— Pourquoi ?
— Est-ce que c’est un original ?
— Oui.
— Si ce n’est pas un original, il sera effacé. D’accord ?
— Euh ben OK. »

(Je ne sais pas comment ils font pour savoir si c’est un original ou pas.)

« Envoi en express ou normal ?
— Normal.
— Si normal, vous ne pourrez pas envoyer la lettre dans le colis, il faudra l’envoyer séparément.
— Ah ben va pour Express alors. »

Elle me remet un formulaire EMS entièrement en chinois. George m’aide à savoir quoi remplir où. Après le lui avoir rendu, elle me dit :
« Non. Il faut tout remplir avec des caractères chinois. »

Échec. Je n’ai pas son adresse en chinois. Tant pis, j’enverrai depuis le Japon.

BONUS GRATUIT : Essai 3, à l’aéroport

Une fois le bagage déposé, j’ai quand même envie de retenter. Je cherche une poste dans l’aéroport. En parallèle je cherche sur Baidu une adresse approchante. Une fois trouvée (!), je ne sais pas quelle est la sous-chaîne2 de l’adresse qui m’intéresse, et qu’est-ce que je dois jeter.

Il y a effectivement un espace « Inquiry », avec deux femmes ne parlant pas anglais. Je leur montre le formulaire EMS. Elles appellent une amie. L’une d’elles m’apporte du thé. Ah non, c’est pour elle. (Foutu résident japonais trop habitué à être traité comme un roi.)

On patiente. Je lui montre la carte d’embarquement qui précise que j’embarque 30 minutes plus tard. Elle panique et dit à son amie nouvellement arrivée de se presser. Serious business incoming.

Challenge 1

Je lui montre le morceau d’adresse que j’ai trouvé sur Baidu, elle commence à la recopier… sauf qu’à un moment je l’interromps :
“之是大厦25” (« Là il faut écrire Building 25 »)

Merci George. Tu m’as sauvé. (Voir plus haut.)

Là elle répond par (j’imagine) : « Attends pourquoi tu m’embêtes je recopie ton adresse alors que tu parles même pas chinois. »
Mais elle écrit “大厦25.”

Challenge 2

Je n’ai pas le nom du destinataire en caractères chinois.

Elle râle un peu, mais avec sa copine elles se convainquent que le numéro de téléphone suffira.

Challenge 3

Elle me demande mon adresse.

Je commence à écrire mon adresse au Japon en kanji.
“No! No! No! China to China!”
Argh. Si près du but.

Je fouille dans mon sac, je trouve miraculeusement le calepin de l’hôtel, avec son adresse !

“20 yuans.” Je paye et file prendre mon avion. “谢谢🙏” (« Merci ! »)

Moralité

  • Posez-vous plein de questions sur les caractères à la con.
  • Gardez les morceaux de papier des hôtels. Ça peut sauver des vies.

Et… 20 yuans (2,50 €) pour un envoi en Express d’un livre, un CD et une lettre ??!!
WOW, ça vaut le coup !


  1. Oui je sais, quelle idée, aussi.

  2. Ou devrais-je dire, le facteur !! krkr

Sci-Fi Reference Graph

Sometimes artists acknowledge that their works are influenced by other artists.
(Sometimes they don’t.)

Anyway, here is a list of acknowledged references I came up with:

Sci-Fi Reference Graph

It’s interesting to see that American directors make remakes of Japanese works, inspired by French artists.

Transcription de partitions de musique d’anime

Il y a 3 ans jour pour jour, le Trio ELM faisait son premier concert, à l’ENS Cachan, à l’occasion des rencontres culturelles interENS :

En voici la playlist complète ainsi que le programme :

À l’époque, on avait une certaine culture du teasing, donc on avait décidé de révéler les musiques du concert petit à petit, et on avait même proposé aux gens de suggérer des musiques via un input.
(Forcément, on s’est retrouvé avec les trolls classiques : l’opening de Naruto en allemand, les Chœurs de l’Armée rouge, 4’33” de John Cage, etc.)

Et en fait, on transcrivait nos partitions nous-mêmes ! On les a interprétées à Japan Expo en 2015, Japan Expo Sud en 2016, et plusieurs années à Epitanime et d’autres conventions.

C’est l’occasion pour moi de revenir sur 12 ans de transcription de partitions de musique d’anime.

Quel langage choisir pour mettre en page de la musique ?

Prenons une musique de piano.

Ces notes au piano constituaient la musique de fond de la page Web de .hack//G.U., un jeu qui était très attendu en 2005. Il fallait transcrire cette musique.

MusiXTeX, un langage pour écrire des partitions en TeX

Je l’ai transcrite en MusiXTeX en 2005, mais le code donnait ça. (Ma première partition par ordinateur.)

...
\maketitle
\startpiece
\Notes\ibu0c0\qb0{Mcf}\ds\qp|\qp\sk\ds\qb0{gh}\tbl0\qb0j\en
\bar
\Notes\ibl0M0\qb0K\tbl0\qb0a\ql e\sk\ql d|\ibu0l0\qb0{ljhfe}\tbu0\qb0d\en
\bar
\Notes\ibl0H0\qb0{FJ}\tbl0\qb0M\ds\qp|\qu c\sk\ds\ibu0c0\qb0{Na}\tbu0\qb0c\en
\bar
\Notes\ibl0F0\qb0D\tbl0\qb0H\ql M\sk\qp|\ibu0j0\qb0{ecghi}\tbu0\qb0j\en
\bar
\Notes\ibl0E0\qb0{CG=KLb}\tbl0\qb0c|\ibu0m0\qb0m\tbu0\qb0l\zq {=k}\qu p\sk\qu n\en
...

Assez indigeste. C’est parce qu’on peut régler tout, jusqu’à l’angle d’inclinaison des ligatures.

PMX, un langage plus simple qui produit du MusiXTeX

Plus tard, j’ai découvert qu’il existait des méthodes plus simples !! (Sans déconner.)
Don Simons a codé un préprocesseur pour le MusiXTeX. Le langage s’appelle PMX et est plus lisible :

1 1 3 4 3 4 0 -4
0 5 16 0.085
Piano
t
./
It60ipi
Tt
.hack//G.U. - Desktop
Tc
Chikayo Fukuda\\Transcribed by Jill-J\^enn Vie
f83 c+ f g af c | ef c a f e d | c2 r4 /

Les premières lignes constituent le préambule, pour indiquer l’armure, la mesure, les instruments, et le tempo du fichier MIDI. Le cœur de la partition est la dernière ligne :

f83 c+ f g af c | ef c a f e d | c2 r4 /

Ce qui donne :
fa do fa sol la do | mi do la fa mi ré | do

(Bon j’ai mis des bémols alors qu’ils sont déjà à l’armure mais comme ça vous voyez comment ça marche.)

  • Par défaut la note suivante est la plus proche, si on souhaite changer d’octave on a + ou -.
  • 8 (8th) indique qu’il s’agit de croches (4 : noires, 2 : blanches, etc.).
  • f (flat) indique un bémol, s (sharp) un dièse.
  • r (rest) est un soupir.

Ce qui est appréciable, c’est que PMX peut créer un fichier MIDI en plus de la partition (.tex), ce qui aide au debug. Sur mon site vous avez une centaine de partitions créées à partir de ce langage.
Je mettrai les sources en ligne, mais il y en a qui ont sombré avec mes anciens ordinateurs 😢.

Il existe aussi LilyPond, mais je trouve ce langage plus compliqué, même s’il faut reconnaître que la communauté est très vivante, et que cela permet un rendu plus net.

VexFlow

Depuis lors, un framework open source a été développé par un fou furieux en JavaScript, qui génère des commandes canvas ou du code SVG, avec lecture audio dans le navigateur, s’il vous plaît ! Ça s’appelle VexFlow et c’est sur GitHub.

vextab options player=true tempo=140 tabstave notation=true tablature=false time=3/4 notes :8 F/3 C-F-G-A@/4 C/5 | E@-C/5 A@-F-E@-D@/4 | notes :2 C/4 options space=15

Produit par le code VexTab suivant :

options player=true tempo=140
tabstave notation=true tablature=false time=3/4
notes :8 F/3 C-F-G-A@/4 C/5 | E@-C/5 A@-F-E@-D@/4 |
notes :2 C/4
options space=15

Les @ indiquent les bémols, les /4 /5 sont les octaves.

Quand je dis que ce sont des fous furieux, c’est qu’ils ont même des tests visuels de rendu et plein d’autres trucs décrits sur leur blog. Plus récemment, l’auteur a conçu un nouveau langage appelé EasyScore, plus lisible.

Trinket

D’autres personnes appréciant le côté feedback immédiat ont codé une surcouche propriétaire du framework open source VexFlow. Leur langage est extrêmement simple (mais du coup, limité) :

Ici des fa d’octaves croissants seront représentés par :

FFF FF F f f' f'' f'''

Tandis que - et + permettent de mettre des bémols et dièses.

Le mouvement OpenScore

Vous devez connaître IMSLP (International Music Score Library Project), c’est la plus grande base de données de partitions dans le domaine public. Ils se sont associés en janvier 2017 avec le logiciel open source MuseScore lors du dernier FOSDEM (Free and Open Source Software Developers’ European Meeting) pour former OpenScore, une initiative visant à ouvrir le code source des musiques pour faciliter les reprises, arrangements, mais aussi l’indexation et l’extraction de données pour la recherche. En savoir plus sur le site du FOSDEM ou de MuseScore.

La question est de savoir quel standard va gagner (MusicXML ? ou le format MSCZ de MuseScore ?).

Connaissez-vous d’autres initiatives prometteuses ? Vous pouvez en faire part dans les commentaires ci-dessous.

Quelques anecdotes à propos des partitions transcrites

Final Fantasy – Swing de Chocobo

Pour moi, le meilleur arrangement philharmonique du thème de Chocobo dans Final Fantasy, c’est Swing de Chocobo issu de Final Fantasy X.

Pour le concert des prépas du lycée Thiers en 2008, on souhaitait à tout prix en faire une interprétation à six instruments + piano. MAIS impossible de mettre la main sur un trompettiste.

Je ne sais plus comment j’ai su que le documentaliste du CDI savait faire de la trompette. Du coup on est allés le voir :

— BONJOUR, paraît que vous savez faire de la TROMPETTE ?
— Hein ? Oui mais je…
— S’IL VOUS PLAÎT c’est important.

Du coup c’était parfait de faire du PMX, parce que j’ai pu pondre toutes les versions pour tout le monde à coups de copier-coller :

Vous pouvez écouter notre interprétation ci-dessous (ça commence à 1:33) et voir toutes les partitions là. C’était une super expérience.

Cosmo Warrior Zero – The Book of Life

Connaissez-vous le merveilleux ending The Book of Life de la série Cosmo Warrior Zero ? Non. Très bien.

Un jour, pour une raison que j’ignore, je suis tombé sur une interprétation live de ce morceau par un quatuor de 3 chanteuses mexicaines et 1 piano : el Cuarteto Nausicaä. Ça se déroulait à l’équivalent mexicain de Japan Expo.

Comme je me souvenais que le refrain était difficile à transcrire au piano dans la musique originale, je me suis demandé : « Tiens, comment elles ont fait, elles ? » puis, au moment du refrain : « Attends… elles ont fait comme moi… SE POURRAIT-CE QUE ? » J’ai écrit à la pianiste, et elle m’a dit : « Yes, you’re right, it’s yours! » Wow.

Ghost in the Shell – I Do

Cette petite pépite nous vient de la compositrice de génie Yoko Kanno, qui compose 50 % du programme du Trio ELM (dont ELM de la série géniale Cowboy Bebop), dont le trio tire son nom).

À l’été 2016, avec Ryan Lahfa, on a remporté un voyage au Japon pour notre projet de système de recommandation Mangaki. À l’aéroport, comme il y a des pianos, on en a profité pour interpréter de la musique d’anime. Alors que Ryan était en train de jouer Sadness and Sorrow de Naruto, un Russe nous a interpellé : « Hey guys, could you please play this? » et il nous montre ceci :

 Mec. C’est moi qui l’ai transcrite ta partition.

TIPE de composition musicale

Avoir tout ce corpus de partitions PMX, c’était pratique quand j’ai voulu faire mon TIPE de génération procédurale de musique par chaînes de Markov. Le programme prenait en entrée des partitions au format PMX et générait une partition PMX inédite, mesure par mesure.

Quand j’ai voulu faire écouter ce que l’algorithme faisait au jury des ENS, ils m’ont dit :

— On aimerait bien écouter mais pour ça il faudrait que votre portable reste dans la salle après l’oral.
— Ah ben non alors.

Notez que la musique de fond de La Faute à l’algo est également composée par une chaîne de Markov sur du code PMX, c’était d’ailleurs le sujet de l’épisode 1 : génération procédurale ! Le code de markov.py est sur GitHub.

Voilà, et pour revenir à l’anniversaire de Trio ELM, sa vidéo la plus vue est : Sis Puella Magica, de Puella Magi Madoka Magica. Et si vous voulez écouter d’autres vidéos, c’est sur le site de trioelm.com ! Joyeux anniversaire, Sedeto et Lily !

La Saga Haruhi Suzumiya

Aujourd’hui, 8 octobre, c’est l’anniversaire de Haruhi Suzumiya, un personnage de manga à l’origine d’une des plus grandes franchises de ces dix dernières années.

Si vous n’avez jamais regardé, je vous conseille vivement de le faire. Mais je vais vous raconter comment j’ai été entraîné par ce soft power japonais (pas si soft, en fait).

2008

C’était il y a 8 ans. En juillet 2008.

À Japan Expo, je croise une fille déguisée en un personnage de manga dont je ne me rappelais plus le nom (Haruhi Suzumiya).

— Il est super ton cosplay ! Je peux te prendre en photo ?
— Ah oui ! Attends un peu… (Elle s’en va.)

Elle va chercher sa copine, et là, elles prennent cette pose :

J’étais légèrement surpris et intrigué, du coup en rentrant je me suis dépêché de mettre les yeux sur les épisodes de La Mélancolie de Haruhi Suzumiya.

Après avoir vu l’épisode 1, je n’ai pas compris. Ça semblait être un film dans le film, avec un humour absurde.

En fait, c’est parce que les épisodes de la série ne sont pas dans l’ordre chronologique. Le premier qu’on regarde est en fait le onzième et ainsi de suite, en tout :

XI I II VII III IX VIII X XIV IV XIII XII V VI.

La plus longue sous-suite croissante est I II III IV V VI, le fil principal de l’intrigue. Imaginez donc la surprise quand, après avoir vu l’épisode II, on tombe sur le VII, qu’on ne comprendra qu’après avoir vu le VI, qui arrive à la toute fin de la saison. Il est d’ailleurs amusant de revoir la série et de repérer tous les détails d’apparence anodins mais qui en fait sont des clins d’œil à la fin de la série. En ce qui me concerne, je suis fan du concept.

En outre, la série fait référence à de nombreux concepts développés dans plusieurs œuvres de science-fiction, ou bien des concepts philosophiques tels que :

C’est un peu de la science-fiction pour enfants, et l’intrigue est super bien ficelée. (Je continue à penser que le pitch est le meilleur pitch possible pour une histoire.) Ça s’inspire en partie de L’Oiseau bleu de Maeterlinck, qui est une autre illustration de la citation de Robert Louis Stevenson : « I travel not to go anywhere, but to go. I travel for travel’s sake. The great affair is to move. »

D’ailleurs, une citation de l’héroïne :

Il ne t’arrivera rien d’amusant si tu ne restes à rien faire.

C’était un truc tout bête, comme ça. Mais à l’époque ça m’a rendu fou. C’est sûrement en partie responsable de la quantité déraisonnable de projets divers que je me suis efforcé d’accomplir ces dernières années.

Fraîchement entré dans ma nouvelle école, j’ai tenté de contaminer un maximum de gens à regarder la série. Une méthode qui marchait bien :

— Non mais regarde JUSTE 3 épisodes ce soir !
— OK.
(Le lendemain.)
— Je te DÉTESTE j’ai dû FINIR LA SÉRIE je me suis couché à MINUIT [etc.]
— De rien.

J’ai rejoint le forum suzumiya.haruhi.fr, qui deviendra une association : la Brigade SOS Francophone1.

2009

Un jour, sur le forum de la Brigade, on apprend qu’une rediffusion est programmée, au Japon, dans l’ordre chronologique.

Certains prophètes du forum, qui ont lu les romans sur lesquels est basée la série, présagent qu’il y aura peut-être une saison 2 basée sur des morceaux d’autres romans, intercalée dans la rediffusion de la saison 1.

Je ne sais pas comment les prophètes ont fait, mais effectivement, le 22 avril 2009, au lieu de suivre le fil de la saison 1, un épisode inédit a été projeté. Et là, je ne vais pas faire un dessin parce que ça commence à devenir compliqué.

C’est ainsi que pendant la diffusion, à raison d’un épisode par semaine2, les prophètes se sont amusés à prédire de quel roman proviendrait l’épisode suivant3.

Dans mon école, on a créé un club anime, pour faire découvrir des séries animées japonaises, notamment celle-ci. À l’époque, l’école était suffisamment cool pour qu’on puisse demander :

— Je peux avoir l’amphi B s’il vous plaît ?
— C’est pour quoi faire ?
— Projeter des séries animées japonaises.
— OK.

(Ça marchait aussi pour les anniversaires.) On a donc placardé cette affiche partout :

Quelques réactions :

— Mais vous êtes débiles ! Les gens vont rien comprendre.
— C’est le but.

Et on a quand même rempli l’amphi.

2010

Aux conventions comme Japan Expo ou Epitanime, l’association vendait des goodies, notamment des fanzines parfois faits en LaTeX4 :

La Brigade SOS est ainsi parvenue à récolter quelques milliers d’euros, lui permettant d’inviter l’illustratrice originale de Haruhi Suzumiya Noizi Ito en France, à Epitanime 2010 ! Et ça les gars, c’est bien joué.

Photo par Rin-kun, sur Wikipédia.

2011

En faisant un peu de veille, j’ai découvert que le festival Scotland Loves Animation projetterait à Édimbourg en octobre le film en avant-première européenne : La Disparition de Haruhi Suzumiya.

Du coup, la Brigade y est allée ! À l’époque, il existait pour des saisons comme celle-ci des billets Ryanair à 7 € aller, 12 € retour (la folie). Du coup, on mangeait des pancakes, on allait voir un film, on revenait à l’auberge manger des pancakes, on retournait voir un film, etc. pendant une semaine.

Et le film était à la hauteur de nos espérances. Un bijou d’animation de 2 h 42 et 53 secondes que je vous conseille vivement, même si vous n’avez pas vu la saison 2 en entier (la saison 1 + l’épisode Bamboo Leaf Rhapsody suffisent). Voici un extrait5 :

2013

Résigné à ce que les tomes restants de la série ne soient jamais adaptés, je me suis attaqué à la lecture des romans en anglais. Si vous avez vu la série, je vous conseille vivement la lecture de « Snow Mountain Syndrome », le dernier chapitre du tome 5.

D’ailleurs je viens de voir qu’il existe des fans tellement désespérés qu’ils l’ont… animé eux-mêmes :D

2016

J’ai enfin fini les romans. Et oui, je suis suffisamment taré pour avoir enregistré ma progression de lecture sur un repo GitHub, pendant 3 ans6.

Au final, ceux qui font vraiment avancer l’intrigue sont les tomes 1, 4, 7 et 10.

Et voici un précieux conseil d’écriture de l’auteur dans les dernières pages, qui s’excuse d’avoir mis 4 ans entre le neuvième et le dixième tome :

Il semblerait qu’après être arrivé à saturation d’avoir ma capacité d’écrire poussée dans ses derniers retranchements, j’ai immédiatement eu l’idée pour La Disparition de Haruhi Suzumiya, et j’ai écrit les séries d’histoires alors même qu’elles me venaient à l’esprit. Ainsi, je me dis que ma pensée selon laquelle « Si tu crains de ne pas y arriver, écris juste tout » était plutôt bonne.

En somme, suivez cet algorithme

  • Regardez la saison 1 de La Mélancolie de Haruhi Suzumiya
  • Peut-être pas toute la saison 2, mais au moins « Bamboo Leaf Rhapsody »
  • Délectez-vous du film La Disparition de Haruhi Suzumiya
  • Lisez « Snow Mountain Syndrome », et les tomes congrus à 1 modulo 3.

Partition : Bouken Desho Desho?, opening de la saison 1.


  1. Hélas récemment dissoute ! Mais nos cœurs en ont été grandis.

  2. Que l’on pouvait suivre en direct en France car l’épisode passait à 25 h au Japon, soit 18 h en France.

  3. Bon, ceux qui ont vu la saison 2 savent que les prophètes – tout prophètes fussent-ils – ne pouvaient pas imaginer que la saison 2 se déroulerait comme elle s’est déroulée.

  4. Si, si.

  5. Ah oui, j’ai oublié de dire que la BO du film était principalement composée de gymnopédies d’Erik Satie.

  6. Notez la longue coupure, qui correspond aux dernières années de thèse.

Clément Beauseigneur, Meilleur Dev de France 2016

Ce lundi 14 mars s’est tenue la 4e édition du concours du Meilleur Dev de France, au Théâtre de Paris. Celle-ci a regroupé 600 développeurs. 10 000 € étaient à la clé, et les 25 premiers repartaient avec un voyage à Amsterdam offert par le parrain, Jean-Baptiste Descroix-Vernier.

Le concours est organisé conjointement par Ametix et la société Isograd, qui fournit la plateforme, sur laquelle j’ai rédigé les sujets algorithmiques1.

Pendant que les développeurs développaient, des stands présentaient leurs produits, BFM TV interviewait Henri Seydoux, Samantha Jerusalmy de Girls in Tech Paris ou bien Stéphane Boukris, l’organisateur du concours. Beaucoup de personnalités étaient présentes, telles qu’Axelle Lemaire, Guy Mamou-Mani ou même… Jean-Claude Van Damme ??!!

Mais revenons sur le déroulement de ce concours, du point de vue des coulisses du théâtre :)

Déroulement du concours

Deux sessions : 45 minutes

Les sessions comportaient 3 problèmes algorithmiques de difficulté croissante.

Les 20 meilleurs ont été sélectionnés à l’issue de chaque session. À noter que dans la 2e session, seule une personne a résolu le 3e exercice. Son commentaire : « Trop facile » Merci mec. Ça fait plaisir de lire ça depuis le back-office. Pendant ce temps, Clément Beauseigneur s’est qualifié in extremis, c’est le dernier des 20 développeurs appelés à rejoindre la finale :

J’ai mis 15 minutes pour me connecter, du coup j’ai eu 5 minutes pour faire les deux premiers exercices, puis je n’ai pas effectué le troisième.

Finale : 40 minutes

40 minutes pour résoudre deux problèmes difficiles, c’est pas facile… Le premier était difficile à développer, mais facile à reconnaître pour quelqu’un d’expérimenté. Or, les développeurs avaient accès à Internet, et pouvaient utiliser et adapter du code.

En tout cas, au bout de seulement 5 minutes, un développeur a déjà résolu le premier exercice. Zut, il ne reste donc plus que deux issues. Soit personne ne résoudra le 2e exercice, et on tient notre gagnant, soit quelqu’un le résoudra et sera sacré Meilleur Dev de France 2016.

L’ultime problème algorithmique

Le tout dernier problème était très difficile, voire impossible à résoudre étant donné le faible temps imparti. Ce problème, le voici :

On vous donne un réseau de 100000 ordinateurs tous reliés entre eux sans cycle et on vous demande de choisir à quel ordinateur donner Internet de façon qu’en cas de coupure d’un câble, un minimum d’ordinateurs perdent leur connexion Internet. Combien d’ordinateurs seront privés d’Internet au pire ?

Par exemple, ici donner Internet à l’ordinateur 3 garantit qu’au pire, c’est-à-dire en cas de coupure du câble entre 2 et 3, seulement 3 ordinateurs seront privés d’Internet.

Vous voyez ? Même si vous ne vous y connaissez pas en algorithmique, vous avez compris ce qui est demandé. La plupart de ces problèmes s’énoncent clairement, mais les algorithmes permettant de les résoudre sont parfois difficiles à voir, et demandent beaucoup de rigueur pour être implémentés sans bug.

Ça fait partie du bagage d’un développeur, qui se demande sans cesse comment accomplir une certaine tâche efficacement, comme mettre en relation un chauffeur et un client par exemple.

Dénouement

Au bout d’un moment, Marc dit : « Ça y est. Clément Beauseigneur l’a résolu. » Je crie de joie. Je préférais tellement cette issue au fait que quelqu’un remporte le concours en ayant codé en 5 minutes un exercice facile à reconnaître.

On nous laisse nous exprimer, j’en profite pour faire éhontément de la pub pour ce livre de Christoph Dürr et moi sorti tout récemment, qui recense 128 problèmes algorithmiques résolus :

Après un discours de Jean-Baptiste Descroix-Vernier en trois messages sur :

  1. je vous admire, vous développeurs ;
  2. derrière un système d’information, il y a un développeur, derrière un système de paiement, il y a un développeur, derrière une élection, il y a un développeur ;
  3. à présent que vous avez les moyens d’accomplir des choses immenses, choisissez bien ce que vous voulez en faire.

Puis, on a annoncé le gagnant : Clément Beauseigneur ! Il a 21 ans, est en deuxième année à l’ENS Cachan, donc n’est pas encore employé. Jean-Baptiste Descroix-Vernier le plaisante :

Ah non mais en cet instant précis, tu viens d’avoir un boulot !

Comme Twitter l’a remarqué, Clément n’en est pas à sa première victoire. Il aime la compétition, fait partie des organisateurs du concours Prologin et aimerait dénicher un stage de robotique via les contacts de son professeur, Jean-Paul Laumond.

En tout cas, laissons-le se délecter de cette gloire bien méritée ! Et si vous souhaitez en savoir plus sur cette passionnante discipline qu’est la résolution de problèmes algorithmiques, essayez tryalgo.org !


  1. Je donne un exemple plus bas, continuez de lire !