1
00:00:00,650 --> 00:00:05,000
Let's now get into the code for solving the Tower of Hanoi problem.

2
00:00:05,030 --> 00:00:09,470
Okay, so as per the question, there are two things that we need to achieve.

3
00:00:09,500 --> 00:00:13,430
So for every movement of a disc we will have to print a statement.

4
00:00:13,430 --> 00:00:16,790
And we are given a sample console.log statement over here.

5
00:00:16,790 --> 00:00:22,640
And we also need to finally return the number of moves that were needed.

6
00:00:22,640 --> 00:00:23,030
Okay.

7
00:00:23,030 --> 00:00:30,350
So we have to move n disks from the from road to the two road using an auxiliary road.

8
00:00:30,350 --> 00:00:31,940
So that's the question at hand.

9
00:00:31,940 --> 00:00:37,700
Now before we get into the details of the solution, let's just first write down the skeleton of the

10
00:00:37,700 --> 00:00:39,230
approach that we are going to take.

11
00:00:39,230 --> 00:00:43,190
So over here it's clearly mentioned that we need to return the number of moves.

12
00:00:43,190 --> 00:00:46,310
So to track that we will need a count variable.

13
00:00:46,310 --> 00:00:49,790
So let me say let count is equal to zero.

14
00:00:49,790 --> 00:00:52,850
And finally we will be returning count okay.

15
00:00:53,060 --> 00:00:54,620
So let's write that also.

16
00:00:56,730 --> 00:00:57,330
All right.

17
00:00:57,330 --> 00:01:02,040
And as we've discussed in the previous video, this is going to be a recursive solution.

18
00:01:02,040 --> 00:01:04,170
And we will need a helper function.

19
00:01:04,170 --> 00:01:07,260
So let me just call the function helper itself.

20
00:01:07,260 --> 00:01:17,550
And to this function we will be passing the parameters in from two and ox okay.

21
00:01:17,550 --> 00:01:20,460
And we'll have to call the function one time over here.

22
00:01:20,460 --> 00:01:25,620
So when we call the function for the first time we call it with the parameters which are given to us

23
00:01:25,620 --> 00:01:29,100
over here itself, which is n from.

24
00:01:29,760 --> 00:01:31,410
Two and ox.

25
00:01:31,500 --> 00:01:38,550
Okay, so this means that move n disks from the from road to the to road using the auxiliary road.

26
00:01:39,540 --> 00:01:40,020
All right.

27
00:01:40,020 --> 00:01:42,930
So this is the skeleton of the approach that we have.

28
00:01:42,930 --> 00:01:46,530
Now let's go ahead and write the details of this helper function over here.

29
00:01:48,080 --> 00:01:55,580
Now in the helper function, we will be writing both the base case as well as the recursive case.

30
00:01:58,940 --> 00:01:59,540
Okay.

31
00:01:59,570 --> 00:02:01,610
Now, what would be the base case?

32
00:02:01,640 --> 00:02:06,530
The base case would be the scenario when n is equal to one okay.

33
00:02:06,530 --> 00:02:13,640
So if n is equal to one then we have reached the base case.

34
00:02:13,640 --> 00:02:20,810
Now again if there is just one disk that we need to move from the from rod to the two rod, then this

35
00:02:20,810 --> 00:02:22,220
is just a trivial problem.

36
00:02:22,220 --> 00:02:26,990
And we can just directly move the disk from the from rod to the two rod.

37
00:02:26,990 --> 00:02:27,350
Okay.

38
00:02:27,350 --> 00:02:31,610
And remember, whenever we move a disk we will have to print a statement.

39
00:02:31,610 --> 00:02:33,110
So let's copy this over here.

40
00:02:33,110 --> 00:02:36,050
So we are given this sample console log statement.

41
00:02:36,050 --> 00:02:38,300
So let's copy it and paste it over here.

42
00:02:38,300 --> 00:02:41,930
And you can leave this as it is like it's written one over here.

43
00:02:41,930 --> 00:02:44,030
And we know that n is equal to one.

44
00:02:44,030 --> 00:02:46,550
But again let me just write n over here.

45
00:02:46,550 --> 00:02:51,230
And we have to move this particular disk from the from rod okay.

46
00:02:51,230 --> 00:02:53,750
And we have the from rod over here.

47
00:02:53,750 --> 00:02:55,820
So that's from to the two rod.

48
00:02:56,300 --> 00:02:58,430
So let's write two over here okay.

49
00:02:58,430 --> 00:03:02,300
And again remember we also have to increment the count variable.

50
00:03:02,300 --> 00:03:05,090
So count plus equal to one.

51
00:03:05,600 --> 00:03:06,380
And that's it.

52
00:03:06,380 --> 00:03:08,270
And we can just return from here.

53
00:03:10,260 --> 00:03:12,000
So this would be the base case.

54
00:03:12,030 --> 00:03:14,730
Now let's go ahead and write the recursive case.

55
00:03:14,760 --> 00:03:20,550
Now as part of the recursive case, as we have discussed in detail in the previous video, there are

56
00:03:20,550 --> 00:03:22,350
three things that we need to do.

57
00:03:22,350 --> 00:03:29,400
And again, the recursive case is the scenario where we have to move more than one disk from the from

58
00:03:29,400 --> 00:03:30,720
root to the two road.

59
00:03:30,720 --> 00:03:31,110
Okay.

60
00:03:31,110 --> 00:03:34,080
And again we have discussed the criteria that has to be preserved.

61
00:03:34,080 --> 00:03:37,410
That is a bigger disk has to be above a smaller disk.

62
00:03:37,410 --> 00:03:37,740
Okay.

63
00:03:37,740 --> 00:03:40,110
So there are three things that we have to do over here.

64
00:03:40,110 --> 00:03:48,000
First we have to move n minus one disks from the from road to the auxiliary road okay.

65
00:03:48,000 --> 00:03:57,300
After that we can move the last disk which is the nth disk from the from road to the two road.

66
00:03:57,480 --> 00:03:58,020
Okay.

67
00:03:58,470 --> 00:04:05,610
And the third step is we will have to move these n minus one disks which are now at the auxiliary road.

68
00:04:05,610 --> 00:04:09,960
So we will have to shift them from the auxiliary road to the two road.

69
00:04:09,960 --> 00:04:12,360
So these are the three steps that we would have to do.

70
00:04:12,360 --> 00:04:17,460
Now these two steps over here will be recursive calls to this helper function itself.

71
00:04:17,460 --> 00:04:22,920
And over here because we are just moving one disk from a particular road to another road, this would

72
00:04:22,920 --> 00:04:24,210
just be a print statement.

73
00:04:24,210 --> 00:04:26,790
So let's go ahead and write the details over here.

74
00:04:26,790 --> 00:04:32,790
Now to move n minus one disks again, as we have discussed will be recursively calling the helper function.

75
00:04:32,790 --> 00:04:36,480
And now the input parameters would be n minus one.

76
00:04:36,840 --> 00:04:40,530
And then from because we are moving the disks from the from road.

77
00:04:40,530 --> 00:04:46,260
But over here we will have the auxiliary road because we are moving the disks to the auxiliary road.

78
00:04:46,260 --> 00:04:53,010
And in this case the initial road which was the two road would serve as the auxiliary road.

79
00:04:53,010 --> 00:04:53,640
Okay.

80
00:04:53,640 --> 00:05:00,600
Now let's move to the next step over here, which is to move the nth disk from the from road to the

81
00:05:00,600 --> 00:05:01,110
two road.

82
00:05:01,110 --> 00:05:06,990
And because as we have discussed, this is just the movement of one disk from a particular road to another

83
00:05:06,990 --> 00:05:07,350
road.

84
00:05:07,350 --> 00:05:09,930
This would just be a console log statement.

85
00:05:09,930 --> 00:05:13,590
So let me copy this over here and let's paste this over here.

86
00:05:13,590 --> 00:05:18,630
So we are going to move the disk n from the from road to the two road.

87
00:05:18,630 --> 00:05:19,920
So this looks good.

88
00:05:19,920 --> 00:05:24,450
And whenever we are moving a disk we will also have to increment the count variable okay.

89
00:05:24,450 --> 00:05:27,480
So let me write over here count plus equal to one.

90
00:05:27,480 --> 00:05:33,600
And the last step is to move the n minus one disks from the auxiliary road to the to road.

91
00:05:33,600 --> 00:05:39,510
And again this would be achieved using a recursive call to the helper function where the input parameters

92
00:05:39,510 --> 00:05:41,580
are n minus one ox.

93
00:05:41,580 --> 00:05:44,190
Because that's where the disks are at this point.

94
00:05:44,190 --> 00:05:45,480
So auxiliary road.

95
00:05:45,480 --> 00:05:48,900
The initial auxiliary road is the from road over here.

96
00:05:48,900 --> 00:05:51,000
And then we are moving them to the two road.

97
00:05:51,000 --> 00:05:56,160
And the initial from road would serve as the auxiliary road in this case.

98
00:05:56,610 --> 00:05:57,090
Okay.

99
00:05:57,090 --> 00:05:57,930
And that's it.

100
00:05:57,930 --> 00:06:00,120
So this should help solve the problem.

101
00:06:00,120 --> 00:06:04,230
Now let's go ahead and run this code and see if it's passing all the test cases.

102
00:06:05,450 --> 00:06:08,210
And you can see that it's passing all the test cases.

103
00:06:08,210 --> 00:06:10,340
Now again, just a quick reminder.

104
00:06:10,340 --> 00:06:12,230
Do make use of the user logs.

105
00:06:12,320 --> 00:06:14,150
Over here you can see the input.

106
00:06:14,150 --> 00:06:20,300
So for example if n is equal to three and from prod is one and the two rod is three and the auxiliary

107
00:06:20,300 --> 00:06:26,570
rod is two, then these are the movements that are required and the expected output is seven.

108
00:06:26,570 --> 00:06:30,440
Movements of disks are involved and the result is also seven.

109
00:06:30,440 --> 00:06:35,450
You will get these statements over here in both scenarios like for example, even if your test case

110
00:06:35,450 --> 00:06:38,780
fails or even if it passes, you will get these statements over here.

111
00:06:38,780 --> 00:06:40,850
So do make use of these user logs.

112
00:06:40,850 --> 00:06:44,030
They will help you debug your code in case you're stuck at some point.

113
00:06:44,030 --> 00:06:49,760
And again, if you want to add some user logs, you can always do that by just having more console log

114
00:06:49,760 --> 00:06:50,180
statements.

115
00:06:50,180 --> 00:06:52,100
And then you just need to click run code.