Ethic en Hedge zijn op de begane grond
in een reusachtige toren.
Energiebarrières weerhouden hen ervan
het tweede doel te bereiken:
de Node van Creatie.
Om daar te komen
moet Ethic met behulp van
drie energiestromen de toren beklimmen.
Zodra ze een stap naar voren zet,
telt een timer automatisch 60 seconden af.
Achterin de ruimte staat een reservoir
dat uit onzichtbare torens bestaat,
waartussen energie opgeslagen kan worden.
Nadat er een minuut verstreken is,
stort er een stroom energie naar beneden
die de units een voor een vult,
waarbij een krachtveld
alle overtollige energie tegenhoudt.
Terwijl de seconden rustig verstrijken
moeten Ethic en Hedge exact berekenen
hoeveel energie-units zullen vallen.
Bij elk van deze drie uitdagingen
moeten ze precies uitzoeken
tot hoever de reservoirs gevuld worden.
Als ze het voor elkaar krijgen,
zal de energie hen omhoog katapulteren.
Maar als de berekening niet klopt,
mislukt de energielift
en vallen ze naar beneden.
Wanddiagrammen
illustreren enkele voorbeelden.
Deze configuratie vormt exact
twee energie-units.
Deze configuratie vormt
vier units -- drie hier en een hier.
En ook deze configuratie vormt vier units,
want aan de rechterkant
zal alle energie eruit stromen.
De energie zal zo uit de lucht vallen,
dat het alleen overstroomt
als er geen ruimte is om het op te slaan.
Hedge kan maximaal
één blokkentoren tegelijk zien
en daarvan de hoogte berekenen,
maar hij kan niet de hele constructie
in een oogopslag bekijken.
Hoe kan Ethic Hedge programmeren
om precies te weten te komen
hoeveel energie elk reservoir kan opslaan?
[Pauzeer nu de video
om het zelf uit te zoeken.]
Je kan het op deze manier bekijken:
elke lege cel slaat alleen energie op
als er uiteindelijk links van hem
en rechts van hem een muur staat.
Maar Hedge heeft veel tijd nodig
om elke afzonderlijke cel te bekijken.
Wat als hij overweegt om een voor een
de kolommen van blokken te bekijken?
Hoeveel energie-units zijn er
bijvoorbeeld nodig om dit op te slaan?
[Pauzeer nu de video
om het zelf uit te zoeken.]
Laten we een probleemanalyse maken
met gebruik van ons voorbeeld.
Er zijn vijf kolommen met blokken.
De meest linkse kolom
kan geen energie opslaan,
want daarboven zijn geen units.
Boven de tweede stapel
is er ruimte vrij voor drie units
die dan tussen deze twee stapels
van vier blokken komen te zitten.
Er zijn drie units als we
de afgevlakte energiehoogte -- vier
en de hoogte van de stapel
eraf trekken -- de som is dus 4 min 1.
De derde stapel lijkt hetzelfde --
4 links, 4 rechts en 3 blokken hoog,
dus het slaat 4 min 3 = 1 unit op.
Naast de vierde en vijfde stapels
staan geen hogere stapels
dus daar kan geen energie
opgeslagen worden.
We kunnen dit idee
implementeren als algoritme.
Door de kolommen een voor een
als referentiepunt te overwegen,
kan Hedge vanaf links
een voor een de stapels afgaan
om de hoogste stapel te vinden,
rechts de stapels afgaan
om de hoogste stapel te vinden
en de kleinste stapel
als energielimiet vaststellen.
Als de uitkomst hoger uitpakt
dan de betreffende kolom,
trek dan de hoogte
van de originele kolom eraf
zodat de uitkomst het aantal units
oplevert die deze kolom kan opslaan.
Als het op gelijke hoogte
of onder het niveau
van de betreffende kolom staat,
zal de energie ernaast vallen.
Hedge kan dit met een loop
op een heel reservoir toepassen.
De loop begint bij de meest linkse kolom
en beweegt een kolom per keer naar rechts.
Voor elke kolom legt hij
dezelfde stappen af --
zoek links naar de hoogste kolom,
herhaal dit ook aan de rechterkant,
selecteer de laagste stapel,
trek de oorspronkelijke kolomhoogte eraf
en verhoog het totaal
als de uitkomst een positief getal is.
Zijn loop wordt net zo vaak herhaald
als het aantal aanwezige kolommen.
Dat zal werken, maar het neemt
veel tijd in beslag
voor een groot reservoir.
Bij elke stap herhaalt Hedge de handeling
om naar links en rechts te kijken.
Als er N stapels zijn,
kijkt hij N keren naar alle N stapels.
Kan het sneller?
Zo bespaar je tijd:
voordat hij actie onderneemt,
kan Hedge aan de linkerkant beginnen
en een turfschema bijhouden
van de hoogste stapel.
Hier is dat 2, nogmaals 2,
omdat de eerste stapel hoger was,
daarna drie keer een 4.
Zo kan hij de hoogste,
meest uiterst rechtse stapels vinden
door dit ook van rechts
naar links te doen: 1, 3, 4, 4, 4.
Uiteindelijk staat deze tabel
in zijn geheugen opgeslagen.
Hedge kan nogmaals proberen te berekenen
hoeveel energie er zal zijn
boven elke stapel met dezelfde
vergelijking als voorheen:
neem de kleinste
van de linkse en rechtse waarden
en trek de hoogte eraf
van de huidige toren.
In plaats van N keer
te kijken naar N stapels,
kijkt hij alleen 3 keer naar N stapels --
dit heet lineaire tijd.
Er zijn zelfs manieren om deze oplossing
verder te optimaliseren,
maar dit werkt prima voor onze helden.
Ethic en Hedge zijn een hecht team.
De eerste stortvloed
valt makkelijk te omzeilen
en ze stijgen richting de top.
De tweede stortvloed
valt iets moeilijker te omzeilen.
De derde stortvloed is ontzettend groot
en bevat tientallen stapels blokken.
De timer telt af naar nul,
maar Ethic gebruikt een snelle applicatie.
Ze zet het wiel binnen de tijd
op de juiste positie ...
en de energie katapulteert hen
naar de Node van Creatie.
Net als de eerste Node
onthult het een visie:
gebeurtenissen van jaren geleden.
De wereldmachine veranderde alles
en Ethic, in haar functie als
hoofd robotica-technicus,
maakte zich zorgen door wat ze zag.
Toen de Bradbarrière omhoog steeg
om het volk binnen te houden,
wist ze dat er iets ergs aan de hand was.
Daarom creëerde ze drie artefacten
die macht, creativiteit en geheugen
van het volk kunnen terughalen
en smokkelde ze mee
naar drie gemeenschappen.
Voor ze het volk hierover kon vertellen,
ontdekte de overheid Ethics inspanningen
en gaf de bots de opdracht om haar
en de andere programmeurs te arresteren.
Ethic heeft de machine
voor de laatste keer gebruikt
om een robot te creëren
die het oude apparaat beschermt
tegen de krachten van onwetendheid
door het te omheinen in een grote doolhof.
Ze benoemde haar creatie Hedge.
Plotseling knippert
de energielift en valt hij uit.