La Tour d'Épiphanie | Pensez comme un programmeur, Ep 7

Leçon complète : https://ed.ted.com/lessons/the-tower-of-epiphany-think-like-a-coder-ep-7

Ceci est le 7e épisode de notre série animée : « Pensez comme un programmeur ». Cette série de 10 épisodes relate les aventures d'Éthique et de son ami robot, Hedge, alors qu'ils tentent de sauver le monde. Ils s'embarquent à la recherche de trois artéfacts et doivent trouver la réponses à une série de problèmes de programmation.

Leçon : Alex Rosenthal, scénarisation : Kozmonot Animation Studio.

Éthique et Hedge sont au pied
d'une tour massive.

Une barrière d'énergie les sépare
de leur deuxième objectif :

le Nœud de Création.

Pour l'atteindre, Éthique doit utiliser
trois flux d'énergie et escalader la tour.

Dès qu'elle avancera d'un pas,
une minuterie décomptera 60 secondes.

Au fond de la salle,
il y a un bassin de tours invisibles

qui peuvent conserver l'énergie ensemble.

Au bout d'une minute, un flot d'énergie
va s'écouler comme un torrent,

remplissant une unité à la fois,

avec un champ de force qui l'empêche
de déborder par l'avant ou l'arrière.

Pendant ces 60 secondes de répit,

Éthique et Hedge doivent décider combien
d'unités d'énergie précisément vont périr.

Pour ces trois défis,

ils doivent choisir le volume précis
qui remplira chaque réservoir.

Une bonne réponse les propulsera en avant.

Mais s'ils se trompent,
l'ascenseur énergétique va s'arrêter

et les laissera tomber.

Au mur, des diagrammes illustrent
des exemples.

Cette configuration captera
deux unités d'énergie précisément.

Celle-ci captera 4 unités,
celle-ci, trois et ici, une.

Celle-ci aussi captera quatre unités

car l'énergie disponible à droite
sera perdue.

L'énergie percera de façon

à ce qu'elle déborde uniquement
si aucun espace ne peut la contenir.

Hedge peut rendre visible une tour
de blocs à la fois et calculer sa hauteur.

Mais il ne peut pas voir la structure
entière d'un seul regard.

Comment Éthique devra-t-elle
programmer Hedge pour estimer

exactement combien d'énergie
chaque réservoir peut contenir ?

Faites une pause maintenant
pour trouver la solution.

Voici une manière de penser
à ce qu'il se passe :

Chaque cellule vide contiendra
de l'énergie

si et seulement s'il y a une paroi
peut-être à sa gauche

et une paroi peut-être à sa droite.

Mais vérifier chaque cellule
nécessite trop de temps.

Et si nous envisagions
une colonne entière à la fois ?

Combien d'unités d'énergie ce motif
pourrait-il contenir, par exemple ?

Faites une pause maintenant
pour trouver la solution.

Analysons le problème
en étudiant cet exemple.

Il y a cinq colonnes de blocs ici.

Celle de gauche ne peut pas contenir
d'énergie car il n'y a rien au-dessus.

La deuxième peut contenir trois unités

car elles seront entourées
par ces rangées de quatre piles.

On a donc 3 unités en prenant la hauteur
où l'énergie va se stabiliser - 4,

et on soustrait la hauteur des piles -
cela fait 4 moins 1.

La troisième pile est similaire :
4 à gauche, 4 à droite et 3 en hauteur.

Elle contient donc
4 moins 3 égale 1 unité.

Les quatrième et cinquième piles
n'ont rien de plus haut qu'elle à droite.

Elles ne peuvent donc pas
contenir d'énergie.

On peut adapter cela dans un algorithme.

En envisageant une colonne à la fois
comme point de référence,

Hedge peut regarder
à gauche de chaque pile

pour déterminer la hauteur
de la plus haute

et faire de même sur la droite.

Il peut alors prendre
la plus basse des deux

comme hauteur d'énergie
qui peut être contenue.

Si le résultat est plus haut
que la colonne concernée,

il soustrait la hauteur
de la colonne originale

et le résultat sera le nombre d'unités
que la colonne peut contenir.

Si c'est égal ou sous le niveau
de la colonne concernée,

l'énergie se répandra.

Hedge peut appliquer ça
au réservoir entier avec une boucle

qui commence à la colonne de gauche
et se dirige vers la droite,

une colonne après l'autre.

Pour chaque colonne, il vérifie quelle est
la colonne la plus élevée à gauche,

il fait pareil sur la droite,
choisit la plus basse des deux,

soustrait la hauteur
de la colonne de départ

et ajoute le résultat au grand total.

Il répète ces étapes en boucle
autant de fois qu'il y a de colonnes.

Cela fonctionnera mais cela prendra
du temps si le réservoir est grand.

À chaque étape, Hedge répète cette action
de regarder à gauche et à droite.

S'il y a N piles, il regardera N fois
toutes les piles.

Y a-t-il un moyen d'aller plus vite ?

Un gain de temps unique existe :
avant de faire autre chose,

Hedge peut commencer à gauche

et vérifier quel est la plus grande pile.

Ici, ce serait 2, 2 encore,
comme la première est plus haute,

ensuite 4, 4, 4.

Il peut ensuite trouver les piles
les plus hautes à droite

en appliquant la mienne action
de droite à gauche : 1, 3, 4, 4, 4.

Il aura ce tableau-ci en mémoire.

Hedge peut prendre un autre raccourci
pour calculer l'énergie qu'il y aura

au-dessus de chaque pile
avec la même équation qu'avant :

prendre la plus petite valeur contenue
à gauche et à droite,

et soustraire la hauteur
de la tour actuelle.

Au lieu de regarder N fois N piles,
il évaluera N piles trois fois seulement.

C'est ce qu'on appelle un temps linéaire.

On pourrait encore optimiser la solution

mais cela suffit à nos héros.

Éthique et Hedge travaillent de concert.

La première cascade est aisée
et ils montent dans la tour.

La deuxième est un peu plus rude.

La troisième est immense
avec des dizaines de piles de blocs.

La minuterie se rapproche de zéro
mais le programme d'Éthique est rapide.

Elle atteint la barre juste à temps

et l'énergie les soulève
vers le Nœud de la Création.

Comme la première, il révèle une vision :
la mémoire des années passées.

La machine du monde a tout changé.

Et Éthique, en tant que
cheffe ingénieur en robotique,

est de plus en plus troublée
par ce qu'elle voit.

Quand la barrière Brad s'est levée
pour enfermer les gens,

elle a compris que quelque chose
avait tourné très mal.

Alors, elle a créé trois artéfacts

capables de restaurer la puissance,
la créativité et la mémoire des gens

et elle les a apportés en cachette
à trois communautés.

Avant de pouvoir expliquer
comment les utiliser,

les gouvernements l'ont découverte
et ont envoyé des bots pour l'arrêter

avec les autres programmeurs.

La dernière chose qu'Éthique a fait créer
par la machine du monde

est un robot pour protéger
l'ancien système

des forces de l'ignorance en l'enfermant
dans un labyrinthe géant.

Elle a nommé sa création Hedge.

Sans prévenir, l'ascenseur énergétique
faiblit et s'éteint définitivement.