The Chasm | Think Like A Coder, Ep 6

Key Takeaways

[Applause] [Music] ethic hedge and Octavius 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 hedges 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 herself called 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 cache 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 bees and finally the sea would Nestle right between the bees however suppose there was one more a first two a blocks form up then two bees but now the remaining C and a have nowhere to go so the whole thing falls apart the note 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 examples of palindromes include anna racecar and madam I'm Adam counting the number of times a given letter appears in a palindrome will reveal a helpful pattern let's first look at a naive solution to this problem a naive solution is a simple brute-force approach that isn't optimized but will get the job done naive solutions are helpful ways to analyze problems and work as stepping stones to better solutions in this case a naive 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 naive 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 two A's and two ends race car has two R's two A's to seize and one e and madam I'm Adam has four M's for a s 2 DS and 1 AI the pattern here is that most of the letters occur an even number of times and there's at most one that occurs just once is what if racecar had three e's instead of one we could tack the new ease on to the ends and still get a palindrome so three is okay but make that three e's and three 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 two odd characters the stack can be made into a palindrome this approach is much much faster than the naive 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 edge is fast but there are so many piles it takes a long time too long [Music] [Music] [Music] ethic and hedge are safe but Octavia is not so lucky continue the adventure in Episode seven of think like a coder or restart the journey with episode 1 and don't forget to subscribe [Music]