I am think you are not stupid, just imagine you can read and write it takes a lot, and you can differentiate between squares and triangles a lot of monkey cant do it
@@princessassmunch4354 Man’s gotta make his bread. At this point, only 20 people support him on Patreon and he has tens of thousands of viewers who get such amazing content for free.
@@princessassmunch4354 That sounds like a lot tbh. A portion of my premium membership fee goes towards this channel, making it easier to support this channel and guarantee an ad-free experience. I'm sure he'll tone down the number of ads once he has a decent number of subscribers.
If anyone else had didn't immediately catch the logic behind the " other = 6 - (start + end) ", it's because if you tally up the values of rods 1,2, 3 that will equal six. Thus if start = rod 1 and end = rod3, 6-(rod1+rod3) = rod2, thus "other = rod2".
unless you are using indices to store values or calculating distance between indices or having some kind of significance with adding up the labels of the rods, im going to call that "logic" presented in the video magic numbered bullshit for the sake of pseudo-genius content.
spent 2 hours last year trying to understand towers of hanoi without any context (just by lloking at code) ...finally gave up and now, after you explained the recursive approach I coded it in python in 10 minutes. just shows what a huge difference a systematic approach can make. your video helped me immensely. thank you
What is the reason for other = 6 - (start + end). There are 10 disks on the example? 14:02. If the first, second and third rod was labeled 1,2 and 3. Then the other rod is 6- (start+end). Is there a 4th rod? Edit: After som afterthought I think you possibly referring to the sum of tower numbers 1+2+3 = 6, but this wasn't explained deeply enough to be satisfying. So essentially this is a method of finding the auxiliary rod at any given time in the recursion.
We always have 3 rods: 1, 2 and 3. When start is 1, end is 2, then other is 6-(1+2) = 3. When start is 1, end is 3, then other is 6-(1+3) = 2. When start is 2, end is 3, then other is 6-(2+3) = 1, and so on. Thus, the formula makes sense.
@@quyenscc Thank you! Our teacher taught us by naming the rods 'from', 'to' and 'other' and passing them as string parameters 'A', 'B', 'C'. The lesson was on divide and conquer though, not recursion, maybe that's why.
This is actually an amazing video, with super clear and simple explanations and animations. This is absolutely amazing and mind blows. Thank you so much
Amazing!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I have been trying to solve this problem for a while now and I was so confused with other solutions on the internet (the code of the solutions) but yours is extremely intuitive and elegant. I am very new to recursion and you made this so understandable. THANKS! I hope you continue making such videos because you really really help the community!
Im really glad that RU-vid finally recommended something that I really needed. Your passion for CS I really resonate with. Amazing video and unparalleled explanation. After encountering recursion, my interest in dynamic programming dwindled quite a lot, but your videos really helped me overcome this hurdle of mine. Many thanks, keep up the amazing work, Here's to hoping for more amazing content Cheers!
Wow, that is one powerful comment Mohammad! Thanks for taking the time to write it and comments like yours mean a lot to me. I'm glad this video helped rekindle your interest in recursion and dynamic programming. Those are hard topics so there's no shame in admitting that they can be frustrating, and the goals of videos like this are to find a way past that frustration and focus on learning the beauty of the concepts, however hard that can be at times. I'm happy that you were able to see that through this video. I'm definitely planning on making future content, so stay tuned!
Great video for introducing the puzzle! One piece of critique though, When you talked about the "recursive leap of faith" (the induction hypothesis) you took n-1 to mean the second to last domino. This can be a bit confusing. I think it's more explanatory if you just said: Pick any domino, and assume it will fall over. If it falls over, prove the next domino (+1) will ALSO fall over. Thus, the first domino falls because of the base case. The second domino falls down, because the first one falls. The third falls, because the second falls because the first, etc etc. That explanation is better at showing how a proof by Induction kind of "cascades" like dominoes, proving every case. Otherwise, it can seem a bit like assuming something random, just to come up with a result.
A few years ago, I solved the towers of hanoi with a loop. I assumed, that there are always three rods. And I said, that an empty rod is a very large disc. I only needed one input: the number of discs. I had realized quite another pattern, for which it is important, whether the number of discs is odd or even. The pattern is, that every other move is the move of the smallest disc. If the number of discs is odd, it always moves start -> end -> other -> start. If the number of discs is even, it always moves start -> other -> end -> start. The other move is always the smaller of the two discs on top of the bigger disc. This solution might might have a few memory issues, but it works.
More contents please! Would like to see some visual explaination on other problems in DSA. Maybe some hard problems on leetcode or google interview questions.
I got lost at pm(1,2). Don't know which line of code is doing that and from there don't also know how start and end keep changing from their given values e.g: start is 1 but then it becomes 3 later on and I don't get where the change in value is coming from. Any form of help is explaining is appreciated
Thank you so much Sir. It gives such satisfaction about understanding these concepts so clearly. Often I end up facing problems while solving recursion and backtracking problems. Please do make videos on those topics. 💓
The thing is i subscribe to your channel in my first arrival to the channel after seeing this video I dont often do that to other channels Keep goodjob!
This was super effective and the example at 16:12 made it that much more understandable. If there's anything I could add, it would be that something like a pointer that was cycling through the line of code that was taking place for the recursive function would have tied everything together. Great job nevertheless
Don't need a "leap of faith" if you prove the n+1 case, this is the principle of mathematical induction. If n is a natural number (n >= 1 in CS terms), and the function holds in the basis case (n=1, the smallest value for which the statement is true), then it is necessary to prove the n+1 case. It is convention in mathematics to assign n = k+1, where k is a natural number that fulfills the base case. If we show that k+1 holds, then that means that we can recursively plug k+1 into k to say that n = (k+1) +1. This process can be repeated for all natural numbers, hence by the principle of mathematical induction the statement is true for all natural numbers. There are no leaps of faith in mathematics. Good video, nice animations.
Thank you for taking the time and effort to make this video. The quality of the editing and animations in the video are excellent and remind me of 3Blue1Brown's videos. Great explanation and it really helped me to visualise and understand how this problem works!
Its not always intuitive to see that the sub problems can be solved the same way as the original problem especially when they share resources like the rods.
Black magic I tell you! That was crazy how a simple rule can solve a seemingly complex problem. I would have spent hours trying to intuit some complex solution to this.
the effort you put into explaining these complex concepts is unimaginable. I have never seen this kind of presentation for explaining an algorithm. Keep it up please.
Yeah it took me all of 45 seconds in my head. I have better than average spacial visualization but even with pen and paper someone should be able to work through all the stuff that doesn’t work in less than several days...
This video is soooo great! It took me awhile, but after repeating your video for 5 times, I finally understand this completely and was able to even work out examples with 5+ discs on my own. Thank you so much!!!
I used to solve this puzzle as it was not even allowed to move a bigger piece over a smaller one. Basically same problem that just takes a few more moves in order to solve it.
Love this! I just recently discovered this channel through the FFT video (RU-vid recommendations) and I just immediately loved it! The topics covered are really cool, and I really like the way they're presented in here (Reminds me of 3b1b, not only because Manin is used here to do the bulk of the animations, but too because of the quality of the explanations). Now, one neat little fact about this algorithm for solving the towers of Hanoi is that if you have n disks, this algorithm takes exactly 2^n - 1 steps to complete (The proof is just a simple induction argument for those who might want to try to figure it out), and in fact, if I'm recalling this correctly, this is actually the optimal amount of steps, you can't go any lower than this! Quite fascinating if you ask me.
Thank you for this comment! I absolutely love compliments like this one! And yeah that's a fun inductive reasoning exercise -- fun fact by the way, you can see the number is steps is 2^n - 1 visually by generalizing the tree diagram for the recursion that we did here. In fact, I believe I touched upon this in the Big O notation video with the O(2^n) example. The basic idea is counting the number of nodes in a tree where at each level we have two branches representing calls to n - 1 and continue until we reach the base case of 1. The inductive argument you mentioned also works for solving this problem, but a fun visual addition. Thanks for sharing this!
What amazes me most with this sort of programming is that the program doesn't know anything about the sizes of the discs. If the discs weren't already sorted by size at the beginning, the program would be completely unable to sort them.
after watching the code part (from 16:00 to 20:00) a couple of times and not understanding a single thing, I wrote the functions on paper and watched again and my mind blew away. Damn you're amazing.
This video just explained it in easy manner.. Using animations make things to understand easily...Carry on and keep on adding the videos of data structures and algorithms in your playlist ..😀 Eagerly waiting for next video !!! Happy Learning !!
I had solved this problem on my own before watching the video. Btw, in my personal case I found the iterative solution harder to come up with than the recursive one. Since I had already solved this problem before watching the video, what blew mi mind was the little arithmetic "hack" to find the "other" rod: 6 - (start + end) LOL. Great stuff!
I think this visualization can be made even better if the value of n(which is decreasing in every recursive subproblems), is also somehow represented in the respective animated subproblems. For e.g.: when the value of n decreases by one, the corresponding one disk can be made to look of the same color as the rod(so only those number of disks remained colored as the value of n) and also the value of n for the current subproblem must be mentioned there.
Its very weird too. If there's an odd number of discs the top disc moves left one (which would go to 3) and the 2nd disc goes to the right, and than the top disc goes left again. After this you simply move the smallest disc other than 1 and 2 to another space with a greater disc number (in this case 0 discs on a rod would be equivalent to the largest disc). This solves the puzzle with any odd number discs, and if you flip the order it solves for every even number. Theres some relationship between the number of rods and the number of times you move the top disc and the second disc, as three rods requires cycles of 3 moves of the top two to work, but cycles of 4 when there's 4 rods. Very strange.
Thank you so much for these awesome videos. I'm currently taking course MITx 6.00.1x over on edX and your videos are really helping me understand the concepts. Thank you again.
This is AMAZING!!! Thank you so much explaining this complicated problem. But I have a question about what does the pm(start, end) do. I see someone asked the similar question before and I just copied his question again and hope someone can help me. Thanks a lot! ---I got lost at pm(1,2). Don't know which line of code is doing that and from there don't also know how start and end keep changing from their given values e.g: start is 1 but then it becomes 3 later on and I don't get where the change in value is coming from. Any form of help is explaining is appreciated
I'm more surprised that screwing with recursive fractal generation made me understand the whole thing _right_ when you showed how to do the 3-disk problem. Have I ascended?
Would be even cleaner if you express it as three recursive calls (moving biggest one is same as hanoi(1, start, end)) then the moving call is in just one place
I have never been good in math, even simple math. I have an app called IMPULSE. One of the games is Tower of Hanoi. It started out relatively simple but I was taking so long to finish each level and was ending up at 2% of the number of moves and time used. So i searched out a video to help me understand how this game works. I never thought it was a mathematical problem. One of my issues is my ADHD & ASD brain. Trying to keep organized in my thinking is not easy. But now I hope to finish my next level in much fewer moves. I will never reach a faster time, but improving in fewer moves is now my biggest goal. Thank you for this video
