The adventure continues! Episode 8: Ethic and Hedge find themselves at a gauntlet of forking paths. Can they find the right one before they’re captured? Find out with episode 8: bit.ly/TLACEp8 And make sure you don't miss another episode by subscribing and smashing the bell!
The only people who managed to give education a plot. I'm going to have to re-watch all 9 just so I can pay attention to the processes more XD. Thank you Ted Ed
I actually found an mistake at 6:04 the graphs shows a linear and exponential growth however N² is not exponential but rather ( maybe I don't know what to call it ) quadratic growth while the exponential growth is (a)^N. But you guys did a great job 👍 and the most loving part was animation 💗
Check some easy problems from programming contests. Of course there aren't any animations (sometime stories), but thats not the case if you are looking for problems to solve.. For example problems "A" from codeforce, in my opinion similar difficulity (in average).
I knew it, the final story is about the importance of morals and ethics in everything including the world of computers and programming. Ethic is one of the few programmers with ethics and the broken world is due to the result of government programmers lacking ethics.
@@lambertlazaro2407 Well computers are also included in science. Yes, agreed all sectors needs ethics, not just computers. From theoretical physics, nuclear physics to biology etc.
One good way is to find the largest height then you find similarly to left of max and to right by keep track of second max while the running the loop it will be liner and constant space
I was able to solve it in about 7 minutes and that made me feel happy, thank you ted, keep it up. I would have shared the way I solved it by a photo if i could. Eritrean civil engineer currently in sudan.
@@ANlMO In Java: import java.util.Random; public class solution {
public static void main(String[] args) { // Randomizer for random number generation Random random = new Random(); // Array with the puzzle blocks, will be random // This is the amount of columns in the puzzle // +3 hence the randomizer starts at 0, min of 3 columns int[] maze = new int[random.nextInt(10) + 3]; // Generate random column heights in the maze // Heights from 0 to 10 at random for (int i = 0; i < maze.length; ++i) { maze[i] = random.nextInt(10); } // Highest column, highest column index int highCol = Integer.MIN_VALUE, highColIndex = 0; // Left to right, grab highest column for (int i = 0; i < maze.length; i++) { if (maze[i] > highCol) { highCol = maze[i]; highColIndex = i; } } // Second highest column, its index int secHighCol = Integer.MIN_VALUE, secHighColIndex = 0; // Right to left, grab second highest column for (int j = maze.length - 1; j >= 0; --j) { if (maze[j] > secHighCol && j != highColIndex && highColIndex != j + 1 && highColIndex != j - 1) { secHighCol = maze[j]; secHighColIndex = j; } } // Calculate sum of energy int sumOfEnergy = 0; if (highCol!=0&&secHighCol!=0) { // Start at the smaller index of both // Then calculate smaller height minus amount of existing blocks if (secHighColIndex < highColIndex) { for (int i = secHighColIndex + 1; i < highColIndex; i++) { sumOfEnergy += secHighCol - maze[i]; } } else { for (int i = highColIndex + 1; i < secHighColIndex; i++) { sumOfEnergy += secHighCol - maze[i]; } } } // Test console output StringBuilder stringBuilder = new StringBuilder(); int mazeSum = 0; for (int i : maze) { mazeSum += i; } for (int i = 0; i < mazeSum; ++i) { for (int j = maze.length-1; j >= 0; --j) { if (maze[j] > 0) { stringBuilder.append("X"); maze[j] -= 1; } else { stringBuilder.append(" "); } } stringBuilder.append(" "); } System.out.println(stringBuilder.reverse().toString() + " "); System.out.println("Highest Index: " + highColIndex); System.out.println("2nd Highest Index: " + secHighColIndex); System.out.println("Amount of energy: " + sumOfEnergy); } }
@@ANlMO I learned C++ and matlab but I almost forgot how to program, so I will try to write only the way. N= number of column's Nc= current column=1 H= height of each column Hc= current height E= energy level Et=total energy=0 Assume £ to be greater and $ to be less that b/c there is no sign in my keyboard for them. Hl means Hleft Hr means Hright Start For Nc $ N-1, Nc=Nc+1 (If the biggest Hl of the Ns $ Nc is £ Hc, (If the biggest Hr of the Ns £ Nc is £ Hc, E= smallest from (Hl and Hr) - Hc,else return to start, else return to start) Et=Et+E, print Et Hope you understand it N.B. I ignored the first and the last column in the iteration b/c it is not necessary.
@@StrongLions Hi, hope you don't mind, but I took a look at your code, and it seems to be unable to come up with the optimal answer. You only searched for the two highest points and find the differences inbetween them. However, in the example shown in 5:09 (ie. int[] maze = {7,6,12,10,3,5,8,11,9,7,8,10,9,1,8,3,5,9};), your program determines the third and eighth to be the highest, determine the differences, and ignore the holes in the right Admittedly the solution I came up with (find the tallest point from each end, stopping if the next is shorter, then finding the differences between the two tallest points) also failed with this test case, as it would just use the first 7 and the last 9, and sum the differences between height of each inbetween with the lower point of 7
Coding uses, and more importantly, builds, a wide array of soft skills and intuition. I've seen many textbooks and videos but few manage to capture these. Even so, the degree to which this series does it is extremely rare. This series not only permanently implants them into your head, but also has a very engaging plot. Honestly, I'm a coder myself, and I'm mostly following this for the plot - but even I found new skills to learn. Really great, and I love it! Will definitely recommend to anyone I know!
Real solution: realize Hedge can store data, look at every one, store the heights in its memory, see the full structure, Now Hedge can see the entire thing and cheat :)
Thank you Ted Ed for keeping me passionate about my subject when the examination questions all seem repeated and uninspiring. Ps. I got the left and right thing, but only did it for the neighbouring two columns. You win some you lose some.
This reminds me of my first programming marathon, those are kinda though, but I recommend URI, virtual judge, if you’re interested in problems such as these
I am a 3rd year computer Science major, and I needed to think about this for a couple of minutes. This was a really fun puzzle. Very unique from the things you see in school, but very helpful for thinking about algorithms.
I just discovered this series and i realized that this is what ive ALwAys needed in my life but never knew. Thank you so much for this TED cant wait for ep8!
Check to see if the units in each column are surrounded by blocks. If they are, then remember to fill until the unsurrounded unit is found, if not don't fill (put conditional in a loop) until all surrounded units are full based on the block's height
Coming back to this series four years later, and I decided to write out and post my solution, before watching the video to see theirs. Make an array with the height of every tower. Take the shortest height and subtract it once from every tower - this accounts for any rows at the bottom that would be completely filled with towers. Compare the tallest height to the second tallest - if there's a tie, do nothing, otherwise set the tallest to the second tallest. This is because the excess height rows of the tallest tower will not contain any energy. Then, turn this into a 2D grid (2D array), filling it from bottom to top with the height of each tower. Create a "fill" variable and set it to zero. Go row by row, and left to right. If Hedge comes across a space on the grid (a "square") with a tower block inside, set a variable to say so, and start counting left to right with a "count" variable. If he encounters no more squares with tower blocks on that row, discard the count; if he does encounter another tower block, however, add "count" to "fill" without counting the square he just moved to, then set "count" to 0 and start counting again, repeating the loop. Do this for every floor of the array, and the final number stored in "fill" is how many units of energy can be contained. This can be made more elegant in a few ways; for example, once you reach the row that's the same height as the new shortest tower, track the count for that row separately and multiply it by the row height, then add that to fill. Or you could remove columns as you go. Do the same set up as in the first paragraph, but this time, every time you encounter a gap between towers on a row, count the number of squares that will be filled in each tower under the gap, and also mark off each filled tower as well as the two towers acting as walls. Once you reach the end of the row, add this count to fill, and remove the marked off towers from memory. Don't worry about missing squares - because every tower is a stack with no gaps, once we determine that the space above it is filled and count how much that filling is, it won't have any more influence on the final total, and removing it makes further calculations that little bit faster. Either way, once Hedge is finished, the final number stored in "fill" is the number Ethic needs to input.
The best solution is to consider local extremes of height, assign each column the smallest of the local extremes surrounding it and subtract the current height.
Because the node of memory is left, And also for you to see the funny robot dance in the next episode. 😂 And to see Hedge's smaller clones die... 😭 Also sorry for spoilers, if I gave u one, go ahead and watch the next episode as it is out! 😉
I am not a student of Computer Science. Actually I hated programming coz I thought it was useless.Thank You Ted Eds for clearing my ignorance.I love this innovative adventure of Coding and am starting to appreciate it's Beauty.
i swear the nodes are rip-offs of infinity stones, but i cant blame you. I wouldn't have thought of anything better either. Also thank you ted for inspiring me to become a computer scientist.
Ok, here's my go at a solution. 1. Do a pass of the whole structure, recording the location and height of the two tallest pillars. 2. Divide the columns into three lists, depending on whether they're on the right, the left, or in between the two tallest columns. Do not add the tallest columns to these groups. 3. For the middle list, simply calculate the difference in each the difference between the height of the second tallest column and the each other column. Add these all together to get your total storage for that section. 4. For the side section, if they contain 2 or more columns, find the tallest column in them. Then create two new lists, the first being between the selected column and the closest tall column, and the second being defined as the everything else in that list. Do not include the selected tallest column in either of these lists. 5. Repeat step 3 for the section in between the two columns, and step 4 for the other section. Repeat until no sections of size 2 or greater remain. At this point, you should have now calculated the total capacity. Notes: looking at this, it seems it would be useful to add a "tall" trait to the columns, to signify whether they represent a local maximum. Also, this would be best implemented using recursion. Anyway, that's my go at it, and I'm sure their are way more efficient ways of doing it.
Hi Animo here. Could some experienced person post the more optimal solution (time complexity < 3n) they talked about in the video. I'd love to know about it. The pseudo code or a python code would really be appreciated.
I wont give the pseudocode but here is the idea in detail: have two variables which at the beginning of the program keep track of both ends of the array. At any point, we check whether the left or right side has the smaller height and start from there. Just for example, lets say the left side is shorter. We have a leftmax variable for the highest point seen on the left side. We move once to the right. If this new height is shorter than we can store water. And we know exactly how much water, it only depends on the current height and leftmax (since we know this side is shorter than the right side, only this side matters to find how much water goes in this column). Then we move onto the next column and repeat until we reach a column that is taller than the right side. Then, we switch sides since the right side is shorter now. We do the same process moving towards the left, and we only need to know rightmax to find how much water goes in these columns. So we keep switching between the left and right sides until the two variables meet somewhere in the middle. At this point every column is filled. This is about as efficient as you can get because each column is analyzed exactly once, and only four variables (left, right, leftmax, rightmax) need to be stored regardless of array size.
Ted Ed, can you do a video explaining the history and the real significance of caduceus (the winged snake medical logo thing). I thinks it's an interesting video topic and not a lot of people know about it
I know it was said that there are easier ways to do this, but why wouldn't hedge just scan from left to right, pick the 2 largest columns up first and calculate how much energy to store? That would cut down the time even further and result in a linear complexity of N (although theoretically seen the complexity of the video's algorithm is also N 2•N, cosidering 2 passes, L to R, R to L)
3:08 DO NOT STEAL MY ANSWER Program hedge to check the inner collums and ingnore the ones on the far left and right count how tall the hole is that is between 2 walls and store the amount repeat but instead of replacing the info ADD it to the variable
The adventure continues! Episode 8: Ethic and Hedge find themselves at a gauntlet of forking paths. Can they find the right one before they’re captured? Find out with episode 8: bit.ly/TLACEp8
And make sure you don't miss another episode by subscribing and smashing the bell!
TED-Ed first comment here!
The only people who managed to give education a plot. I'm going to have to re-watch all 9 just so I can pay attention to the processes more XD. Thank you Ted Ed
I actually found an mistake at 6:04 the graphs shows a linear and exponential growth however N² is not exponential but rather ( maybe I don't know what to call it ) quadratic growth while the exponential growth is (a)^N. But you guys did a great job 👍 and the most loving part was animation 💗
@@Dylan-xl9gp NO I’M FIRST KAREN!!
@@DOGSAVESTHEDAY_SYSTEM LIAR
Animator and narrator are the best duo ever.
One needs many animators to make a film on time.
Duo? It's a studio
What about the story writer?
Please upload this more often. I can't even begin to explain how hooked I am on this
Man it takes time to make quality content.
@@almuhimen8023 And money! 3D-animation is expensive, trust me.
Check some easy problems from programming contests. Of course there aren't any animations (sometime stories), but thats not the case if you are looking for problems to solve.. For example problems "A" from codeforce, in my opinion similar difficulity (in average).
@@dscmtr686 Problems A of div3. Div1 A problems are often hard than div2 E or F.
@@almuhimen8023 yeah, div matters.
(div 1 A is often div 2 C)
"By enclosing it in a giant maze. She named her creation hedge."
Hedge maze, i see what you did there *wink wink*
Is this a reference to The Shining movie (not the book) ?
@@why_tho hedge
/hɛdʒ/
noun
a fence or boundary formed by closely growing bushes or shrubs.
@@bravomike4734 yes, I know.
I was talking about the hedge maze in which Jack freezes to death.
so did i
1984 them the shining, they definitely are putting Easter eggs for classics
I knew it, the final story is about the importance of morals and ethics in everything including the world of computers and programming. Ethic is one of the few programmers with ethics and the broken world is due to the result of government programmers lacking ethics.
ethics it self is another story bro for science.
@@lambertlazaro2407 Well computers are also included in science. Yes, agreed all sectors needs ethics, not just computers. From theoretical physics, nuclear physics to biology etc.
6:04
“There are ways to optimize the solution even further”
Please let us know.
Look for sorting algorithms. Bubble sort, merge sort etc.
One good way is to find the largest height then you find similarly to left of max and to right by keep track of second max while the running the loop it will be liner and constant space
@@theowl5402 those are inefficient and plus you can't sort it either you'll ruin configuration
@@theowl5402 you know?!?!
6:00
N^2 is polonomial.
Exponential means the growing number is in the exponent, Like 2^N.
This grows even faster than N^2.
Oh yes, you are right, this is indeed polynomial. x^a is polynomial and a^x is exponential where a is constant
*wot*
@@chervilious No, it isn't. There is absolutely no area of study that refers to polynomial growth as exponential.
This is a true P vs NP debate.
I agree you man.👏👏👏👏👏👏
I was able to solve it in about 7 minutes and that made me feel happy, thank you ted, keep it up. I would have shared the way I solved it by a photo if i could.
Eritrean civil engineer currently in sudan.
paste your code here! Or maybe use pastebin and send the url here
@@ANlMO In Java:
import java.util.Random;
public class solution {
public static void main(String[] args) {
// Randomizer for random number generation
Random random = new Random();
// Array with the puzzle blocks, will be random
// This is the amount of columns in the puzzle
// +3 hence the randomizer starts at 0, min of 3 columns
int[] maze = new int[random.nextInt(10) + 3];
// Generate random column heights in the maze
// Heights from 0 to 10 at random
for (int i = 0; i < maze.length; ++i) {
maze[i] = random.nextInt(10);
}
// Highest column, highest column index
int highCol = Integer.MIN_VALUE, highColIndex = 0;
// Left to right, grab highest column
for (int i = 0; i < maze.length; i++) {
if (maze[i] > highCol) {
highCol = maze[i];
highColIndex = i;
}
}
// Second highest column, its index
int secHighCol = Integer.MIN_VALUE, secHighColIndex = 0;
// Right to left, grab second highest column
for (int j = maze.length - 1; j >= 0; --j) {
if (maze[j] > secHighCol && j != highColIndex
&& highColIndex != j + 1 && highColIndex != j - 1) {
secHighCol = maze[j];
secHighColIndex = j;
}
}
// Calculate sum of energy
int sumOfEnergy = 0;
if (highCol!=0&&secHighCol!=0) {
// Start at the smaller index of both
// Then calculate smaller height minus amount of existing blocks
if (secHighColIndex < highColIndex) {
for (int i = secHighColIndex + 1; i < highColIndex; i++) {
sumOfEnergy += secHighCol - maze[i];
}
} else {
for (int i = highColIndex + 1; i < secHighColIndex; i++) {
sumOfEnergy += secHighCol - maze[i];
}
}
}
// Test console output
StringBuilder stringBuilder = new StringBuilder();
int mazeSum = 0;
for (int i : maze) {
mazeSum += i;
}
for (int i = 0; i < mazeSum; ++i) {
for (int j = maze.length-1; j >= 0; --j) {
if (maze[j] > 0) {
stringBuilder.append("X");
maze[j] -= 1;
} else {
stringBuilder.append(" ");
}
}
stringBuilder.append("
");
}
System.out.println(stringBuilder.reverse().toString() + "
");
System.out.println("Highest Index: " + highColIndex);
System.out.println("2nd Highest Index: " + secHighColIndex);
System.out.println("Amount of energy: " + sumOfEnergy);
}
}
@@ANlMO I learned C++ and matlab but I almost forgot how to program, so I will try to write only the way.
N= number of column's
Nc= current column=1
H= height of each column
Hc= current height
E= energy level
Et=total energy=0
Assume £ to be greater and $ to be less that b/c there is no sign in my keyboard for them.
Hl means Hleft Hr means Hright
Start
For Nc $ N-1,
Nc=Nc+1
(If the biggest Hl of the Ns $ Nc is £ Hc,
(If the biggest Hr of the Ns £ Nc is £ Hc,
E= smallest from (Hl and Hr) - Hc,else return to start, else return to start)
Et=Et+E, print Et
Hope you understand it
N.B. I ignored the first and the last column in the iteration b/c it is not necessary.
@@StrongLions Hi, hope you don't mind, but I took a look at your code, and it seems to be unable to come up with the optimal answer. You only searched for the two highest points and find the differences inbetween them. However, in the example shown in 5:09 (ie. int[] maze = {7,6,12,10,3,5,8,11,9,7,8,10,9,1,8,3,5,9};), your program determines the third and eighth to be the highest, determine the differences, and ignore the holes in the right
Admittedly the solution I came up with (find the tallest point from each end, stopping if the next is shorter, then finding the differences between the two tallest points) also failed with this test case, as it would just use the first 7 and the last 9, and sum the differences between height of each inbetween with the lower point of 7
Coding uses, and more importantly, builds, a wide array of soft skills and intuition. I've seen many textbooks and videos but few manage to capture these. Even so, the degree to which this series does it is extremely rare. This series not only permanently implants them into your head, but also has a very engaging plot. Honestly, I'm a coder myself, and I'm mostly following this for the plot - but even I found new skills to learn. Really great, and I love it! Will definitely recommend to anyone I know!
Solution: Hedge should get a software update
yes
Lol
HedgeOS
HedgeOS, Version 5, let’s you see all the blocks at once
Real solution: realize Hedge can store data, look at every one, store the heights in its memory, see the full structure, Now Hedge can see the entire thing and cheat :)
So if 198Forest was a reference to 1984, then...
Bradbarriers...
Bradburriers...
Bradburyers...
RAY BRADBURY?!
Did you spot the reference to Mary Shelley's Frankenstein in this episode?
@@askalski :0 No, I didn't! wHeRe is it
@@MochYee Have a closer look at the JavaScript code at 7:35
@@askalski :O
Andrew Skalski idk how to read JavaScript currently so I didn’t know what it meant
What a twist!! And what a great problem as always, thank you 🙏🏻❤️
Thank you Ted Ed for keeping me passionate about my subject when the examination questions all seem repeated and uninspiring.
Ps. I got the left and right thing, but only did it for the neighbouring two columns. You win some you lose some.
I did the same except i also removed the cells in thé outer column
I got this one right. Awesome series Ted ed
This reminds me of my first programming marathon, those are kinda though, but I recommend URI, virtual judge, if you’re interested in problems such as these
I'm literally checking out for episode 8 almost everyday. Loved it...☺
Same here!
I love this series...!!
Thanks Ted Ed for this series ...
Will love to see some more series in future...
HOLY SHEEP THIS IS THE BEST EPISODE SO FAR I'M DYINGGGG!!!!11!!!one!!!!
I love the animations!! Ethic looks so cool
Yaasssss!!!!!! Love these videos!!!! Waiting anxiously for episode 8!!!
I just can't believe we are getting this for free 🔥🔥🔥🔥
I would prefer this over Netflix!!😍
what if it was on Netflix? (It would be cool if it was)
@@harrisongerdes7078 Why do we need it on Netflix if it's here for free?
@@ArunKumar-dv8zw idk, i just thought of it being a funny and nice idea
clearmebabyshow.link/qQ7BiAQTqch
me to!!
I love these videos. They're giving my brain a workout! I can't wait for more! Good luck on your quest Ethic!
N^2 its actually polinomial, or quadratic, but not exponential
I was waiting for this episode for a long time
Same.
"sent bots to arrest her"
"she named her creation hedge"
i am starting to see everything
This is like the most exciting series of videos ever I love it. You need to post more often. I am like totally addicted to this.
Thank you TED-ED. You can't imagine how much I like your series.
When you realize hedge probably started this and tricked Ethic into doing his work:
WOOOOOOOW HEDGE WAIT TO GO DUDE DROWN REAL LIFE IN ROBOTS
One could call the problem "stack overflow" XD
... Your smart
When you hype something until you forget about it but it comes out :
*Ok*
The best TED-Ed series! Ever! Ever!
Best videos to understand flow control. Loved it Ted-Ed. It's Awesome
me: ehhh i don't wana think on this one
also me: pulls up visual studio and starts coding the entire problem and solution
I am a 3rd year computer Science major, and I needed to think about this for a couple of minutes. This was a really fun puzzle. Very unique from the things you see in school, but very helpful for thinking about algorithms.
I think this makes youtube better than all other platforms including unproductive Netflix
Please release the eighth episode. I've been waiting for it.
Thank you! I've been waiting for a long time for another episode. I love the series!
I love this series,please make more series on coding in future.
I just love this voice
I'm late to the series, but I'm calling it now. The last episode will be about a maze solving algorithm and they'll probably use DFS to do so.
H
I just discovered this series and i realized that this is what ive ALwAys needed in my life but never knew. Thank you so much for this TED cant wait for ep8!
In the first episode, I thought the Node of Creation was yellow.
oh yeah and the memory was blue
but the node of power stayed red, i'm seeing some connection here...
Traffic light.
Heyyy, you're right!
True! LoL
Can you guys make a video on how sound recording works?
Btw, Great video!!!
Love this series.
Who else loves this series
Best Puzzle so far!! Good Job making it so fun to solve!
As always you have been excellent Ted-Ed, the title itself is more charming than anything, seriously you have outdone yourself! Love You, Ted-Ed:)
Waouuu, it's wonderful!!! I'm learning in each episode. I love it🥰
Wow, this is really interesting!
please update soon! videos like these are brilliant time killers during the pandemic
Okay but why is this the best narrator Ted Ed has
Okay wow. This is the first time I got a puzzle fully wrong in think like a coder. Wow this is getting more complicated
This might be the my most favorite episode
Animator and narrator are the best duo ever
Oh gosh this lore is getting deep
Our computer science teacher lets us watch this in Cs class 😂
A U I hope that my teacher would be like that...
( •-• )
Nicely explained rain water problem.
Wow, this episode of Numberblocks has really changed.
Wow, this is incredible.
I wonder how the narrator said the challenge before the timer ended because I think it took like, 2 minutes 🤔
No, I was wrong, it took 5 minutes 🤣
Hoping for season 2 of this series
Best playlist ever for a beginner, to start coding
Random fun Fact: The # symbol isn’t officially called hashtag or pound.
Its technical name is octothorpe. The “octo-” means “eight” to refer to its points, though reports disagree on where “-thorpe” came from.
Its called sharp 🎵🎶
or just hash.
Hence hashtag is a tag made with the use of the hash.
i call it "number" for some reason
or tic tac toe
number symbol
Wasn’t the Node of Creation yellow in the first episode?
I think I need to rewatch this episode
This is the first episode that left me unsure of whether I could write an algorithm to accommodate the problem. It's genuinely tricky.
0:45 what a shot there guys
Beautiful animation and wonderful content 😍 Keep it up!
can't wait to watch the next episode. it is a wonderful portrayal of computer language. should show these videos in the classes. 😋
This series is just great !!!! Here's a suggestion: Make some series related to electronics also.......
0:44 The tiles Ethic steps on make blinking sounds that mimic the intro music
Check to see if the units in each column are surrounded by blocks. If they are, then remember to fill until the unsurrounded unit is found, if not don't fill (put conditional in a loop) until all surrounded units are full based on the block's height
This series is awesome!!!
Ahaaa yes its finally here
Is the World Machine at the prison Ethic was held in?
Coming back to this series four years later, and I decided to write out and post my solution, before watching the video to see theirs.
Make an array with the height of every tower. Take the shortest height and subtract it once from every tower - this accounts for any rows at the bottom that would be completely filled with towers. Compare the tallest height to the second tallest - if there's a tie, do nothing, otherwise set the tallest to the second tallest. This is because the excess height rows of the tallest tower will not contain any energy. Then, turn this into a 2D grid (2D array), filling it from bottom to top with the height of each tower. Create a "fill" variable and set it to zero.
Go row by row, and left to right. If Hedge comes across a space on the grid (a "square") with a tower block inside, set a variable to say so, and start counting left to right with a "count" variable. If he encounters no more squares with tower blocks on that row, discard the count; if he does encounter another tower block, however, add "count" to "fill" without counting the square he just moved to, then set "count" to 0 and start counting again, repeating the loop. Do this for every floor of the array, and the final number stored in "fill" is how many units of energy can be contained.
This can be made more elegant in a few ways; for example, once you reach the row that's the same height as the new shortest tower, track the count for that row separately and multiply it by the row height, then add that to fill.
Or you could remove columns as you go. Do the same set up as in the first paragraph, but this time, every time you encounter a gap between towers on a row, count the number of squares that will be filled in each tower under the gap, and also mark off each filled tower as well as the two towers acting as walls. Once you reach the end of the row, add this count to fill, and remove the marked off towers from memory. Don't worry about missing squares - because every tower is a stack with no gaps, once we determine that the space above it is filled and count how much that filling is, it won't have any more influence on the final total, and removing it makes further calculations that little bit faster.
Either way, once Hedge is finished, the final number stored in "fill" is the number Ethic needs to input.
Ted ed ! Finally I can go and sleep in peace
I have been waiting for this since last month
Thank you very much !
Bro this story is crazzy omg :o
The best solution is to consider local extremes of height, assign each column the smallest of the local extremes surrounding it and subtract the current height.
The ground bellow falls:
Me: Wait why are there 3 more episodes?
Because the node of memory is left,
And also for you to see the funny robot dance in the next episode. 😂
And to see Hedge's smaller clones die... 😭
Also sorry for spoilers, if I gave u one, go ahead and watch the next episode as it is out! 😉
The Randomizer YT I meant to say they died, so why are there 3 more episodes
@@baconninja4481
I meant to say, the didn't die 😏
@@baconninja4481
Also the next episode is out, so go ahead, watch it.
Love this series!!!!
I am not a student of Computer Science. Actually I hated programming coz I thought it was useless.Thank You Ted Eds for clearing my ignorance.I love this innovative adventure of Coding and am starting to appreciate it's Beauty.
Loving this!!!
Love ted-ed keep going yall
Love this show!
How am I just now finding it's series??
i swear the nodes are rip-offs of infinity stones, but i cant blame you. I wouldn't have thought of anything better either. Also thank you ted for inspiring me to become a computer scientist.
Please make more videos like this, please
Ok, here's my go at a solution.
1. Do a pass of the whole structure, recording the location and height of the two tallest pillars.
2. Divide the columns into three lists, depending on whether they're on the right, the left, or in between the two tallest columns. Do not add the tallest columns to these groups.
3. For the middle list, simply calculate the difference in each the difference between the height of the second tallest column and the each other column. Add these all together to get your total storage for that section.
4. For the side section, if they contain 2 or more columns, find the tallest column in them. Then create two new lists, the first being between the selected column and the closest tall column, and the second being defined as the everything else in that list. Do not include the selected tallest column in either of these lists.
5. Repeat step 3 for the section in between the two columns, and step 4 for the other section. Repeat until no sections of size 2 or greater remain. At this point, you should have now calculated the total capacity.
Notes: looking at this, it seems it would be useful to add a "tall" trait to the columns, to signify whether they represent a local maximum. Also, this would be best implemented using recursion.
Anyway, that's my go at it, and I'm sure their are way more efficient ways of doing it.
I have never used my analytical skills that much except for when I try to answer Ted-Ed riddles. Key word is try
best explanation for complexity 😁
Memory - Jason Bourne
Stunts - Ethan Hunt,
Infinity Stones - Thanos
Robot sidekick- Knight Rider
Wow, Ethic, slow down
Now I can finally defeat Tetris
Hi Animo here. Could some experienced person post the more optimal solution (time complexity < 3n) they talked about in the video. I'd love to know about it. The pseudo code or a python code would really be appreciated.
I wont give the pseudocode but here is the idea in detail: have two variables which at the beginning of the program keep track of both ends of the array.
At any point, we check whether the left or right side has the smaller height and start from there. Just for example, lets say the left side is shorter. We have a leftmax variable for the highest point seen on the left side. We move once to the right. If this new height is shorter than we can store water. And we know exactly how much water, it only depends on the current height and leftmax (since we know this side is shorter than the right side, only this side matters to find how much water goes in this column). Then we move onto the next column and repeat until we reach a column that is taller than the right side.
Then, we switch sides since the right side is shorter now. We do the same process moving towards the left, and we only need to know rightmax to find how much water goes in these columns.
So we keep switching between the left and right sides until the two variables meet somewhere in the middle. At this point every column is filled.
This is about as efficient as you can get because each column is analyzed exactly once, and only four variables (left, right, leftmax, rightmax) need to be stored regardless of array size.
Ted Ed, can you do a video explaining the history and the real significance of caduceus (the winged snake medical logo thing). I thinks it's an interesting video topic and not a lot of people know about it
Not me
Just a note for correcting some information in 6:02
N^2 is not exponential, it's quadratic. An exponential function is (commonly in algorithms) 2^N
I know it was said that there are easier ways to do this, but why wouldn't hedge just scan from left to right, pick the 2 largest columns up first and calculate how much energy to store? That would cut down the time even further and result in a linear complexity of N (although theoretically seen the complexity of the video's algorithm is also N 2•N, cosidering 2 passes, L to R, R to L)
thanks for doing this 👍👍👍👍
3:08 DO NOT STEAL MY ANSWER
Program hedge to check the inner collums and ingnore the ones on the far left and right count how tall the hole is that is between 2 walls and store the amount repeat but instead of replacing the info ADD it to the variable
The last time I was this early, Mesopotamia was still standing.