The Chasm | Think Like A Coder, Ep 6

Vertaald door: Tahlia Flora Nagekeken door: Esther van Driel

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

Ethic, Hedge en Octavia staan op de rand van een bodemloze ravijn.

It’s the only thing between them and the tower

Het is het enige wat tussen hen en de toren instaat,

that houses the second of three powerful artifacts.

waar de tweede van de drie krachtige artefacten wordt ondergebracht.

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

Ze moeten in een korte tijdspanne naar de overkant zien te komen,

voordat de bewakers terugkeren.

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

Nu Hedges brandstofmeter op nul staat kan hij Ethic niet overvliegen

so the only option is to make a bridge.

en dus is een brug bouwen de enige optie.

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

Gelukkig zijn de nabijgelegen zwevende stapels stenen delen van een brug --

invented by Octavia herself— called hover-blocks.

Octavia heeft ze zelf ontworpen -- die hoverblokken heten.

Activate a pile with a burst of energy,

Activeer een stapel door een energiestoot af te vuren

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

en deze zal het ravijn overbruggen terwijl Ethic naar de overkant loopt.

But there is, of course, a catch.

Maar er schuilt natuurlijk een addertje onder het gras.

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

De hoverblokken zijn alleen stabiel wanneer ze perfecte palindromen zijn.

Meaning they have to form a sequence

Dit houdt in dat ze een sequentie moeten vormen

that’s the same when viewed forwards and backwards.

dat van links naar rechts gezien hetzelfde is als van rechts naar links.

The stacks start in random orders,

De stapels zijn gerangschikt in willekeurige volgorde,

but will always put themselves into a palindromic configuration

maar vormen zich altijd tot een palindromische configuratie

if they can.

als dit mogelijk is.

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

Als ze op een punt komen waar geen palindroom gevormd kan worden,

the bridge will collapse,

zal de brug ineenstorten

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

en zal degene die erop staat in het ravijn vallen.

Let’s look at an example.

Laten we een voorbeeld bekijken.

This stack would make itself stable.

Deze stapel maakt zichzelf stabiel.

First the A blocks hold themselves in place.

Eerst houden de A-blokken zichzelf in stand.

Then the B’s.

Dan de B-blokken.

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

En uiteindelijk nestelt het C-blok zich tussen de B-blokken.

However, suppose there was one more A.

Stel, er was nog een A-blok.

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

Eerst worden twee A-blokken gevormd en daarna twee B-blokken,

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

maar nu kunnen de overgebleven blokken nergens geplaatst worden,

so the whole thing falls apart.

dus valt het hele ding uit elkaar.

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

De Node van Macht stelt Hedge in staat

om een enkele stapel blokken te activeren.

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

Welke instructies kan Ethic aan Hedge geven

zodat hij efficiënt

een stabiele stapel palindromen kan vinden en aandrijven?

and power a stable palindromic stack?

Pause now to figure it out for yourself.

[Pauzeer nu de video om het zelf uit te zoeken.]

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

Voorbeelden van palindromen zijn ANNA, RACECAR en MADAM IM ADAM.

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

Door te tellen hoe vaak een bepaalde letter

in een palindroom voorkomt,

will reveal a helpful pattern.

zal een nuttig patroon worden onthuld.

Pause now to figure it out for yourself.

[Pauzeer nu de video om het zelf uit te zoeken.]

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

Laten we eerst een naïeve oplossing voor dit probleem bekijken.

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

Een naïeve oplossing is een eenvoudige, op brute kracht gebaseerde logica

die niet optimaal is,

but will get the job done.

maar wel de klus klaart.

Naïve solutions are helpful ways to analyze problems,

Naïeve oplossingen zijn nuttige methoden om problemen te analyseren

and work as stepping stones to better solutions.

en werken als opstap naar betere oplossingen.

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

De naïeve oplossing voor dit probleem

is een stapel blokken te benaderen, alle opstellingen te proberen

try all the arrangements,

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

en een palindroom te zoeken door deze voorwaarts en achterwaarts te lezen.

The problem with this approach

Het probleem bij deze aanpak

is that it would take a tremendous amount of time.

is dat het een enorme hoeveelheid tijd in beslag neemt.

If Hedge tried one combination every second,

Als Hedge een combinatie per seconde uitprobeert

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

zal een stapel van tien verschillende blokken

hem 42 dagen kosten om af te voeren.

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

Dat komt doordat de totale tijd een faculteitsfunctie is

of the number of blocks there are.

van het totale aantal bestaande blokken.

10 blocks have over 3 million combinations.

Met tien blokken kunnen er meer dan drie miljoen combinaties gemaakt worden.

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

Deze naïeve oplossing toont aan dat we een snellere methode nodig hebben

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

om te zien of een stapel blokken een palindroom kan vormen.

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

Om te beginnen is het intuïtief duidelijk dat een stapel met verschillende blokken

will never form one.

nooit een geheel zal vormen.

Why?

Waarom?

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

De eerste en laatste blokken kunnen niet hetzelfde zijn zonder herhaalde letters.

So when can a given sequence become a palindrome?

Wanneer kan een bepaalde sequentie een palindroom worden?

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

Een manier om erachter te komen is door bestaande palindromen te analyseren.

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

In ANNA staan twee A's en twee keer een N.

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

RACECAR heeft twee keer een R, twee A's, twee C's en een E.

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

En MADAM IM ADAM heeft vier keer een M, vier A's, twee D's en een I.

The pattern here is that most of the letters occur

Het patroon hier is dat de meeste letters

an even number of times,

een even aantal keer voorkomen

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

en er is hooguit een letter die slechts een keer voorkomt.

Is that it?

Is dat alles?

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

Wat als RACECAR drie E's heeft in plaats van een?

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

We kunnen de nieuwe E's aan de uiteinden vastmaken en toch een palindroom maken,

so 3 is ok.

dus drie E's is goed.

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

Maar maak er drie E's en drie C's van

en de laatste C past nergens bij.

So the most generalized insight is that

Het meest gegeneraliseerde inzicht is dat hoogstens een letter

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

een oneven aantal keer kan voorkomen,

but the rest have to be even.

maar de rest moet een even aantal zijn.

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

Hedge kan in elke stapel de letters tellen en ze ordenen tot een woordenboek,

which is a tidy way of storing information.

zodat alle informatie netjes opgeslagen wordt.

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

Een loop zal alles doorlopen en het aantal oneven getallen tellen.

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

Als er minder dan twee oneven tekens zijn

kan de stapel omgebouwd worden tot een palindroom.

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

Deze aanpak werkt veel sneller dan de naïeve oplossing.

Instead of factorial time, it takes linear time.

In plaats van in factoriale tijd wordt deze in lineaire tijd uitgevoerd.

That’s where the time increases

Dat is waar de tijd oploopt in verhouding tot het aantal bestaande blokken.

in proportion to the number of blocks there are.

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

Noteer nu een loop voor Hedge om de stapels een voor een te benaderen,

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

stop wanneer hij een goede gevonden heeft en je bent klaar om te gaan.

Here’s what happens:

Dit is wat er gebeurt:

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

Hedge is snel, maar er zijn veel stapels waardoor het proces hem veel tijd kost.

Too long.

Teveel tijd.

Ethic and Hedge are safe.

Ethic en Hedge zijn veilig aangekomen.

But Octavia is not so lucky.

Maar Octavia heeft minder geluk.