De afgrond | Denken als een programmeur, Afl. 6

Bekijk de volledige les: https://ed.ted.com/lessons/the-chasm-think-like-a-coder-ep-6

Dit is aflevering zes van onze animatieserie 'Denken als een programmeur.' Dit tiendelige verhaal gaat over een meisje genaamd Ethic dat met haar robotmaatje Hedge de wereld probeert te redden. De twee beginnen hun zoektocht naar drie artefacten en zullen een weg moeten banen door een reeks programmeerpuzzels.

Les door Alex Rosenthal, geregisseerd door Kozmonot Animation Studio.

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

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

waar de tweede van de drie krachtige
artefacten wordt ondergebracht.

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

voordat de bewakers terugkeren.

Nu Hedges brandstofmeter op nul staat
kan hij Ethic niet overvliegen

en dus is een brug bouwen de enige optie.

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

Octavia heeft ze zelf ontworpen --
die hoverblokken heten.

Activeer een stapel
door een energiestoot af te vuren

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

Maar er schuilt natuurlijk
een addertje onder het gras.

De hoverblokken zijn alleen stabiel
wanneer ze perfecte palindromen zijn.

Dit houdt in dat ze
een sequentie moeten vormen

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

De stapels zijn gerangschikt
in willekeurige volgorde,

maar vormen zich altijd
tot een palindromische configuratie

als dit mogelijk is.

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

zal de brug ineenstorten

en zal degene die erop staat
in het ravijn vallen.

Laten we een voorbeeld bekijken.

Deze stapel maakt zichzelf stabiel.

Eerst houden de A-blokken
zichzelf in stand.

Dan de B-blokken.

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

Stel, er was nog een A-blok.

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

maar nu kunnen de overgebleven blokken
nergens geplaatst worden,

dus valt het hele ding uit elkaar.

De Node van Macht stelt Hedge in staat

om een enkele stapel blokken te activeren.

Welke instructies
kan Ethic aan Hedge geven

zodat hij efficiënt

een stabiele stapel palindromen
kan vinden en aandrijven?

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

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

Door te tellen hoe vaak
een bepaalde letter

in een palindroom voorkomt,

zal een nuttig patroon worden onthuld.

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

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

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

die niet optimaal is,

maar wel de klus klaart.

Naïeve oplossingen zijn nuttige methoden
om problemen te analyseren

en werken als opstap
naar betere oplossingen.

De naïeve oplossing voor dit probleem

is een stapel blokken te benaderen,
alle opstellingen te proberen

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

Het probleem bij deze aanpak

is dat het een enorme hoeveelheid
tijd in beslag neemt.

Als Hedge een combinatie
per seconde uitprobeert

zal een stapel van
tien verschillende blokken

hem 42 dagen kosten om af te voeren.

Dat komt doordat de totale tijd
een faculteitsfunctie is

van het totale aantal bestaande blokken.

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

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

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

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

nooit een geheel zal vormen.

Waarom?

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

Wanneer kan een bepaalde sequentie
een palindroom worden?

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

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

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

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

Het patroon hier is dat de meeste letters

een even aantal keer voorkomen

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

Is dat alles?

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

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

dus drie E's is goed.

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

en de laatste C past nergens bij.

Het meest gegeneraliseerde inzicht
is dat hoogstens een letter

een oneven aantal keer kan voorkomen,

maar de rest moet een even aantal zijn.

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

zodat alle informatie
netjes opgeslagen wordt.

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

Als er minder dan twee oneven tekens zijn

kan de stapel omgebouwd worden
tot een palindroom.

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

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

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

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

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

Dit is wat er gebeurt:

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

Teveel tijd.

Ethic en Hedge zijn veilig aangekomen.

Maar Octavia heeft minder geluk.