The Chasm | Think Like A Coder, Ep 6

Traduttore: Revisore: Chiara Polesinanti

[EPISODIO 06 L'ABISSO]

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

Ethic, Hedge e Octavia si trovano sull’orlo di un burrone senza fine.

It’s the only thing between them and the tower

È l'unica cosa che li separa dalla torre

that houses the second of three powerful artifacts.

che ospita il secondo di tre potenti artefatti.

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

Hanno poco tempo per attraversare prima che le guardie ritornino.

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

Senza carburante Hedge non riuscirà a trasportare Ethic,

so the only option is to make a bridge.

quindi l’unica opzione è costruire un ponte.

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

Fortunatamente, i mucchi di pietre che fluttuano lì vicino

sono pezzi del ponte, inventati da Octavia stessa,

invented by Octavia herself— called hover-blocks.

chiamati blocchi sospesi.

Activate a pile with a burst of energy,

Attiva uno dei mucchi con un’esplosione di energia

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

e si assembleranno da soli per far attraversare il burrone a Ethic.

Ma ovviamente c'è un problema.

But there is, of course, a catch.

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

I blocchi sospesi sono stabili

solo se disposti secondo un palindromo perfetto.

Meaning they have to form a sequence

Ovvero devono formare una sequenza

that’s the same when viewed forwards and backwards.

che sia identica quando vista sia in un senso che nell’altro.

The stacks start in random orders,

I mucchi partono con sequenze casuali,

but will always put themselves into a palindromic configuration

ma formeranno sempre una struttura palindroma

if they can.

se questa è possibile.

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

Se arrivano a un punto in cui il palindromo non è possibile,

the bridge will collapse,

il ponte collasserà,

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

e chiunque vi si trovi sopra cadrà nel burrone.

Let’s look at an example.

Vediamo un esempio.

This stack would make itself stable.

Questo mucchio rimarrà stabile.

First the A blocks hold themselves in place.

Prima si posizioneranno i blocchi A.

Then the B’s.

Poi i B.

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

E infine il C si metterà tra i B.

However, suppose there was one more A.

Tuttavia, supponiamo che ci sia ancora un A.

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

Prima si posizioneranno i due blocchi A, poi i due B.

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

Ma ora i rimanenti C e A non avranno dove mettersi,

so the whole thing falls apart.

così l'intera costruzione crollerà.

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

Il Nodo dell’Energia consente a Hedge di dare energia a un solo mucchio.

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

Che istruzioni può dare Ethic a Hedge per permettergli di trovare

and power a stable palindromic stack?

e alimentare un mucchio che diventi un palindromo stabile?

Pause now to figure it out for yourself.

Metti in pausa e cerca di scoprirlo da solo.

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

Esempi di palindromi sono ANNA, RACECAR, e MADAM IM ADAM.

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

Contare il numero di volte in cui una data lettera compare in un palindromo

will reveal a helpful pattern.

rivelerà uno schema utile.

Pause now to figure it out for yourself.

Metti in pausa e cerca di scoprirlo da solo.

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

Cominciamo vedendo una soluzione Naif per questo problema.

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

Una soluzione Naif è un approccio semplice, per tentativi, non ottimizzato,

but will get the job done.

che permette, però, di finire il lavoro.

Naïve solutions are helpful ways to analyze problems,

Le soluzioni Naif rappresentano modi utili per analizzare i problemi

and work as stepping stones to better solutions.

e lavorare per gradi verso soluzioni migliori.

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

In questo caso, una soluzione Naif è quella di affrontare un mucchio,

try all the arrangements,

tentare tutte le disposizioni

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

e vedere se una di queste è un palindromo leggendola in un verso e poi nell’altro.

The problem with this approach

Il problema con questo approccio è che richiede tantissimo tempo.

is that it would take a tremendous amount of time.

If Hedge tried one combination every second,

Se Hedge tentasse una combinazione ogni secondo,

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

per disporre un mucchio di soli 10 blocchi diversi

ci metterebbe 42 giorni.

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

Questo perché il tempo totale necessario è in funzione del fattoriale

of the number of blocks there are.

del numero di blocchi presenti.

10 blocks have over 3 million combinations.

Per 10 blocchi ci sono più di 3 milioni di combinazioni.

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

Questa soluzione Naif ci mostra che abbiamo bisogno di un modo più veloce

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

per predire se un mucchio di blocchi possa formare un palindromo.

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

Per iniziare, potrebbe risultare intuitivo che un mucchio con blocchi tutti diversi

will never form one.

non formerà mai un palindromo.

Why?

Perché?

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

Il primo e l’ultimo blocco non possono essere uguali

se i blocchi sono tutti diversi.

So when can a given sequence become a palindrome?

Allora quando una data sequenza può diventare un palindromo?

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

Per scoprirlo possiamo analizzare alcuni esempi di palindromi.

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

In ANNA ci sono 2 A e 2 N.

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

RACERCAR ha 2 R, 2 A, 2 C e 1 E.

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

E MADAM IM ADAM ha 4 M, 4 A, 2 D e 1 I.

The pattern here is that most of the letters occur

Lo schema qui prevede

che la maggior parte delle lettere siano presenti in numero pari

an even number of times,

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

e che ce ne sia al massimo 1 presente una sola volta.

Is that it?

Tutto qui?

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

E se RACECAR avesse 3 E invece che 1?

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

Potremmo aggiungere le nuove E alle estremità

e avremmo ancora un palindromo.

so 3 is ok.

Quindi 3 vanno bene.

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

Ma mettiamo che ci siano 3 E e 3 C, e non ci sia posto per l’ultima C.

So the most generalized insight is that

Quindi, la regola generale prevede

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

che ci sia al massimo una lettera presente un numero dispari di volte,

but the rest have to be even.

ma le altre devono essere pari.

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

Hedge può contare le lettere di ogni mucchio

e sistemarle in un dizionario,

which is a tidy way of storing information.

che è un modo ordinato di conservare le informazioni.

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

Utilizzando un ciclo si può contare quante volte sono presenti numeri dispari.

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

Se ci sono meno di 2 caratteri dispari, il mucchio può ordinarsi in un palindromo.

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

Questo approccio è decisamente molto più veloce della soluzione Naif.

Instead of factorial time, it takes linear time.

Invece di un tempo fattoriale richiede un tempo lineare.

That’s where the time increases

Ossia il tempo necessario aumenta

in proportion to the number of blocks there are.

in modo proporzionale al numero di blocchi presenti.

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

Ora scrivi un ciclo per Hedge affinché affronti i mucchi uno alla volta

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

e si fermi una volta trovato quello adatto, e sarai pronto per partire.

Here’s what happens:

Ecco cosa succede:

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

Hedge è veloce,

ma ci sono così tanti mucchi che ci mette molto tempo.

Too long.

Troppo.

Ethic and Hedge are safe.

Ethic e Hedge sono in salvo.

But Octavia is not so lucky.

Ma Octavia non è altrettanto fortunata.