The Chasm | Think Like A Coder, Ep 6

Tłumaczenie: Kornelia Szyszka Korekta: Rysia Wand

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

Etyka, Hedge i Octavia stoją na skraju jaru bez dna.

It’s the only thing between them and the tower

To jedyne, co dzieli ich od wieży,

that houses the second of three powerful artifacts.

która mieści drugi z trzech potężnych artefaktów.

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

Mają tylko chwilę, by do niej dotrzeć przed powrotem straży.

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

Z prawie pustym zbiornikiem paliwa Hedge nie może zabrać Etyki na drugą stronę,

so the only option is to make a bridge.

jedyną opcją jest budowa mostu.

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

Na szczęście unoszące się nieopodal stosy kamieni to elementy mostu.

invented by Octavia herself— called hover-blocks.

Wynalazła je Octavia i nazwała wiszącymi kamieniami.

Activate a pile with a burst of energy,

Stos aktywuje się za pomocą energii,

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

a elementy same ułożą się nad jarem z każdym krokiem Etyki.

But there is, of course, a catch.

Jest oczywiście pewien haczyk.

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

Wiszące kamienie są stabilne jedynie, gdy są całkowicie symetryczne.

Meaning they have to form a sequence

Co oznacza, że muszą stworzyć sekwencję,

that’s the same when viewed forwards and backwards.

która jest taka sama z przodu i z tyłu.

The stacks start in random orders,

Pierwszy blok ze sterty jest losowy,

but will always put themselves into a palindromic configuration

ale kolejne nakładają się na siebie, zachowując układ palindromu

if they can.

jeśli się da.

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

Jeśli dotrą tam, gdzie palindrom nie jest możliwy,

the bridge will collapse,

most się zawali,

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

a ten, kto na nim stoi, spadnie do jaru.

Let’s look at an example.

Spójrzmy na przykład.

This stack would make itself stable.

Ten stos stałby się stabilny.

First the A blocks hold themselves in place.

Najpierw pozycję zajmują bloki A.

Then the B’s.

Potem B.

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

Na końcu blok C usadowiłby się pomiędzy dwoma B.

However, suppose there was one more A.

Załóżmy jednak, że jest jeszcze jeden blok A.

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

Najpierw rozkładają się dwa bloki A, potem B,

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

ale w ten sposób bloki A i C nie mają gdzie się podziać,

so the whole thing falls apart.

więc całość się rozpada.

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

Dzięki Węzłowi Mocy Hedge może aktywować pojedynczy stos bloków.

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

Jaką instrukcję powinna dać Etyka, by Hedge sprawnie odnalazł

and power a stable palindromic stack?

i uruchomił stabilny stos palindromiczny?

Pause now to figure it out for yourself.

Zatrzymaj, by znaleźć rozwiązanie.

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

Przykłady palindromów to ANNA, RACECAR czy MADAM IM ADAM.

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

Liczenie, jak często dana litera pojawia się w palindromie,

will reveal a helpful pattern.

ujawni przydatny wzorzec.

Pause now to figure it out for yourself.

Zatrzymaj, by znaleźć rozwiązanie.

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

Spróbujmy najpierw rozwiązania naiwnego.

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

Rozwiązanie naiwne to podejście proste, "na siłę", które nie jest zoptymalizowane,

but will get the job done.

ale wykona zadanie.

Naïve solutions are helpful ways to analyze problems,

Rozwiązania naiwne przydają się do analizowania problemu

and work as stepping stones to better solutions.

i jako podwaliny dla lepszych rozwiązań.

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

W tym przypadku naiwnym rozwiązaniem jest budowa stosu bloków

try all the arrangements,

i próba wszystkich możliwych kombinacji,

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

by znaleźć palindrom czytając każdą wprzód i w tył.

The problem with this approach

Niestety to podejście

is that it would take a tremendous amount of time.

zajęłoby ogromnie dużo czasu.

If Hedge tried one combination every second,

Gdyby Hedge próbował jednej kombinacji na sekundę,

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

stos zaledwie 10 różnych bloków zająłby mu 42 dni.

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

To dlatego, że całkowity czas to silnia

of the number of blocks there are.

liczby dostępnych bloków.

10 blocks have over 3 million combinations.

10 bloków to ponad 3 miliony kombinacji.

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

Rozwiązanie naiwne pokazuje, że potrzeba znacznie szybszego sposobu,

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

by sprawdzić czy dany stos może utworzyć palindrom.

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

Po pierwsze, intuicja podpowiada, że stos 10 różnych bloków

will never form one.

nigdy nie utworzy palindromu.

Why?

Dlaczego?

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

Pierwszy i ostatni blok nie będą identyczne,

jeśli nie ma dwóch takich samych bloków.

So when can a given sequence become a palindrome?

Kiedy więc dana sekwencja utworzy palindrom?

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

Jednym ze sposobów, by to ustalić jest analiza istniejących palindromów.

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

W ANNA są 2 A, 2 N.

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

W słowie RACECAR mamy 2 R, 2 A, 2C i 1 E.

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

Zwrot MADAM IM ADAM ma 4 M, 4 A, 2 D i 1 I.

The pattern here is that most of the letters occur

Schemat ten pokazuje, że większość liter pojawia się

an even number of times,

parzystą liczbę razy

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

i najwyżej 1 pojawia się tylko raz.

Is that it?

Czy to wystarczy?

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

Co by było gdyby słowo RACECAR miało 3 E zamiast 1?

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

Można by dodać E na każdym z końców i nadal utworzyć palindrom,

so 3 is ok.

więc 3 jest ok.

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

Ale jeśli będziemy mieć 3 E i 3 C, ostatnie C nie będzie miało miejsca.

So the most generalized insight is that

Tak więc, uogólniając,

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

najwyżej jedna litera może pojawić się nieparzystą ilość razy,

but the rest have to be even.

reszta musi być parzysta.

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

Hedge może policzyć litery w każdym stosie i uporządkować je w słownik,

which is a tidy way of storing information.

co jest schludną metodą przechowywania informacji.

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

Za pomocą pętli można policzyć ile razy pojawia się nieparzysta liczba.

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

Jeśli są mniej niż 2 nieparzyste liczby, stos może stworzyć palindrom.

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

To podejście jest znacznie szybsze, niż rozwiązanie naiwne.

Instead of factorial time, it takes linear time.

Zamiast złożoności typu silnia, mamy złożoność liniową.

That’s where the time increases

Czasu przybywa

in proportion to the number of blocks there are.

proporcjonalnie do liczby bloków, którymi dysponujemy.

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

Wystarczy napisać pętlę, dzięki której Hedge podejdzie do każdego stosu osobno

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

i zatrzyma się, gdy znajdzie właściwy.

Here’s what happens:

Oto, co się dzieje:

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

Hedge jest szybki, ale taka liczba stosów zabiera dużo czasu.

Too long.

Za dużo.

Ethic and Hedge are safe.

Etyka i Hedge są bezpieczni.

But Octavia is not so lucky.

Ale Octavia nie ma tyle szczęścia.