Subtitles section Play video

• 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 herselfcalled 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.

• Then the B's.

• And finally the C would nestle right between the B's.

• However, suppose there was one more A.

• First two A blocks form up, then two B's,

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

• 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.

• 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.

• 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.

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

• And MADAM IM ADAM has 4 M's, 4 A's, 2 D's, and 1 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?

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

• so 3 is ok.

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

• 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.

• 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.

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

Subtitles and vocabulary

Operation of videos Adjust the video here to display the subtitles

B1 INT US TED-Ed palindrome hedge ethic stack ravine

Video vocabulary