The Chasm | Think Like A Coder, Ep 6

Reviewer: Prameswari Rahmanu

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

Ethic, Hedge, dan Octavia berdiri di tepi jurang tak berdasar.

It’s the only thing between them and the tower

Hanya itu yang ada di antara mereka dan menara

that houses the second of three powerful artifacts.

yang menampung artefak kedua dari tiga yang kuat.

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

Mereka punya waktu singkat untuk menyeberang sebelum penjaga kembali.

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

Dengan pengukur bahan bakar Hedge kosong, ia tidak akan bisa menerbangkan Ethic,

so the only option is to make a bridge.

jadi, satu-satunya pilihan adalah membuat jembatan.

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

Untungnya, tumpukan batu yang mengapung di dekatnya adalah komponen jembatan—

invented by Octavia herself— called hover-blocks.

ditemukan oleh Octavia sendiri-- disebut hover-block.

Activate a pile with a burst of energy,

Aktifkan tumpukan dengan ledakan energi,

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

dan mereka akan berkumpul sendiri sepanjang jurang saat Ethic melintas.

Namun, tentu saja ada masalah.

But there is, of course, a catch.

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

Hover-block hanya stabil saat palindromik sempurna.

Meaning they have to form a sequence

Artinya mereka harus membentuk urutan

that’s the same when viewed forwards and backwards.

sama ketika dilihat maju dan mundur.

The stacks start in random orders,

Tumpukan mulai dengan pesanan acak,

but will always put themselves into a palindromic configuration

tapi akan selalu menempatkan diri dalam konfigurasi palindromic

if they can.

jika mereka bisa.

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

Jika palindrom tidak memungkinkan,

the bridge will collapse,

jembatan akan runtuh,

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

dan siapa pun yang berada di atasnya akan jatuh ke jurang.

Let’s look at an example.

Mari kita lihat sebuah contoh.

This stack would make itself stable.

Tumpukan ini akan membuat dirinya stabil.

First the A blocks hold themselves in place.

Pertama, balok A menempatkan diri.

Then the B’s.

Lalu balok B.

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

dan akhirnya C akan terletak tepat di antara balok B.

However, suppose there was one more A.

Namun, anggaplah ada satu lagi A.

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

Dua balok A pertama terbentuk, lalu dua balok B,

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

tapi sekarang C dan A yang tersisa tidak punya tempat untuk pergi,

so the whole thing falls apart.

jadi semuanya berantakan.

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

Node of Power memungkinkan Hedge memberi energi satu tumpukan balok.

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

Apa instruksi Ethic pada Hedge agar ia dapat menemukan secara efisien

and power a stable palindromic stack?

dan memberi energi kepada tumpukan palindrom yang stabil?

Pause now to figure it out for yourself.

Jeda sekarang untuk berpikir.

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

Contoh palindrom termasuk ANNA, RACECAR, dan MADAM IM ADAM.

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

Menghitung berapa kali huruf yang diberikan muncul dalam palindrom

will reveal a helpful pattern.

akan mengungkapkan pola yang berguna.

Pause now to figure it out for yourself.

Jeda sekarang untuk mencari tahu sendiri.

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

Mari kita lihat solusi naif untuk masalah ini.

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

Solusi naif adalah pendekatan sederhana, kasar yang tidak dioptimalkan

but will get the job done.

tapi akan menyelesaikan pekerjaan.

Naïve solutions are helpful ways to analyze problems,

Solusi naif adalah cara yang bermanfaat untuk menganalisis masalah

and work as stepping stones to better solutions.

dan bekerja sebagai batu loncatan untuk solusi yang lebih baik.

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

Dalam hal ini, solusi naif adalah mendekati tumpukan balok,

try all the arrangements,

coba semua pengaturan,

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

dan lihat apakah ada palindrom dengan membacanya maju dan mundur.

The problem with this approach

Masalah dengan pendekatan ini

is that it would take a tremendous amount of time.

adalah bahwa itu akan memakan banyak waktu.

If Hedge tried one combination every second,

Jika Hedge mencoba satu kombinasi setiap detik,

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

10 blok yang berbeda akan perlu waktu 42 hari untuk dia buang.

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

Sebab total waktu adalah fungsi faktorial

of the number of blocks there are.

dari jumlah balok yang ada.

10 blocks have over 3 million combinations.

Sepuluh balok memiliki lebih dari 3 juta kombinasi.

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

Solusi naif ini menunjukkan bahwa kita perlu cara yang jauh lebih cepat

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

untuk mengetahui apakah setumpuk balok dapat membentuk palindrom.

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

Untuk memulai, mungkin secara intuitif jelas tumpukan semua balok berbeda

will never form one.

tidak akan membentuk satu.

Why?

Mengapa?

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

Balok pertama dan terakhir tidak bisa sama jika tidak ada pengulangan.

So when can a given sequence become a palindrome?

Jadi, kapan urutan tertentu bisa menjadi palindrom?

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

Satu cara mengetahuinya adalah dengan menganalisis beberapa palindrom yang ada.

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

Di ANNA, ada 2 A dan 2 N.

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

RACECAR memiliki 2 R, 2 A, 2 C, dan 1 E.

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

Dan MADAM IM ADAM memiliki 4 M, 4 A, 2 D, dan 1 I.

The pattern here is that most of the letters occur

Pola di sini adalah sebagian besar huruf muncul

an even number of times,

dalam hitungan genap,

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

dan ada paling banyak 1 yang terjadi sekali saja.

Is that it?

Itu saja?

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

Bagaimana jika RACECAR memiliki 3 E, bukan 1?

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

Kita bisa meletakkan E baru ke ujung dan masih mendapatkan palindrom,

so 3 is ok.

jadi, 3 tidak apa-apa.

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

Namun, buatlah 3 E dan 3 C, dan tidak ada tempat untuk C terakhir.

So the most generalized insight is that

Jadi,wawasan yang paling umum adalah

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

paling banyak satu huruf dapat muncul dalam hitungan ganjil,

but the rest have to be even.

tetapi sisanya harus genap.

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

Hedge dapat menghitung huruf tiap tumpukan dan mengaturnya ke dalam kamus,

which is a tidy way of storing information.

yang merupakan cara rapi menyimpan informasi.

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

Sebuah loop kemudian dapat melewati dan menghitung jumlah angka ganjil muncul

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

Jika ada kurang dari 2 karakter ganjil, tumpukan dapat dibuat menjadi palindrom.

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

Pendekatan ini jauh lebih cepat daripada solusi naif.

Instead of factorial time, it takes linear time.

Alih-alih waktu faktorial, ini memakai waktu linier.

That’s where the time increases

Di situlah waktu meningkat

in proportion to the number of blocks there are.

sebanding dengan jumlah balok yang ada.

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

Sekarang tulis satu loop untuk Hedge untuk mendekati tumpukan secara individual

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

dan berhenti ketika dia menemukan yang bagus, dan Anda akan siap bergerak.

Here’s what happens:

Inilah yang terjadi:

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

Hedge cepat, tetapi ada banyak tumpukan yang membutuhkan waktu lama.

Too long.

Terlalu lama.

Ethic and Hedge are safe.

Etika dan Hedge aman.

But Octavia is not so lucky.

Tapi Octavia tidak seberuntung itu.