Le gantelet | Pense comme un codeur, Ep 8

Voir la leçon complète : https://ed.ted.com/lessons/the-gauntlet-think-like-a-coder-ep-8

Voici l'épisode 8 de notre série animée "Pense comme un codeur". Ce récit en 10 épisodes suit une fille, Ethic, et son compagnon robot, Hedge, alors qu'ils tentent de sauver le monde. Les deux se lancent dans une quête pour collecter trois artefacts et doivent résoudre une série d'énigmes de programmation.

Leçon d'Alex Rosenthal, réalisée par Kozmonot Animation Studio.

Leur chute de la tour
envoie Ethic et Hedge

tournoyer dans les rapides
d'une rivière d'énergie pure.

Ce torrent coule du
Bradbarrier jusqu'à Huxenborg.

Là-bas, toute une ville d'usines

construit les robots et
abriter le Noeud de Mémoire,

le dernier des trois puissants
artefacts qu'Ethic doit collecter.

Après une longue journée
et une nuit encore plus longue,

ils se retrouvent dans un
canyon de brique et d'acier.

Juste au moment où ils sont sur
le point d'atteindre la fin de la ligne,

une corde les attrape.

Leur sauveur, Lemma, les attendait.

Quand Ethic a réclamé le Nœud
de la Création de la tour de la forêt,

les radios du pays ont repris vie.

Adila, chef de la résistance,

a immédiatement commencé
à contacter ses alliés,

dont le plus important, Lemme,

une brillante scientifique travaillant
depuis Huxenborg

pour faire tomber les machines.

Malheureusement, les radios
ont également averti les robots.

Ils ont donc pris des mesures défensives

pour protéger l'artefact final dans
sa maison en plein cœur de la ville.

Il n'y a qu'une seule façon d'y arriver :
le gantelet des chemins qui bifurquent.

C’est une série mortelle de convoyeurs
lumineux qui serpentent sous Huxenborg.

À partir de la position actuelle,

chaque section court sur une
distance, puis se divise en deux.

Chaque branche fait
la même chose, encore et encore.

Il y a des milliers de branches.

Un seul chemin mène à l'artefact ;
tous les autres à la destruction.

Heureusement, le Nœud de Création a
accordé à Hedge un étrange pouvoir :

il peut produire des versions
légèrement plus petites de lui-même.

Chaque version
ne peut faire que deux choses :

renvoyer les informations radio
à son parent,

et produire des versions
légèrement plus petites de lui-même…

qui peuvent faire les deux mêmes
choses, tout comme leurs enfants,

pour autant de générations que nécessaire.

Une patrouille se rapproche
de sa position,

le temps d’Ethic est donc limité.

Quelles instructions doit-elle donner à
Hedge pour trouver le seul chemin sûr ?

Mettez la vidéo en pause
pour comprendre vous-même.

Indice dans 3,

2,

1.

Les programmeurs ont un outil élégant
dans leur arsenal appelé récursivité.

La récursion, c'est quand on a un ensemble
d'instructions qui se réfère à lui-même.

C’est comme utiliser
un mot dans sa propre définition,

sauf là où c'est mal perçu,
c'est incroyablement efficace.

La récursivité implique la répétition,
mais d'une manière différente des boucles.

Alors qu'une boucle effectue
une action et la répète encore et encore,

la récursion lancera une action, et avant
qu'elle ne soit terminée, la réutilise,

et avant que cela ne soit terminé,
la réutilise, etc.

Elle continue comme ça jusqu'à ce
qu'un certain état final soit atteint.

Elle transmet ensuite les
informations, couche après couche,

jusqu'à ce qu'elle atteigne
le sommet et termine le cycle.

La récursivité est idéale

pour les problèmes
qui impliquent l'auto-similitude,

où chaque partie ressemble
au plus grand ensemble.

Comme, par exemple,
un système de défense mortel

conçu pour mettre fin
à toute personne ou chose

qui ose marcher dessus.

Mettez la vidéo en pause
pour comprendre.

Solution en 3,

2,

1.

L’énigme d’Ethic semble
s’étendre à la surface,

mais il existe une solution très
simple en utilisant la récursivité.

Pour la trouver, regardons d'abord
la version la plus simple de ce puzzle :

Et si tout le labyrinthe
n'était que deux chemins ?

Si Hedge se copie lui-même, la copie
qui va dans le mauvais sens sera détruite.

Donc, l'autre, qui atteindra l'artefact,

peut retransmettre par radio
le chemin qu'il a pris,

et peu importe le chemin qui est correct,

c'est la réponse que Hedge recevra.

C'est ce qu'on appelle
le « cas de base » de la récursivité.

A présent, supposons que le labyrinthe

a deux embranchements
depuis le point de départ,

et à chaque intersection,
les copies de Hedge...

appelons-les Twig 1 et Twig 2—

font plus de copies -
appelons-les Leaves 1 à 4.

Trois Leaves seront détruites.

Celui qui atteint l'artefact
transmettra par radio la bonne réponse,

mais seulement à son parent.

Donc, si Twig 1 ou 2
attend à une intersection

et entend quelque chose à la radio,

c'est la bonne façon d'aller
à l'artefact d'où il se trouve.

Pour dire à Hedge la bonne
réponse de son point de vue,

la Twig devrait dire
par où elle est passée,

puis l'itinéraire qu'elle
vient d'entendre à la radio.

Ce même processus fonctionnera

quel que soit le nombre
d'embranchements du labyrinthe.

Toute réponse qu'une copie
entend à la radio

doit être le chemin de la salle
de contrôle depuis son emplacement,

et si elle ajoute ensuite
la branche qu'elle a prise,

elle peut également indiquer à
son parent comment s'y rendre.

Nous pouvons résumer les instructions
dans une action appelée Pathfinder

que chaque version de Hedge suivra :

1. Si vous avez atteint l'artefact,
faites un appel radio à votre parent,

que vous soyez arrivé
en allant à gauche ou à droite.

2. Lorsque vous atteignez
une intersection, sortez du convoyeur

et envoyer de nouvelles copies
sur les chemins gauche et droit.

Demandez-leur d'exécuter Pathfinder.

C'est là qu'intervient la récursivité,

et elle peut se produire plusieurs fois

avant le déclenchement
de la dernière instruction, qui est :

3. Si vous entendez quoi que ce soit
à la radio,

vous devez faire un appel radio
à votre parent

que vous arriviez à votre place
en allant à gauche ou à droite,

puis répétez tout
ce que vous venez d'entendre.

Pathfinder est un exemple de ce que
les programmeurs appellent des fonctions,

sous-programmes ou procédures.

Quelle que soit la terminologie,
l'idée est la même...

c'est un ensemble d'instructions
avec une étiquette

pour pouvoir être facilement réutilisé...
peut-être même par lui-même.

Et dans notre cas,
cela fonctionnera parfaitement...

un réseau entier de chemins mappés
en utilisant seulement trois instructions.

Voici donc ce qui se passe.

Au moment où la patrouille arrive,

Ethic et Lemme
ont improvisé des déguisements.

Elles essaient de confondre les robots

assez longtemps
pour donner du temps à Hedge.

Enfin, la radio de Hedge prend
vie avec une série d'instructions.

Les trois plongent sur le convoyeur
et fuient pour sauver leur vie,

avec un escadron de robots
exécuteurs en poursuite.