The Chasm | Think Like A Coder, Ep 6

المترجم: Maram Turkya المدقّق: omar idmassaoud

فكر كـمبرمج الحاسوب

الموقع: الغابة 198

الحلقة السادسة بعنوان "الهوة"

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 لتتموضع بين الأحجار B.

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.

الرزمة المكونة فقط من 10 أحجار مختلفة ستأخذ منه 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.

عشرة أحجار لديها أكثر من ثلاثة ملايين نمط.

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.

ونمط MADMA 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,

سنتمكن من وضع الـ E في النهايات ويستمر النمط بكونه تناوبي،

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.

ولكن أوكتيفيا ليست بهذا الحظ.