The Chasm | Think Like A Coder, Ep 6

Tradutor: Margarida Ferreira Revisora: Isabel Vaz Belchior

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

A Ética, o Hedge e a Otávia encontram-se na borda duma ravina sem fundo.

It’s the only thing between them and the tower

É a única coisa entre eles e a torre

that houses the second of three powerful artifacts.

onde se encontra o segundo de três poderosos artefactos.

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

Têm um breve período de tempo para atravessar,

antes de os guardas voltarem.

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

O combustível do Hedge está esgotado, não pode transportar a Ética pelo ar,

so the only option is to make a bridge.

por isso, a única opção é fazer uma ponte.

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

Felizmente, as pedras que flutuam à volta deles são elementos duma ponte

invented by Octavia herself— called hover-blocks.

— inventada pela Otávia — chamados "blocos flutuantes".

Activate a pile with a burst of energy,

Se ativarmos uma pilha com uma descarga de energia,

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

elas montam-se sozinhas sobre a ravina que a Ética tem de atravessar.

But there is, of course, a catch.

Mas, claro, há um inconveniente.

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

Os blocos flutuantes só se mantêm estáveis se formarem perfeitas capicuas.

Meaning they have to form a sequence

Ou seja, têm de formar uma sequência que seja igual

that’s the same when viewed forwards and backwards.

quer vista da frente para trás ou de trás para a frente.

The stacks start in random orders,

As pilhas começam numa ordem aleatória,

but will always put themselves into a palindromic configuration

mas colocam-se sempre numa configuração de capicuas

if they can.

se puderem.

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

Se chegarem a um ponto em que não seja possível uma capicua,

the bridge will collapse,

a ponte desabará

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

e quem quer que se encontre nela cairá na ravina.

Let’s look at an example.

Vejamos um exemplo.

This stack would make itself stable.

Esta pilha configura-se de forma estável.

First the A blocks hold themselves in place.

Primeiro, os blocos A colocam-se no seu lugar.

Then the B’s.

Depois, os blocos B.

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

E por fim, os C encaixam-se entre os B.

However, suppose there was one more A.

Contudo, suponhamos que havia mais um A.

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

Primeiro formam-se dois blocos A, depois dois blocos B,

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

mas agora, os restantes blocos C e A não têm onde se encaixar,

so the whole thing falls apart.

e assim, tudo se desmorona.

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

O Nódulo do Poder permite ao Hedge fornecer energia a uma só pilha de blocos.

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

Que instruções deve a Ética dar ao Hedge para ele encontrar eficazmente

and power a stable palindromic stack?

e fornecer energia a uma pilha em forma de capicua?

Pause now to figure it out for yourself.

[Suspende aqui o vídeo para resolveres sozinho.]

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

São exemplos de capicuas ANNA, RACECAR e MADAM IM ADAM.

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

Contar o número de vezes que uma letra aparece numa capicua

will reveal a helpful pattern.

revela um padrão útil.

Pause now to figure it out for yourself.

[Suspende aqui o vídeo para resolveres sozinho]

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

Primeiro, vejamos uma solução ingénua para este problema.

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

Uma solução ingénua é uma abordagem simples que não está otimizada

but will get the job done.

— mas consegue realizar a tarefa.

Naïve solutions are helpful ways to analyze problems,

As soluções ingénuas são formas úteis de analisar um problema

and work as stepping stones to better solutions.

e funcionam como degraus para melhores soluções.

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

Neste caso, uma solução ingénua é abordar uma pilha de blocos,

try all the arrangements,

tentar todos os arranjos

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

e ver se um deles é uma capicua lendo-o nos dois sentidos.

The problem with this approach

O problema com esta abordagem

is that it would take a tremendous amount of time.

é que isso demora imenso tempo.

If Hedge tried one combination every second,

Se o Hedge tentar uma combinação por segundo,

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

uma pilha de 10 blocos diferentes demoraria 42 dias a explorar.

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

Isso porque o tempo total

é uma função do fatorial do número de blocos que há.

of the number of blocks there are.

10 blocks have over 3 million combinations.

Dez blocos têm mais de três milhões de combinações.

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

Esta solução ingénua mostra que precisamos de uma forma mais rápida

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

de saber se uma pilha de blocos pode formar uma capicua.

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

Para começar, pode ser intuitivo que uma pilha de blocos diferentes

will never form one.

nunca formem uma capicua.

Why?

Porquê?

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

O primeiro e o último bloco

não podem ser os mesmos se não houver repetições.

So when can a given sequence become a palindrome?

Quando é que uma dada sequência forma uma capicua?

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

Uma forma de imaginar isso é analisar algumas capicuas existentes.

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

Em ANNA, há dois A e dois N.

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

em RACECAR, há dois R, dois A, dois C e um E.

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

E em MADAM I, ADAM, há quatro M, quatro A, dois D e um I.

The pattern here is that most of the letters occur

O padrão aqui é que a maioria das letras ocorre

an even number of times,

num número par de vezes

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

e, no máximo, só há uma que aparece uma vez.

Is that it?

Será assim?

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

E se RACECAR tivesse três E, em vez de um só?

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

Podíamos deslocar os E para as pontas e continuávamos a ter uma capicua,

so 3 is ok.

portanto, se houver três, tudo bem.

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

Mas se tivermos três E e três C, não temos onde encaixar o último C.

So the most generalized insight is that

Portanto, a primeira conclusão que tiramos

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

é que só uma letra pode aparecer numa quantidade ímpar.

but the rest have to be even.

Todas as outras têm de ser em número par.

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

Hedge pode contar as letras em cada pilha e organizá-las num dicionário

which is a tidy way of storing information.

que é uma forma rigorosa de guardar informações.

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

Assim, podemos usar um "loop"

e contar quantas vezes aparecem números ímpares.

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

Se houver menos de duas letras em número ímpar,

a pilha pode ser transformada numa capicua.

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

Esta abordagem é muito mais rápida do que uma solução ingénua.

Instead of factorial time, it takes linear time.

Em vez dum tempo fatorial, usa-se o tempo linear.

That’s where the time increases

É quando o tempo aumenta

in proportion to the number of blocks there are.

em proporção com o número de blocos que há.

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

Então, escrevemos um "loop" para o Hedge abordar as pilhas, individualmente

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

e parar quando encontrasse uma boa e pudesse continuar.

Here’s what happens:

É isto que acontece.

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

O Hedge é rápido, mas há muitas pilhas e demora muito tempo.

Too long.

Demasiado tempo.

Ethic and Hedge are safe.

A Ética e o Hedge estão em segurança,

But Octavia is not so lucky.

mas Octavia não tem tanta sorte.