The Chasm | Think Like A Coder, Ep 6

Traducteur: Morgane Quilfen Relecteur: eric vautier

Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.

Éthique, Hedge et Octavia se tiennent au bord d'un ravin sans fond.

It’s the only thing between them and the tower

C'est la seule chose entre eux et la tour

that houses the second of three powerful artifacts.

qui abrite le deuxième des trois puissants artefacts.

They’ve got a brief window of time to get across before the guards return.

Ils ont une brève fenêtre temporelle pour traverser avant le retour des gardes.

With Hedge’s fuel gauge on empty he won’t be able to fly Ethic across,

Avec la jauge de carburant de Hedge vide, il ne pourra pas faire traverser Éthique.

so the only option is to make a bridge.

La seule option est donc de construire un pont.

Fortunately, the floating stacks of stones nearby are bridge components—

Heureusement, les roches flottant autour d'eux

sont des éléments de pont -

invented by Octavia herself— called hover-blocks.

inventés par Octavia elle-même - appelés hoverblocs.

Activate a pile with a burst of energy,

Activez une pile avec une poussée d'énergie

and they’ll self-assemble to span the ravine as Ethic walks across.

et ils s'assembleront d'eux-mêmes pour enjamber le ravin

pendant qu'Éthique traverse.

But there is, of course, a catch.

Mais bien sûr, il y a un piège.

The hover-blocks are only stable when they’re perfectly palindromic.

Les hoverblocs ne sont stables que s'ils sont parfaitement palindromiques.

Meaning they have to form a sequence

Ils doivent former une séquence qui est identique

that’s the same when viewed forwards and backwards.

vue à l'endroit et à l'envers.

The stacks start in random orders,

Les tas commencent dans un ordre aléatoire

but will always put themselves into a palindromic configuration

mais se placeront toujours dans une configuration palindromique

if they can.

s'ils le peuvent.

If they get to a point where a palindrome isn’t possible,

S'ils en arrivent à un point où un palindrome est impossible,

the bridge will collapse,

le pont s'effondrera

and whoever’s on it will fall into the ravine.

et quiconque se trouvant dessus tombera dans le ravin.

Let’s look at an example.

Considérons un exemple.

This stack would make itself stable.

Ce tas se stabiliserait.

First the A blocks hold themselves in place.

Les blocs A se mettraient en place.

Then the B’s.

Puis les B.

And finally the C would nestle right between the B’s.

Finalement, le C se nicherait entre les deux B.

However, suppose there was one more A.

Cependant, supposez qu'il y avait un A de plus.

First two A blocks form up, then two B’s,

Deux blocs A se positionnent, puis deux blocs B,

but now the remaining C and A have nowhere to go,

mais alors les blocs C et A restant n'ont nulle part où aller

so the whole thing falls apart.

et donc tout s'effondre.

The Node of Power enables Hedge to energize a single stack of blocks.

Le nœud du pouvoir permet à Hedge de donner de l'énergie à un seul tas.

What instructions can Ethic give Hedge to allow him to efficiently find

Quelles instructions Éthique peut-elle donner à Hedge

pour lui permettre de trouver efficacement

and power a stable palindromic stack?

et de transmettre de l'énergie à une pile palindromique ?

Pause now to figure it out for yourself.

Mettez en pause maintenant si vous voulez trouver la réponse seul.

Examples of palindromes include ANNA, RACECAR, and MADAM IM ADAM.

Des exemples de palindromes incluent « ANNA », « RACECAR », « MADAM IM ADAM ».

Counting the number of times a given letter appears in a palindrome

Compter le nombre de fois

qu'une lettre donnée apparaît dans un palindrome

will reveal a helpful pattern.

révélera une tendance utile.

Pause now to figure it out for yourself.

Mettez en pause maintenant si vous voulez trouver la réponse seul.

Let’s first look at a naïve solution to this problem.

Considérons d'abord une solution naïve à ce problème.

A naïve solution is a simple, brute-force approach that isn’t optimized—

Une solution naïve est une approche simple, utilisant de la force brute

mais n'étant pas optimisée -

but will get the job done.

mais qui accomplira la tâche.

Naïve solutions are helpful ways to analyze problems,

Les solutions naïves sont des façons utiles d'analyser des problèmes

and work as stepping stones to better solutions.

et servent de fondation à de meilleures solutions.

In this case, a naïve solution is to approach a pile of blocks,

Dans ce cas, une solution naïve est d'approcher un tas de blocs,

try all the arrangements,

d'essayer toutes les dispositions

and see if one is a palindrome by reading it forward and then backwards.

et de voir si l'une est un palindrome en la regardant à l'endroit et à l'envers.

The problem with this approach

Le problème avec cette approche

is that it would take a tremendous amount of time.

est qu'elle prendrait un temps considérable.

If Hedge tried one combination every second,

Si Hedge essayait une combinaison par seconde,

a stack of just 10 different blocks would take him 42 days to exhaust.

une pile de seulement 10 blocs lui prendrait 42 jours à parcourir.

That’s because the total time is a function of the factorial

C'est parce que la durée totale est une fonction de la factorielle

of the number of blocks there are.

du nombre de blocs.

10 blocks have over 3 million combinations.

Dix blocs ont plus de trois millions de combinaisons.

What this naïve solution shows is that we need a much faster way

Ce que montre cette solution naïve,

c'est qu'il nous faut une méthode bien plus rapide

to tell whether a pile of blocks can form a palindrome.

de dire si une pile de blocs peut former un palindrome.

To start, it may be intuitively clear that a pile of all different blocks

Pour commencer, de façon intuitive,

il peut être clair qu'une pile de blocs différents

will never form one.

n'en formera jamais un.

Why?

Pourquoi ?

The first and last blocks can’t be the same if there are no repeats.

Le premier et le dernier bloc ne peuvent pas être identiques

s'il n'y a pas de doubles.

So when can a given sequence become a palindrome?

Quand est-ce qu'une séquence donnée peut-elle devenir un palindrome ?

One way to figure that out is to analyze a few existing palindromes.

Une façon de le déterminer est d'analyser quelques palindromes existants.

In ANNA, there are 2 A’s and 2 N’s.

Dans « ANNA », il y a deux A et deux N.

RACECAR has 2 R’s, 2 A’s, 2 C’s, and 1 E.

« RACECAR » a deux R, deux A, deux C et un E.

And MADAM IM ADAM has 4 M’s, 4 A’s, 2 D’s, and 1 I.

Et « MADAM IM ADAM » a quatre M, quatre A, deux D et un I.

The pattern here is that most of the letters occur

Le motif ici est que la majorité des lettres

an even number of times,

apparaissent un nombre pair de fois

and there’s at most 1 that occurs just once.

et il y en au maximum une qui n'apparaît qu'une fois.

Is that it?

Est-ce tout ?

What if RACECAR had 3 E’s instead of 1?

Et si « RACECAR » avait trois E au lieu d'un ?

We could tack the new E’s onto the ends and still get a palindrome,

Nous pourrions mettre les nouveaux E aux extrémités et obtenir un palindrome,

so 3 is ok.

donc trois fonctionne.

But make that 3 E’s and 3 C’s, and there’s nowhere for the last C to go.

Mais avec trois E et trois C, le dernier C n'a nulle part où aller.

So the most generalized insight is that

L'idée la plus généralisée

at most one letter can appear an odd number of times,

est qu'au maximum une lettre peut apparaître un nombre impair de fois

but the rest have to be even.

mais les autres doivent apparaître un nombre pair de fois.

Hedge can count the letters in each stack and organize them into a dictionary,

Hedge peut compter les lettres dans chaque pile

et les organiser en un dictionnaire,

which is a tidy way of storing information.

ce qui est une façon ordonnée de sauvegarder des informations.

A loop could then go through and count how many times odd numbers appear.

Une boucle pourrait le parcourir

et compter combien de fois un nombre impair apparaît.

If there are less than 2 odd characters, the stack can be made into a palindrome.

S'il y a moins de deux lettres en nombre impair,

le tas peut être organisé sous forme d'un palindrome.

This approach is much, much faster than the naïve solution.

Cette approche est bien plus rapide que la solution naïve.

Instead of factorial time, it takes linear time.

Au lieu d'une durée en factorielle, nous sommes en linéaire.

That’s where the time increases

C'est quand la durée augmente en proportion du nombre de blocs.

in proportion to the number of blocks there are.

Now write a loop for Hedge to approach the piles individually,

Écrivez une boucle pour que Hedge approche les piles une à une

and stop when he finds a good one, and you’ll be ready to go.

et s'arrête quand il en trouve une adéquate

et vous serez paré.

Here’s what happens:

Voici ce qu'il se passe :

Hedge is fast, but there are so many piles it takes a long time.

Hedge est rapide mais il y a tant de piles que cela lui prend longtemps.

Too long.

Trop longtemps.

Ethic and Hedge are safe.

Éthique et Hedge sont en sécurité

But Octavia is not so lucky.

mais Octavia n'a pas autant de chance.