The Chasm | Think Like A Coder, Ep 6

Translator: sann tint Reviewer: Myo Aung

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

Ethic Hedge နဲ့ Octavia တို့ဟာ အသူတစ်ရာ နက်တဲ့ ချောက်ကမ်းပါမှာ ရပ်နေတယ်။

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,

Hedge ရဲ့ ဗလာဖြစ်နေတဲ့ ကိရိယာနဲ့ဆို သူဟာ Ethic ဆီ ဖြတ်ကူးနိုင်မှာ မဟုတ်တော့​

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.

Octavia ကိုယ်တိုင် တီထွင်ထားတဲ့ ဝဲပျံနေတဲ့ ကျောက်တုံးများလို့ခေါ်ပါတယ်။

Activate a pile with a burst of energy,

စွမ်းအင်ပေါက်ကွဲတစ်ခုနဲ့အတူ အပုံကြီးကို အသက်သွင်းပါ။

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

Ethic ဖြတ်လျှောက်စဉ်မှာ ချောက်ကို တံတားခင်းဖို့ အလိုလို တပ်ဆင်သွားမယ်။

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.

Node of Power က အတုံးတွေရဲ့ တစ်ခုတည်းသော အပုံကို အားရှိစေဖို့ Hedge ကို ကူပေးတယ်။

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

တည်ငြိမ်တဲ့ ရှေ့ပြန်နောက်ပြန်ညီတဲ့ အပုံတစ်ပုံကို Hedge အချိန်တိုတိုနဲ့တွေ့ကာ

and power a stable palindromic stack?

မောင်းနှင်ဖြစ်ဖို့ သူ့ကို Ethic က ဘာညွှန်ကြားချက်တွေ ပေးနိုင်လဲ။

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,

Hedge ဟာ စက္ကန့်တိုင်း အတွဲတစ်ခုကို စမ်းသပ်ကြည့်တယ်ဆိုရင်

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

အတုံး ၁၀ မျိုးသာရှိတဲ့ အဆင့်တစ်ခုဟာ ပြီးပြည့်စုံဖို့ ၄၂ ရက် ကြာလိမ့်မယ်။

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.

ပြီးတော့ MADAM IM ADAM မှာ M ၄ ခု၊ 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,

Hedge ဟာ အဆင့်တိုင်းထဲက စာလုံးတွေကို ရေပြီး အဘိဓာန်လို့ စီစဉ်နိုင်တယ်။

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,

အပုံတွေကို တစ်ခုချင်း ချဉ်းကပ်ဖို့ Hedge အတွက် ကျော့ကွင်းတစ်ခုကို အခု ရေးပြီး

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.

Hedge ဟာ လျင်မြန်ပေမဲ့ အပုံတွေက သိပ်များလွန်းတော့ အချိန်အကြာကြီး ယူရတယ်။

Too long.

ကြာကို ကြာလွန်းတာပါ။

Ethic and Hedge are safe.

Ethic နဲ့ Hedge ဟာ ဘေးကင်းပေမဲ့

But Octavia is not so lucky.

Octavia ကတော့ ကံသိပ်မကောင်းရှာဘူး။