The Chasm | Think Like A Coder, Ep 6

תרגום: עריכה: Ido Dekkers

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.

ל 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, יש 2 A ושני N.

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

ל RACECAR יש 2 R, יש 2 A, שני C, ו E אחד.

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

ול MADAM IM ADAM יש 4 M, יש 4 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.

ויש מקסימום 1 שחוזר רק פעם אחת.

Is that it?

האם זהו זה?

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

מה אם ב RACECAR היו 3 E במקום 1?

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

נוכל להוסיף E חדשים בקצוות ועדיין לקבל פלינדרום,

so 3 is ok.

אז 3 בסדר.

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

אבל אם נעשה את זה 3 E ו 3C, אז אין ל 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.

אם יש פחות מ 2 אותיות בכמות אי זוגית, הערמה יכולה להפוך לפלינדרום.

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.

אבל לאוקטביה לא היה מזל.