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.