The Chasm | Think Like A Coder, Ep 6

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

Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.

Этика, Хедж и Октавия стоят на краю бездонного ущелья,

It’s the only thing between them and the tower

отделяющего их от башни,

that houses the second of three powerful artifacts.

в которой находится второй из трёх могущественных артефактов.

They’ve got a brief window of time to get across before the guards return.

У них очень мало времени,

чтобы перебраться через ущелье до возвращения роботов.

With Hedge’s fuel gauge on empty he won’t be able to fly Ethic across,

У Хеджа заканчивается топливо,

поэтому он не сможет перенести Этику на другую сторону.

so the only option is to make a bridge.

Единственный вариант — это построить мост.

Fortunately, the floating stacks of stones nearby are bridge components—

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

invented by Octavia herself— called hover-blocks.

изобретённые Октавией и называемые ховерблоками.

Activate a pile with a burst of energy,

При активации груды ховерблоков толчком энергии

and they’ll self-assemble to span the ravine as Ethic walks across.

они сформируют мост и позволят Этике перебраться через ущелье.

But there is, of course, a catch.

Конечно, тут есть одно «но».

The hover-blocks are only stable when they’re perfectly palindromic.

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

Meaning they have to form a sequence

Это значит, что они должны сформировать последовательность,

that’s the same when viewed forwards and backwards.

одинаковую в обоих направлениях.

The stacks start in random orders,

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

but will always put themselves into a palindromic configuration

но всегда перестраиваются в палиндром,

if they can.

если это возможно.

If they get to a point where a palindrome isn’t possible,

Если палиндром невозможен,

the bridge will collapse,

мост разрушится,

and whoever’s on it will fall into the ravine.

и те, кто находится на нём, упадут в ущелье.

Let’s look at an example.

Давайте рассмотрим один пример.

This stack would make itself stable.

Из этой груды получится крепкий мост.

First the A blocks hold themselves in place.

Сначала будут установлены блоки A.

Then the B’s.

Затем блоки B.

And finally the C would nestle right between the B’s.

И, наконец, C разместится между ними.

However, suppose there was one more A.

А теперь представьте, что у нас есть ещё один блок A.

First two A blocks form up, then two B’s,

Сначала будут установлены первые два блока A, затем два блока B,

but now the remaining C and A have nowhere to go,

но теперь для оставшихся блоков C и A нет места,

so the whole thing falls apart.

поэтому вся конструкция распадается.

The Node of Power enables Hedge to energize a single stack of blocks.

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

What instructions can Ethic give Hedge to allow him to efficiently find

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

and power a stable palindromic stack?

и зарядить устойчивую палиндромную груду блоков?

Pause now to figure it out for yourself.

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

Examples of palindromes include ANNA, RACECAR, and MADAM IM ADAM.

Примерами палиндромов служат такие слова и фразы,

как ANNA, RACECAR и MADAM IM ADAM.

Counting the number of times a given letter appears in a palindrome

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

will reveal a helpful pattern.

можно выявить закономерность.

Pause now to figure it out for yourself.

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

Let’s first look at a naïve solution to this problem.

Сначала давайте рассмотрим наивное решение этой задачи.

A naïve solution is a simple, brute-force approach that isn’t optimized—

Наивное решение — это простой, грубый метод, не являющийся оптимальным,

but will get the job done.

но тем не менее позволяющий найти ответ.

Naïve solutions are helpful ways to analyze problems,

Наивные решения — это полезные способы анализа задач,

and work as stepping stones to better solutions.

промежуточные ступени на пути к более рациональному решению.

In this case, a naïve solution is to approach a pile of blocks,

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

try all the arrangements,

перебрать все сочетания

and see if one is a palindrome by reading it forward and then backwards.

и узнать, будет ли одно из них палиндромом.

The problem with this approach

Проблема этого метода в том,

is that it would take a tremendous amount of time.

что это займёт огромное количество времени.

If Hedge tried one combination every second,

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

a stack of just 10 different blocks would take him 42 days to exhaust.

на груду из всего десяти блоков у него уйдёт 42 дня.

That’s because the total time is a function of the factorial

А всё потому, что общее время — это факториал

of the number of blocks there are.

количества блоков.

10 blocks have over 3 million combinations.

Из 10 блоков можно составить более 3 миллионов сочетаний.

What this naïve solution shows is that we need a much faster way

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

to tell whether a pile of blocks can form a palindrome.

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

To start, it may be intuitively clear that a pile of all different blocks

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

will never form one.

никогда не сформирует палиндром. Почему?

Why?

The first and last blocks can’t be the same if there are no repeats.

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

So when can a given sequence become a palindrome?

Так когда же последовательность может стать палиндромом?

One way to figure that out is to analyze a few existing palindromes.

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

In ANNA, there are 2 A’s and 2 N’s.

В примере ANNA две буквы A и две буквы N.

RACECAR has 2 R’s, 2 A’s, 2 C’s, and 1 E.

В примере RACECAR — две буквы R, две A, две C и одна E,

And MADAM IM ADAM has 4 M’s, 4 A’s, 2 D’s, and 1 I.

а в MADAM IM ADAM — четыре M, четыре A, две D и одна I.

The pattern here is that most of the letters occur

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

an even number of times,

чётное количество раз,

and there’s at most 1 that occurs just once.

и максимум одна может не иметь пары.

Is that it?

И это всё?

What if RACECAR had 3 E’s instead of 1?

Что, если бы в слове RACECAR было три буквы E, а не одна?

We could tack the new E’s onto the ends and still get a palindrome,

Мы могли бы разместить их в начале и конце слова, и это был бы палиндром,

so 3 is ok.

поэтому три буквы допустимы.

But make that 3 E’s and 3 C’s, and there’s nowhere for the last C to go.

Но если взять три E и три C, то последней букве C не будет места.

So the most generalized insight is that

То есть наиболее обобщённый вывод таков:

at most one letter can appear an odd number of times,

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

but the rest have to be even.

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

Hedge can count the letters in each stack and organize them into a dictionary,

Хедж может подсчитать буквы в каждой груде и упорядочить их в виде словаря;

which is a tidy way of storing information.

это удобный способ хранения информации.

A loop could then go through and count how many times odd numbers appear.

Затем с помощью цикла можно подсчитать, сколько раз встречаются нечётные числа.

If there are less than 2 odd characters, the stack can be made into a palindrome.

Если их там меньше двух, то из груды блоков можно сделать палиндром.

This approach is much, much faster than the naïve solution.

Такой метод гораздо быстрее, чем наивное решение.

Instead of factorial time, it takes linear time.

Вместо факториала здесь линейная зависимость.

That’s where the time increases

То есть время увеличивается

in proportion to the number of blocks there are.

пропорционально количеству блоков.

Now write a loop for Hedge to approach the piles individually,

Теперь напишите цикл, чтобы Хедж подлетал к каждой груде,

and stop when he finds a good one, and you’ll be ready to go.

пока не найдёт нужную, и вам можно будет действовать.

Here’s what happens:

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

Hedge is fast, but there are so many piles it takes a long time.

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

Too long.

Слишком много.

Ethic and Hedge are safe.

Этика и Хедж спасаются,

But Octavia is not so lucky.

но Октавию ждёт другая судьба.