1
00:00:00,840 --> 00:00:01,040
Hello.

2
00:00:01,860 --> 00:00:06,330
We just finished coding the very first partner algorithm, the DFS.

3
00:00:06,810 --> 00:00:11,580
Now we want to test it naturally to better understand the inner workings of an algorithm.

4
00:00:11,790 --> 00:00:15,240
We will start all by testing on a much smaller, tiny means.

5
00:00:15,570 --> 00:00:21,990
If the DFS is able to find a part to go after mapping, then we can be confident enough to run it on

6
00:00:21,990 --> 00:00:22,620
the original.

7
00:00:23,160 --> 00:00:28,800
Now let's head over to the desk mapping dot pi, which I modified a little bit to test out our path

8
00:00:28,800 --> 00:00:29,790
planner algorithm.

9
00:00:30,270 --> 00:00:30,960
Let's go.

10
00:00:32,330 --> 00:00:34,760
So here we are at the desk mapping the pie.

11
00:00:35,240 --> 00:00:39,170
We start by importing the DFS class that we've just developed earlier.

12
00:00:39,650 --> 00:00:44,930
We then create its object and then after we perform the mapping stage on the tiny maze.

13
00:00:45,140 --> 00:00:51,110
We then head on over to the port planning algorithm where we call the get pass function of our DFS class.

14
00:00:51,440 --> 00:00:53,570
Now this function takes in three arguments.

15
00:00:53,810 --> 00:00:56,480
The first is the graph extracted from the board member class.

16
00:00:56,810 --> 00:01:02,040
Then we have the start and the point, basically the start and the goal point from which you want to

17
00:01:02,040 --> 00:01:03,500
find all possible parts.

18
00:01:04,130 --> 00:01:09,410
Once we find all possible paths, this gets output to this false variable and then displayed by the

19
00:01:09,410 --> 00:01:10,310
sprint statement.

20
00:01:10,700 --> 00:01:16,160
Now for the start point, I've simply said this to the entry point of the myth and for the end.

21
00:01:17,220 --> 00:01:17,950
Or the ghoul.

22
00:01:17,970 --> 00:01:22,610
We are simply said this to the random interest point on our meals.

23
00:01:22,860 --> 00:01:24,140
That is three common four.

24
00:01:24,600 --> 00:01:25,680
Now, if I run this.

25
00:01:28,350 --> 00:01:30,190
What we got are these three windows.

26
00:01:30,210 --> 00:01:33,060
After performing mappings did so the tiny miss.

27
00:01:33,060 --> 00:01:36,510
If we zoom this over you will see that this is a lot simpler.

28
00:01:36,630 --> 00:01:42,930
What we used for debugging the mappings did so right on the top is the maze entry point and the right

29
00:01:42,930 --> 00:01:44,610
in the bottom is a maze exit.

30
00:01:45,000 --> 00:01:50,520
But we want to find all possible paths from the maze entry and three four, which will be somewhere

31
00:01:50,520 --> 00:01:51,780
in the middle of this maze.

32
00:01:52,140 --> 00:01:54,690
So all possible path that lead up to the school.

33
00:01:55,560 --> 00:01:59,730
So and below here in the terminal you can see the graph that has been extracted.

34
00:02:00,360 --> 00:02:05,730
Now, if I press enter, it should give us the path planning towards the goal.

35
00:02:07,230 --> 00:02:13,470
Woops we have an error and the error is a name error which says that the name get path is not defined.

36
00:02:14,250 --> 00:02:15,300
Why is that happening?

37
00:02:15,330 --> 00:02:18,780
It says on the line 28 of the bot path meaning or part.

38
00:02:19,320 --> 00:02:22,560
So let's head on over and see why we have the center.

39
00:02:23,220 --> 00:02:28,740
So line 28 is right here we are where we are recursively calling the get bots function.

40
00:02:29,310 --> 00:02:35,640
But the problem is we tried to solve this problem or problem solve this problem of finding all possible

41
00:02:35,640 --> 00:02:36,870
path using recursion.

42
00:02:37,380 --> 00:02:40,350
But we have named this function as a static method.

43
00:02:40,800 --> 00:02:45,780
And the reason we did that, because we wanted this function to be a static method, because we did

44
00:02:45,780 --> 00:02:51,300
not want access to any instance variable or the member function of the DFS class.

45
00:02:52,050 --> 00:02:57,000
But the problem exist because we want to inform this or solve this problem.

46
00:02:57,000 --> 00:03:05,190
Using recursion and recursion requires the X to the member function of the same that or the same access

47
00:03:05,190 --> 00:03:07,710
to the same function that is getting called from.

48
00:03:08,280 --> 00:03:10,020
So this is a problem.

49
00:03:10,380 --> 00:03:11,430
So how do we fix this?

50
00:03:11,790 --> 00:03:17,520
One method is to remove the instance or static method that we have declared this function as and simply

51
00:03:17,520 --> 00:03:22,800
keep it as a member function so that we could access this function from inside the function.

52
00:03:23,820 --> 00:03:30,360
But another method that can simply let this method be a static method and still call this function from

53
00:03:30,360 --> 00:03:32,520
inside it and perform recursion.

54
00:03:33,000 --> 00:03:38,550
And that can be done by simply writing the class name and then calling the the function.

55
00:03:38,970 --> 00:03:40,200
That was the static method.

56
00:03:40,680 --> 00:03:42,300
So one says Kristy.

57
00:03:42,690 --> 00:03:45,120
This should hopefully solve this problem.

58
00:03:45,780 --> 00:03:48,320
We don't know what the test method or fight and plus play.

59
00:03:49,400 --> 00:03:54,860
After the mapping stage has been performed in space groups, we now have anywhere.

60
00:03:55,340 --> 00:03:59,540
So the recursion error, it says, is the maximum recursion depth exceeded.

61
00:04:00,410 --> 00:04:06,980
So basically what's happening is that whichever recursion that we were using, the problem is that it

62
00:04:07,070 --> 00:04:13,670
went into an infinite loop and basically set up a maximum recursion depth exceeded it.

63
00:04:14,360 --> 00:04:20,420
So we need to head on over to the board part, planning part and see where in this algorithm this is

64
00:04:20,420 --> 00:04:20,930
happening.

65
00:04:21,830 --> 00:04:23,900
Now, there are two goals of this error.

66
00:04:23,900 --> 00:04:29,720
One course can be that we haven't defined the simplest case or the best condition for our particular

67
00:04:29,720 --> 00:04:31,490
function that is using recursion.

68
00:04:32,270 --> 00:04:35,180
But if you look right here, we have defined the simplest case.

69
00:04:35,450 --> 00:04:43,040
So there is no in the problem the function to theoretically get simplified until it leaves to this base

70
00:04:43,040 --> 00:04:48,830
condition and then returns this part and rolled back all the previous sub problems, eventually finishing

71
00:04:48,830 --> 00:04:49,370
the function.

72
00:04:50,090 --> 00:04:55,730
And then the problem that could occur that could cost is infinite because an error is that when this

73
00:04:55,730 --> 00:05:00,020
function is getting called, there is no check whether it is stuck in a loop or not.

74
00:05:00,650 --> 00:05:07,580
And this can get stuck into a loop when we're using undirected graphs and we're using injector graphs.

75
00:05:07,970 --> 00:05:11,260
So we need to keep a check of which node that we were visiting.

76
00:05:11,720 --> 00:05:18,590
So if we look on the graph that we extracted earlier, we have see neighbor nodes that includes nodes

77
00:05:19,490 --> 00:05:22,130
that have access to and from each other.

78
00:05:22,580 --> 00:05:25,910
So we do not visit knows that we have already visited.

79
00:05:26,180 --> 00:05:31,760
So that can be done by simply saying that if the node was already visited, do not visit that node.

80
00:05:31,760 --> 00:05:37,100
And there is inside the fourth variable right here, because when we call this function that becomes

81
00:05:37,100 --> 00:05:39,740
start and that gets saved inside the path variable.

82
00:05:40,070 --> 00:05:44,210
So we need to check whether if the node is in path, don't visit that node.

83
00:05:44,540 --> 00:05:50,060
Another thing that we do, we really hope that apart from the neighbor nodes, we also keep track of

84
00:05:50,060 --> 00:05:51,350
the case of each note.

85
00:05:52,040 --> 00:05:57,260
So the case of Node is not a neighbor node, it's just represents the case of each node.

86
00:05:57,470 --> 00:06:01,190
For example, the start node is the this case is start.

87
00:06:01,550 --> 00:06:03,260
So we don't want to visit that node.

88
00:06:03,710 --> 00:06:10,250
So these are the two conditions that we need to apply to solve this infinite precaution error for this

89
00:06:10,250 --> 00:06:11,180
particular function.

90
00:06:11,660 --> 00:06:12,380
So let's do this.

91
00:06:12,950 --> 00:06:16,220
So we write here if the node not in path.

92
00:06:17,790 --> 00:06:19,680
So we like to, if not, not in part.

93
00:06:20,070 --> 00:06:26,670
So if it is not already visited and nor does not equal to case, then you should visit that particular

94
00:06:26,670 --> 00:06:29,190
note and then recursively call that function.

95
00:06:29,640 --> 00:06:33,600
So this will hopefully solve the error of infinite recursion.

96
00:06:34,230 --> 00:06:38,550
Now, if I head on over to this map and our path presently.

97
00:06:40,160 --> 00:06:46,820
And once the mapping stage has been completed, we press spacebar and this time we have the solution.

98
00:06:47,090 --> 00:06:52,820
So we have found the path that lead up to the mass entry that was zero four to the random interest point

99
00:06:52,820 --> 00:06:53,720
that was three or four.

100
00:06:53,930 --> 00:06:58,730
So we have found all possible paths and they are basically three for this particular case.

101
00:06:59,540 --> 00:06:59,930
So.

102
00:07:01,060 --> 00:07:02,230
This has worked correctly.

103
00:07:02,440 --> 00:07:07,000
But to better understand what was happening behind the scenes, we need to perform the same step.

104
00:07:07,240 --> 00:07:13,360
But using the debug tools of the VR score so that we could see what would happen.

105
00:07:13,360 --> 00:07:14,290
What was happening.

106
00:07:14,380 --> 00:07:18,970
Line by line when we were solving to find all possible paths to the goal.

107
00:07:19,660 --> 00:07:20,350
Let's do that.

108
00:07:22,030 --> 00:07:26,710
So we are now ready to debug the get pass function and understand recursion along the way.

109
00:07:27,190 --> 00:07:30,610
So I've opened several windows and let's see them one by one.

110
00:07:31,000 --> 00:07:36,580
On the right hand side of the graph that you've just extracted that represents the node and the connection

111
00:07:36,580 --> 00:07:37,510
between those nodes.

112
00:07:37,930 --> 00:07:39,910
And on the left hand side you have the debug window.

113
00:07:40,150 --> 00:07:46,510
And in the middle we have the test mapping North Point and right at line 28, I've added a breakpoint

114
00:07:46,720 --> 00:07:51,430
to indicate to a debugger that this is the function that I want to debug a lesson on this.

115
00:07:52,720 --> 00:07:58,210
When this gets started, you will see that the mapping process executes and then when I press spacebar,

116
00:07:58,780 --> 00:08:00,490
this function gets called.

117
00:08:00,730 --> 00:08:04,150
This is the point where the program has stopped because of the breakpoint.

118
00:08:04,690 --> 00:08:12,400
Now let's close this terminal and you will see once I press F11 or step into, we enter this function

119
00:08:12,700 --> 00:08:13,620
on the left hand side.

120
00:08:13,630 --> 00:08:15,790
A lot of things has gone populated.

121
00:08:16,330 --> 00:08:18,440
So let's look at this watch window.

122
00:08:18,640 --> 00:08:24,700
This watch window is basically for us to watch some specific variables that we want to keep track while

123
00:08:24,700 --> 00:08:25,870
executing this function.

124
00:08:26,170 --> 00:08:31,660
This includes the start and end node, which is basically the start point and the goal point from which

125
00:08:31,660 --> 00:08:33,220
you want to find all possible parts.

126
00:08:33,520 --> 00:08:36,040
So these are zero four and three four.

127
00:08:36,190 --> 00:08:41,320
If you look on the right hand side of this image, you're going to see a04 and three four have been

128
00:08:41,320 --> 00:08:45,250
given distinct indicate the start point and end point respectively.

129
00:08:45,760 --> 00:08:48,880
So this is giving us the correct output.

130
00:08:49,180 --> 00:08:52,750
And then we have the node which is not populated here at this moment.

131
00:08:52,930 --> 00:08:58,120
Then we have the path which is initialized to an empty list, and then we have the path now pass basically

132
00:08:58,540 --> 00:09:03,250
restored all the possible paths towards our goal node and then we have the call stack window.

133
00:09:03,430 --> 00:09:09,340
Now this window was very useful in recursion because it basically tells how many missing methods and

134
00:09:09,340 --> 00:09:13,600
how many times have they been called by executing the particular window.

135
00:09:13,870 --> 00:09:17,710
So you can see the main has been called once and the great path has been called once.

136
00:09:18,010 --> 00:09:22,700
So we are right now executing the good parts and that is why it is right on the top for a stick.

137
00:09:23,530 --> 00:09:29,290
So at this moment we have the start point as zero four and .34, which is on the spot window.

138
00:09:29,770 --> 00:09:30,970
And in this graph class.

139
00:09:31,390 --> 00:09:36,160
Let's proceed further by pressing F11 and you will see that the path now gets concatenated.

140
00:09:36,520 --> 00:09:36,770
Well.

141
00:09:36,910 --> 00:09:37,720
So start now.

142
00:09:37,720 --> 00:09:41,080
Get candidate for the empty list of path variable.

143
00:09:41,350 --> 00:09:47,230
So path is now not an empty list, but it has been updated to zero four tuple inside the list.

144
00:09:47,530 --> 00:09:53,380
So this includes all the visited variables or visited nodes that we have visited while moving towards

145
00:09:53,380 --> 00:09:53,980
the goal node.

146
00:09:54,670 --> 00:09:59,470
And then we proceed to a condition that ticks whether we have reached the simplest case or not.

147
00:09:59,710 --> 00:10:04,270
And that would be if the start node is equal to load, but the starting with the zero four and the end

148
00:10:04,270 --> 00:10:05,020
notice three four.

149
00:10:05,230 --> 00:10:06,580
So they are not equal.

150
00:10:06,760 --> 00:10:08,230
This condition does not get through.

151
00:10:08,470 --> 00:10:10,210
So we move on to the next condition.

152
00:10:10,330 --> 00:10:13,720
The next condition is where the start node is part of the graph or not.

153
00:10:14,200 --> 00:10:18,190
And if you look on the right hand side, you can see this dark node is indeed part of the graph and

154
00:10:18,190 --> 00:10:20,050
it is connected to other neighbors notes.

155
00:10:20,380 --> 00:10:23,830
So this is part of the graph, so this will not get executed.

156
00:10:24,040 --> 00:10:28,570
We move to the next step that is initializing the past variable to an empty list.

157
00:10:28,840 --> 00:10:31,000
Now this way we will have installed all possible paths.

158
00:10:31,180 --> 00:10:34,090
Once they get extracted, we then proceed to the next step.

159
00:10:34,510 --> 00:10:35,290
This includes.

160
00:10:36,490 --> 00:10:40,420
The neighbour knows extracting the neighbour knows iteratively from a stock note.

161
00:10:40,660 --> 00:10:43,120
At the moment the stock notes zeal for its neighbor.

162
00:10:43,120 --> 00:10:46,060
Note If you look right over here is two four.

163
00:10:46,270 --> 00:10:47,650
So it has only one neighbor.

164
00:10:47,830 --> 00:10:52,210
And also another thing that each node has is the case of that node.

165
00:10:52,210 --> 00:10:55,270
And that is also can be represented as a neighbor node.

166
00:10:55,510 --> 00:10:57,100
But we don't want to visit the case.

167
00:10:57,280 --> 00:11:03,250
So we will simply ignore the the node that is equal to case which that which I mentioned right over

168
00:11:03,250 --> 00:11:03,550
here.

169
00:11:03,970 --> 00:11:09,160
So we literally extract all the neighbor node of our start node, so we proceed further.

170
00:11:09,280 --> 00:11:11,170
At the moment, the name of Node is Case.

171
00:11:11,560 --> 00:11:16,210
As I mentioned before, we want to ignore all nodes that are named as case, which is indicated right

172
00:11:16,210 --> 00:11:16,660
over here.

173
00:11:17,350 --> 00:11:22,000
So this will move back and iterate over the next neighbor known for our stock node.

174
00:11:22,930 --> 00:11:30,190
So it does move back and then we trade over the next neighbor node is to put the two for is the neighbor

175
00:11:30,190 --> 00:11:35,980
node of our zero for function and it is the only neighbor node and it is not visited and it is not equal

176
00:11:35,980 --> 00:11:36,430
to case.

177
00:11:36,640 --> 00:11:37,930
So this condition gets true.

178
00:11:38,200 --> 00:11:43,150
So we recursively call the get part function by providing the node of the neighbor node.

179
00:11:43,150 --> 00:11:45,910
That is true port as the start note.

180
00:11:46,980 --> 00:11:52,950
So this sticker simply called and you will see the note now equals 2 to 4 and this will get recursively

181
00:11:52,950 --> 00:11:53,310
call.

182
00:11:53,640 --> 00:11:56,280
And the good false function is now being called recursively.

183
00:11:56,520 --> 00:11:59,640
And this is why the start node now becomes two four.

184
00:12:00,240 --> 00:12:01,470
So this is a two fold.

185
00:12:01,620 --> 00:12:07,260
And in the call stack you will see that the recursion has called the gets good part function once more.

186
00:12:07,500 --> 00:12:10,100
So you can see two calls of the same function.

187
00:12:10,320 --> 00:12:16,230
And this is how recursion, books and this is why call stack is very useful in understanding the understanding

188
00:12:16,230 --> 00:12:16,740
recursion.

189
00:12:17,130 --> 00:12:23,340
So at this moment we have called get pass function twice and they have not been completed as of yet.

190
00:12:23,940 --> 00:12:28,430
So we have to start node of two four and the end node of three four.

191
00:12:28,710 --> 00:12:30,120
So we are visiting two four.

192
00:12:30,600 --> 00:12:35,870
So if you look at two four, it has three neighbor nodes zero, four, three, three and three, four

193
00:12:35,880 --> 00:12:36,990
and also the case node.

194
00:12:37,410 --> 00:12:38,460
So we proceed further.

195
00:12:38,520 --> 00:12:42,300
You will see that this is not equal to end because two four is not equal three four.

196
00:12:42,870 --> 00:12:46,380
So this does not get executed and it is also part of the graph.

197
00:12:46,620 --> 00:12:50,940
So this also gets nodes executed, baskets really slide to an empty list.

198
00:12:51,240 --> 00:12:57,980
And then we as the neighbor node for our two for note the neighbor note 424043, three and three four.

199
00:12:57,990 --> 00:12:58,860
And the key is no.

200
00:12:59,370 --> 00:13:01,320
So the first we ignore the case node.

201
00:13:02,390 --> 00:13:07,280
We go back it later with the next neighbor note for our two four that now becomes.

202
00:13:08,740 --> 00:13:09,490
That all becomes.

203
00:13:12,120 --> 00:13:18,270
Zero four, but the offer has already been visited, which is indicated if we look at the part which

204
00:13:18,270 --> 00:13:19,830
is zero four and two four.

205
00:13:20,430 --> 00:13:26,430
So we don't want to with the zero four, we go back and iterate over the next neighbor node and the

206
00:13:26,430 --> 00:13:28,710
next neighbor will be either three, three, three, four.

207
00:13:29,160 --> 00:13:31,890
You proceed further, you will see that this is three, three.

208
00:13:32,220 --> 00:13:33,810
So three is not part of the.

209
00:13:34,440 --> 00:13:35,520
It has not been visited.

210
00:13:35,640 --> 00:13:37,890
So we visit three three as a neighbor node.

211
00:13:39,820 --> 00:13:41,020
So once it was in the treaty.

212
00:13:42,480 --> 00:13:48,330
So we visit the city and once to visit the TNC, you will see that this particular node is a four junction

213
00:13:48,330 --> 00:13:50,340
and it has access to four other nodes.

214
00:13:50,610 --> 00:13:55,620
That includes two, four, three, four, three, one and four, four, and also the case node.

215
00:13:56,130 --> 00:13:59,400
Now we start off by simply congratulating the start node.

216
00:13:59,400 --> 00:14:03,030
That was three three because it was being treated as the node.

217
00:14:03,540 --> 00:14:08,190
This guest could get native to the port, which is which is zero 4 to 4 right now.

218
00:14:08,370 --> 00:14:11,730
Once this statement gets executed, this now becomes zero for.

219
00:14:12,990 --> 00:14:14,200
Two, four and two, three.

220
00:14:15,150 --> 00:14:20,490
Now we proceed further and check whether this starting word is equal to N, but three three is not equal

221
00:14:20,490 --> 00:14:21,120
to three four.

222
00:14:21,270 --> 00:14:22,740
So this does not get executed.

223
00:14:22,950 --> 00:14:28,170
It is also part of the graph indicated by this window and then proceed for the initials or part.

224
00:14:28,380 --> 00:14:30,780
And then it was in the neighbor node for the TSI note.

225
00:14:31,410 --> 00:14:33,390
So the first neighbor node is always case.

226
00:14:33,390 --> 00:14:34,230
We ignore the case.

227
00:14:34,410 --> 00:14:37,530
With the next node there is now 313.

228
00:14:37,530 --> 00:14:38,730
One is not part of the part.

229
00:14:39,120 --> 00:14:42,150
If we look right over here, so there is no three one right over here.

230
00:14:42,330 --> 00:14:44,850
So we can visit three when we visit three, one next.

231
00:14:47,520 --> 00:14:50,400
So we visit T1 next and then proceed to three one.

232
00:14:51,880 --> 00:14:54,160
So we recursively call our get function.

233
00:14:54,370 --> 00:14:59,500
So at the moment, if we look on the call stack, right at this moment, there are four, four calls

234
00:14:59,500 --> 00:15:00,730
of the get pass function.

235
00:15:00,910 --> 00:15:07,090
And all of these calls have not been completed because once a particular call has completed, it gets

236
00:15:07,090 --> 00:15:08,080
removed from the stack.

237
00:15:08,410 --> 00:15:12,970
So this whole process will complete when this text is simply empty.

238
00:15:13,180 --> 00:15:18,850
At this moment, we have fourth call of the get pass function and this is called when we are visited

239
00:15:19,120 --> 00:15:19,720
three one.

240
00:15:20,110 --> 00:15:21,280
Now this is the point.

241
00:15:21,280 --> 00:15:26,560
You will see that the get passed call inside the call stick will will decrease by one.

242
00:15:26,800 --> 00:15:31,270
And the reason is, when we visit the three one, you will see that the neighbor note of three one is

243
00:15:31,270 --> 00:15:31,750
three Z.

244
00:15:32,020 --> 00:15:35,680
But we have just been to three Z, so it is already part of the fourth.

245
00:15:35,950 --> 00:15:37,150
So if you look right here.

246
00:15:37,540 --> 00:15:40,080
So it is already part of the fourth.

247
00:15:41,160 --> 00:15:42,990
So it was already part of the plot.

248
00:15:42,990 --> 00:15:45,210
And Steven also gets added to this plot.

249
00:15:45,780 --> 00:15:51,330
So once we proceed further, it is not equal to end because this is Article three, four or one is an

250
00:15:51,330 --> 00:15:55,620
Article four, and it is also part of the graph as indicated on this image.

251
00:15:56,370 --> 00:15:58,140
So this does not get executed.

252
00:15:58,140 --> 00:15:59,850
Also get initialized to an empty list.

253
00:16:00,180 --> 00:16:02,010
And then it was eight, the neighbor node order three one.

254
00:16:02,370 --> 00:16:06,780
So three one has only one name a note that is three three apart from the case note.

255
00:16:07,290 --> 00:16:12,330
So after the case, nor was it we see that we have the neighbor node of.

256
00:16:13,330 --> 00:16:15,630
They were all dizzy, but.

257
00:16:15,630 --> 00:16:19,330
Well, see, these all already been visited, which is indicated by the.

258
00:16:20,370 --> 00:16:21,900
Well, it's variable right over here.

259
00:16:21,930 --> 00:16:24,060
You can see it is already part of the board.

260
00:16:24,420 --> 00:16:30,540
So this condition does not get to you because we go back and we see that there is no other never known.

261
00:16:31,810 --> 00:16:36,510
So what has done is basically an empty list or an empty plot.

262
00:16:37,000 --> 00:16:38,400
So this gets written.

263
00:16:38,710 --> 00:16:42,310
And with this, Goodstein is right over here where it was being called.

264
00:16:42,550 --> 00:16:46,030
So you will see at this moment there are four called the get false function.

265
00:16:46,390 --> 00:16:50,830
But once this gets it down, the get path called stack decreases by one.

266
00:16:51,010 --> 00:16:54,520
So now there are only 3 seconds left.

267
00:16:55,180 --> 00:16:56,800
Now you proceed further.

268
00:16:57,220 --> 00:17:00,010
We simply get this empty list as a new path.

269
00:17:00,550 --> 00:17:03,670
We calculate this out of the parts because it's an empty list.

270
00:17:06,120 --> 00:17:07,050
So now we visit.

271
00:17:09,470 --> 00:17:16,280
So now we visit the Nord is right now to vote, but the two port has already visited so we don't visit

272
00:17:16,280 --> 00:17:16,550
that.

273
00:17:18,330 --> 00:17:20,630
So this is I mean, was it it was all done.

274
00:17:20,640 --> 00:17:22,320
Was it to go back to treaty?

275
00:17:23,340 --> 00:17:24,780
We don't bother to to poll.

276
00:17:25,560 --> 00:17:27,930
So now we have already visited three one.

277
00:17:28,320 --> 00:17:32,430
So what is left for us to do is to visit either three, four or four foot.

278
00:17:33,980 --> 00:17:35,270
So what are we visiting right now?

279
00:17:35,930 --> 00:17:36,620
So we will see.

280
00:17:37,660 --> 00:17:39,710
That now the neighbor notice to report.

281
00:17:39,950 --> 00:17:41,570
So we are visiting three four.

282
00:17:41,900 --> 00:17:47,120
So t four is going to be visited next because it is not part of the port is indicated right over here.

283
00:17:47,390 --> 00:17:48,980
So three four is not part of the park.

284
00:17:49,250 --> 00:17:51,740
We can visit see four and it is not equal to kids.

285
00:17:52,100 --> 00:17:53,300
So we visit three for next.

286
00:17:53,810 --> 00:17:56,600
And once they visit three, four, you will realize.

287
00:17:57,920 --> 00:18:03,620
That we can coordinate this to the pot, which was basically diagonal zero 4 to 4 and to three.

288
00:18:04,460 --> 00:18:09,290
So we concatenate this two, three, three in the end, and this becomes, you know, four, two, four,

289
00:18:09,310 --> 00:18:10,220
two and three, four.

290
00:18:10,670 --> 00:18:14,600
We realize the triple is equal to and the start is equal to earn.

291
00:18:14,780 --> 00:18:17,270
So we return the port that we have right now.

292
00:18:17,600 --> 00:18:22,070
So this is the part that leads up to the goal, you know, four, two, four, two, three, four.

293
00:18:23,110 --> 00:18:31,540
So we return this time as a new boss and goals to reduce by one new pots and new products added to the

294
00:18:31,540 --> 00:18:31,900
pots.

295
00:18:35,710 --> 00:18:43,750
And then we go back and once we edit this for the passwords found a042433 and three four and this gets

296
00:18:43,780 --> 00:18:46,060
included to the parts, so forth.

297
00:18:46,090 --> 00:18:49,150
Now here's one part that leads up to the goal.

298
00:18:49,540 --> 00:18:54,040
So in this way, recursion has found one part where it has not completed as of yet.

299
00:18:54,340 --> 00:18:57,370
It will complete until it has found all possible path to the goal.

300
00:18:57,730 --> 00:19:02,530
So at this moment, what is happening is that the start node is now three three.

301
00:19:03,820 --> 00:19:05,530
So we have visited one.

302
00:19:05,860 --> 00:19:08,740
We have visited seafood and we have already visited Tupac.

303
00:19:09,010 --> 00:19:11,080
So what is left is two, four, four to visit.

304
00:19:11,680 --> 00:19:16,970
So you will see the note now becomes maybe it will not become four, four, visit four, four, because

305
00:19:16,970 --> 00:19:17,980
it's not part of the part.

306
00:19:18,640 --> 00:19:24,280
And once we waited for the call in case by one, and this goes concatenated to our part.

307
00:19:26,240 --> 00:19:27,920
So it was it was it the four four?

308
00:19:28,790 --> 00:19:32,510
So once you visit the four four, you will see that this has three labor nodes.

309
00:19:32,900 --> 00:19:37,070
This includes three, four, three, three and six, four.

310
00:19:37,400 --> 00:19:42,680
And the problem with this is that we have already visited three, four and three, three.

311
00:19:43,280 --> 00:19:44,630
So these are we visited.

312
00:19:44,900 --> 00:19:45,290
And three.

313
00:19:45,290 --> 00:19:46,760
Four is already visited.

314
00:19:47,600 --> 00:19:50,090
Sorry, we have visited two or three, but we have not visited three.

315
00:19:50,100 --> 00:19:50,370
Four.

316
00:19:50,690 --> 00:19:55,010
It was visited in the previous part, but in the current part it has not been visited.

317
00:19:55,280 --> 00:20:02,390
So if you look on the parts right now, it includes zero 4 to 4, 20 and three and four and four four.

318
00:20:02,750 --> 00:20:07,540
So there is no three for right now because default is it was in the previous block.

319
00:20:07,820 --> 00:20:11,900
So in this part, we don't have three, four, so we haven't visit three four yet.

320
00:20:12,110 --> 00:20:14,150
So we will now visit three for next.

321
00:20:14,930 --> 00:20:19,010
So once we proceed further at this moment, you will see that we are on four four.

322
00:20:19,190 --> 00:20:23,210
It is an article two and it is part of the graph and parts.

323
00:20:23,420 --> 00:20:26,300
Just initialize two empty list within the neighbor node.

324
00:20:26,600 --> 00:20:28,820
The first is always obviously the case node.

325
00:20:29,690 --> 00:20:30,920
We ignore the case node.

326
00:20:31,070 --> 00:20:34,760
We then within the next node that is three, three, three, three is already visited.

327
00:20:35,060 --> 00:20:36,020
So we don't visit that.

328
00:20:36,440 --> 00:20:37,070
We go back.

329
00:20:38,410 --> 00:20:43,720
And then we have the next day with no that is three four or it is it is just not part of the park.

330
00:20:44,410 --> 00:20:50,050
So was it that not called a function a game called stack increased by one and then.

331
00:20:51,270 --> 00:20:57,930
Once we proceed further, we add this to the part three, four to the part that includes 04242, three,

332
00:20:57,930 --> 00:21:00,840
four, four and three, four, four and three, four.

333
00:21:01,230 --> 00:21:02,280
But this isn't a path now.

334
00:21:02,640 --> 00:21:06,750
And if you look right over here, the start is now three four and is three four.

335
00:21:07,080 --> 00:21:08,760
So these both gets equal.

336
00:21:08,970 --> 00:21:09,960
So we return the pot.

337
00:21:10,260 --> 00:21:14,030
So we have found a path that leads up to that goes know it.

338
00:21:14,340 --> 00:21:15,690
So we are visiting three four.

339
00:21:16,350 --> 00:21:17,790
So three, four is the gold node.

340
00:21:18,600 --> 00:21:21,330
And this means that we have found a path that leads up to the gold.

341
00:21:21,650 --> 00:21:27,360
So this is from 042242332442, three, four.

342
00:21:27,660 --> 00:21:29,010
So we have on the second pot.

343
00:21:29,250 --> 00:21:33,510
So this gets output as new pots and this gets concatenated to the path.

344
00:21:33,840 --> 00:21:36,630
So we have now found two paths to our gold note.

345
00:21:38,740 --> 00:21:41,860
So we proceed further and then proceed to the next case.

346
00:21:42,310 --> 00:21:44,380
Now for the next case, you're building for four.

347
00:21:44,710 --> 00:21:48,970
So we are still three, three, and we have now visited three or four and they're only left for us to

348
00:21:48,970 --> 00:21:50,440
do is to visit six for.

349
00:21:51,510 --> 00:21:55,440
So if you look if you move further, you will see that maybe one or 264.

350
00:21:56,190 --> 00:21:58,140
So you're visiting six for now.

351
00:21:59,070 --> 00:22:02,640
It is not part of the path as it is evident right over here.

352
00:22:03,270 --> 00:22:08,970
And then it was at six four called the function again and then this get good coordinated to the part.

353
00:22:09,480 --> 00:22:10,320
This is not equal to.

354
00:22:10,320 --> 00:22:11,880
And this is part of the curve.

355
00:22:13,180 --> 00:22:15,130
And baskets in a slice to an empty list.

356
00:22:15,820 --> 00:22:17,110
And then the neighbor.

357
00:22:17,110 --> 00:22:17,380
No.

358
00:22:17,410 --> 00:22:20,750
464064172264.

359
00:22:20,770 --> 00:22:26,350
You will see that it has only one neighbor node that is for pork, but for vote is already visited because

360
00:22:26,350 --> 00:22:29,470
we have been through that node two needs to this node.

361
00:22:29,770 --> 00:22:33,100
So we cannot go back and we need to simply ignore six four.

362
00:22:33,550 --> 00:22:34,570
So what would happen is.

363
00:22:35,850 --> 00:22:38,400
But if you look right over here, then they would know it would be.

364
00:22:39,860 --> 00:22:41,690
Firstly the case, not ignore the case.

365
00:22:41,960 --> 00:22:47,150
The next is the fourth for what we have already been to for, for as it is indicated from the fourth.

366
00:22:47,480 --> 00:22:50,280
So if you look at the part you've already been to for four.

367
00:22:50,690 --> 00:22:52,010
So we will not visit that node.

368
00:22:52,460 --> 00:22:54,610
Then we can return an empty list or two.

369
00:22:54,620 --> 00:22:55,190
Empty list.

370
00:22:55,670 --> 00:22:56,540
This is done.

371
00:22:57,410 --> 00:22:58,070
You go back.

372
00:22:59,230 --> 00:23:02,140
We go back to four, four because it was already visited.

373
00:23:02,980 --> 00:23:08,200
And then we see that we have visited all neighbors of four, four, so we can go back again.

374
00:23:08,920 --> 00:23:11,590
And this time you will see the stock node now become.

375
00:23:11,800 --> 00:23:12,310
So you see.

376
00:23:13,090 --> 00:23:17,440
So we go back to treaty and you will see that we have visited three, four, four, four and three,

377
00:23:17,440 --> 00:23:17,740
one.

378
00:23:18,130 --> 00:23:22,900
So we need to go back again because all the neighboring nodes of three three have also been visited.

379
00:23:28,690 --> 00:23:32,680
So this time we go back one more step and go back to two four.

380
00:23:32,890 --> 00:23:34,480
And you will see the two four.

381
00:23:34,480 --> 00:23:38,580
We have already missed the zero four and the Canadian of two four.

382
00:23:38,950 --> 00:23:41,950
The only thing left for us to do is to visit the final.

383
00:23:41,950 --> 00:23:43,570
They were node of the three port.

384
00:23:44,440 --> 00:23:45,580
So this will be evident.

385
00:23:46,580 --> 00:23:47,420
Once they visited.

386
00:23:51,570 --> 00:23:55,740
Mostly it was the neighbor note for our two four that is left that is three four.

387
00:23:56,010 --> 00:24:01,140
We visit the T for this guide to the path, which is right now zero four and two four.

388
00:24:02,120 --> 00:24:07,280
This gets added to the pot, which becomes zero four, two, four and three four as three four is a

389
00:24:07,280 --> 00:24:10,010
start and three four is, then this becomes equal.

390
00:24:10,250 --> 00:24:11,300
So we return the part.

391
00:24:11,480 --> 00:24:13,100
So we have found another solution.

392
00:24:13,850 --> 00:24:15,350
So you're visiting t four.

393
00:24:16,070 --> 00:24:17,390
So T four is the goal.

394
00:24:17,780 --> 00:24:18,830
So this is the part.

395
00:24:18,830 --> 00:24:20,960
The third part that we found was the goal.

396
00:24:21,320 --> 00:24:24,050
So this is the final part that we found was the goal.

397
00:24:24,320 --> 00:24:28,880
And in total, we have found three paths that lead up to the goal.

398
00:24:29,150 --> 00:24:32,030
And this will get concatenated for the false list.

399
00:24:32,750 --> 00:24:33,170
And.

400
00:24:35,120 --> 00:24:36,980
Once we can coordinate all these parts.

401
00:24:39,080 --> 00:24:39,890
And return them.

402
00:24:40,220 --> 00:24:42,890
This function gets executed in the baskets return.

403
00:24:43,400 --> 00:24:44,510
We now have the possibility.

404
00:24:45,350 --> 00:24:48,320
And if you expand this path, you will see that three paths that we have.

405
00:24:48,740 --> 00:24:52,070
And then we will print out the user, return the mean.

406
00:24:54,140 --> 00:24:55,070
And if for display.

407
00:24:58,330 --> 00:25:02,200
And if you display a terminal, you will see that the path that we have just found.

408
00:25:04,080 --> 00:25:05,190
So these are the bars.

409
00:25:06,160 --> 00:25:10,900
So these are all possible paths that lead up to the goal node from 04234.

410
00:25:11,050 --> 00:25:13,420
We have found three paths to lead up to the goal.

411
00:25:13,720 --> 00:25:19,750
So this is how recursion can be used to find all possible paths inside a DFS algorithm.

412
00:25:20,200 --> 00:25:25,930
So this was working correctly and we can now test it out on our original maze and find all possible

413
00:25:25,930 --> 00:25:29,020
paths that lead up to the maze exit building.

414
00:25:29,410 --> 00:25:29,950
Thank you.

415
00:25:30,320 --> 00:25:30,550
And.

416
00:25:30,550 --> 00:25:30,880
But.

417
00:25:32,270 --> 00:25:32,740
All right.

418
00:25:33,200 --> 00:25:39,140
In the previous session, we not only debunked but also rated the good part function for the DFS.

419
00:25:39,530 --> 00:25:44,150
Now all that is left for us to do is to simply integrated to the whole project.

420
00:25:44,620 --> 00:25:50,270
Now, for this reason, I made a few modifications in a few files, starting with the board part, planning

421
00:25:50,270 --> 00:25:52,790
that part apart from the DFS.

422
00:25:53,060 --> 00:25:56,240
I've got a new class that is brought forth then.

423
00:25:56,570 --> 00:25:59,540
And the reason for creating this class is twofold.

424
00:25:59,930 --> 00:26:05,840
The first reason being that I wanted to display the phone part back on the miss from which it was extracted

425
00:26:05,840 --> 00:26:06,140
from.

426
00:26:06,440 --> 00:26:12,260
Because just printing out the part on the console seems to be not or insufficient.

427
00:26:12,590 --> 00:26:19,280
And the reason is that for the larger maze is displaying that the path in the form of tuples does not

428
00:26:19,280 --> 00:26:22,400
help in understanding whether it was the correct path or not.

429
00:26:23,000 --> 00:26:29,360
Rather, displaying it on the maze from which it was extracted from seems to be a much better option.

430
00:26:29,960 --> 00:26:37,040
The other reason is that I wanted to develop and test out different path planning algorithms other than

431
00:26:37,040 --> 00:26:37,670
DFS.

432
00:26:38,150 --> 00:26:44,810
So creating a separate class that has access to all these path planning algorithms and can be tested

433
00:26:45,170 --> 00:26:51,080
by simply selecting a method as an argument for a function seems to be the best option.

434
00:26:52,060 --> 00:26:58,720
And the other modification that I did was inside the boat mapping out by way of a new instance variable

435
00:26:58,720 --> 00:27:00,090
that is not me.

436
00:27:00,640 --> 00:27:07,150
And this variable gets initialized inside the graph y function where it gets initialized to thin crop

437
00:27:07,600 --> 00:27:09,370
or the boundary to move me.

438
00:27:10,090 --> 00:27:17,680
Now this setup is well initialized and created because of the path planning function of find, path

439
00:27:17,680 --> 00:27:18,340
and display.

440
00:27:18,610 --> 00:27:24,610
And its third argument is third argument is the means on which you want to draw the following part.

441
00:27:25,000 --> 00:27:30,880
So this is the maze that will get become as a third argument that was extracted in the mapping or part.

442
00:27:31,480 --> 00:27:38,830
So now we can simply head over to Salvador part and import this board port planner class and then call

443
00:27:39,040 --> 00:27:40,620
the fine python display function.

444
00:27:41,230 --> 00:27:42,430
So we do exactly that.

445
00:27:43,270 --> 00:27:43,960
We import.

446
00:27:45,380 --> 00:27:52,010
Bought porcelain glass from the bought bought planning file by writing import bar pot planner.

447
00:27:52,700 --> 00:27:58,820
We had only worked with a solar class after we have created the object for bought mapper required the

448
00:27:58,820 --> 00:27:59,360
object.

449
00:28:00,370 --> 00:28:01,660
For Bought Planet.

450
00:28:05,940 --> 00:28:07,770
And then rewrite.

451
00:28:08,040 --> 00:28:08,370
What?

452
00:28:08,370 --> 00:28:09,510
Portland an object.

453
00:28:10,490 --> 00:28:14,060
And then we head on over to the main solving function here.

454
00:28:14,150 --> 00:28:17,060
After we perform the mapping process or the mapping stage.

455
00:28:18,970 --> 00:28:24,190
We now call the port plan a function of fine ports.

456
00:28:24,190 --> 00:28:26,980
And the split of this takes in four arguments.

457
00:28:27,220 --> 00:28:30,220
The first being the graph that was extracted in the mapping stage.

458
00:28:30,670 --> 00:28:38,140
So we pass in the graph by writing self dot board member dot graph.

459
00:28:39,270 --> 00:28:39,850
Da da.

460
00:28:40,620 --> 00:28:43,570
So this is the graph that becomes the first argument for this function.

461
00:28:43,950 --> 00:28:49,500
Then we need to provide the start and end point are basically the entry and exit point of the miss.

462
00:28:49,980 --> 00:28:52,140
So start point just initialize to self.

463
00:28:53,310 --> 00:29:02,280
But bought matter not drop not stuck in the same way we we we initialize the end point.

464
00:29:03,860 --> 00:29:06,830
For our partner that glass and that is theft or bought.

465
00:29:06,830 --> 00:29:08,080
My partner dropped or dead.

466
00:29:09,070 --> 00:29:12,760
And the last thing that is left for us to do is to simply describe the mess.

467
00:29:13,900 --> 00:29:18,250
The mist will get initialized to surf dot board mapper.

468
00:29:20,680 --> 00:29:21,240
Not me.

469
00:29:21,850 --> 00:29:26,450
So the mess that we have just initialized earlier in the bot mapping class to 10:00.

470
00:29:26,890 --> 00:29:32,200
So these are the four arguments that become the inputs to find path and display.

471
00:29:32,530 --> 00:29:37,780
And this will simply get us all possible paths from the main entry to the main exit.

472
00:29:38,140 --> 00:29:44,980
And once it finds all those possible paths, it will display one part to the user so that we could validate

473
00:29:45,190 --> 00:29:47,440
whether those phone paths were correct or not.

474
00:29:47,950 --> 00:29:52,300
Now we can simply head on over to a terminal where I've already started the simulation.

475
00:29:53,020 --> 00:29:55,810
Run the miss solver after building it.

476
00:29:57,160 --> 00:29:59,590
Once I build this, I run the missile over.

477
00:30:00,280 --> 00:30:05,580
And you will see after the process completes, we have the maze occupancy grid dressing space for.

478
00:30:06,730 --> 00:30:11,230
Gives us the interest points and the connected note that was output or the mapping process.

479
00:30:11,860 --> 00:30:13,360
Then pressing spacebar again.

480
00:30:14,540 --> 00:30:17,480
We will get the phone back from the DFS.

481
00:30:18,140 --> 00:30:24,050
So here you have simply displayed the phone card from the DFS that leads from the maze entry to the

482
00:30:24,050 --> 00:30:27,320
maze exit and is shown in the form of beautiful colors.

483
00:30:27,740 --> 00:30:35,150
So this has been relative to twice now that the DFS is indeed working correctly and finding the bot

484
00:30:35,150 --> 00:30:36,860
from the maze entry to the maze exit.

485
00:30:37,280 --> 00:30:44,090
So now we can head on over to using DFS to find the shortest path to the go from the maze entry to the

486
00:30:44,090 --> 00:30:45,650
maze exit building.

487
00:30:46,010 --> 00:30:46,430
Thank you.

488
00:30:46,430 --> 00:30:46,540
And.

489
00:30:46,550 --> 00:30:46,850
But.