The Chasm | Think Like A Coder, Ep 6

Traductor: Sonia Escudero Sánchez Revisor: José Miguel Godoy Muñoz

[Una serie original de TEDEd]

[Diseñada y animada por Kozmonot Studio]

[Piensa como un programador]

[Localización: Bosque198]

Episodio 6: El Abismo

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

Ética, Hedge y Octavia se encuentran al borde de un barranco sin fondo.

It’s the only thing between them and the tower

Es lo único entre ellos y la torre

that houses the second of three powerful artifacts.

que custodia el segundo de los tres poderosos artefactos.

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

Tienen un breve período de tiempo para cruzar antes de que los guardias regresen.

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

Con el indicador de combustible casi vacío, Hedge no podrá transportar a Ética,

so the only option is to make a bridge.

así que la única opción es construir un puente.

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

Por suerte, las pilas de piedras flotantes cercanas son componentes del puente

invented by Octavia herself— called hover-blocks.

- inventadas por la propia Octavia - llamadas bloques flotantes.

Activate a pile with a burst of energy,

Activa una pila con un estallido de energía,

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

y se autoensamblarán para abarcar el barranco mientras Ética cruza.

But there is, of course, a catch.

Pero hay, por supuesto, una trampa.

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

Los bloques flotantes solo son estables cuando son palíndromos perfectos

Meaning they have to form a sequence

Lo que significa que tienen que formar una secuencia idéntica

that’s the same when viewed forwards and backwards.

cuando se vea por delante y por detrás.

The stacks start in random orders,

Las pilas empiezan en órdenes aleatorios,

but will always put themselves into a palindromic configuration

pero siempre que puedan se colocarán en una configuración palindrómica.

if they can.

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

Si llegan a un punto donde no es posible un palíndromo,

the bridge will collapse,

el puente colapsará y, quien se encuentre sobre él, caerá hacia el barranco.

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

Let’s look at an example.

Veamos un ejemplo.

This stack would make itself stable.

Esta pila se haría estable.

First the A blocks hold themselves in place.

Primero, los bloques A se sitúan en su lugar.

Then the B’s.

Posteriormente, los B.

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

Y, finalmente, el C se ubicaría justo entre los B.

However, suppose there was one more A.

Sin embargo, imagina que hay un bloque A más.

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

Primero, se forman dos bloques A; después, dos B;

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

pero, ahora, los bloques C y A restantes no tienen donde ir y todo se derrumba.

so the whole thing falls apart.

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

El nodo de poder permite a Hedge energizar una única pila de bloques.

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

¿Qué instrucciones puede dar Ética a Hedge para permitirle encontrar

and power a stable palindromic stack?

y alimentar eficientemente una pila palindrómica estable?

Pause now to figure it out for yourself.

[Pausa el vídeo si quieres descubrirlo por ti mismo.]

[Pista en: 5]

[Pista en: 4]

[Pista en: 3]

[Pista en: 2]

[Pista en: 1]

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

Ejemplos de palíndromos incluyen ANNA, RACECAR, y MADAM IM ADAM.

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

Contando el número de veces que una letra dada aparece en un palíndromo

will reveal a helpful pattern.

revelará un patrón útil.

Pause now to figure it out for yourself.

[Pausa el vídeo si quieres descubrirlo por ti mismo.]

[Solución en: 3]

[Solución en: 2]

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

[Solución en: 1]

Primeros veamos una solución ingenua a este problema.

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

Una solución ingenua es una aproximación simple con fuerza bruta no optimizada,

but will get the job done.

pero que hará el trabajo.

Naïve solutions are helpful ways to analyze problems,

Las soluciones ingenuas son formas útiles de analizar problemas,

and work as stepping stones to better solutions.

y sirven como peldaños para mejorar soluciones.

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

En este caso, una solución ingenua es acercarse a una pila de bloques,

try all the arrangements,

probar todas las combinaciones,

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

y ver si una de ellas es un palíndromo al leerlo hacia delante y atrás.

The problem with this approach

El problema con este enfoque

is that it would take a tremendous amount of time.

es que tomaría una tremenda cantidad de tiempo.

If Hedge tried one combination every second,

Si Hedge intentara una combinación cada segundo,

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

una pila de solo 10 bloques diferentes le llevaría 42 días hasta el agotamiento.

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

Esto se debe a que el tiempo total es una función del factorial

of the number of blocks there are.

del número de bloques que hay.

10 blocks have over 3 million combinations.

10 bloques tienen más de tres millones de combinaciones.

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

Lo que muestra la solución ingenua es que necesitamos una manera rápida

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

de decir si una pila de bloques pueden forman un palíndromo.

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

Para empezar, se puede intuir que una pila con todos los bloques diferentes

will never form one.

nunca formará una pila. ¿Por qué?

Why?

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

El primer y último bloque no pueden ser iguales si no hay repeticiones.

So when can a given sequence become a palindrome?

Así que, ¿cuándo una secuencia dada puede convertirse en un palíndromo?

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

Una forma de resolverlo es analizar algunos palíndromos existentes.

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

En ANNA hay 2 bloques A y 2 N.

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

RACECAR tiene 2 R, 2 A, 2 C y 1 E.

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

Y MADAM IM ADAM tiene 4 M, 4 A, 2 D y 1 I.

The pattern here is that most of the letters occur

El patrón aquí es que la mayoría de letras aparecen

an even number of times,

un número par de veces,

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

y hay al menos una que aparece solo una vez.

Is that it?

¿Es así?

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

¿Qué pasa si RACECAR tuviera 3 E en lugar de 1?

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

Podemos colocar la nueva E en los extremos y obtener también un palíndromo,

so 3 is ok.

así que tres está bien.

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

Pero haz eso con 3 E y 3 C, y no hay dónde colocar la última C.

So the most generalized insight is that

Entonces, la idea más generalizada es que,

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

como máximo, una letra puede aparecer un número impar de veces,

but the rest have to be even.

pero el resto tiene que ser par.

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

Hedge puede contar las letras en cada pila y organizarlas en un diccionario,

which is a tidy way of storing information.

que es una forma ordenada de almacenar la información.

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

Un ciclo podría pasar y contar cuántas veces aparecen los números impares.

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

Si hay menos de dos caracteres impares, las pilas pueden ordenarse en palíndromos.

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

Este enfoque es mucho, mucho más rápido que la solución ingenua.

Instead of factorial time, it takes linear time.

En lugar de tiempo factorial, se necesita tiempo lineal.

That’s where the time increases

El tiempo aumentará de forma proporcional al número de bloques que hay.

in proportion to the number of blocks there are.

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

Ahora, escribe un bucle temporal para que Hedge se aproxime

a las pilas individuales,

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

y pare cuando encuentre una buena, y estarás listo para irte.

Here’s what happens:

Esto es lo que ocurre:

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

Hedge es rápido, pero hay tantas pilas que lleva mucho tiempo.

Too long.

Demasiado.

Ethic and Hedge are safe.

Ética y Hedge están a salvo.

But Octavia is not so lucky.

Pero Octavia no ha tenido tanta suerte.