The Chasm | Think Like A Coder, Ep 6

Reviewer: Dinh Lieu Vu

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

Ethic, Hedge, và Octavia đứng trước bờ vực thẳm.

It’s the only thing between them and the tower

Đó là thứ duy nhất ngăn cách họ tiến tới tòa tháp

that houses the second of three powerful artifacts.

mà cất giấu hiện vật thứ hai trong số ba hiện vật.

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

Họ chỉ có khoảng thời gian ít ỏi

để vượt qua bên đó trước khi lũ người máy quay trở lại.

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

Năng lượng của Hedge không đủ để có thể đưa Ethic bay sang bên đó,

so the only option is to make a bridge.

vậy nên lựa chọn duy nhất là làm cầu bắc qua.

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

May thay, những tảng đá nổi gần đó sẽ là vật liệu làm cầu—

invented by Octavia herself— called hover-blocks.

loại đá này do Octavia tự phát minh— được gọi là các khối-lơ lửng.

Activate a pile with a burst of energy,

Kích hoạt một khối đá với một nguồn năng lượng bùng nổ,

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

và nó sẽ tự lắp ráp với nhau thành nhịp cầu để Ethic có thể đi qua.

Nhưng tất nhiên là có đi kèm vướng mắc.

But there is, of course, a catch.

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

Các khối-lơ lửng chỉ ổn định khi chúng ở một trạng thái đồng nhất.

Meaning they have to form a sequence

Tức là tạo thành một trình tự

that’s the same when viewed forwards and backwards.

giống nhau từ trước tới sau.

The stacks start in random orders,

Các khối đá có thứ tự ngẫu nhiên,

but will always put themselves into a palindromic configuration

nhưng luôn luôn thiết lập chúng theo một trình tự nhất định

if they can.

nếu có thể.

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

Nếu sắp xếp không theo trình tự nhất định,

the bridge will collapse,

thì cây cầu sẽ sập,

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

và bất kì ai ở trên cây cầu sẽ rơi ngay xuống vực.

Let’s look at an example.

Hãy xem qua một ví dụ.

This stack would make itself stable.

Đây là khối đá sẽ tạo ra sự ổn định.

First the A blocks hold themselves in place.

Đầu tiên, các khối đá A sẽ tự dính chặt.

Then the B’s.

Rồi đến khối đá B.

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

Và cuối cùng là khối đá C lồng giữa hai khối đá B.

However, suppose there was one more A.

Tuy nhiên, giả sử có thêm một khối A.

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

Đầu tiên sẽ vẫn là hai khối đá A, rồi đến hai khối đá B,

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

nhưng giờ đây ta có khối đá C và A cùng xếp chung với nhau,

so the whole thing falls apart.

và khi này mọi thứ sẽ tan rã.

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

Viên Đá Sức Mạnh cho phép Hedge

cấp năng lượng cho một chồng các khối đá.

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

Vậy chỉ dẫn gì mà Ethic có thể đưa ra cho Hedge giúp nó tìm

and power a stable palindromic stack?

và nạp năng lượng hiệu quả cho một khối đá ổn định?

Pause now to figure it out for yourself.

Tạm dừng một lúc để chúng ta có thể hình dung.

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

Ví dụ về trình tự bao gồm ANNA, RACECAR, và MADAM IM ADAM.

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

Đếm số lần đưa ra những kí tự xuất hiện trong trình tự này

will reveal a helpful pattern.

sẽ tìm ra giải pháp cho tình thế này.

Pause now to figure it out for yourself.

Tạm dừng một lúc để chúng ta có thể hình dung.

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

Hãy tính đến một giải pháp ngây thơ

cho vấn đề này.

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

Giải pháp ngây thơ

là một cách tiếp cận đơn giản, thô bạo và không được tối ưu hóa—

but will get the job done.

nhưng vẫn sẽ xong việc.

Naïve solutions are helpful ways to analyze problems,

Giải pháp ngây thơ sẽ có ích khi phân tích vấn đề,

and work as stepping stones to better solutions.

và là bước đệm đưa tới các giải pháp tốt hơn.

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

Trong trường hợp này,

ta sẽ tiếp cận với một chồng các khối đá,

try all the arrangements,

thử sắp xếp chúng,

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

và xem liệu có khối đá nào tuân theo trình tự từ trước tới sau.

The problem with this approach

Vấn đề của cách tiếp cận này

is that it would take a tremendous amount of time.

đó là nó sẽ mất rất nhiều thời gian.

If Hedge tried one combination every second,

Nếu Hedge cố thử một tổ hợp mỗi giây,

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

với một chồng với mười khối đá khác nhau

sẽ mất tới 42 ngày làm việc kiệt sức.

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

Đó là bởi vì tổng thời gian là một hàm giai thừa

of the number of blocks there are.

của số lượng khối đá.

10 blocks have over 3 million combinations.

Mười khối đã có trên 3 triệu tổ hợp.

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

Những gì mà giải pháp ngây thơ cho thấy

đó là chúng ta cần một cách nhanh hơn

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

để biết khi nào một khối đá có thể sắp xếp thành một trình tự.

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

Để bắt đầu,

bằng trực giác ta biết rằng một tập hợp các khối khác nhau

will never form one.

sẽ không tạo ra một trình tự phù hợp.

Why?

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

Những khối đầu tiên và cuối cùng

không thể giống nhau nếu không có sự lặp lại.

So when can a given sequence become a palindrome?

Vậy khi nào thì sẽ tạo ra được một trình tự phù hợp?

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

Cách để hình dung ra đó là phân tích các chuỗi sẵn có.

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

Với chuỗi ANNA, có hai chữ A và hai chữ N.

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

Chuỗi RACECAR có hai chữ R, hai chữ A, hai chữ C, và một chữ E.

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

Và chuỗi MADAM IM ADAM có bốn chữ M, bốn chữ A,

hai chữ D, và một chữ I.

The pattern here is that most of the letters occur

Với công thức này thì hầu hết các kí tự xuất hiện

an even number of times,

với số lần chẵn,

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

và duy chỉ có một kí tự xuất hiện đúng một lần.

Is that it?

Phải vậy không?

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

Vậy nếu RACECAR có ba chữ E thay vì chỉ một?

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

Chúng ta có thể nhặt hai chữ E

vào hai đầu và sẽ có một trình tự hợp lý,

so 3 is ok.

vậy nên ba E vẫn ổn.

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

Nhưng nếu có ba E và ba C,

thì sẽ không xếp chữ C cuối cùng vào đâu được.

So the most generalized insight is that

Và tổng quát hóa

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

hầu hết các kí tự có thể xuất hiện theo số lần chẵn

but the rest have to be even.

nhưng số lần xuất hiện của kí tự cuối sẽ là số lẻ.

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

Hedge có thể đếm các kí tự trong mỗi khối

và tổ chức chúng thành từ điển,

which is a tidy way of storing information.

đó là cách lưu trữ thông tin có trật tự.

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

Một vòng lặp có thể duyệt

và đếm ra bao nhiêu lần số chẵn xuất hiện.

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

Nếu ít hơn hai kí tự là chẵn,

thì khối đó có thể tạo thành một trình tự hợp lí.

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

Cách tiếp cận này nhanh hơn rất nhiều

so với cách trước.

Instead of factorial time, it takes linear time.

Thay vì tính giai thừa số lần, thì ta tính số lần tuyến tính.

That’s where the time increases

Đó là chỗ mà thời gian tăng lên

in proportion to the number of blocks there are.

tương ứng với số khối đá.

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

Bây giờ, hãy viết một vòng lặp

để Hedge tiếp cận các khối đá riêng lẻ

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

và dừng lại khi nó tìm thấy một khối phù hợp

và hãy bắt đầu thôi.

Here’s what happens:

Đây là những gì sảy ra:

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

Hedge rất nhanh, nhưng có quá nhiều khối đá

và mất rất nhiều thời gian.

Too long.

Rất lâu.

Ethic and Hedge are safe.

Ethic và Hedge đã may mắn thoát được.

But Octavia is not so lucky.

Nhưng Octavia thì không.