1
00:00:00,180 --> 00:00:04,230
All right guys, it's time for the final project of today.

2
00:00:04,860 --> 00:00:09,860
And the goal is to be able to write some code here in Reeborg's world,

3
00:00:10,590 --> 00:00:13,320
to be able to get our the little robot

4
00:00:13,350 --> 00:00:17,730
to be able to navigate to the goal and go through a maze

5
00:00:18,000 --> 00:00:22,230
no matter what the maze look like. So if you go back to Reeborgs world,

6
00:00:22,230 --> 00:00:23,640
if you already got a link open..

7
00:00:23,910 --> 00:00:28,080
if you don't, then simply click on the direct link in the course resources

8
00:00:28,380 --> 00:00:29,760
and it should take you here.

9
00:00:30,180 --> 00:00:34,770
And we've got the maze selected in the dropdown, which is right here.

10
00:00:36,150 --> 00:00:41,130
Here, we have a maze. And even though the maze doesn't change,

11
00:00:41,520 --> 00:00:46,520
the robot does. The direction that the robot is going to face is completely

12
00:00:46,920 --> 00:00:51,390
random, the position of the robot is also random.

13
00:00:51,420 --> 00:00:54,180
So you can see every time I restart the game,

14
00:00:54,600 --> 00:00:58,800
it will face a different direction. So in this case, it's facing up

15
00:00:59,160 --> 00:01:02,730
But the next time it might be facing down, in this case.

16
00:01:03,210 --> 00:01:08,130
And it's also always going to start at a random location in the maze.

17
00:01:08,640 --> 00:01:10,380
If you click on the world info,

18
00:01:10,590 --> 00:01:15,240
it will tell you that the secret to getting the robot to complete the maze is to

19
00:01:15,240 --> 00:01:18,540
get it to follow along the right edge of the maze.

20
00:01:19,110 --> 00:01:23,520
If it starts anywhere in the maze and it just continues following along

21
00:01:23,520 --> 00:01:24,510
the right wall,

22
00:01:24,810 --> 00:01:28,770
it should eventually get to the final destination.

23
00:01:29,340 --> 00:01:33,060
For example, like this. Now in this case,

24
00:01:33,090 --> 00:01:38,090
the robot is not making a beeline straight to the exit as if it could see what

25
00:01:38,940 --> 00:01:43,890
we can see, but it is following a strategy or rather what you would call in

26
00:01:43,890 --> 00:01:45,600
programming, an algorithm.

27
00:01:46,020 --> 00:01:50,760
And the algorithm here is to simply follow along the right edge of the wall.

28
00:01:51,360 --> 00:01:52,980
And if the right side is clear,

29
00:01:53,010 --> 00:01:58,010
then continue going right until it's no longer clear at which point it should

30
00:01:59,010 --> 00:02:03,900
just go straight. And if you can't go straight and you can't go right,

31
00:02:04,230 --> 00:02:07,710
then the last option is to turn left.

32
00:02:08,160 --> 00:02:12,480
It's almost like the robot is getting a set of instructions in terms of

33
00:02:12,480 --> 00:02:17,040
hierarchy. The most important telling it to turn right if it can,

34
00:02:17,430 --> 00:02:20,520
if it can't turn right then go straight ahead. And finally,

35
00:02:20,520 --> 00:02:22,770
if it can't turn right or go straight ahead,

36
00:02:23,070 --> 00:02:25,920
then to turn left as a last resort.

37
00:02:26,400 --> 00:02:30,120
So you're going to need to use a lot of the functions that you saw previously

38
00:02:30,120 --> 00:02:33,240
such as move, turn_left, and testing

39
00:02:33,240 --> 00:02:36,270
whether if the front is clear or the right is clear,

40
00:02:36,660 --> 00:02:40,710
or there's a wall in the front or a wall in the right. And whether

41
00:02:40,710 --> 00:02:45,300
if the robot is the goal. Think about how you can use a while loop

42
00:02:45,660 --> 00:02:47,370
and also the conditional

43
00:02:47,400 --> 00:02:51,990
if, elif, else statements to achieve this goal and get our robot

44
00:02:52,140 --> 00:02:54,660
to be able to go to the final destination

45
00:02:54,990 --> 00:02:59,160
no matter where it starts out and what direction it's facing.

46
00:02:59,830 --> 00:03:00,820
Pause the video now

47
00:03:00,850 --> 00:03:03,970
and try to use what you've learned to complete this final project.

48
00:03:04,410 --> 00:03:09,410
[inaudible]

49
00:03:10,620 --> 00:03:14,700
All right. So did you manage to complete this challenge? If not,

50
00:03:14,910 --> 00:03:18,870
let's work through the solution together. The first thing we need to do,

51
00:03:19,050 --> 00:03:23,880
which we've always pretty much needed completing each of these challenges, is we

52
00:03:23,880 --> 00:03:27,180
need a way to turn right. So I'm not gonna type it all out again.

53
00:03:27,480 --> 00:03:29,640
This should be already pretty clear; turn_right

54
00:03:29,640 --> 00:03:32,280
is just turning left three times. Now,

55
00:03:32,280 --> 00:03:36,960
the next thing we need to do is we need to tell the robot to do things and to

56
00:03:36,960 --> 00:03:40,500
check for things until it reaches the goal.

57
00:03:40,890 --> 00:03:44,310
We know that we have this test called at_goal.

58
00:03:44,700 --> 00:03:49,700
So we can use a while loop to get the robot to continue working until it reaches

59
00:03:50,880 --> 00:03:55,880
the goal. To define that, we could say while not at goal,

60
00:03:57,270 --> 00:04:02,270
so basically keep repeating the instructions inside this while loop until at_goal

61
00:04:03,510 --> 00:04:07,050
becomes true and not true is false.

62
00:04:07,230 --> 00:04:11,100
So once this condition becomes false, then our while loop stops.

63
00:04:12,090 --> 00:04:17,089
So what we were told in the world info is we should follow along the right edge.

64
00:04:17,519 --> 00:04:22,520
We should test to see if the right side is clear, and if it is,

65
00:04:22,920 --> 00:04:25,650
then we should turn right and go straight.

66
00:04:25,830 --> 00:04:28,470
So that basically means moving right.

67
00:04:28,950 --> 00:04:30,870
Let's use an if statement to test

68
00:04:30,900 --> 00:04:35,900
if right_is_clear and in this instance,

69
00:04:36,390 --> 00:04:40,890
so in this if block, we're going to say well turn_right

70
00:04:40,920 --> 00:04:43,530
using our prebuilt function up here.

71
00:04:44,250 --> 00:04:49,020
And then once you're facing the right then move forwards.

72
00:04:49,680 --> 00:04:54,090
This should achieve a right move, so from here to here

73
00:04:54,090 --> 00:04:54,923
for example.

74
00:04:55,650 --> 00:05:00,030
Now let's test this and see what happens. In this case, the right is clear

75
00:05:00,030 --> 00:05:03,270
so it moved right The right is not clear

76
00:05:03,330 --> 00:05:05,160
so it doesn't know what else to do

77
00:05:05,160 --> 00:05:09,270
and it's now stuck in what we would call an infinite loop.

78
00:05:11,010 --> 00:05:16,010
And it will never stop until the browser actually forces it to by crashing.

79
00:05:16,860 --> 00:05:21,860
So what we have to do instead is we have to provide an alternative condition;

80
00:05:22,770 --> 00:05:25,860
when the right is not clear, what should it do?

81
00:05:26,460 --> 00:05:29,790
So we're going to provide that condition by using an elif statement.

82
00:05:30,300 --> 00:05:34,650
And what we want to say is if the right is not clear,

83
00:05:35,460 --> 00:05:39,150
well, then maybe you should check if the front is clear.

84
00:05:41,460 --> 00:05:45,450
And if that is the case, then simply just move forwards.

85
00:05:46,410 --> 00:05:50,970
Now, this would work unless we're in the situation that we're in right now

86
00:05:51,030 --> 00:05:52,260
where we're boxed in

87
00:05:52,620 --> 00:05:56,820
and the only side that's clear is actually the remaining one, which is the left.

88
00:05:58,040 --> 00:06:00,590
That's why we have to put in the last line of code

89
00:06:00,950 --> 00:06:05,900
which is going to be an else statement. So in all other conditions, um,

90
00:06:05,930 --> 00:06:09,170
when the right is not clear and the front is not clear,

91
00:06:09,380 --> 00:06:12,230
so once both of these have been checked and they're false,

92
00:06:12,590 --> 00:06:15,110
then actually just turn left.

93
00:06:16,730 --> 00:06:17,540
So now

94
00:06:17,540 --> 00:06:20,300
you can see that when our robot is able to go right,

95
00:06:20,540 --> 00:06:23,420
it will try to follow along the right wall.

96
00:06:24,110 --> 00:06:28,500
But when it can't go right, it will go forwards instead.

97
00:06:28,500 --> 00:06:32,540
And when it can't go right or go forward, then it's gonna turn left

98
00:06:32,810 --> 00:06:35,600
and hopefully the next time it checks the loop,

99
00:06:35,900 --> 00:06:39,380
the front will be clear and it will be able to move forwards.

100
00:06:40,010 --> 00:06:45,010
So notice how our robot is somewhat haphazardly navigating through this maze,

101
00:06:45,980 --> 00:06:49,550
but it is following the algorithm that we specified,

102
00:06:49,580 --> 00:06:54,580
which is to follow along the right-handed wall until you reach the goal.

103
00:06:56,180 --> 00:07:01,180
And that's what these few lines of code does using our while statements, our if,

104
00:07:01,490 --> 00:07:05,360
elif, else statements and also our turn_right function.

105
00:07:06,260 --> 00:07:09,050
Now, while everything seems to work all right,

106
00:07:09,440 --> 00:07:14,440
there are select cases where the robot might start out in a position and face a

107
00:07:16,490 --> 00:07:21,200
particular direction that gets the robot into an endless loop.

108
00:07:21,770 --> 00:07:23,360
So here's an example.

109
00:07:23,720 --> 00:07:28,310
Let's say the robot starts off at this particular position facing down.

110
00:07:28,850 --> 00:07:32,270
If we go ahead and let the robot run the code,

111
00:07:32,720 --> 00:07:37,250
you can see that firstly, there's over a thousand steps in the code.

112
00:07:37,850 --> 00:07:42,740
And what happens is because the robot doesn't have a wall on it's right,

113
00:07:43,160 --> 00:07:48,160
it's going to keep looping through the circle because after all we're telling it

114
00:07:49,520 --> 00:07:50,930
if your right side is clear,

115
00:07:50,960 --> 00:07:55,910
turn right and move. And the right is always clear when it's inside this

116
00:07:56,000 --> 00:08:00,560
boundary box. So depending on where the robot starts out,

117
00:08:00,860 --> 00:08:04,940
it might get itself into what we call it an infinite loop,

118
00:08:04,970 --> 00:08:08,180
because you can see the code just goes again and again,

119
00:08:08,240 --> 00:08:12,950
through this while statement, and the robot's never going to be able to escape

120
00:08:13,220 --> 00:08:14,210
from this position.

121
00:08:15,050 --> 00:08:20,050
So this is one of the things that happens to your programs.

122
00:08:20,540 --> 00:08:24,650
Sometimes there are edge cases which you might not have thought of

123
00:08:25,010 --> 00:08:28,040
but it's only through testing the code do you discover them.

124
00:08:28,940 --> 00:08:33,940
Now this particular issue I would say is more of an intermediate debugging

125
00:08:34,940 --> 00:08:35,773
problem.

126
00:08:36,169 --> 00:08:41,169
So if you're somebody who's already really comfortable with Python and you want

127
00:08:42,260 --> 00:08:46,190
to try out debugging this particular problem,

128
00:08:46,670 --> 00:08:51,670
then I've included some problem worlds for you to test your code against.

129
00:08:54,530 --> 00:08:54,800
Now,

130
00:08:54,800 --> 00:08:59,610
if you are somebody who is still getting to grips with Python,

131
00:08:59,640 --> 00:09:03,600
I would say this is not the right time point to tackle this challenge,

132
00:09:04,020 --> 00:09:09,020
and I would go ahead and make a note to yourself that once you've completed day

133
00:09:09,330 --> 00:09:14,330
15 and you're firmly within the intermediate territory of Python to come back to

134
00:09:16,260 --> 00:09:21,260
this problem and to continue to debug this particular edge case.

135
00:09:22,350 --> 00:09:26,820
Now, if you are a beginner, I recommend to skip the rest of the video

136
00:09:27,060 --> 00:09:31,680
but make a bookmark and make a note here so that you know to come back. Now,

137
00:09:31,710 --> 00:09:33,990
if you are more of an intermediate programmer,

138
00:09:34,350 --> 00:09:36,780
then let's go ahead and debug this.

139
00:09:37,590 --> 00:09:42,590
So what you can do with Reeborg's world is you can actually create a file to load

140
00:09:43,650 --> 00:09:46,530
up a particular map and robot position.

141
00:09:47,610 --> 00:09:52,410
So what I've done is I've created a bunch of problem worlds for you to test your

142
00:09:52,410 --> 00:09:56,070
code against that we know if you use a normal code,

143
00:09:56,100 --> 00:09:58,140
it's definitely going to get into an infinite loop.

144
00:09:58,860 --> 00:10:02,970
So what you need to do is head to the course resources for this lesson

145
00:10:03,360 --> 00:10:05,610
and then download the zip file

146
00:10:05,670 --> 00:10:09,720
which contains three problem worlds for you to test your code against.

147
00:10:10,350 --> 00:10:14,490
And then in Reeborgs world, you're going to click on additional options,

148
00:10:14,970 --> 00:10:19,020
open world from file and you're going to select that folder

149
00:10:19,020 --> 00:10:23,340
which hopefully you've unzipped, and go through each of these problem worlds

150
00:10:23,400 --> 00:10:27,630
testing your code in all of the cases. Now, when you open this up,

151
00:10:27,660 --> 00:10:32,490
you can close off this box and the robot will start at a particular problem

152
00:10:32,490 --> 00:10:37,490
position, facing a direction that is going to cause it to go into an

153
00:10:37,590 --> 00:10:40,380
infinite loop. And you can know this ahead of time

154
00:10:40,380 --> 00:10:45,380
because when you actually go to start the robot and you hit play, when you 

155
00:10:45,660 --> 00:10:48,150
see the number of steps here over a thousand,

156
00:10:48,510 --> 00:10:52,680
it usually means that you're probably in a situation where it's going to turn into

157
00:10:52,680 --> 00:10:53,520
an infinite loop.

158
00:10:54,180 --> 00:10:59,180
So write your code here and then test it to make sure that the step count goes

159
00:10:59,250 --> 00:11:04,250
down below 1000 and your robot doesn't get stuck in this endless circle. Now,

160
00:11:06,480 --> 00:11:10,680
because the different problem worlds can have different solutions,

161
00:11:10,980 --> 00:11:15,630
but what you're aiming for is one solution code that solves all of the problem

162
00:11:15,630 --> 00:11:16,350
worlds,

163
00:11:16,350 --> 00:11:21,240
I want you to test your code against all three of these problem worlds I've

164
00:11:21,240 --> 00:11:22,073
created for you.

165
00:11:23,250 --> 00:11:27,660
So here's the time, if you want to tackle this challenge, to go ahead and pause

166
00:11:27,660 --> 00:11:32,400
the video and see if you can debug this pretty hard problem.

167
00:11:32,910 --> 00:11:36,450
It took me a while. So I think it's going to take you a while as well.

168
00:11:36,690 --> 00:11:40,950
But you might be smarter. It might take less time. So good luck,

169
00:11:41,100 --> 00:11:45,030
pause the video and we'll go through the solution together a little bit later

170
00:11:45,030 --> 00:11:45,863
on.

171
00:11:51,380 --> 00:11:55,510
All right. So first let's try and figure out what the problem is.

172
00:11:55,870 --> 00:12:00,870
The problem here is that every time when the robot's right side is clear,

173
00:12:01,600 --> 00:12:06,430
our code tells it to turn to that direction, move forwards,

174
00:12:06,880 --> 00:12:11,860
and then check to see if it's at the goal. So it's not, and again

175
00:12:11,860 --> 00:12:15,610
the right side is clear so it turns right and moves, turns right and moves,

176
00:12:15,670 --> 00:12:20,200
turns right and moves. So basically in any of these four positions,

177
00:12:20,590 --> 00:12:22,360
depending on the way it's facing,

178
00:12:22,660 --> 00:12:26,170
there might not be a wall on the right side of the robot.

179
00:12:26,620 --> 00:12:29,860
So that is the key to solving this bug.

180
00:12:30,820 --> 00:12:35,820
We have to get our robot to a starting position where it has a wall on the right

181
00:12:36,760 --> 00:12:38,050
side of the robot.

182
00:12:39,520 --> 00:12:43,960
Now I've been thinking about various ways of doing this and the shortest most

183
00:12:43,960 --> 00:12:48,910
succinct way that's also most understandable, I think, is this.

184
00:12:49,510 --> 00:12:53,500
So if we create another while loop before this while loop runs,

185
00:12:53,530 --> 00:12:55,750
so remember the code goes from top to bottom,

186
00:12:55,810 --> 00:12:57,670
it's going to hit this while loop first.

187
00:12:58,390 --> 00:13:03,220
And we check while the front is clear,

188
00:13:04,030 --> 00:13:08,170
well then the robot is not next to a wall, right? Such as in this case.

189
00:13:08,740 --> 00:13:13,270
Well, if that is the case, we're going to tell our robot to just move forwards.

190
00:13:13,870 --> 00:13:18,580
So this means that our robot is going to seek out a wall. So in this case,

191
00:13:18,580 --> 00:13:19,413
for example,

192
00:13:20,080 --> 00:13:25,080
it's going to go forwards until it reaches a wall.

193
00:13:27,970 --> 00:13:32,740
So it's going to loop through that loop twice and it moves twice until it hits a

194
00:13:32,740 --> 00:13:35,950
wall in front. Now this is the point which we want,

195
00:13:36,250 --> 00:13:40,240
because we want to make sure that now that it's hit a wall in front,

196
00:13:40,690 --> 00:13:45,400
that it's definitely got a wall on the right side of the robot. So what do we do?

197
00:13:45,790 --> 00:13:49,330
Well, once it's hit a wall, so it's exited this while loop,

198
00:13:49,570 --> 00:13:52,000
we're going to tell it to turn left.

199
00:13:52,420 --> 00:13:56,080
So this loop makes sure that the robot has a wall in front of it.

200
00:13:56,590 --> 00:13:59,890
And once it's found a wall in front, we tell it to turn left

201
00:14:00,190 --> 00:14:03,010
to turn that wall on to the right side of the robot.

202
00:14:03,610 --> 00:14:08,350
So now you can see we're going through this while loop. First front is clear,

203
00:14:08,350 --> 00:14:10,150
so it's going to move.

204
00:14:12,220 --> 00:14:15,760
And then front is still clear after that one move

205
00:14:15,820 --> 00:14:20,770
so it's going to move again until it's hit a wall in front. Now,

206
00:14:20,770 --> 00:14:21,400
at this point,

207
00:14:21,400 --> 00:14:24,910
it exits the while loop and it goes to the next line of instruction

208
00:14:25,180 --> 00:14:29,770
which tells it to turn left. Now that the robot has turned left

209
00:14:29,890 --> 00:14:34,890
it now has a wall on the right side and it enters the next loop.

210
00:14:35,770 --> 00:14:40,420
So in this loop, if the right side is clear, turn right and move.

211
00:14:40,720 --> 00:14:45,070
If the front is clear, just simply move forward, otherwise turn left.

212
00:14:45,490 --> 00:14:50,230
So as long as the robot started in a position where there is a wall on the right

213
00:14:50,230 --> 00:14:54,440
side of it, right next to it, it's never going to get into that infinite loop with

214
00:14:55,130 --> 00:14:59,320
this code. So this is one solution to this problem.

215
00:14:59,800 --> 00:15:02,080
Now there's lots of other solutions,

216
00:15:02,320 --> 00:15:07,320
but you gotta make sure that your solution works in every single one of these

217
00:15:08,410 --> 00:15:09,280
test cases.

218
00:15:09,640 --> 00:15:13,870
So we can go ahead and open up problem world 2 where the robot starts at a

219
00:15:13,870 --> 00:15:16,240
different position, facing a different position,

220
00:15:16,570 --> 00:15:21,280
and we want to make sure that still we don't have an infinite loop. In this case,

221
00:15:21,340 --> 00:15:25,930
it doesn't. So that's great. And finally, let's test the last one,

222
00:15:26,170 --> 00:15:27,760
which is a problem world 3,

223
00:15:28,420 --> 00:15:33,420
and now we can run our program and you can see it's also less than a thousand

224
00:15:34,240 --> 00:15:36,190
steps. So, it works.

225
00:15:37,000 --> 00:15:41,980
So this is a bit of advanced debugging because we're now testing our

226
00:15:41,980 --> 00:15:46,980
code against various terrible scenarios where the robot starts off at a position

227
00:15:48,310 --> 00:15:53,260
where it's really dangerous and can get into these infinite loops. Now,

228
00:15:53,290 --> 00:15:55,600
if you didn't manage to get the solution,

229
00:15:55,810 --> 00:15:59,410
don't despair and don't be too hard on yourself. This is a really,

230
00:15:59,830 --> 00:16:00,670
really hard one.

231
00:16:00,670 --> 00:16:05,470
And it took me a long time to find a solution that I think is readable and

232
00:16:05,590 --> 00:16:08,080
explainable and sort of makes sense.

233
00:16:08,800 --> 00:16:13,800
Now, it might be that you should put in a note in your calendar to come and

234
00:16:14,440 --> 00:16:16,510
revisit this issue in a week

235
00:16:16,690 --> 00:16:20,950
once you've had some time to think about it, and to really digest and understand

236
00:16:20,950 --> 00:16:23,860
the solution, then write the code yourself.

237
00:16:24,460 --> 00:16:27,460
Because you would have forgotten exactly what the code was,

238
00:16:27,520 --> 00:16:32,470
but you will still remember how it works. So if that is a case,

239
00:16:32,770 --> 00:16:37,240
this is what you should do. If you solved it by yourself, then congratulations.

240
00:16:37,240 --> 00:16:40,450
This is really, truly quite a difficult task.