Ethic, Hedge, and Octavia find themselves standing at the edge of a massive ravine. This deep gap is the only thing stopping them from reaching a tower that holds the second of three powerful artifacts they need. They have to act quickly because the guards will be back soon. Unfortunately, Hedge’s fuel is empty, so he can’t fly Ethic across. The only way to get to the other side is by building a bridge.
Luckily, there are floating stacks of stones nearby called hover-blocks. These are special bridge components invented by Octavia. By giving them a burst of energy, the hover-blocks can assemble themselves into a bridge that Ethic can walk across. But there’s a tricky part: the hover-blocks will only stay stable if they form a palindromic sequence. This means the order of the blocks must be the same forwards and backwards. If they can’t form a palindrome, the bridge will collapse, and anyone on it will fall into the ravine.
Let’s look at how these blocks work. Imagine a stack that can stabilize itself. First, the A blocks hold steady, then the B’s, and finally, the C fits perfectly between the B’s. But if there’s an extra A, the sequence can’t balance, and everything falls apart.
Hedge has a special tool called the Node of Power that can energize a stack of blocks. Ethic needs to figure out how to instruct Hedge to find and power a stable palindromic stack efficiently.
Examples of palindromes are words like ANNA, RACECAR, and MADAM IM ADAM. If you count the letters in these words, you’ll notice a pattern. 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. MADAM IM ADAM has 4 M’s, 4 A’s, 2 D’s, and 1 I. Most letters appear an even number of times, and at most, one letter appears an odd number of times.
Initially, you might think of trying every possible arrangement of blocks to see if one is a palindrome. This is called a naïve solution. While it works, it’s incredibly slow. For example, if Hedge tried one combination every second, it would take him 42 days to go through all the possibilities for just 10 blocks!
Instead, there’s a quicker way. Hedge can count the letters in each stack and organize them into a dictionary, which is a neat way to store information. Then, he can loop through and count how many letters appear an odd number of times. If there’s only one or none, the stack can form a palindrome.
This method is much faster because it takes linear time, meaning the time it takes increases in proportion to the number of blocks. Hedge can quickly check each pile and stop when he finds a good one. However, even though Hedge is fast, there are so many piles that it still takes a long time. Ethic and Hedge make it safely across, but unfortunately, Octavia isn’t as lucky.
Imagine you are Ethic, and you need to build a bridge using hover-blocks. Use colored blocks or paper to create a sequence that reads the same forwards and backwards. Try different combinations and see which ones form a stable bridge. Remember, only one block can appear an odd number of times!
Find as many palindromic words as you can in a dictionary or online. Write them down and count the number of letters that appear an odd number of times. Share your findings with the class and discuss why these words are palindromes.
Work in pairs to solve a series of palindrome puzzles. Each puzzle will have a set of letters, and your task is to arrange them into a palindromic sequence. The first pair to solve all puzzles wins a prize!
Using a simple programming language like Python, create a program that checks if a given sequence of letters is a palindrome. Test your program with different sequences and see if it correctly identifies palindromes.
In groups, create a short skit or story that continues the adventure of Ethic, Hedge, and Octavia. Incorporate the concept of palindromes into your story and present it to the class. Be creative and have fun!
**Sanitized Transcript:**
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 have 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—called hover-blocks—invented by Octavia herself.
By activating a pile with a burst of energy, the hover-blocks will self-assemble to span the ravine as Ethic walks across. However, there is a catch: the hover-blocks are only stable when they’re perfectly palindromic, meaning they must form a sequence that’s the same when viewed forwards and backwards. The stacks start in random orders but will always arrange themselves into a palindromic configuration if possible. If they reach a point where a palindrome isn’t possible, the bridge will collapse, and whoever is 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 efficiently find and power a stable palindromic stack?
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.
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. Ten 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 place the new E’s onto the ends and still get a palindrome, so 3 is okay. But if there are 3 E’s and 3 C’s, 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 faster than the naïve solution. Instead of factorial time, it takes linear time, 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 that it takes a long time. Too long. Ethic and Hedge are safe, but Octavia is not so lucky.
Bridge – A connection or link between two separate parts in a program or mathematical concept. – In coding, a bridge function can connect different modules to work together seamlessly.
Hover-blocks – Graphical elements in a coding environment that can be manipulated or moved around to create a program. – Using hover-blocks, students can easily design interactive animations in their coding projects.
Palindrome – A sequence of characters or numbers that reads the same forward and backward. – The number 121 is a palindrome because it remains the same when reversed.
Sequence – An ordered list of numbers or elements that follow a specific pattern or rule. – The Fibonacci sequence is a famous series where each number is the sum of the two preceding ones.
Letters – Characters used in programming and mathematics to represent variables or constants. – In algebra, letters like x and y are often used to denote unknown values.
Count – The process of determining the number of elements in a set or list. – In a loop, the program will count the number of times a condition is met.
Dictionary – A data structure in programming that stores data in key-value pairs. – In Python, a dictionary can be used to store and retrieve data efficiently using keys.
Stable – Referring to a system or solution that remains consistent and reliable under different conditions. – A stable algorithm will produce the same output even if the input order changes.
Solution – The answer to a problem or equation in mathematics or coding. – After solving the equation, the solution for x was found to be 5.
Energy – A concept in mathematics and physics often used to describe the capacity to perform work, sometimes used in algorithms to describe efficiency. – The algorithm was optimized to use less computational energy, making it faster and more efficient.
