Лабиринт | Думай по-кодерски — эпизод 8

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

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

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

Упав с башни, Этика и Хедж

оказываются в потоке чистой энергии.

Эта река течёт от Брэдбарьера
до Хаксенбурга.

В этом городе находятся заводы,

производящие роботов,
и хранится Модуль памяти —

последний из трёх артефактов,
который необходимо найти Этике.

После долгого дня и ещё более долгой ночи

они наконец оказываются
в каньоне из бетона и стали.

В самый последний момент

кто-то бросает им верёвку.

Их спасительница, Лемма,
ждала их прибытия.

Когда Этика нашла Модуль
творения в лесной башне,

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

Лидер сопротивления Адила незамедлительно
оповестила своих союзников,

главной из которых была Лемма:

она блестящий учёный и работает
в Хаксенбурге над выводом машин из строя.

К сожалению, роботы тоже
уловили эти радиосигналы

и теперь предпринимали оборонительные меры

по защите артефакта в самом центре города.

Единственный способ попасть туда —
это через лабиринт расходящихся тропок.

Он представляет собой подземную
систему светящихся конвейеров.

Начиная с исходной точки,

каждый отрезок идёт прямо,
а затем разветвляется.

Так происходит с каждой веткой,
снова и снова.

Этих веток тысячи.

К артефакту ведёт только одна тропа,
а все остальные ведут к верной гибели.

К счастью, Модуль творения
дал Хеджу удивительную способность:

теперь он может создавать
более мелкие копии самого себя.

Каждая копия может делать только две вещи:
посылать радиосигнал родителю

и создавать ещё более мелкую
копию самого себя,

которая, в свою очередь,
может делать то же самое,

и так может создаваться
бесконечное количество поколений.

Патруль почти настигает их,
поэтому у Этики нет времени.

Какие инструкции ей следует дать Хеджу,
чтобы найти нужную тропу?

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

Подсказка через: 3

Подсказка через: 2

Подсказка через: 1

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

Рекурсия — это набор указаний,
отсылающих к самим себе.

Это схоже с использованием
самогó слова в его определении,

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

Рекурсия предполагает повторение,
но не такое, как в цикле.

Если в цикле одно действие
повторяется снова и снова,

в рекурсии действие начинается и, прежде
чем будет завершено, используется снова,

и до завершения этого
начинается снова, и так далее.

Это продолжается до тех пор, пока не будет
достигнуто конечное состояние.

Затем информация передаётся
обратно по уровням

до тех пор, пока не достигнет верха
и цикл не будет завершён.

Рекурсия идеально подходит
для ситуаций с самоподобием,

где каждая часть подобна целому.

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

кто посмеет ступить на неё.

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

Ответ через: 3

Ответ через: 2

Ответ через: 1

Эта головоломка на первый взгляд
кажется очень сложной,

но для неё есть невероятно простое
решение с помощью рекурсии.

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

что, если бы весь лабиринт
состоял всего из двух троп?

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

Тогда другая — та,
которая доберётся до артефакта, —

пошлёт сигнал о том,
по какой тропе она двигалась,

и Хедж его получит.

Это называется базовым случаем рекурсии.

А теперь представьте, что из исходной
точки тропа разветвляется дважды

и на каждой развилке копии Хеджа —

назовём их Ветка 1 и Ветка 2 —

создают другие копии,
назовём их Лист 1, 2, 3 и 4.

Три Листа будут уничтожены.

Тот, который достигнет артефакта,
отправит правильный ответ

только своему родителю.

Поэтому если Ветка 1 или 2
ждёт на развилке

и получает радиосигнал,

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

Чтобы дать Хеджу верный маршрут
из того места, где находится он,

Ветка должна сказать, каким путём она шла,

а также то, что она получила по радио.

Этот процесс будет эффективным
вне зависимости от того,

сколько разветвлений придётся пройти.

Каждый ответ, который копия
получает по радиосвязи,

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

и добавив к этому ту тропу,
по которой шла она сама,

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

Мы можем суммировать все указания
в действии под названием «Навигатор»,

которое будет выполнять
каждая копия Хеджа:

1. По достижении артефакта

сообщи по радиосвязи своему родителю,
двигалась ли ты по левой или правой тропе.

2. Когда окажешься на развилке,
сойди с конвейера

и отправь новые копии
по левой и правой тропе.

Дай им задание «Навигатор».

Это и есть рекурсия,

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

3. Если ты услышишь что-то по радио,
сообщи своему родителю,

двигалась ли ты по левой или правой тропе,

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

«Навигатор» — это пример того,
что программисты называют функциями,

подпрограммами или процедурами.

Вне зависимости от используемого термина,
идея остаётся неизменной —

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

возможно, даже сам по себе.

Это идеально подходит для нашего случая —

всю сеть троп можно проследить
с помощью всего трёх указаний.

Происходит следующее.

Когда патруль выворачивает из-за угла,
Этика и Лемма надевают самодельные маски.

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

Наконец, после некоторых помех,
по радио Хеджа слышится ряд указаний.

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

а по пятам за ними мчится отряд роботов.