How to solve tower of Hanoi - Inside code
How to solve tower of Hanoi - Inside code
Solution code:
Python: https://gist.github.com/syphh/3ba0ccd…
Java: https://gist.github.com/syphh/c7ad1bd…
C++: https://gist.github.com/syphh/0359c54…
JavaScript: https://gist.github.com/syphh/400eb2b…
Play the tower of Hanoi puzzle: http://www.sdmath.com/games/hanoi.html
🔴 Learn graph theory algorithms: https://inscod.com/graphalgo
⚙ Learn dynamic programming: https://inscod.com/dp_course
💡 Learn to solve popular coding interview problems: https://inscod.com/50problems_course
⌛ Learn time and space complexity analysis: https://inscod.com/complexity_course
🔁 Learn recursion: https://inscod.com/recursion_course
NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent
I also post content on LinkedIn (https://inscod.com/linkedin) and Instagram (https://inscod.com/instagram)
Content
5.96 -> Welcome to this new inside code video where
we will see how to solve the tower of Hanoi
9.7 -> puzzle.
10.91 -> First of all, what is the tower of Hanoi puzzle?
13.79 -> The tower of Hanoi puzzle says, given 3 vertical
pegs and n disks of different size, you are
19.33 -> asked to move the n disks from the first peg
to the third peg, by following three rules:
24.51 -> you can move the disk on top of the peg only,
and you can move only one disk at a time,
29.68 -> and you can't put a disk on a smaller one.
32 -> If you want to try playing the puzzle, I'll
put a link in the description to give it a
36.36 -> try.
38.88 -> Before starting, you must know something,
you must know that we have the source peg,
43.26 -> which is the peg 'A' here, it's the peg from
where we take the disks.
47.06 -> We also have the destination peg, the one
where we take the disks, it's the peg 'C'
51.98 -> here.
52.98 -> And we have the auxiliary peg, the one that
will help us for our task, it's the peg 'B'
57.22 -> here.
60.04 -> Now we can start, let's solve the puzzle for
n equal to 1, with 1 disk in other words.
65.89 -> When we have only 1 disk, we just take it
from source to destination, from 'A' to 'C'
70.96 -> in our case.
73.36 -> Now with 2 disks, to solve the puzzle, we
move from 'A' to 'B', we move from 'A' to
78.27 -> 'C', and we move from 'B' to 'C'.
81.03 -> Now for 3 disks, to solve the puzzle, we move
from 'A' to 'C', from 'A' to 'B', from 'C'
86.31 -> to 'B', from 'A' to 'C', from 'B' to 'A',
from 'B' to 'C', and from 'A' to 'C'.
92.399 -> Now for 4 disks, to solve the puzzle, we move
from 'A' to 'B', from 'A' to 'C', from 'B'
97.96 -> to 'C', from 'A' to 'B', from 'C' to 'A',
from 'C' to 'B', from 'A' to 'B', from 'A'
103.25 -> to 'C', from 'B' to 'C', from 'B' to 'A',
from 'C' to 'A', from 'B' to 'C', from 'A'
108.549 -> to 'B', from 'A' to 'C', and from 'B' to 'C'.
113.35 -> Now we can notice a pattern that is being
repeated at each execution, the pattern is,
118.39 -> with any value of n, we move n-1 disks from
'A' to 'B', we move one disk from 'A' to 'C',
124.04 -> and we move those n-1 disks from 'B' to 'C'.
128.289 -> And you can verify by yourself that it's what
we did each time.
131.72 -> For example with n is equal to 3, here are
the 8 steps, and here is the part where we
136.23 -> move n-1 disks to 'B', here is the part where
we move a disk from 'A' to 'C', and here is
141.39 -> the part where we move those n-1 disks from
'B' to 'C'.
145.48 -> With n is equal to 4, same thing, here are
the 16 steps, and here is the part where we
150.69 -> move n-1 disks from 'A' to 'B', here is the
part where we move a disk from 'A' to 'C',
155.28 -> and here is the part where we move those n-1
disks from 'B' to 'C'.
159.96 -> But wait, there is something interesting here,
because in reality what we are doing in tower
164.23 -> of Hanoi in general is that we are moving
n disks from source to destination right?
169.22 -> And we said that in order to do that, we move
n-1 disks from source to auxiliary, then we
174.09 -> move one disk from source to destination,
then we move n-1 disks from auxiliary to destination.
180.62 -> And when n is equal to 1, we just move one
disk from source to destination.
185.16 -> And here is the interesting part, the action
inside the function is being called again,
189.62 -> so it's recursion.
191.33 -> And if we wanted to write the function in
code, in Python we would first define the
195.12 -> function, it takes n, the number of disks,
and it takes the source, the auxiliary, and
200.26 -> the destination.
202.04 -> The initial value of source is 'A', the initial
value of auxiliary is 'B', and the initial
206.7 -> value of destination is 'C'.
209.37 -> Now inside the function, we set the base case,
it's when n is equal to 1, in that case, we
214.731 -> just move 1 disk from source to destination,
so we print: "we move from source to destination",
219.7 -> where source and destination are variables
of course.
223.23 -> Else, we want to move n-1 disks from source
to auxiliary, so we call the function again
228.59 -> with n-1, and the source remains the source,
but we switch between auxiliary and destination,
234.36 -> because now the destination is the auxiliary,
for example we were taking those disks from
238.7 -> 'A' to 'B' and not to 'C'.
241.4 -> After it, we said that we move one disk from
source to destination, so we print: "we move
246.32 -> from source to destination".
248.34 -> Last step, we want to move those n-1 disks
from auxiliary to destination, so we call
253.64 -> the same function with n-1, and the destination
remains the destination, but we switch between
259.01 -> the source and the auxiliary, because we were
taking those disks from 'B' to 'C' and not
263.289 -> from 'A' to 'C'.
264.94 -> That's it, we finished our task, and this
function will do all the work, and will print
269.37 -> all the moves we need to perform, in order
to solve a tower of Hanoi puzzle of n disks.
275.3 -> Not convinced yet?
276.55 -> Let's call this function with n equal to 4.
279.43 -> You have the pegs, the output, the code, and
the call stack, to visualize what's happening.
284.93 -> So n is not equal to 1, so we call the function
with n-1, and auxiliary and destination switched.
292.65 -> n is not equal to 1, so we call the function
with n-1, and auxiliary and destination switched.
298.389 -> n is still not equal to 1, we call the function
with n-1, and auxiliary and destination switched.
304.22 -> Now, n is equal to 1, so we print: "we move
from source to destination", and here source
309.71 -> is 'A' and destination is 'B', and we backtrack.
313.759 -> We went back to the previous call, and now
we print: "we move from source to destination",
318.52 -> and here source is 'A' and destination is
'C'.
321.99 -> Now third step of the call, we call the function
with n-1, and with source and auxiliary swapped.
327.79 -> n is equal to 1, so we print, and we backtrack.
332.319 -> Now we finished this function call, so we
backtrack.
335.33 -> Back to call with n equal to 3, now we print,
and we call the function with n-1, and source
340.83 -> and auxiliary swapped.
342.95 -> n is not equal to 1, so we call with n-1,
and auxiliary and destination switched.
348.659 -> n is equal to 1, so we print, and we backtrack.
352.25 -> We continue in our call, we print, and we
call with n-1, and source and auxiliary swapped.
359.419 -> n is equal to 1, we print, and we backtrack.
362.87 -> We finished this call, so we backtrack.
365.219 -> We also finished this call, so we backtrack.
368.34 -> Now we went back to the first call, so we finished
the first part.
371.74 -> Second part, we move one disk from source
to destination, we print it.
376.37 -> Third part, we call with n-1, and source and
auxiliary swapped.
381.57 -> n is not equal to 1, so we call with n-1,
and auxiliary and destination swapped.
387.49 -> n is not equal to 1, then same thing, we call
with n-1, and auxiliary and destination swapped.
393.5 -> Now n is equal to 1, we print, and we backtrack.
398.31 -> Now in this call, we print, and we call with
n-1, with source and auxiliary swapped.
404.289 -> n is equal to 1, we print, and we backtrack.
407.83 -> The call ends here, so we also backtrack.
410.719 -> We went back to n equal to 3, we print, and
we call with n-1, and source and auxiliary
416.11 -> swapped.
417.759 -> n is not equal to 1, so we call with n-1,
and auxiliary and destination swapped.
423.93 -> n is equal to 1, we print, and we backtrack.
427.61 -> Now we print, and we call with n-1, and source
and auxiliary swapped.
432.55 -> n is equal to 1, we print, and we backtrack.
435.409 -> This call has no more instructions, we backtrack.
438.36 -> Same thing for this one, we backtrack.
441.11 -> And same thing for the original call, we backtrack,
and our process ends here, and you can see
445.81 -> that we solved the tower of Hanoi puzzle,
and we even got all the moves to do, the power
451.559 -> of recursion.
452.979 -> For the time complexity, here we have a recursive
function, and each call is calling the same
457.409 -> function twice, so we have the initial call,
it calls the function twice, then each one
462.51 -> of them calls the function twice, and so on.
465.789 -> So it will give us a time complexity of O(2^n).
470.199 -> And for the space complexity, it's a recursive
function, so we need to have a look on the
474.379 -> call stack maximum size, which is equal to
n here, because there can be at most n calls
479.6 -> on the call stack, so our space complexity
is O(n).
484.12 -> I hope that you found this video interesting,
you can find the code in the first link in
488.139 -> the description, and see you in the next video.
Source: https://www.youtube.com/watch?v=UR1lOWMvAIA