1
00:00:31,587 --> 00:00:36,148
Ethic en Hedge zijn op de begane grond
in een reusachtige toren.

2
00:00:37,288 --> 00:00:41,945
Energiebarrières weerhouden hen ervan
het tweede doel te bereiken:

3
00:00:41,945 --> 00:00:43,945
de Node van Creatie.

4
00:00:52,667 --> 00:00:53,619
Om daar te komen

5
00:00:53,619 --> 00:00:57,479
moet Ethic met behulp van
drie energiestromen de toren beklimmen.

6
00:00:57,479 --> 00:00:59,407
Zodra ze een stap naar voren zet,

7
00:00:59,407 --> 00:01:03,479
telt een timer automatisch 60 seconden af.

8
00:01:07,359 --> 00:01:11,659
Achterin de ruimte staat een reservoir 
dat uit onzichtbare torens bestaat,

9
00:01:11,659 --> 00:01:14,725
waartussen energie opgeslagen kan worden.

10
00:01:14,725 --> 00:01:18,865
Nadat er een minuut verstreken is, 
stort er een stroom energie naar beneden

11
00:01:18,865 --> 00:01:21,015
die de units een voor een vult,

12
00:01:21,015 --> 00:01:25,475
waarbij een krachtveld 
alle overtollige energie tegenhoudt.

13
00:01:25,475 --> 00:01:27,615
Terwijl de seconden rustig verstrijken

14
00:01:27,615 --> 00:01:32,713
moeten Ethic en Hedge exact berekenen
hoeveel energie-units zullen vallen.

15
00:01:32,713 --> 00:01:34,403
Bij elk van deze drie uitdagingen

16
00:01:34,403 --> 00:01:38,098
moeten ze precies uitzoeken
tot hoever de reservoirs gevuld worden.

17
00:01:38,098 --> 00:01:41,918
Als ze het voor elkaar krijgen, 
zal de energie hen omhoog katapulteren.

18
00:01:41,918 --> 00:01:46,568
Maar als de berekening niet klopt,
mislukt de energielift

19
00:01:46,568 --> 00:01:48,098
en vallen ze naar beneden.

20
00:01:48,098 --> 00:01:51,348
Wanddiagrammen
illustreren enkele voorbeelden.

21
00:01:51,348 --> 00:01:55,608
Deze configuratie vormt exact 
twee energie-units.

22
00:01:55,608 --> 00:02:00,735
Deze configuratie vormt 
vier units -- drie hier en een hier.

23
00:02:00,735 --> 00:02:03,275
En ook deze configuratie vormt vier units,

24
00:02:03,275 --> 00:02:06,678
want aan de rechterkant
zal alle energie eruit stromen.

25
00:02:06,678 --> 00:02:10,910
De energie zal zo uit de lucht vallen,
dat het alleen overstroomt

26
00:02:10,910 --> 00:02:13,498
als er geen ruimte is om het op te slaan.

27
00:02:13,498 --> 00:02:17,175
Hedge kan maximaal 
één blokkentoren tegelijk zien

28
00:02:17,175 --> 00:02:18,875
en daarvan de hoogte berekenen,

29
00:02:18,875 --> 00:02:22,725
maar hij kan niet de hele constructie 
in een oogopslag bekijken.

30
00:02:22,725 --> 00:02:26,360
Hoe kan Ethic Hedge programmeren 
om precies te weten te komen

31
00:02:26,360 --> 00:02:29,340
hoeveel energie elk reservoir kan opslaan?

32
00:02:29,340 --> 00:02:32,795
[Pauzeer nu de video
om het zelf uit te zoeken.]

33
00:02:38,805 --> 00:02:41,615
Je kan het op deze manier bekijken:

34
00:02:41,615 --> 00:02:44,697
elke lege cel slaat alleen energie op

35
00:02:44,697 --> 00:02:48,607
als er uiteindelijk links van hem

36
00:02:48,607 --> 00:02:51,497
en rechts van hem een muur staat.

37
00:02:51,497 --> 00:02:56,322
Maar Hedge heeft veel tijd nodig 
om elke afzonderlijke cel te bekijken.

38
00:02:56,322 --> 00:03:01,175
Wat als hij overweegt om een voor een 
de kolommen van blokken te bekijken?

39
00:03:01,175 --> 00:03:05,025
Hoeveel energie-units zijn er 
bijvoorbeeld nodig om dit op te slaan?

40
00:03:05,025 --> 00:03:08,049
[Pauzeer nu de video
om het zelf uit te zoeken.]

41
00:03:10,349 --> 00:03:13,759
Laten we een probleemanalyse maken 
met gebruik van ons voorbeeld.

42
00:03:13,759 --> 00:03:15,894
Er zijn vijf kolommen met blokken.

43
00:03:15,894 --> 00:03:18,414
De meest linkse kolom 
kan geen energie opslaan,

44
00:03:18,414 --> 00:03:20,484
want daarboven zijn geen units.

45
00:03:20,484 --> 00:03:23,201
Boven de tweede stapel
is er ruimte vrij voor drie units

46
00:03:23,201 --> 00:03:27,244
die dan tussen deze twee stapels 
van vier blokken komen te zitten.

47
00:03:27,244 --> 00:03:32,186
Er zijn drie units als we 
de afgevlakte energiehoogte -- vier

48
00:03:32,186 --> 00:03:36,346
en de hoogte van de stapel 
eraf trekken -- de som is dus 4 min 1.

49
00:03:36,346 --> 00:03:41,808
De derde stapel lijkt hetzelfde -- 
4 links, 4 rechts en 3 blokken hoog,

50
00:03:41,808 --> 00:03:46,537
dus het slaat 4 min 3 = 1 unit op.

51
00:03:46,537 --> 00:03:50,875
Naast de vierde en vijfde stapels
staan geen hogere stapels

52
00:03:50,875 --> 00:03:53,427
dus daar kan geen energie 
opgeslagen worden.

53
00:03:53,427 --> 00:03:57,245
We kunnen dit idee 
implementeren als algoritme.

54
00:03:57,245 --> 00:04:01,015
Door de kolommen een voor een 
als referentiepunt te overwegen,

55
00:04:01,015 --> 00:04:03,651
kan Hedge vanaf links
een voor een de stapels afgaan

56
00:04:03,651 --> 00:04:05,396
om de hoogste stapel te vinden,

57
00:04:05,396 --> 00:04:08,063
rechts de stapels afgaan
om de hoogste stapel te vinden

58
00:04:08,063 --> 00:04:12,833
en de kleinste stapel
als energielimiet vaststellen.

59
00:04:12,833 --> 00:04:15,963
Als de uitkomst hoger uitpakt 
dan de betreffende kolom,

60
00:04:15,963 --> 00:04:18,537
trek dan de hoogte 
van de originele kolom eraf

61
00:04:18,537 --> 00:04:22,984
zodat de uitkomst het aantal units 
oplevert die deze kolom kan opslaan.

62
00:04:23,444 --> 00:04:24,651
Als het op gelijke hoogte

63
00:04:24,651 --> 00:04:27,244
of onder het niveau 
van de betreffende kolom staat,

64
00:04:27,244 --> 00:04:29,397
zal de energie ernaast vallen.

65
00:04:29,397 --> 00:04:32,927
Hedge kan dit met een loop 
op een heel reservoir toepassen.

66
00:04:32,927 --> 00:04:37,975
De loop begint bij de meest linkse kolom
en beweegt een kolom per keer naar rechts.

67
00:04:38,605 --> 00:04:41,642
Voor elke kolom legt hij
dezelfde stappen af --

68
00:04:41,642 --> 00:04:43,913
zoek links naar de hoogste kolom,

69
00:04:43,913 --> 00:04:47,201
herhaal dit ook aan de rechterkant,
selecteer de laagste stapel,

70
00:04:47,201 --> 00:04:49,318
trek de oorspronkelijke kolomhoogte eraf

71
00:04:49,318 --> 00:04:53,178
en verhoog het totaal
als de uitkomst een positief getal is.

72
00:04:53,178 --> 00:04:56,848
Zijn loop wordt net zo vaak herhaald
als het aantal aanwezige kolommen.

73
00:04:56,848 --> 00:04:59,574
Dat zal werken, maar het neemt
veel tijd in beslag

74
00:04:59,574 --> 00:05:00,798
voor een groot reservoir.

75
00:05:00,798 --> 00:05:05,328
Bij elke stap herhaalt Hedge de handeling 
om naar links en rechts te kijken.

76
00:05:05,328 --> 00:05:10,280
Als er N stapels zijn, 
kijkt hij N keren naar alle N stapels.

77
00:05:10,280 --> 00:05:12,260
Kan het sneller?

78
00:05:12,260 --> 00:05:15,608
Zo bespaar je tijd:
voordat hij actie onderneemt,

79
00:05:15,608 --> 00:05:17,468
kan Hedge aan de linkerkant beginnen

80
00:05:17,468 --> 00:05:21,338
en een turfschema bijhouden 
van de hoogste stapel.

81
00:05:21,338 --> 00:05:25,098
Hier is dat 2, nogmaals 2, 
omdat de eerste stapel hoger was,

82
00:05:25,098 --> 00:05:27,848
daarna drie keer een 4.

83
00:05:27,848 --> 00:05:30,714
Zo kan hij de hoogste, 
meest uiterst rechtse stapels vinden

84
00:05:30,714 --> 00:05:36,492
door dit ook van rechts
naar links te doen: 1, 3, 4, 4, 4.

85
00:05:36,882 --> 00:05:40,663
Uiteindelijk staat deze tabel 
in zijn geheugen opgeslagen.

86
00:05:40,663 --> 00:05:45,961
Hedge kan nogmaals proberen te berekenen 
hoeveel energie er zal zijn

87
00:05:45,961 --> 00:05:50,001
boven elke stapel met dezelfde 
vergelijking als voorheen:

88
00:05:50,001 --> 00:05:53,638
neem de kleinste 
van de linkse en rechtse waarden

89
00:05:53,638 --> 00:05:56,708
en trek de hoogte eraf 
van de huidige toren.

90
00:05:56,708 --> 00:05:59,565
In plaats van N keer 
te kijken naar N stapels,

91
00:05:59,565 --> 00:06:02,273
kijkt hij alleen 3 keer naar N stapels --

92
00:06:02,273 --> 00:06:04,573
dit heet lineaire tijd.

93
00:06:04,573 --> 00:06:07,814
Er zijn zelfs manieren om deze oplossing
verder te optimaliseren,

94
00:06:07,814 --> 00:06:10,564
maar dit werkt prima voor onze helden.

95
00:06:10,564 --> 00:06:12,684
Ethic en Hedge zijn een hecht team.

96
00:06:14,952 --> 00:06:17,197
De eerste stortvloed
valt makkelijk te omzeilen

97
00:06:17,197 --> 00:06:18,956
en ze stijgen richting de top.

98
00:06:21,573 --> 00:06:24,133
De tweede stortvloed
valt iets moeilijker te omzeilen.

99
00:06:33,051 --> 00:06:36,891
De derde stortvloed is ontzettend groot 
en bevat tientallen stapels blokken.

100
00:06:36,891 --> 00:06:39,156
De timer telt af naar nul,

101
00:06:39,156 --> 00:06:41,344
maar Ethic gebruikt een snelle applicatie.

102
00:06:41,344 --> 00:06:44,528
Ze zet het wiel binnen de tijd 
op de juiste positie ...

103
00:06:49,015 --> 00:06:51,935
en de energie katapulteert hen 
naar de Node van Creatie.

104
00:06:55,640 --> 00:06:58,423
Net als de eerste Node 
onthult het een visie:

105
00:06:58,423 --> 00:07:01,057
gebeurtenissen van jaren geleden.

106
00:07:01,057 --> 00:07:03,187
De wereldmachine veranderde alles

107
00:07:03,187 --> 00:07:06,856
en Ethic, in haar functie als 
hoofd robotica-technicus,

108
00:07:06,856 --> 00:07:08,876
maakte zich zorgen door wat ze zag.

109
00:07:08,876 --> 00:07:11,892
Toen de Bradbarrière omhoog steeg 
om het volk binnen te houden,

110
00:07:11,892 --> 00:07:14,576
wist ze dat er iets ergs aan de hand was.

111
00:07:14,576 --> 00:07:16,676
Daarom creëerde ze drie artefacten

112
00:07:16,676 --> 00:07:21,221
die macht, creativiteit en geheugen 
van het volk kunnen terughalen

113
00:07:21,221 --> 00:07:24,121
en smokkelde ze mee
naar drie gemeenschappen.

114
00:07:24,121 --> 00:07:26,519
Voor ze het volk hierover kon vertellen,

115
00:07:26,519 --> 00:07:30,090
ontdekte de overheid Ethics inspanningen 
en gaf de bots de opdracht om haar

116
00:07:30,090 --> 00:07:31,999
en de andere programmeurs te arresteren.

117
00:07:31,999 --> 00:07:35,209
Ethic heeft de machine 
voor de laatste keer gebruikt

118
00:07:35,209 --> 00:07:37,979
om een robot te creëren 
die het oude apparaat beschermt

119
00:07:37,979 --> 00:07:39,799
tegen de krachten van onwetendheid

120
00:07:39,799 --> 00:07:42,329
door het te omheinen in een grote doolhof.

121
00:07:42,329 --> 00:07:44,743
Ze benoemde haar creatie Hedge.

122
00:07:51,801 --> 00:07:55,631
Plotseling knippert 
de energielift en valt hij uit.