Башня прозрения | Думай по-кодерски — эпизод 7

Посмотреть урок полностью: https://ed.ted.com/lessons/the-tower-of-epiphany-think-like-a-coder-ep-7

Перед вами седьмой эпизод нашего мультипликационного сериала «Думай по-кодерски». В этом сериале из десяти эпизодов вы познакомитесь с девушкой по имени Этика и её напарником, роботом Хеджем, которые пытаются спасти мир. Они отправляются на поиск трёх артефактов, но по пути им придётся разгадать множество головоломок, связанных с программированием.

Урок — Алекс Розенталь, мультипликация — Kozmonot Animation Studio.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и они упадут.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

затем 4, 4, 4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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