The Chasm | Think Like A Coder, Ep 6

Tradutor: Simone Gumier Revisor: Maricene Crus

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

Ethic, Hedge e Octavia se encontram à beira de um abismo,

It’s the only thing between them and the tower

a única coisa que os separa da torre

that houses the second of three powerful artifacts.

que abriga o segundo de três poderosos artefatos.

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

Eles têm um breve espaço de tempo para atravessar,

antes que os guardas voltem.

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

Hedge está sem combustível e não conseguirá levar Ethic até a torre.

so the only option is to make a bridge.

Então, a única opção é construir uma ponte.

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

Felizmente, as pilhas flutuantes de pedras próximas são componentes de ponte,

invented by Octavia herself— called hover-blocks.

inventados pela própria Octavia, chamados "blocos flutuantes".

Activate a pile with a burst of energy,

Ative uma pilha de blocos com uma descarga de energia

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

e os blocos formarão uma ponte, enquanto Ethic atravessa o abismo.

But there is, of course, a catch.

Mas é claro que há um empecilho:

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

os blocos flutuantes só têm estabilidade quando são perfeitamente palindrômicos.

Meaning they have to form a sequence

Ou seja, eles devem formar uma sequência que é igual

that’s the same when viewed forwards and backwards.

quando vista de trás para frente.

The stacks start in random orders,

As pilhas de blocos começam aleatoriamente,

but will always put themselves into a palindromic configuration

mas sempre se colocarão em um configuração palindrômica

if they can.

se puderem.

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

Se eles atingirem um ponto no qual o palíndromo não for possível,

the bridge will collapse,

a ponte desmoronará e quem estiver sobre ela cairá no abismo.

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

Let’s look at an example.

Vejamos um exemplo.

This stack would make itself stable.

Esta pilha se manteria estável.

First the A blocks hold themselves in place.

Primeiro, os blocos A se posicionariam; depois, os blocos B.

Then the B’s.

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

Por fim, o bloco C se posicionaria entre os blocos B.

However, suppose there was one more A.

Porém, suponhamos que houvesse mais um bloco A.

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

Primeiro, os dois blocos A se posicionariam, depois os dois blocos B,

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

mas os blocos C e A restantes não teriam como se encaixar.

so the whole thing falls apart.

Então, tudo entraria em colapso.

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

O "Node do Poder" permite que Hedge energize uma única pilha de blocos.

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

Quais instruções Ethic pode dar a Hedge para que ele encontre

and power a stable palindromic stack?

e energize uma pilha palindrômica estável?

Pause now to figure it out for yourself.

[Uma pausa agora para que você descubra sozinho.]

[Regra 1] [Regra 2] [Regra 3] [Regra 4]

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

São exemplos de palíndromos: 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 dada letra aparece em um palíndromo

will reveal a helpful pattern.

revelará um padrão útil.

Pause now to figure it out for yourself.

[Uma pausa agora para que você descubra sozinho.]

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

Primeiro, vejamos uma solução "naïve" para este problema.

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

Um solução naïve é uma abordagem simples e de força bruta, não otimizada,

but will get the job done.

mas que fará o trabalho.

Naïve solutions are helpful ways to analyze problems,

Soluções naïve são manerias úteis de analisar problemas

and work as stepping stones to better solutions.

e trabalham como pontos de partida para encontrar melhores soluções.

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

Neste caso, uma solução naïve significa abordar uma pilha de blocos,

try all the arrangements,

tentar todos os agrupamentos e verificar se alguma é um palíndromo,

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

lendo-a de trás para frente.

The problem with this approach

O problema dessa abordagem é que ela tomaria muitíssimo tempo.

is that it would take a tremendous amount of time.

If Hedge tried one combination every second,

Se Hedge tentasse uma combinação a cada segundo,

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

seriam necessários 42 dias para ler uma pilha com apenas 10 blocos diferentes.

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 existentes.

of the number of blocks there are.

10 blocks have over 3 million combinations.

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

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

O que essa solução naïve mostra é que precisamos de um modo mais rápido

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

de dizer se uma pilha de blocos pode formar um palíndromo.

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

Para começar,

deve-se intuir claramente que uma pilha com todos os diferentes blocos

will never form one.

nunca formará um palíndromo. Por quê?

Why?

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

O primeiro e o último blocos não podem ser iguais se não há repetições.

So when can a given sequence become a palindrome?

Então, quando uma dada sequência pode se tornar um palíndromo?

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

Um jeito de resolver isso é analisar alguns palíndromos existentes.

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

Em ANNA, há duas letras A, e duas letras N.

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

Em RACECAR, há duas letras R, duas letras C e uma letra E.

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

Em MADAM IM ADAM, há quatro M, quatro A, dois D e uma letra I.

The pattern here is that most of the letters occur

O padrão aqui é que a maioria das letras aparece um número par de vezes,

an even number of times,

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

e que há, no máximo, uma letra que aparece apenas uma vez.

Is that it?

É isso mesmo?

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

E se RACECAR tivesse três letras E em vez de uma?

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

Poderíamos pôr as novas letras E nos lados e ainda ter um palíndromo.

so 3 is ok.

Então, tudo bem se tiver três letras iguais.

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

Mas se tentarmos três letras E e três C, a última letra C não se encaixará.

So the most generalized insight is that

Então, a visão mais generalizada é que, no máximo, uma letra

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

pode aparecer um número ímpar de vezes, mas as outras devem ser pares.

but the rest have to be even.

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 em um dicionário,

which is a tidy way of storing information.

que é um modo ordenado de armazenar informações.

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

Um loop poderia, então, analisar e contar

quantas vezes os números ímpares aparecessem.

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

Se houver menos de dois caracteres ímpares,

a pilha poderá ser transformada em um palíndromo.

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

Esta abordagem é muito mais rápida do que a solução naïve.

Instead of factorial time, it takes linear time.

Em vez do tempo fatorial, ela utiliza o tempo linear.

That’s where the time increases

É aí que o tempo aumenta em relação ao número de blocos existentes.

in proportion to the number of blocks there are.

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

Agora, faça um loop para que Hedge analise as pilhas de maneira individual,

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

e pare quando encontrar uma que for boa, e você estará pronto para começar.

Here’s what happens:

Eis o que acontece:

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

Hedge é rápido, mas há muitas pilhas e isso levaria muitíssimo tempo.

Too long.

Ethic and Hedge are safe.

Ethic e Hedge estão seguros, mas Octavia não teve tanta sorte.

But Octavia is not so lucky.