The Tower of Epiphany | Think Like A Coder, Ep 7

Переводчик: Elena McDonnell Редактор: Yulia Kallistratova

Ethic and Hedge are on the ground floor of a massive tower.

Этика и Хедж оказываются на первом этаже огромной башни.

Barriers of energy separate them from their quest’s second goal:

Энергетические барьеры отделяют их от следующей цели —

the Node of Creation.

Модуля творения.

To reach it, Ethic must use three energy streams to climb the tower.

Чтобы добраться до него, Этике нужно использовать три энергетических потока,

которые поднимут её вверх.

As soon as she steps forward a timer will begin counting down from 60 seconds.

Как только она сделает шаг вперёд, таймер начнёт отсчёт 60 секунд.

At the back of the room there’s a basin made of invisible towers

В задней части зала расположен резервуар из невидимых башен,

that can hold energy between them.

между которыми может удерживаться энергия.

After one minute, a torrent of energy will pour down from above,

По прошествии минуты поток энергии обрушится сверху,

filling one unit at a time,

заполняя отсеки один за другим.

with a force field preventing it from spilling out the front or back.

Силовое поле не позволяет энергии выливаться спереди или сзади.

During the 60 calm seconds,

В течение 60 спокойных секунд

Ethic and Hedge must decide exactly how many units of energy will fall.

Этика и Хедж должны определить, сколько единиц энергии будет спущено.

For each of the three challenges,

Для каждого из трёх этапов

they must choose the amount that will fill the basin exactly.

они должны вычислить точное количество энергии, которое заполнит резервуар.

If they do so, the energy will propel them further upwards.

Если им это удастся, энергия поднимет их выше.

But if they get the amount at all wrong, the energy lift will fail,

Но если они ошибутся, энергетический лифт выйдет из строя

dropping them.

и они упадут.

Diagrams on the walls illustrate some examples.

На стенах висят диаграммы с примерами.

This configuration will capture exactly 2 units of energy.

Такая конфигурация может удержать 2 единицы энергии,

This configuration will capture 4— 3 here, and 1 here.

а такая удержит 4 — 3 здесь и 1 здесь.

And this one will also capture 4,

Такая конфигурация тоже удержит 4,

because any energy on the right would spill out.

потому что энергия из правого отсека выльется.

The energy will rain down in such a way

Энергия подаётся сверху таким образом,

that it’ll only overflow if there’s no space that could hold it.

что она выльется только в том случае, если её ничто не будет удерживать.

Hedge can make one tower of blocks visible at a time and count how tall it is,

Хедж может за раз сделать видимым один столбик блоков и подсчитать его высоту,

but he can’t look at the whole structure all at once.

но он не может рассмотреть всю конструкцию целиком.

How does Ethic program Hedge to figure out

Как Этике следует запрограммировать Хеджа, чтобы рассчитать,

exactly how much energy each basin can hold?

сколько энергии поместится в каждый резервуар?

Pause now to figure it out for yourself.

Приостановите видео, чтобы найти ответ самостоятельно.

Here’s one way of thinking about what’s happening:

Один из способов взглянуть на ситуацию следующий:

each unoccupied cell will hold energy

каждая незаполненная клетка удерживает энергию только в том случае,

if and only if there is a wall eventually to its left,

если где-то левее есть стена

and a wall eventually to its right.

и где-то правее есть стена.

But it would take a long time for Hedge to check this for each individual cell.

Но если Хедж будет проверять эти условия для каждой клетки,

на это уйдёт очень много времени.

So what if he were to consider a whole column of blocks at a time?

Что, если он будет одновременно рассматривать весь столбик блоков?

How many units of energy can this hold, for instance?

Например, сколько единиц энергии может удержать эта конфигурация?

Pause now to figure it out for yourself.

Приостановите видео, чтобы найти ответ самостоятельно.

Let’s analyze the problem by looking at our example.

Давайте проанализируем задачу, рассмотрев наш пример.

There are 5 columns of blocks here.

Здесь 5 столбиков блоков.

The leftmost one can’t hold any energy, because there’s nothing higher than it.

Крайний левый не может удерживать энергию, потому что он самый высокий.

The 2nd stack can have 3 units above it,

Второй может уместить 3 единицы,

as they would be trapped between these two 4 block stacks.

потому что они будут удерживаться этими двумя столбиками из 4-х блоков.

We get 3 units by taking the height where the energy would level off— 4,

Мы получаем 3 единицы, взяв высоту верхнего предела 4

and subtracting the height of the stack— so that’s 4 minus 1.

и отняв высоту данного столбика, то есть 4 минус 1.

The 3rd stack is similar— 4 to the left, 4 to the right, and it’s 3 high,

Третий столбик такой же: 4 слева и 4 справа, а высота — 3,

so it’ll hold 4 minus 3 equals 1 unit.

то есть 4 минус 3 равно 1 отсеку.

The 4th stack and 5th stacks have nothing higher than them to the right,

У четвёртого и пятого столбика справа нет столбиков, которые выше их,

so they can’t hold any energy.

поэтому они не будут удерживать энергию.

We can adapt this idea into an algorithm.

На основе этой идеи можно создать алгоритм.

Considering one column at a time as the point of reference,

Взяв один столбик за точку отсчёта,

Hedge can look to the left stack by stack to find the height of the tallest one,

Хедж может двигаться влево, чтобы найти высоту самого высокого столбика,

look to the right to find the height of the tallest one,

а затем сделать то же самое, двигаясь вправо,

and take the smaller of the two as the height the energy can fill up to.

и выбрать меньшее из этих значений как высоту, которой достигнет энергия.

If the result is higher than the column in question,

Если результат выше взятого за основу столбика,

subtract the height of the original column,

вычтите из него высоту исходного столбика.

and the result will be the number of units that column can hold.

Результатом будет количество отсеков этого столбика, где энергия удержится.

If it's equal to or below the level of the column in question,

Если же он равен или ниже взятого за основу столбика,

the energy would spill off.

энергия выльется.

Hedge can apply that to an entire basin with a loop

Хедж может применить алгоритм ко всему резервуару с помощью цикла,

that starts on the left-most column and moves right, one column at a time.

который начинается с крайнего левого столбика и двигается по столбикам вправо.

For each column, he’ll run the same steps— look all the way left for the tallest,

Он выполнит одни и те же шаги для каждого столбика: найдёт самый высокий слева,

do the same to the right, take the lower height of the two,

самый высокий справа; возьмёт меньшее из этих значений,

subtract the original column height,

вычтет из него высоту исходного столбика

and increase the grand total if that number is positive.

и увеличит общий итог, если это положительное число.

His loop will repeat as many times as there are columns.

Цикл повторится столько раз, сколько у нас столбиков.

That will work, but it’ll take a long time for a large basin.

Это поможет достичь цели, но на большой резервуар уйдёт много времени.

At every step Hedge repeats the action of looking left and looking right.

Для каждого шага Хедж должен повторить движение влево и вправо.

If there are N stacks, he’ll look at all N stacks N times.

Если у нас N столбиков, ему придётся рассмотреть N столбиков N раз.

Is there a faster way?

Есть ли более быстрый способ?

Here’s one time saver: before doing anything else,

Вот один способ сэкономить время: прежде чем что-либо делать,

Hedge can start on the left,

Хедж может начать слева

and keep a running tally of what the highest stack is.

и фиксировать самый высокий столбик по нарастающей.

Here that would be 2, 2 again, since the first was higher,

Здесь это будет 2, тут тоже 2, потому что первый столбик был выше,

then 4, 4, 4.

затем 4, 4, 4.

He can then find the highest right-most stacks

Затем он может найти самый высокий столбик справа,

by doing the same going right-to-left: 1, 3, 4, 4, 4.

выполнив то же самое справа налево: 1, 3, 4, 4, 4.

In the end he’ll have a table like this in his memory.

В итоге у него в памяти будет вот такая таблица.

Now, Hedge can take one more pass to calculate how much energy there will be

Теперь Хедж может пройти по столбикам ещё один раз, чтобы подсчитать,

сколько энергии будет над каждым из них, с помощью того же уравнения:

above every stack with the same equation from before:

take the smaller of the stored left and right values,

меньшее из сохранённых значений слева и справа

and subtract the height of the current tower.

минус высота текущего столбика.

Instead of looking at N stacks N times, he’ll look at N stacks just 3 times—

Вместо рассмотрения N столбиков N раз он рассмотрит N столбиков всего 3 раза;

which is what’s called linear time.

это называется линейным временем.

There are ways to optimize the solution even further,

Есть способы ещё более оптимизировать это решение,

but this is good enough for our heroes.

но нашим героям этого достаточно.

Ethic and Hedge work as one.

Этика и Хедж сплочённо работают.

The first cascade is a breeze, and they rise up the tower.

Первый поток совсем не сложный, и они поднимаются на следующий уровень.

The second is a little tougher.

Второй немного сложнее.

The third is huge, with dozens of stacks of blocks.

Третий — самый большой, с дюжинами столбиков.

The timer ticks down towards zero, but Ethic’s program is fast.

Отсчёт таймера приближается к нулю, но программа Этики работает быстро.

She gets the wheel in position just in time,

Она вовремя поворачивает руль в нужное положение,

and the energy lifts them to the Node of Creation.

и энергия поднимает их к Модулю творения.

Like the first, it reveals a vision: memories of years gone by.

Как и первый артефакт, он отображает сцену из прошлого.

The world machine changed everything,

Мировая машина всё изменила,

and Ethic, in her position as chief robotics engineer,

и Этике, которая была главным инженером по робототехнике,

grew troubled by what she saw.

это совсем не понравилось.

When the Bradbarrier went up to keep the people in,

Когда возвели Брэдбарьер и люди не могли выбраться за его пределы,

she knew something was seriously wrong.

она поняла, что что-то не так.

So she created three artifacts

Поэтому она создала три артефакта,

with the ability to restore people’s power, creativity, and memory,

которые могли восстановить силу, творчество и память людей,

and smuggled them to three communities.

и тайно доставила их в три сообщества.

Но прежде чем она смогла рассказать людям, как ими пользоваться,

Before she could tell people how to use them,

the government discovered her efforts and sent bots to arrest her

правительство узнало об этой попытке и приказало роботам арестовать её

and the other programmers.

и других программистов.

The last thing Ethic used the world machine to create

Последним, что она создала с помощью мировой машины,

was a robot that would protect the ancient device

был робот, который сможет защитить древнее устройство от невежества,

from the forces of ignorance by enclosing it in a giant maze.

спрятав его в огромном лабиринте.

She named her creation Hedge.

Она назвала его Хедж.

Without warning, the energy lift flickers, then fizzles out.

Внезапно энергетический лифт начинает мигать, а затем полностью угасает.