1
00:00:00,506 --> 00:00:09,246
[ Silence ]

2
00:00:09,746 --> 00:00:11,416
>> Alright, hello every body.

3
00:00:11,416 --> 00:00:13,316
Welcome to Walkthrough 3.

4
00:00:13,626 --> 00:00:16,836
This week's Pset, among my
favorites, implementing the game

5
00:00:16,836 --> 00:00:19,696
of Fifteen although I still
can't solve the Fifteen puzzle.

6
00:00:19,996 --> 00:00:22,876
So, today's music was
Kesha, always entertaining

7
00:00:23,126 --> 00:00:25,686
and so this is the
agenda for today.

8
00:00:25,686 --> 00:00:28,276
So our problem set this week is
kinda split up into two parts.

9
00:00:28,376 --> 00:00:31,926
There's that part Find and
there's that other folder 15

10
00:00:32,146 --> 00:00:34,566
and so here is basically a
breakdown of all the things

11
00:00:34,566 --> 00:00:36,086
that you need to
do with our help.

12
00:00:36,436 --> 00:00:40,186
So, first thing you need to do
is look at this generate file

13
00:00:40,186 --> 00:00:42,166
and your task for this
part is pretty simple

14
00:00:42,166 --> 00:00:44,676
where you're given a C file,
it already works, we promise,

15
00:00:44,846 --> 00:00:46,196
and all you need to
do is comment it.

16
00:00:46,196 --> 00:00:47,966
So, if we are to comment
it you'd kinda need

17
00:00:47,966 --> 00:00:49,766
to understand how it works,

18
00:00:50,396 --> 00:00:52,076
so let's take a look
at what's going on.

19
00:00:52,076 --> 00:00:53,686
So, you have this generate file.

20
00:00:53,956 --> 00:00:56,066
Now when you run generate
it takes two arguments,

21
00:00:56,066 --> 00:01:00,506
N and this optional argument S,
so and when you supplied an N

22
00:01:00,506 --> 00:01:01,336
which it needs to have,

23
00:01:01,686 --> 00:01:04,416
that tells generate how many
random numbers that you want it

24
00:01:04,416 --> 00:01:07,016
to generate, just gonna
spit them out one per line.

25
00:01:08,116 --> 00:01:10,786
Now, this C value is used

26
00:01:10,786 --> 00:01:13,456
in what's called a
pseudo-random number generator.

27
00:01:14,016 --> 00:01:16,906
So, because computers can't
actually generate random

28
00:01:16,906 --> 00:01:19,446
numbers, we have
this pseudo-random

29
00:01:19,446 --> 00:01:22,356
so that it appears random
but it's not actually random.

30
00:01:23,276 --> 00:01:24,316
So what do I mean by that?

31
00:01:24,316 --> 00:01:26,386
So, using this built-in
function called rand,

32
00:01:26,706 --> 00:01:28,706
this was again written by
someone else and given to us

33
00:01:28,706 --> 00:01:32,396
for free, and rand can
openly take a seed value

34
00:01:32,396 --> 00:01:33,656
or kind of a starting value.

35
00:01:33,926 --> 00:01:36,026
That's not gonna be the
first value that's generated

36
00:01:36,246 --> 00:01:38,416
but if you start everything
off at the same seed,

37
00:01:38,416 --> 00:01:41,586
you're gonna get back the same
sequence of random numbers.

38
00:01:41,946 --> 00:01:44,186
So, let's just take a look
at what I mean by that.

39
00:01:44,406 --> 00:01:46,116
So, I'm inside my Pset 3 folder.

40
00:01:46,386 --> 00:01:49,416
I should note before you start
the Pset we're actually giving

41
00:01:49,416 --> 00:01:52,446
you some code this time, so
in order to get that code

42
00:01:52,446 --> 00:01:55,636
as the problem set mentions,
you wanna open up a terminal

43
00:01:55,636 --> 00:01:57,956
in your appliance, go
into your home directory

44
00:01:58,156 --> 00:02:02,116
and execute this guy, git
clone and then this long URL.

45
00:02:02,216 --> 00:02:05,246
What this is gonna do is
it's going to download some

46
00:02:05,246 --> 00:02:07,686
of the code that we've
written from that server

47
00:02:07,736 --> 00:02:09,686
and it's just gonna put it
inside your home directory,

48
00:02:09,686 --> 00:02:11,166
so you're all set
up and good to go.

49
00:02:11,766 --> 00:02:14,186
And so we'll see more about
git later in the semester

50
00:02:14,186 --> 00:02:16,456
but basically what this does
is it allows you to keep track

51
00:02:16,456 --> 00:02:17,916
of different versions
of your files.

52
00:02:18,316 --> 00:02:20,656
And so when we've been using
submit50 all semester we've

53
00:02:20,656 --> 00:02:22,406
actually been using
this thing called git

54
00:02:22,586 --> 00:02:24,176
and so every time
you're on submit50,

55
00:02:24,176 --> 00:02:27,146
we have a different version of
your submission on our servers,

56
00:02:27,316 --> 00:02:29,286
of course I'm gonna grade
the latest one but what

57
00:02:29,286 --> 00:02:32,286
that allows you to do is kinda
make backups and let's say,

58
00:02:32,286 --> 00:02:34,546
oh man, I messed up, I
really wish I could go back

59
00:02:34,546 --> 00:02:35,346
to 10 minutes ago.

60
00:02:35,636 --> 00:02:37,696
We'll with git you can
and we'll learn how to do

61
00:02:37,696 --> 00:02:38,796
that later in the semester.

62
00:02:38,946 --> 00:02:39,906
So, right now all you need

63
00:02:39,906 --> 00:02:41,966
to know is just run
this incantation

64
00:02:41,966 --> 00:02:43,816
and it's gonna download
all the files you need

65
00:02:43,986 --> 00:02:46,266
to start your Pset.

66
00:02:46,496 --> 00:02:49,426
So, back to generate, so
once I run that git clone,

67
00:02:49,426 --> 00:02:53,766
I have two folders, Fifteen
and Find, so let's go into Find

68
00:02:54,606 --> 00:02:57,726
and now we have this
generate.c that I mentioned

69
00:02:57,726 --> 00:02:58,896
so if you say make generate,

70
00:02:59,366 --> 00:03:00,546
it's gonna create this
generate [inaudible]

71
00:03:00,546 --> 00:03:02,576
and if I say generate,

72
00:03:02,866 --> 00:03:05,156
I just want three random
numbers, so there we go.

73
00:03:05,216 --> 00:03:08,156
So, there's three random
numbers or so it appears.

74
00:03:08,156 --> 00:03:11,256
I'll run it again and I get
three different random numbers.

75
00:03:11,256 --> 00:03:13,516
So, you notice here I
didn't specify a seed

76
00:03:13,516 --> 00:03:16,576
and so you kinda have to figure
out by reading generate.c,

77
00:03:16,576 --> 00:03:17,506
what that's actually doing.

78
00:03:17,936 --> 00:03:22,286
So, now if I say generate 3-1,
I'm specifying a seed value of 1

79
00:03:23,226 --> 00:03:25,236
so I get these three
random numbers.

80
00:03:25,466 --> 00:03:27,236
So, now let's run it
again with the same seed,

81
00:03:28,086 --> 00:03:30,356
I got these three random numbers

82
00:03:30,356 --> 00:03:32,916
which just maybe coincidentally
they're the same three,

83
00:03:32,986 --> 00:03:35,316
let's try again, it's
probably not so coincidental.

84
00:03:36,316 --> 00:03:38,896
So, this seed thing
determines what you're gonna get

85
00:03:38,896 --> 00:03:41,376
out of your random
number sequence so random

86
00:03:41,576 --> 00:03:44,036
but not really random,
so why is this useful?

87
00:03:44,936 --> 00:03:47,856
So, let's say that you're
running your sorting algorithm

88
00:03:48,096 --> 00:03:50,196
and it works sometimes and
not some of the other times.

89
00:03:50,366 --> 00:03:52,306
So let's say, okay,
these random numbers,

90
00:03:52,306 --> 00:03:53,916
I really wish I could
generate this sequence

91
00:03:53,916 --> 00:03:55,946
of 1024 random numbers again.

92
00:03:56,316 --> 00:03:58,686
Well, you can if just
specify the same seed.

93
00:03:59,096 --> 00:04:01,866
So, that's super helpful
that it can do that.

94
00:04:02,656 --> 00:04:05,476
So, also super helpful are these
little command line tricks.

95
00:04:06,116 --> 00:04:08,906
So, if you wanna take the output
of some program and instead

96
00:04:08,906 --> 00:04:11,596
of displaying it, out in the
terminal you wanna write it

97
00:04:11,596 --> 00:04:14,216
to some file, you can
just use this right arrow

98
00:04:14,216 --> 00:04:15,426
or the greater than operator.

99
00:04:16,246 --> 00:04:18,486
So, if I have the name of
my program like generate

100
00:04:18,586 --> 00:04:21,056
and then the greater than and
then where I wanna write it to,

101
00:04:21,056 --> 00:04:22,696
so this is probably just
gonna be a text file.

102
00:04:23,556 --> 00:04:27,736
So, if I do that, I can say
the same thing, generate 3-1

103
00:04:27,796 --> 00:04:30,816
but now I wanna pipe
it to numbers.txt.

104
00:04:30,816 --> 00:04:32,916
So, I ran it and
you know instead,

105
00:04:32,916 --> 00:04:35,006
I didn't get any random numbers,

106
00:04:35,566 --> 00:04:38,026
that's because we no longer
output it to the terminal

107
00:04:38,286 --> 00:04:41,576
but if we open up this
file, numbers.txt,

108
00:04:42,036 --> 00:04:44,156
there are my three
random numbers.

109
00:04:45,046 --> 00:04:47,366
So, similarly, if you wanna
go the other way around,

110
00:04:47,976 --> 00:04:50,486
you're gonna use the
less than operator.

111
00:04:50,486 --> 00:04:52,766
So, this says, okay,
I have some file

112
00:04:53,276 --> 00:04:54,776
and inside that file are lines.

113
00:04:55,376 --> 00:04:59,276
I want to send each of those
lines as input to this program,

114
00:04:59,846 --> 00:05:02,846
so finally we have the pipe.

115
00:05:03,586 --> 00:05:06,236
And the pipe is really just a
combination of these two things.

116
00:05:06,686 --> 00:05:09,276
So if I have a program, a
pipe and then another program,

117
00:05:09,276 --> 00:05:10,846
so let's say generate a pipe

118
00:05:10,846 --> 00:05:12,446
and then I call my
other executable find,

119
00:05:12,446 --> 00:05:15,976
what that's gonna do is send
all the output of program 1,

120
00:05:16,386 --> 00:05:19,106
it's gonna send it as
the input to program 2.

121
00:05:19,616 --> 00:05:21,106
So, there's a nice little trick

122
00:05:21,106 --> 00:05:22,736
where you can generate
a thousand numbers

123
00:05:23,096 --> 00:05:26,406
and then run find over those
1000 numbers using this pipe.

124
00:05:26,556 --> 00:05:29,136
I mentioned how to do that
in the Pset, just generate

125
00:05:29,486 --> 00:05:31,076
so then we're gonna
generate other numbers

126
00:05:31,076 --> 00:05:33,366
and then we're gonna send all
those to instead of a file,

127
00:05:33,576 --> 00:05:34,886
the input of another program

128
00:05:34,886 --> 00:05:36,416
which is gonna run
once that's all done.

129
00:05:37,426 --> 00:05:39,556
So, the Pset explains all
this in a little more detail

130
00:05:39,556 --> 00:05:42,636
but any questions on this cool
little hacky Unix trick we're

131
00:05:42,636 --> 00:05:43,116
doing here?

132
00:05:44,276 --> 00:05:44,506
Yup.

133
00:05:44,936 --> 00:05:48,516
>> How are all these seeds
chosen if not specified?

134
00:05:48,586 --> 00:05:50,456
>> So, how are these seeds
chosen if you don't specify,

135
00:05:50,456 --> 00:05:52,936
so that's where you have to
regenerate that C and find out.

136
00:05:52,966 --> 00:05:59,126
So, if we just open up
generate.c, you'll see we have

137
00:05:59,776 --> 00:06:03,006
to do a comment me, comment
me, comment me, comment me,

138
00:06:03,006 --> 00:06:06,536
comment me, so here we have
a mention of RT equals 3

139
00:06:06,536 --> 00:06:08,516
or RT not being equal to 3

140
00:06:08,606 --> 00:06:09,936
and it's doing these
two different things.

141
00:06:10,246 --> 00:06:11,366
And so you need to explain

142
00:06:11,366 --> 00:06:13,396
in this comment what's
actually going on here.

143
00:06:13,396 --> 00:06:16,946
So, you have one, two, three,
four things that you need

144
00:06:16,946 --> 00:06:18,706
to comment inside of
generate, just to prove to us

145
00:06:18,706 --> 00:06:20,446
that you know what's going on.

146
00:06:21,176 --> 00:06:22,846
So, questions on generate?

147
00:06:23,416 --> 00:06:26,156
Okay, cool.

148
00:06:26,156 --> 00:06:27,516
No code, you actually
have to write.

149
00:06:27,516 --> 00:06:29,076
So, there, here are
those examples,

150
00:06:29,076 --> 00:06:31,686
that is examples we just looked
at if you want to instead

151
00:06:31,686 --> 00:06:34,136
of write out to the terminal,
write to a file or take

152
00:06:34,136 --> 00:06:35,636
that file and read
it in somewhere else

153
00:06:35,876 --> 00:06:37,266
or combine the two, yeah?

154
00:06:37,266 --> 00:06:38,076
[ Inaudible Remark ]

155
00:06:38,076 --> 00:06:43,956
>> Oh sure, so how to open
that file in G edit, sure.

156
00:06:43,956 --> 00:06:48,116
So, if we go into G edit,
we noticed that we piped it

157
00:06:48,116 --> 00:06:52,896
to this file, numbers.txt,
so I'm in my Pset 3 Find,

158
00:06:53,106 --> 00:06:55,756
this is after I ran my git clone
and downloaded all the files.

159
00:06:56,016 --> 00:06:58,296
You'll see I created
this numbers.txt file.

160
00:06:58,536 --> 00:07:01,536
So, if I remove it,
let's say remove it,

161
00:07:02,406 --> 00:07:04,276
so now it's gone,
that RM for remove.

162
00:07:04,276 --> 00:07:09,846
And now let's do generate
3-1 into numbers.txt,

163
00:07:09,846 --> 00:07:12,606
so this file doesn't exist
anymore but after I pipe to it,

164
00:07:12,776 --> 00:07:16,016
I now have this numbers.txt
file, and now if I wanna look

165
00:07:16,126 --> 00:07:19,836
at it, I can just go
into G edit, open,

166
00:07:20,066 --> 00:07:22,396
and now I have this
numbers.txt right here

167
00:07:22,396 --> 00:07:25,646
and those are the three
random numbers I generated.

168
00:07:26,126 --> 00:07:29,006
Other questions?

169
00:07:29,536 --> 00:07:39,186
Okay, so also kind of not
necessarily the problem set

170
00:07:39,186 --> 00:07:42,086
but we've seen these, we've
seen these for the first time,

171
00:07:42,346 --> 00:07:43,486
are these things
called Makefiles.

172
00:07:44,146 --> 00:07:46,636
So, in Pset 1 and 2 you noticed
that you type things like,

173
00:07:46,856 --> 00:07:49,866
make scissor or make pennies
and we just kinda took

174
00:07:49,866 --> 00:07:51,746
for granted what Make
was actually doing.

175
00:07:53,016 --> 00:07:55,406
And so, what this program
Make does is it's gonna look

176
00:07:55,406 --> 00:07:58,566
for this file named Makefile
with the capital M and it has

177
00:07:58,596 --> 00:08:00,406
to be named that, that's
what Make is gonna look for

178
00:08:00,716 --> 00:08:02,126
and inside of this Makefile,

179
00:08:02,406 --> 00:08:05,276
you're gonna specify what
happens when you make something.

180
00:08:05,276 --> 00:08:07,856
So, here's an example from
the Pset kind of condensed

181
00:08:07,856 --> 00:08:08,616
so it fits in the slide.

182
00:08:08,616 --> 00:08:12,706
So you see find colon, then a
list of files and then some line

183
00:08:12,976 --> 00:08:15,416
of what's going to happen.

184
00:08:15,646 --> 00:08:17,546
So, when I say Make Find,

185
00:08:18,116 --> 00:08:20,156
this is the command
that's gonna get executed,

186
00:08:20,156 --> 00:08:21,786
this GCC, GDB whatever.

187
00:08:22,706 --> 00:08:25,206
So, after the find,
there's a colon and after

188
00:08:25,206 --> 00:08:28,326
that colon is a list of all
the files that I'm going to use

189
00:08:28,326 --> 00:08:29,776
in this command down here.

190
00:08:30,126 --> 00:08:31,456
So, if the file doesn't
exist or something

191
00:08:31,456 --> 00:08:33,096
like that Make can
yell at you and say,

192
00:08:33,096 --> 00:08:34,836
you need this file before
you can do anything with it.

193
00:08:34,836 --> 00:08:36,906
So, really frequently
you're gonna-- yup.

194
00:08:36,906 --> 00:08:37,556
>> If you make your
own Makefile,

195
00:08:37,826 --> 00:08:41,446
can you define your
own functions in it?

196
00:08:41,446 --> 00:08:42,686
>> So, if you make
your own Makefile,

197
00:08:42,686 --> 00:08:43,776
can you define your
own function?

198
00:08:43,776 --> 00:08:46,666
Sure, so just be careful
when editing Makefiles

199
00:08:47,036 --> 00:08:49,646
because this here
needs to be a tab

200
00:08:49,646 --> 00:08:52,276
and get it is gonna default two
spaces and it's not gonna work

201
00:08:52,276 --> 00:08:54,426
if there's spaces so just
make sure that's a tab,

202
00:08:54,426 --> 00:08:55,336
if you wanna play
around with it.

203
00:08:55,336 --> 00:08:57,576
So, you definitely don't have to
for this Pset, it's good to go

204
00:08:57,576 --> 00:09:00,806
as is but if you wanna learn a
little bit how Makefiles work,

205
00:09:00,806 --> 00:09:01,736
yeah, you're definitely welcome

206
00:09:01,736 --> 00:09:03,766
to have your own
different targets.

207
00:09:04,496 --> 00:09:06,266
So, Make Find, this
is gonna compel find

208
00:09:06,326 --> 00:09:09,006
and we also have
things like Make Clean,

209
00:09:09,006 --> 00:09:10,436
so this isn't gonna
compile something,

210
00:09:10,436 --> 00:09:11,956
it's just gonna execute
some other command,

211
00:09:11,956 --> 00:09:15,586
in this case it's gonna execute
anything that's not dot C file

212
00:09:15,586 --> 00:09:16,346
or dot H file.

213
00:09:16,766 --> 00:09:19,106
So, anything you compile there
or any time you save files

214
00:09:19,106 --> 00:09:20,246
in it, it's just gonna
get rid of those,

215
00:09:20,246 --> 00:09:22,236
you have a clean
directory again.

216
00:09:22,776 --> 00:09:26,246
So, yes, you're definitely free
to write your own Makefiles,

217
00:09:26,246 --> 00:09:30,556
just be careful about that whole
tabs and spaces thing and just

218
00:09:30,556 --> 00:09:32,466
to be clear, you don't need
to write your own Makefile,

219
00:09:32,466 --> 00:09:34,666
it's done for you this
time but it's good

220
00:09:34,666 --> 00:09:35,966
to learn how those things work.

221
00:09:37,206 --> 00:09:39,276
So questions on Makefiles
or Make?

222
00:09:39,656 --> 00:09:47,216
Alright, so let's get into
the actual find problem set.

223
00:09:47,276 --> 00:09:49,246
So there are two things
we need to do here,

224
00:09:49,246 --> 00:09:52,566
we need to implement sorting and
we need to implement searching.

225
00:09:53,166 --> 00:09:57,186
So, we have this file find.c
and it's written for us,

226
00:09:57,646 --> 00:10:00,076
so what this file is gonna do
is it's gonna prompt the user

227
00:10:00,346 --> 00:10:01,706
for a bunch of numbers
and they're going

228
00:10:01,706 --> 00:10:05,176
to fill a haystack, so using
that clever finding a needle

229
00:10:05,176 --> 00:10:07,816
in a haystack metaphor, which
is actually like not just us.

230
00:10:07,816 --> 00:10:09,806
It's a really common
programming thing beyond me.

231
00:10:10,426 --> 00:10:12,556
>> So while we're prompting
the user for numbers we need

232
00:10:12,556 --> 00:10:14,586
to eventually tell
us to stop prompting,

233
00:10:14,586 --> 00:10:17,266
so to do that we're gonna hit
Control D on our keyboard.

234
00:10:17,806 --> 00:10:20,576
What that does is it's gonna
send a special character called

235
00:10:20,576 --> 00:10:22,596
the end of file which is
something that's obviously not a

236
00:10:22,596 --> 00:10:24,336
number and find is
gonna say okay,

237
00:10:24,336 --> 00:10:26,536
if you type Control D I'm
just gonna stop asking you

238
00:10:26,536 --> 00:10:27,376
and the haystack is full.

239
00:10:28,546 --> 00:10:30,406
So after you've entered
all the numbers

240
00:10:30,406 --> 00:10:34,726
that compose your haystack
find.c is gonna use these two

241
00:10:34,726 --> 00:10:39,106
functions to find in
helpers.c to find it.

242
00:10:39,106 --> 00:10:42,806
So let's take a look at find.c
so we can see what's going on.

243
00:10:44,556 --> 00:10:49,246
So up here we have a nice,
well, a commenting book

244
00:10:49,246 --> 00:10:53,686
that tells us what's going on
including some social files.

245
00:10:53,686 --> 00:10:56,296
You also notice we're
including helpers.h,

246
00:10:56,466 --> 00:10:58,246
so you notice this
is not a library file

247
00:10:58,696 --> 00:11:00,806
that someone else has written
but helpers.h is something

248
00:11:00,806 --> 00:11:03,386
that we have written and it's
included in that same directory.

249
00:11:04,756 --> 00:11:06,596
So now we just have
a constant for--

250
00:11:06,676 --> 00:11:08,606
well, you know, the
maximum number of pieces

251
00:11:08,606 --> 00:11:09,766
of hay you can implement.

252
00:11:10,606 --> 00:11:13,466
This const in front of int just
means that this is a constant.

253
00:11:13,676 --> 00:11:15,126
It means you can't change it.

254
00:11:15,126 --> 00:11:16,696
So if you try to change
it then C is gonna yell

255
00:11:16,696 --> 00:11:17,716
at you and not like you.

256
00:11:18,816 --> 00:11:21,956
So now we're into our
main so first thing,

257
00:11:22,226 --> 00:11:23,536
we just wanna do a
quick sanity check,

258
00:11:23,686 --> 00:11:26,556
make sure that we've supplied
a number that we need to find,

259
00:11:26,556 --> 00:11:28,036
if not then we're just
gonna quit right away.

260
00:11:28,036 --> 00:11:31,446
We're not gonna ask him for
it or anything and so now just

261
00:11:31,446 --> 00:11:33,446
like in Pset 1 we use
this a2i [phonetic]

262
00:11:33,966 --> 00:11:37,766
and does anyone remember
what a2i does?

263
00:11:38,076 --> 00:11:38,316
Yeah.

264
00:11:38,316 --> 00:11:38,383
[ Inaudible Remark ]

265
00:11:38,383 --> 00:11:39,376
>> Exactly.

266
00:11:39,376 --> 00:11:42,676
So it converts a string to an
integer so when I say something

267
00:11:42,676 --> 00:11:46,926
like find 13 that 13 is
actually a string and we want

268
00:11:46,926 --> 00:11:48,426
to get the integer
value of that.

269
00:11:48,926 --> 00:11:52,046
So saying a2i just says okay,
take the string, make it an int

270
00:11:52,046 --> 00:11:54,826
and so now I have the integer
value of what I'm searching for.

271
00:11:55,966 --> 00:11:58,736
So now you can see that
we're just iterating

272
00:11:58,736 --> 00:12:01,316
until we reach this
maximum bound, this hay max

273
00:12:01,316 --> 00:12:03,446
that we specified and
until we don't have

274
00:12:03,446 --> 00:12:06,056
that many we're asking
the user for a number

275
00:12:06,476 --> 00:12:09,356
and if they give us a number
then we're just putting it

276
00:12:09,356 --> 00:12:11,176
as the next space
in the haystack.

277
00:12:12,026 --> 00:12:13,946
So this for loop just
fills up the haystack

278
00:12:13,946 --> 00:12:17,786
until we hit Control D and
now we're doing two things,

279
00:12:17,786 --> 00:12:19,236
the sort and search.

280
00:12:19,656 --> 00:12:22,306
So these are the two functions
that are defined in helpers.c.

281
00:12:22,916 --> 00:12:26,316
So sort is just kinda take
this array, it's gonna put it

282
00:12:26,316 --> 00:12:29,106
in ascending order and
then search is gonna see

283
00:12:29,106 --> 00:12:31,686
if the number we specified,
remember that needle came

284
00:12:31,686 --> 00:12:34,596
from the command line argument
after we call a2i on it

285
00:12:34,596 --> 00:12:37,906
and the haystack is just the
array that we're searching.

286
00:12:38,466 --> 00:12:40,786
So if this returns true
that means that we found it

287
00:12:40,786 --> 00:12:42,016
and if it returns
false we didn't.

288
00:12:42,156 --> 00:12:42,456
Question.

289
00:12:42,456 --> 00:12:43,506
[ Inaudible Remark ]

290
00:12:43,506 --> 00:12:48,446
>> Oh, that's a good question.

291
00:12:48,446 --> 00:12:51,366
So why I'm including
helpers.c but not helpers.h?

292
00:12:51,746 --> 00:12:58,076
So actually, if we open up
our Makefile, so right here,

293
00:12:58,076 --> 00:13:03,426
capital M, Makefile,
you'll see this.

294
00:13:04,716 --> 00:13:09,236
So GCC blah, blah, blah, so this
O just says I want the resulting

295
00:13:09,236 --> 00:13:12,816
file to be called Find and now
we have not just one C file

296
00:13:12,816 --> 00:13:16,286
but two C files, so
find.c and helpers.c

297
00:13:16,546 --> 00:13:19,316
so when Make compiles this
it's gonna look in both

298
00:13:19,316 --> 00:13:21,386
of those files to
form the executable.

299
00:13:21,696 --> 00:13:24,326
So now why do we include the
header file and not the C file?

300
00:13:24,926 --> 00:13:31,756
So if we open up the header file
you'll see all this includes are

301
00:13:31,756 --> 00:13:33,636
two function prototypes.

302
00:13:33,916 --> 00:13:36,626
You know remember what these do
is this just tells the compiler

303
00:13:36,916 --> 00:13:38,326
that these functions exist.

304
00:13:38,646 --> 00:13:40,036
Don't worry, they're
defined somewhere.

305
00:13:40,416 --> 00:13:43,776
So as in compiling my code if I
run into one of these functions

306
00:13:43,776 --> 00:13:46,436
as the compiler says okay, no
worries, this exists somewhere

307
00:13:46,436 --> 00:13:50,686
and it exists in helpers.c
which we are also including

308
00:13:50,876 --> 00:13:52,096
because we put it here.

309
00:13:52,776 --> 00:13:54,476
So in short it's kind
of a C convention

310
00:13:54,476 --> 00:13:58,316
to have all this prototypes and
variables defined in dot H files

311
00:13:58,396 --> 00:13:59,986
so that the compiler
knows they exist

312
00:14:00,136 --> 00:14:03,076
but actually define
what they do in C files.

313
00:14:03,216 --> 00:14:05,746
So when you include the H files
that's gonna tell the compiler

314
00:14:05,746 --> 00:14:06,676
everything is good to go

315
00:14:06,876 --> 00:14:09,656
and if you include the C file
we're actually compiling,

316
00:14:09,706 --> 00:14:11,946
so running that GCC,
that's gonna make sure

317
00:14:11,946 --> 00:14:14,076
that the functions that
you define are included

318
00:14:14,076 --> 00:14:15,286
in the resulting executable.

319
00:14:16,496 --> 00:14:19,896
So we'll see more about how that
process works in future weeks

320
00:14:19,896 --> 00:14:22,686
but any questions
on a high level?

321
00:14:22,876 --> 00:14:22,996
Yeah.

322
00:14:22,996 --> 00:14:23,156
[ Inaudible Remark ]

323
00:14:23,156 --> 00:14:30,426
>> So then a good question, so
why is that helpers.h surrounded

324
00:14:30,426 --> 00:14:32,836
in quotes instead
of curly brackets.

325
00:14:33,246 --> 00:14:39,016
So if we go back into helpers,
yeah, so we have two things.

326
00:14:39,416 --> 00:14:43,266
So the cs50.h, this is kind
of a system library, right.

327
00:14:43,736 --> 00:14:45,526
It's something that
someone else wrote for us

328
00:14:45,526 --> 00:14:47,376
and they put it somewhere
on our computer

329
00:14:47,686 --> 00:14:49,446
and GCC knows where to look.

330
00:14:49,986 --> 00:14:53,676
But this helpers.h actually
exists in the same directory

331
00:14:53,676 --> 00:14:54,816
as the rest of our files.

332
00:14:55,256 --> 00:14:57,676
So if I do an LS
there's helpers.h

333
00:14:58,036 --> 00:15:01,256
so that quote means I want you
to look right here for this file

334
00:15:01,346 --> 00:15:03,906
or some other places I've
defined and those brackets mean

335
00:15:03,906 --> 00:15:06,296
that this is some system file
and I want you to go look

336
00:15:06,296 --> 00:15:07,886
for all the secret
system files stored.

337
00:15:07,886 --> 00:15:10,356
So that's the difference there.

338
00:15:11,686 --> 00:15:13,226
Other questions on
how we're compiling?

339
00:15:13,706 --> 00:15:17,606
Alright. So now inside

340
00:15:20,876 --> 00:15:23,616
of helpers we have
these two functions.

341
00:15:24,406 --> 00:15:26,106
Sort is gonna take
two arguments.

342
00:15:26,416 --> 00:15:28,726
The first is an array that
you actually want to sort.

343
00:15:28,726 --> 00:15:32,706
And the second argument is going
to be the size of that array.

344
00:15:32,706 --> 00:15:34,946
So you all remember
in C there's no way

345
00:15:35,026 --> 00:15:37,096
of simply determining
how big an array is.

346
00:15:37,456 --> 00:15:40,036
So instead we need to
explicitly pass around the size

347
00:15:40,036 --> 00:15:42,496
of the array so we don't try
to go too far in segfault

348
00:15:42,496 --> 00:15:43,956
or not consider all
the elements.

349
00:15:44,356 --> 00:15:46,866
So in both of these functions
you're gonna be passing the size

350
00:15:46,866 --> 00:15:49,176
explicitly so you don't have
to do anything fancy to try

351
00:15:49,176 --> 00:15:51,136
to figure out how long
the array is you just know

352
00:15:51,136 --> 00:15:52,296
because it's an argument.

353
00:15:52,846 --> 00:15:55,836
So similarly with search,
it's gonna take an array,

354
00:15:55,836 --> 00:15:57,856
it's gonna take something
to look for

355
00:15:58,006 --> 00:16:00,116
and it's also gonna need
the size of the array.

356
00:16:00,806 --> 00:16:05,226
So the sort is actually a void,
it doesn't return anything.

357
00:16:05,556 --> 00:16:09,306
Instead this array is
gonna be sorted in place.

358
00:16:09,376 --> 00:16:12,156
So after the function finishes,
the argument that was passed

359
00:16:12,156 --> 00:16:13,676
to it is probably
gonna be different

360
00:16:13,676 --> 00:16:15,676
and this was already
sorted whereas search

361
00:16:15,676 --> 00:16:17,306
on the other hand
does return something.

362
00:16:17,306 --> 00:16:20,206
It's gonna return true if it's
found and false if it's not.

363
00:16:20,896 --> 00:16:28,886
So if we open up helpers.c we'll
see that all we have is this,

364
00:16:29,376 --> 00:16:31,396
so sort it's not
gonna do anything.

365
00:16:31,516 --> 00:16:32,596
Okay, we have a little
note here.

366
00:16:32,596 --> 00:16:34,776
You wanna implement it
other than [inaudible] sort

367
00:16:34,826 --> 00:16:36,346
which we'll take a look at.

368
00:16:37,176 --> 00:16:40,466
Search on the other hand has
something here and what this is,

369
00:16:40,466 --> 00:16:42,916
is basically a linear
search so this is gonna look

370
00:16:42,916 --> 00:16:45,806
at every single element
in the array and try

371
00:16:45,806 --> 00:16:46,966
to find the one you're
looking for.

372
00:16:47,866 --> 00:16:49,306
So this isn't what
we want you to do

373
00:16:49,306 --> 00:16:50,666
because this is super slow.

374
00:16:50,896 --> 00:16:52,686
Instead we're gonna
ask you to take--

375
00:16:52,796 --> 00:16:56,016
rip this out and implement
your own binary search.

376
00:16:56,756 --> 00:16:58,606
So let's take a look at
both of these things.

377
00:16:59,686 --> 00:17:03,046
So again, we're not going to try
to return an array from sort,

378
00:17:03,406 --> 00:17:05,446
we're just going to change
the one that was passed in

379
00:17:05,446 --> 00:17:08,706
and that's possible because
arrays are passed by reference

380
00:17:08,706 --> 00:17:12,116
in C and so we're gonna see more
about this in lecture shortly

381
00:17:12,626 --> 00:17:14,716
but their basic difference
between passing something

382
00:17:14,716 --> 00:17:16,996
like an integer and
passing an array is

383
00:17:17,196 --> 00:17:20,276
that when you pass an integer C
is basically gonna make a copy

384
00:17:20,276 --> 00:17:22,126
of that integer and
pass it to the function.

385
00:17:22,736 --> 00:17:25,526
So it's not gonna be changed
once the function is finished.

386
00:17:25,526 --> 00:17:28,166
Within array on the other hand
it's not gonna make a copy.

387
00:17:28,166 --> 00:17:29,686
It's just gonna say
here's the array

388
00:17:29,746 --> 00:17:31,286
if you wanna change
it, go ahead.

389
00:17:32,016 --> 00:17:34,586
So again, we'll see more about
that in lecture but just know

390
00:17:34,586 --> 00:17:36,996
that these arrays, when you pass
an array through a function,

391
00:17:37,196 --> 00:17:39,196
it's treated specially
and that if you change it

392
00:17:39,196 --> 00:17:40,916
in the function it's
gonna be changed

393
00:17:41,266 --> 00:17:45,916
from where you called
the function.

394
00:17:45,916 --> 00:17:49,106
So let's take a look at two
different sorting algorithms.

395
00:17:49,936 --> 00:17:51,746
So the first is called
bubble sort,

396
00:17:52,266 --> 00:17:53,876
so this is the simpler one.

397
00:17:54,256 --> 00:17:57,036
So what this says is I wanna
keep going through every element

398
00:17:57,036 --> 00:17:59,196
in this list and
if two elements are

399
00:17:59,196 --> 00:18:01,196
in the wrong order I
want to switch them.

400
00:18:01,926 --> 00:18:04,266
So this has the effect of
elements kinda bubbling

401
00:18:04,266 --> 00:18:05,596
over to their correct location

402
00:18:05,596 --> 00:18:08,226
because they're gonna get a move
one more with each iteration

403
00:18:08,226 --> 00:18:10,796
and kinda make their way slowly
to where they need to be.

404
00:18:11,616 --> 00:18:14,676
So we know when to stop once
no elements have been swapped.

405
00:18:14,676 --> 00:18:17,906
So if we have the condition
that every time elements are

406
00:18:17,906 --> 00:18:19,206
out of place we make a swap.

407
00:18:19,596 --> 00:18:21,836
If we know that we haven't
made a swap that must mean

408
00:18:21,836 --> 00:18:23,846
that every element is in place.

409
00:18:24,406 --> 00:18:26,876
So here's some pseudo-code
for that.

410
00:18:27,236 --> 00:18:28,326
So we have some while loop

411
00:18:28,326 --> 00:18:31,656
and while the elements have
been swapped you wanna say okay,

412
00:18:31,656 --> 00:18:33,656
at this iteration we
haven't swapped anything

413
00:18:33,656 --> 00:18:37,466
yet so now we just wanna go
through everything in the array

414
00:18:37,466 --> 00:18:40,296
and if the current element is
bigger than the element next

415
00:18:40,296 --> 00:18:42,556
to it then that means that
these two elements must be

416
00:18:42,556 --> 00:18:45,256
out of order because you
wanna start with low elements

417
00:18:45,476 --> 00:18:46,896
and have them to order
from low to high.

418
00:18:47,166 --> 00:18:49,016
So if anything is higher
than the thing to the right

419
00:18:49,016 --> 00:18:50,166
of it they're not in order.

420
00:18:50,806 --> 00:18:54,046
So we can just swap them and now
we want to remember that okay,

421
00:18:54,046 --> 00:18:57,166
we did swap elements this time
so you probably wanna check

422
00:18:57,166 --> 00:18:58,936
over it again because
we're not guaranteed

423
00:18:58,936 --> 00:18:59,726
that we're sorted yet.

424
00:19:01,176 --> 00:19:02,746
So let's take a look t
how this is gonna run.

425
00:19:03,636 --> 00:19:06,316
So let's say I have
this list 50164.

426
00:19:06,316 --> 00:19:08,336
So I'm gonna start
at the beginning

427
00:19:08,336 --> 00:19:09,776
of the list, I'm
gonna look at 5.

428
00:19:10,306 --> 00:19:12,416
I'm also gonna look at the
element that's next to 5.

429
00:19:12,546 --> 00:19:13,596
In this case it's a 0.

430
00:19:14,166 --> 00:19:17,796
So 5 is greater than 0 so
I need to switch these.

431
00:19:19,016 --> 00:19:22,026
So now I have 05164.

432
00:19:22,026 --> 00:19:25,046
So now I'm gonna look at the
5 and the 1, again they're

433
00:19:25,046 --> 00:19:26,396
out of order so I switch them.

434
00:19:27,656 --> 00:19:29,176
Now we have a 5 and a 6.

435
00:19:29,176 --> 00:19:32,286
In this case we don't need to do
anything because the 5 is less

436
00:19:32,286 --> 00:19:34,266
than the 6 we don't
need to swap.

437
00:19:34,836 --> 00:19:37,606
However, once we get to 6,
4 we again do need to swap.

438
00:19:37,606 --> 00:19:40,436
So now we have 01546.

439
00:19:40,436 --> 00:19:42,566
So now we're gonna
go through it again.

440
00:19:42,566 --> 00:19:46,186
We need to switch no, no,
yes, now we do need to switch

441
00:19:46,606 --> 00:19:51,226
and again 5, 6, we're
good to go and that means

442
00:19:51,226 --> 00:19:52,786
that our list is sorted.

443
00:19:53,956 --> 00:20:03,776
So any questions on
how bubble sort works?

444
00:20:03,776 --> 00:20:04,796
[ Inaudible Remark ]

445
00:20:04,796 --> 00:20:04,906
>> Yup.

446
00:20:04,906 --> 00:20:05,176
[ Inaudible Remark ]

447
00:20:05,176 --> 00:20:06,816
>> Sure. So if we go
back to the pseudo-code

448
00:20:06,816 --> 00:20:08,996
so how do we make sure that
we go-- that looks not cool.

449
00:20:09,216 --> 00:20:11,006
So how do we make sure that
we go through this list?

450
00:20:11,616 --> 00:20:15,766
So notice that my for loop, I'm
maintaining this index, right?

451
00:20:15,766 --> 00:20:18,086
So after every iteration
of the for loop,

452
00:20:18,306 --> 00:20:19,796
I'm gonna update
this value of I.

453
00:20:20,096 --> 00:20:23,146
And this case this value of I
is effectively the left element.

454
00:20:23,966 --> 00:20:25,356
So after everything continues,

455
00:20:25,356 --> 00:20:27,096
I'm gonna have a
new left element.

456
00:20:27,746 --> 00:20:29,616
So if I have new left
element and I add one to it

457
00:20:29,616 --> 00:20:31,046
that means my element
is different.

458
00:20:31,096 --> 00:20:34,786
So that means even if we swap,
we're still gonna move I forward

459
00:20:34,786 --> 00:20:36,176
and compare it to the next one.

460
00:20:36,566 --> 00:20:41,036
Other questions on bubble sort?

461
00:20:41,036 --> 00:20:41,186
Yeah?

462
00:20:41,656 --> 00:20:43,926
>> Once I'd make the final swap,
does it need to go back over

463
00:20:43,926 --> 00:20:44,896
and make sure everything
is right

464
00:20:44,996 --> 00:20:48,696
or like you just stop there once
it does that last little switch?

465
00:20:48,946 --> 00:20:52,716
You won't have to like go one
more over and make sure that's--

466
00:20:52,716 --> 00:20:53,916
>> Right. So I kind
of just, you know,

467
00:20:53,916 --> 00:20:55,536
instead of copying-pasting
5 slides,

468
00:20:55,536 --> 00:20:56,386
I just kind of [inaudible]
there.

469
00:20:56,386 --> 00:20:57,256
So, af-- so yes.

470
00:20:57,256 --> 00:21:00,956
So after we just
made this 4, 5 swap.

471
00:21:01,566 --> 00:21:04,896
At this point the algorithm
doesn't know that it's done.

472
00:21:05,126 --> 00:21:06,616
Because looking at our
pseudo-code strictly,

473
00:21:06,616 --> 00:21:08,146
we said, did we make a swap?

474
00:21:08,336 --> 00:21:10,996
Yes. If we did make a swap,
we need to go over again.

475
00:21:11,516 --> 00:21:13,096
So now we're gonna go over again

476
00:21:13,096 --> 00:21:14,796
and at no point do
we make a swap

477
00:21:14,796 --> 00:21:16,666
so now we break the
condition of our while loop

478
00:21:16,666 --> 00:21:19,366
because we did not make a swap
which means that we're done.

479
00:21:20,216 --> 00:21:21,206
So yes, so we're gonna need

480
00:21:21,206 --> 00:21:23,206
to make sure we go
through every time.

481
00:21:23,486 --> 00:21:23,656
Yup?

482
00:21:23,656 --> 00:21:24,356
[ Inaudible Remark ]

483
00:21:24,356 --> 00:21:28,196
>> So do we have two loops?

484
00:21:28,336 --> 00:21:31,746
So yes, so they don't
necessarily have to be a while

485
00:21:31,746 --> 00:21:33,656
and a for or a for then a while,
they could be whatever you want.

486
00:21:33,656 --> 00:21:36,786
But bubble sort has a
run time of O N squared.

487
00:21:36,786 --> 00:21:38,516
So that means that
there's gonna be a

488
00:21:38,516 --> 00:21:39,916
for loop inside of a for loop.

489
00:21:39,956 --> 00:21:42,396
So for every single
element, I need to look

490
00:21:42,536 --> 00:21:43,756
at every single element.

491
00:21:43,756 --> 00:21:47,806
And that's where that N squared
comes in instead of N or log N.

492
00:21:48,586 --> 00:21:50,606
So we definitely need
two loops because we need

493
00:21:50,606 --> 00:21:53,716
to compare every element by
at least that many times.

494
00:21:54,156 --> 00:21:54,506
Question?

495
00:21:54,506 --> 00:21:55,196
[ Inaudible Remark ]

496
00:21:55,196 --> 00:22:00,686
>> So why is it I
equals zero to N minus 2?

497
00:22:00,686 --> 00:22:04,176
So this, you know, could just
be indexing to pseudo-code

498
00:22:04,176 --> 00:22:08,176
but we wanna make sure that we
don't ever use the last element

499
00:22:08,176 --> 00:22:09,436
as our left, right?

500
00:22:09,526 --> 00:22:11,116
Because if we're at
the end of the array,

501
00:22:11,116 --> 00:22:13,866
and we look one element
ahead, we're now outside

502
00:22:13,866 --> 00:22:15,046
of the array and
we're in trouble.

503
00:22:15,946 --> 00:22:18,386
So one way of solving that is
to say, okay, I don't wanna--

504
00:22:18,386 --> 00:22:20,386
I wanna make sure that
I stop at the second

505
00:22:20,386 --> 00:22:22,056
to last element and
that's my left.

506
00:22:22,386 --> 00:22:25,256
They don't necessarily have to
look right, you could also say,

507
00:22:25,256 --> 00:22:27,506
okay, that I is gonna be
the element on the right.

508
00:22:27,506 --> 00:22:28,846
Now I'm gonna look
one behind me.

509
00:22:28,906 --> 00:22:30,836
And if those are out of
order then you can swap them.

510
00:22:31,006 --> 00:22:33,316
At this case you'd wanna
start I instead of at 0

511
00:22:33,316 --> 00:22:35,686
at 1 then you'd wanna
iterate until the end

512
00:22:35,686 --> 00:22:37,336
of the list instead of the
second to last element.

513
00:22:37,796 --> 00:22:39,776
So yes, so be really careful
here, if you segfault,

514
00:22:39,776 --> 00:22:41,886
that probably means that
you're either looking too far

515
00:22:41,886 --> 00:22:43,656
to the right or looking
too far to the left.

516
00:22:44,776 --> 00:22:44,996
Yeah.

517
00:22:44,996 --> 00:22:45,063
[ Inaudible Remark ]

518
00:22:45,063 --> 00:22:50,856
>> So is there a
command for swapping?

519
00:22:50,856 --> 00:22:53,466
No. So this is a function that
you have to write yourself.

520
00:22:53,926 --> 00:22:55,616
So you may have seen
that in lecture,

521
00:22:55,916 --> 00:22:57,226
how we can swap two numbers

522
00:22:57,226 --> 00:22:58,766
and how we can't
actually swap two numbers,

523
00:22:59,076 --> 00:23:01,606
but so this isn't something
that is written for you.

524
00:23:02,186 --> 00:23:05,166
But basically what you
just need to do is you need

525
00:23:05,166 --> 00:23:07,696
to say I have some value
here, I have some value here,

526
00:23:08,126 --> 00:23:10,636
I wanna store one
temporarily, swap it,

527
00:23:10,636 --> 00:23:12,376
and then put the
temporary variable back

528
00:23:12,376 --> 00:23:13,886
into the value that I swapped.

529
00:23:14,316 --> 00:23:15,896
So there's definitely
an example in lecture

530
00:23:15,896 --> 00:23:18,066
of how we can swap something
in array, in an array.

531
00:23:18,816 --> 00:23:20,916
But basically we're gonna
have some temporary variable,

532
00:23:21,156 --> 00:23:22,256
put something there
for a minute,

533
00:23:22,396 --> 00:23:25,996
swap the value and
then put it back.

534
00:23:26,226 --> 00:23:29,316
Other questions on bubble?

535
00:23:29,466 --> 00:23:29,696
Yeah.

536
00:23:30,516 --> 00:23:42,846
[ Inaudible Remark ]

537
00:23:43,346 --> 00:23:44,126
>> So there could-- yes,

538
00:23:44,126 --> 00:23:46,096
so there could be different
variants on bubble sort.

539
00:23:46,096 --> 00:23:47,906
So this is just kind of
the most basic one, just if

540
00:23:47,906 --> 00:23:50,716
and then keep going to the list
and if I know the list is wrong,

541
00:23:50,716 --> 00:23:51,576
I'm just gonna swap things.

542
00:23:51,836 --> 00:23:53,626
So yes, so you're definitely
welcome to implement, you know,

543
00:23:53,626 --> 00:23:55,076
a variation that you
might have seen elsewhere.

544
00:23:55,686 --> 00:23:57,446
But this is the most
basic version.

545
00:23:58,396 --> 00:23:58,616
Yeah.

546
00:23:58,616 --> 00:23:58,976
[ Inaudible Remark ]

547
00:23:58,976 --> 00:24:03,386
>> So why is it N minus 2?

548
00:24:03,386 --> 00:24:04,176
So as I mentioned before,

549
00:24:04,176 --> 00:24:06,266
we just wanna make sure we
don't go outside of the array.

550
00:24:07,166 --> 00:24:10,336
So if we're at the last element
and we try to go one more,

551
00:24:10,546 --> 00:24:12,996
that means that I'm gonna index
outside of the array, yeah.

552
00:24:13,446 --> 00:24:14,886
So remember that
array start at 0.

553
00:24:15,156 --> 00:24:16,706
So if I have an array
of length 5,

554
00:24:16,826 --> 00:24:21,366
that means my last element
is at index 4, not 5.

555
00:24:21,566 --> 00:24:24,086
Easy mistake to make.

556
00:24:24,286 --> 00:24:25,056
Other questions?

557
00:24:25,596 --> 00:24:29,686
Okay, so that's bubble sort.

558
00:24:31,096 --> 00:24:32,906
That looks really cool.

559
00:24:33,136 --> 00:24:34,766
So now for our selection sort.

560
00:24:35,516 --> 00:24:37,976
So this is a little more
complicated than bubble sort,

561
00:24:37,976 --> 00:24:39,716
and most of the time it's
also gonna be faster.

562
00:24:40,066 --> 00:24:42,676
So the basic idea behind
selection sort is you're going

563
00:24:42,676 --> 00:24:46,576
to build the sorted list
one element at a time.

564
00:24:46,626 --> 00:24:49,126
So at first you're gonna start
at the beginning of the list

565
00:24:49,766 --> 00:24:51,376
because we're gonna build
the list from left to right.

566
00:24:52,006 --> 00:24:54,516
So now we wanna find out
what element should be

567
00:24:54,516 --> 00:24:55,626
at the beginning of the list.

568
00:24:55,626 --> 00:24:59,646
And that element has to be the
smallest element because we know

569
00:24:59,646 --> 00:25:01,706
that the first element has
to be the smallest one.

570
00:25:02,336 --> 00:25:04,256
So we're gonna look through
the list and we're gonna find

571
00:25:04,586 --> 00:25:05,796
that smallest element.

572
00:25:06,446 --> 00:25:07,706
And we're gonna just switch it

573
00:25:07,706 --> 00:25:10,426
with the element that's
already there in the first spot.

574
00:25:10,426 --> 00:25:12,206
So we're gonna start
at the beginning,

575
00:25:12,276 --> 00:25:14,316
find the smallest element
and put it at the beginning.

576
00:25:14,546 --> 00:25:17,866
Now we know that the element in
the first position is correct

577
00:25:18,356 --> 00:25:20,096
because it's the
smallest so it has

578
00:25:20,096 --> 00:25:21,366
to start off the sorted array.

579
00:25:22,146 --> 00:25:24,236
So now we can move on
to the next element

580
00:25:24,606 --> 00:25:25,756
which might be wrong.

581
00:25:26,366 --> 00:25:29,266
And again, we're gonna find
the smallest thing that's left

582
00:25:29,266 --> 00:25:29,626
in the array.

583
00:25:30,006 --> 00:25:31,896
Obviously, we don't want
the absolute smallest

584
00:25:31,956 --> 00:25:33,736
because we know that that's
already in the right place

585
00:25:33,736 --> 00:25:34,516
and we don't wanna touch it.

586
00:25:35,046 --> 00:25:37,716
So we wanna find inside
of the unsorted part

587
00:25:37,716 --> 00:25:39,196
of the array the
smallest element

588
00:25:39,446 --> 00:25:40,516
and we're gonna swap them again.

589
00:25:41,326 --> 00:25:42,766
So we're just gonna keep going

590
00:25:43,426 --> 00:25:45,186
until every element
has been swapped

591
00:25:45,266 --> 00:25:47,516
with what is the minimum
element at the time

592
00:25:47,516 --> 00:25:50,466
and that means we're gonna
have a sorted list at the end.

593
00:25:51,636 --> 00:25:53,336
So let's just take
a look at an example

594
00:25:53,336 --> 00:25:53,956
and then look at the code.

595
00:25:53,956 --> 00:25:57,396
So here's my list again, 50164.

596
00:25:57,986 --> 00:26:00,356
So this blue is gonna be
where I am in my list.

597
00:26:00,356 --> 00:26:02,646
So what the element I'm
looking to swap this.

598
00:26:03,486 --> 00:26:06,586
Now the minimum of this
list is going to be 0.

599
00:26:06,586 --> 00:26:10,086
So that means I need to
swap this 0 and this 5.

600
00:26:10,746 --> 00:26:15,166
So after I do that, we know that
this 0 is in the correct place

601
00:26:15,166 --> 00:26:15,996
because it's the minimum.

602
00:26:16,396 --> 00:26:18,706
So we don't-- we need, we can
just forget that that 0 exist.

603
00:26:19,286 --> 00:26:20,356
So now we're looking at the 5

604
00:26:20,436 --> 00:26:22,646
and we wanna swap something
into where the 5 is.

605
00:26:23,276 --> 00:26:25,946
So again, we're gonna find the
minimum, not counting the 0

606
00:26:25,946 --> 00:26:27,436
because it's done, we
can forget about it,

607
00:26:27,716 --> 00:26:29,046
so the new minimum is now 1.

608
00:26:29,046 --> 00:26:33,216
So we're gonna swap the 5
and the 1 and now we know

609
00:26:33,216 --> 00:26:35,986
that these first 2 elements
are in the correct position.

610
00:26:35,986 --> 00:26:37,806
So now you move it over again

611
00:26:37,806 --> 00:26:39,446
and this 5 just keeps
getting kicked out.

612
00:26:39,446 --> 00:26:43,486
So the new minimum in these
last 3 elements is the 4.

613
00:26:43,936 --> 00:26:48,906
So we swap the 5 and the
4, now we have the 6,

614
00:26:49,336 --> 00:26:52,716
we can swap that with the 5
and we know that we're done

615
00:26:53,056 --> 00:26:55,186
because once you reach the last
element, there is nowhere else

616
00:26:55,186 --> 00:26:57,786
to look, so that must mean that
it's also in the right location.

617
00:26:58,666 --> 00:27:01,406
So the pseudo-code for this,
although it looks cool.

618
00:27:01,736 --> 00:27:05,286
So the pseudo-code for this,
again we're O N squared,

619
00:27:05,286 --> 00:27:07,686
so that means, for every
element, we need to look

620
00:27:07,686 --> 00:27:09,526
at every element at least once.

621
00:27:09,526 --> 00:27:11,286
So we're gonna have
a loop within a loop.

622
00:27:11,286 --> 00:27:14,376
So we're gonna start off at
the absolute left of our list

623
00:27:14,526 --> 00:27:16,526
because we're moving
basically from left to right

624
00:27:16,526 --> 00:27:18,666
and swapping elements
as we move to the right.

625
00:27:19,906 --> 00:27:22,556
So that means that our minimum
value is gonna start off

626
00:27:22,556 --> 00:27:22,996
at the left.

627
00:27:23,946 --> 00:27:26,496
So now we need to find
anything that's smaller

628
00:27:26,496 --> 00:27:27,406
than that minimum value.

629
00:27:28,116 --> 00:27:31,616
So we're gonna start at that
location and find the minimum.

630
00:27:31,616 --> 00:27:33,576
So that's why we have
J equals I plus 1.

631
00:27:33,856 --> 00:27:35,826
So wherever we're looking
we wanna start looking

632
00:27:35,826 --> 00:27:38,166
for the minimum right
after that.

633
00:27:38,276 --> 00:27:42,086
So if we find an element that's
smaller than our current minimum

634
00:27:42,536 --> 00:27:44,266
that means that we
found a new minimum.

635
00:27:44,806 --> 00:27:46,696
We can update what
our minimum index is.

636
00:27:47,016 --> 00:27:50,056
So that min is always gonna hold
where the smallest element is,

637
00:27:50,286 --> 00:27:52,196
and this J is gonna hold
where we're looking.

638
00:27:52,926 --> 00:27:55,046
So now once we've iterated
through every element

639
00:27:55,456 --> 00:27:57,136
to the right of our
sorted position,

640
00:27:57,356 --> 00:27:59,806
we found the minimum element
because we're always--

641
00:28:00,356 --> 00:28:02,956
excuse me-- we're always
updating what our minimum is.

642
00:28:03,496 --> 00:28:06,786
So now once we have our minimum,
we just wanna swap them,

643
00:28:07,486 --> 00:28:08,766
we just also have
this extra check.

644
00:28:09,106 --> 00:28:11,246
Well, if I'm already-- my
minimum is already in my place,

645
00:28:11,596 --> 00:28:12,476
there's nothing really to swap

646
00:28:12,476 --> 00:28:13,896
so we can save ourselves
to swap there.

647
00:28:13,896 --> 00:28:16,346
So does everyone see
how this is working?

648
00:28:17,066 --> 00:28:19,126
This J equals I plus 1
is a little confusing

649
00:28:19,126 --> 00:28:21,236
but it just says, that as
I'm looking over elements,

650
00:28:21,426 --> 00:28:23,126
I don't need to look over
the whole list again.

651
00:28:23,126 --> 00:28:25,356
I just need to look at
everything to the right

652
00:28:25,716 --> 00:28:27,056
of what I know is
already sorted.

653
00:28:27,366 --> 00:28:29,026
Because that's probably
wrong and everything

654
00:28:29,026 --> 00:28:31,476
to the left we know is correct.

655
00:28:32,036 --> 00:28:38,426
So selection sort questions?

656
00:28:38,496 --> 00:28:38,696
Yeah?

657
00:28:39,516 --> 00:28:45,216
[ Inaudible Remark ]

658
00:28:45,716 --> 00:28:49,576
>> So yes, so asymptotically
yes, they are the same.

659
00:28:49,906 --> 00:28:52,146
Just in practice usually
selection sort is gonna run a

660
00:28:52,146 --> 00:28:52,766
little bit quicker.

661
00:28:53,516 --> 00:28:57,936
[ Inaudible Remark ]

662
00:28:58,436 --> 00:28:59,496
>> So is there a preference?

663
00:28:59,496 --> 00:29:02,026
No, we wanna implement whatever
you think is more interesting

664
00:29:02,026 --> 00:29:03,846
or more straightforward or
what you wanna learn more

665
00:29:03,846 --> 00:29:04,906
about by actually writing.

666
00:29:05,196 --> 00:29:07,006
So yeah, so both of
these are definitely good

667
00:29:07,006 --> 00:29:07,766
to go to implement.

668
00:29:07,766 --> 00:29:10,776
If you-- I don't know if David
showed this yet but there's

669
00:29:10,776 --> 00:29:12,316
like a graphic that you'll see

670
00:29:12,316 --> 00:29:14,436
of like the sorting
algorithms raising

671
00:29:14,846 --> 00:29:17,356
and so bubble sorts
usually kinda last and some

672
00:29:17,356 --> 00:29:19,406
of the better ones are gonna
finish faster even though

673
00:29:19,406 --> 00:29:20,956
they're same big O. Yeah.

674
00:29:21,516 --> 00:29:36,306
[ Inaudible Remark ]

675
00:29:36,806 --> 00:29:39,006
>> Exactly, so now let's
look at the omega case

676
00:29:39,006 --> 00:29:40,016
of both of these algorithms.

677
00:29:40,706 --> 00:29:43,606
So selection sort, the omega
case, what is that gonna do?

678
00:29:43,896 --> 00:29:46,096
At every element list, well
it's gonna find the minimum,

679
00:29:46,096 --> 00:29:48,386
it's gonna realize the minimum
is already there and move on.

680
00:29:48,576 --> 00:29:50,166
So it's still gonna
be O of N squared.

681
00:29:50,546 --> 00:29:54,356
Now if we back up the
bubble sort, we have this,

682
00:29:54,356 --> 00:29:55,996
while the elements
have not been swapped,

683
00:29:56,366 --> 00:29:58,226
so let's say the list
is already in order

684
00:29:58,396 --> 00:30:00,206
which is our omega
or our best case.

685
00:30:00,206 --> 00:30:02,266
It can't get any
better then what we have

686
00:30:02,266 --> 00:30:03,076
to do is already done.

687
00:30:03,876 --> 00:30:05,536
So bubble sort is gonna realize

688
00:30:05,706 --> 00:30:08,646
that the list is already
sorted just going over it once.

689
00:30:09,046 --> 00:30:11,746
So yes, in the best case,
bubble sort is faster

690
00:30:11,896 --> 00:30:14,016
because it's not gonna
waste time doing an O

691
00:30:14,016 --> 00:30:15,156
of N squared operation.

692
00:30:15,306 --> 00:30:16,706
Instead it's just gonna
go through it once

693
00:30:16,706 --> 00:30:18,096
and say I'm sorted, I'm done.

694
00:30:18,396 --> 00:30:20,756
Where selection sort is
going to go-- a lot simple.

695
00:30:21,106 --> 00:30:22,986
So selection sort is
every single time,

696
00:30:23,476 --> 00:30:26,216
no matter what the list I talk
with, look at every element

697
00:30:26,216 --> 00:30:28,206
and for every element
look at every element.

698
00:30:29,096 --> 00:30:30,926
However, when I say

699
00:30:30,926 --> 00:30:32,426
that selection sort
is usually faster,

700
00:30:32,426 --> 00:30:34,046
that's because that
omega is pretty rare

701
00:30:34,046 --> 00:30:36,176
and rarely do we
have to solve list--

702
00:30:36,176 --> 00:30:37,576
sort list that are
already sorted.

703
00:30:37,836 --> 00:30:40,486
So on average, selection
sort is probably faster

704
00:30:40,876 --> 00:30:42,086
but in the best case,
you're right yes,

705
00:30:42,086 --> 00:30:44,526
bubble sort is both
asymptotically and in terms

706
00:30:44,526 --> 00:30:47,496
of actual machine time, faster.

707
00:30:47,736 --> 00:30:47,956
Yeah?

708
00:30:48,516 --> 00:30:54,006
[ Inaudible Remark ]

709
00:30:54,506 --> 00:30:55,966
>> Yeah. So why is it faster?

710
00:30:55,966 --> 00:30:57,736
You could just kinda
see that selection sort,

711
00:30:57,886 --> 00:30:59,906
you know where we're kinda
moving, we're more efficient.

712
00:30:59,906 --> 00:31:01,616
Like we know that this
part of list is sorted.

713
00:31:01,616 --> 00:31:04,026
With bubble sort, we can just
kinda, you know, bounce back

714
00:31:04,026 --> 00:31:06,666
and forth and keep
going over the list

715
00:31:06,666 --> 00:31:08,116
that many times wherein
selection sort,

716
00:31:08,116 --> 00:31:09,946
we're kind of reducing the
size of the problem each time.

717
00:31:10,406 --> 00:31:12,816
Right after we know that these
3 elements have been sorted,

718
00:31:12,816 --> 00:31:14,636
we're not looking at every
element of the list again.

719
00:31:15,226 --> 00:31:16,566
So little optimizations
like that,

720
00:31:17,196 --> 00:31:19,656
that don't change the
big O, make it faster

721
00:31:19,656 --> 00:31:20,516
when you're actually running it.

722
00:31:21,056 --> 00:31:23,076
So selection sort kind of
reduces the size of problem

723
00:31:23,076 --> 00:31:27,146
and bubble sort just kind of
bounces around and fix things.

724
00:31:27,376 --> 00:31:29,686
So, other questions on
either of these sorts?

725
00:31:33,536 --> 00:31:36,126
Okay. So let's take
a look at search.

726
00:31:36,656 --> 00:31:38,656
So that's sort, that's done.

727
00:31:39,266 --> 00:31:40,996
So let's take a look
at binary search.

728
00:31:41,466 --> 00:31:44,326
So right now it's implemented
as I said as linear search.

729
00:31:44,646 --> 00:31:46,576
So this has a big O
of N, we need to look

730
00:31:46,576 --> 00:31:47,696
at every single element.

731
00:31:48,516 --> 00:31:51,396
So this actually doesn't require
that our array is sorted.

732
00:31:51,716 --> 00:31:54,186
So right now if you just run
generate and find, it find,

733
00:31:54,186 --> 00:31:55,856
it's gonna work, you
know, like oh you're done.

734
00:31:56,186 --> 00:31:56,706
Not really.

735
00:31:57,826 --> 00:32:00,416
So the reason that this works is
'cause sort doesn't do anything

736
00:32:00,626 --> 00:32:03,356
but linear search doesn't
require a sorted list.

737
00:32:04,166 --> 00:32:06,576
However, what we wanna do
is implement binary search

738
00:32:06,856 --> 00:32:09,656
which as you recall does
require a sorted list.

739
00:32:10,416 --> 00:32:13,016
And the benefit of this
is that it's O of log N

740
00:32:13,356 --> 00:32:16,416
which is much faster
than just O of N.

741
00:32:16,706 --> 00:32:19,426
So this is our pseudo-code
for binary search.

742
00:32:19,916 --> 00:32:22,326
So while the length of our
list is greater than 0,

743
00:32:22,376 --> 00:32:24,666
so while we still have
some elements to look at

744
00:32:24,666 --> 00:32:27,726
or you know while we haven't
looked at everything yet,

745
00:32:27,726 --> 00:32:30,336
we wanna look at the
very middle of our list.

746
00:32:30,956 --> 00:32:32,956
We wanna look at that element
and we wanna compare it

747
00:32:33,076 --> 00:32:34,196
to the number we're looking for.

748
00:32:34,726 --> 00:32:36,486
If we found it, that
means true, we're done.

749
00:32:37,816 --> 00:32:40,636
If our number is too high
that means that everything

750
00:32:40,636 --> 00:32:42,826
to the right of that
number is also too high.

751
00:32:43,236 --> 00:32:45,106
So we can forget
that the right half--

752
00:32:45,106 --> 00:32:46,876
that that half of
the list exists.

753
00:32:46,876 --> 00:32:49,276
So the same thing with
the other way around,

754
00:32:49,276 --> 00:32:50,236
if our number is too low,

755
00:32:50,396 --> 00:32:52,776
then we can forget the other
half of that list exists.

756
00:32:53,066 --> 00:32:54,116
So let's just look
at an example.

757
00:32:54,116 --> 00:32:56,326
So here are 10 numbers.

758
00:32:56,856 --> 00:33:03,206
Yeah. So if our number is too
high, that means we only need

759
00:33:03,206 --> 00:33:05,076
to look at the left
half because everything

760
00:33:05,076 --> 00:33:06,766
to the right we know
is also too high.

761
00:33:07,486 --> 00:33:09,566
So if our number is
too low, we only need

762
00:33:09,566 --> 00:33:12,006
to consider the right half
because everything that's

763
00:33:12,006 --> 00:33:14,416
to the left of that
number is also too low.

764
00:33:14,416 --> 00:33:20,046
So we can definitely
forget about it.

765
00:33:20,186 --> 00:33:20,286
Yeah.

766
00:33:20,286 --> 00:33:20,716
[ Inaudible Remark ]

767
00:33:20,716 --> 00:33:21,206
>> Exactly.

768
00:33:21,206 --> 00:33:23,136
So what happens if
the list is 10 digits?

769
00:33:23,136 --> 00:33:25,016
So at this point you kinda
need to make a decision,

770
00:33:25,016 --> 00:33:27,466
do I need to, do I wanna round
up or do I wanna round down?

771
00:33:27,736 --> 00:33:28,746
So let's just look at this case.

772
00:33:28,746 --> 00:33:30,266
So here I have 10 elements.

773
00:33:30,736 --> 00:33:31,916
So I'm gonna calculate
the middle,

774
00:33:31,916 --> 00:33:34,456
I have 10 over 2 and that's 5.

775
00:33:34,456 --> 00:33:35,096
So that's fine.

776
00:33:35,646 --> 00:33:39,696
So I can go over 0, 1, 2, 3,
4, 5 and I'm at element 161.

777
00:33:39,696 --> 00:33:42,556
So in this case, I'm
just looking for 164.

778
00:33:42,996 --> 00:33:44,896
So, some little messaging
intended.

779
00:33:45,236 --> 00:33:46,816
So I'm looking for 164.

780
00:33:46,816 --> 00:33:50,976
161 is too low, so
what are we gonna do?

781
00:33:50,976 --> 00:33:53,376
We're gonna throw away
everything to the left

782
00:33:53,376 --> 00:33:56,826
of the 161 including the 161
because we don't need to look

783
00:33:56,826 --> 00:33:58,706
at that either, we
know that it's too low.

784
00:33:59,176 --> 00:34:00,406
So now we just have this list.

785
00:34:00,886 --> 00:34:04,136
So, now as you said when
we divide by 2, we're not--

786
00:34:04,136 --> 00:34:05,176
well, I know we still are.

787
00:34:05,506 --> 00:34:07,126
So we have 0-- we
have 4 elements,

788
00:34:07,126 --> 00:34:08,916
so we have 0, 1, 2, 3, 4.

789
00:34:09,266 --> 00:34:13,136
4 over 2 is 2, we're gonna look
at 0, 1, 2 and we're at the 175.

790
00:34:13,986 --> 00:34:15,916
So in this case the
175 is too high.

791
00:34:16,526 --> 00:34:18,166
So we can forget about
this whole left half.

792
00:34:18,886 --> 00:34:22,706
So this 175 and the
182 don't exist anymore

793
00:34:22,706 --> 00:34:23,816
because they're definitely
wrong.

794
00:34:24,696 --> 00:34:28,716
So now I have the 161 and the
1-- I actually got rid of that.

795
00:34:28,716 --> 00:34:30,906
So we actually just
have the 164 left.

796
00:34:31,836 --> 00:34:33,766
So to answer your
question what happens,

797
00:34:33,826 --> 00:34:34,806
we basically need to round.

798
00:34:35,396 --> 00:34:37,946
So if I had 9 elements
here, when I divide by 2,

799
00:34:37,946 --> 00:34:39,176
I'm gonna get 4 and a half.

800
00:34:39,696 --> 00:34:41,516
So probably just
wanna make that 4.

801
00:34:42,416 --> 00:34:43,826
As long as I do that
consistently,

802
00:34:43,826 --> 00:34:46,286
I'm always gonna find
the middle element.

803
00:34:47,886 --> 00:34:49,826
Other questions on
binary search?

804
00:34:52,796 --> 00:34:53,176
Yup.

805
00:34:54,516 --> 00:35:04,786
[ Inaudible Remark ]

806
00:35:05,286 --> 00:35:05,656
>> So, yes.

807
00:35:05,656 --> 00:35:07,756
So, in this case, we took
something that was O of N,

808
00:35:07,756 --> 00:35:09,456
just [inaudible]
search and we made it O

809
00:35:09,456 --> 00:35:12,036
of N squared log N.
So yes, that is true.

810
00:35:12,666 --> 00:35:17,756
But, that's what you did for
Pset, so yes, in general,

811
00:35:17,756 --> 00:35:20,316
technically, if you
combine the two it's faster.

812
00:35:20,316 --> 00:35:22,666
We do have sorting algorithms
that are faster than O

813
00:35:22,666 --> 00:35:24,516
of N squared which
we'll learn shortly,

814
00:35:24,516 --> 00:35:25,886
and using those faster
algorithms

815
00:35:25,886 --> 00:35:27,166
where it can actually
get a better time.

816
00:35:28,176 --> 00:35:30,276
However, yes, in this case
you are technically making it

817
00:35:30,276 --> 00:35:31,506
slower, but you're
making better,

818
00:35:31,506 --> 00:35:33,716
so it's so much better
design, and so there's

819
00:35:33,716 --> 00:35:35,016
so much more edification
out if this.

820
00:35:35,256 --> 00:35:35,576
Yeah.

821
00:35:36,516 --> 00:35:43,826
[ Inaudible Remark ]

822
00:35:44,326 --> 00:35:44,766
>> So this one?

823
00:35:45,226 --> 00:35:47,436
Yes. So, right now, so
there's nothing wrong,

824
00:35:47,876 --> 00:35:49,716
correcting is wise,
with what's done now,

825
00:35:50,326 --> 00:35:51,766
but if you're having this
thing you're gonna get a one

826
00:35:51,766 --> 00:35:54,466
for design, because you can do
so much better than just looking

827
00:35:54,466 --> 00:35:55,436
at every single element.

828
00:35:56,166 --> 00:35:58,286
So, there's nothing correct
me if I was wrong, it works,

829
00:35:58,396 --> 00:35:59,946
and whatever you throw
at it, it's gonna work,

830
00:36:00,426 --> 00:36:02,806
but we wanna change it, so
that it's better designed

831
00:36:03,586 --> 00:36:05,586
and so you learn
about binary search.

832
00:36:06,376 --> 00:36:07,086
Question.

833
00:36:07,426 --> 00:36:11,846
>> How do you get it to forget
half of them, half of the list?

834
00:36:11,846 --> 00:36:13,096
>> Yeah, so that's
a good question,

835
00:36:13,096 --> 00:36:15,336
so how do we effectively
forget about half the list?

836
00:36:15,336 --> 00:36:18,136
So there are basically two
ways you can do binary search.

837
00:36:18,426 --> 00:36:21,666
That algorithm we just looked at
is effectively iterative, right.

838
00:36:21,666 --> 00:36:25,016
We're using a for loop,
that's what we've been using

839
00:36:25,016 --> 00:36:26,096
so far in all of our Psets.

840
00:36:26,436 --> 00:36:27,496
This week in lecture,
we're gonna look

841
00:36:27,496 --> 00:36:28,766
at something called recursion,

842
00:36:29,296 --> 00:36:32,036
and recursion is basically
one function calls itself,

843
00:36:32,626 --> 00:36:35,406
and it can continue to call
itself until we reach some goal

844
00:36:35,596 --> 00:36:36,826
or we know that we're
never gonna find it.

845
00:36:37,916 --> 00:36:41,206
So in the iterative case, we can
forget the left half of the list

846
00:36:41,566 --> 00:36:43,216
by just updating
some left bound.

847
00:36:43,746 --> 00:36:45,936
So if we say we have a left
bound like this is the most,

848
00:36:46,196 --> 00:36:48,506
left most element and this
is the right most element,

849
00:36:48,736 --> 00:36:50,606
and I can calculate the middle
based on these two bounds

850
00:36:50,976 --> 00:36:54,036
so after I need to move left
to right, if I just move

851
00:36:54,036 --> 00:36:55,136
like say the right bound,

852
00:36:55,596 --> 00:36:57,506
that means that this is
effectively the new end

853
00:36:57,506 --> 00:36:58,976
of the list as far
as you're concerned.

854
00:36:59,526 --> 00:37:01,996
So we don't actually need to
remove the elements from memory.

855
00:37:02,346 --> 00:37:04,806
In fact, C has a really hard
time with resizing arrays,

856
00:37:05,256 --> 00:37:07,716
so instead of physically
removing it, we just wanna kind

857
00:37:07,716 --> 00:37:11,006
of pretend that it doesn't
exist anymore, so same thing

858
00:37:11,006 --> 00:37:13,386
with recursive, you're gonna
continue to call search,

859
00:37:13,956 --> 00:37:15,066
but each time you call it,

860
00:37:15,306 --> 00:37:17,676
you're gonna supply a
different set of arguments

861
00:37:18,306 --> 00:37:20,356
and effectively you're gonna
say forget the left half

862
00:37:20,356 --> 00:37:22,616
and use this middle, forget the
right half and use this middle,

863
00:37:23,016 --> 00:37:26,396
so you see more about that
this week but just now

864
00:37:26,396 --> 00:37:27,596
that you can do it both ways.

865
00:37:27,796 --> 00:37:29,526
I know-- do whichever
way you prefer,

866
00:37:29,526 --> 00:37:31,106
in which way you find
more straightforward.

867
00:37:31,656 --> 00:37:34,176
But in both cases, you're
gonna need to be able

868
00:37:34,176 --> 00:37:37,386
to determine the middle element
based on some current left bound

869
00:37:37,586 --> 00:37:40,396
and some current right bound
that have to change based

870
00:37:40,396 --> 00:37:42,906
on what number you've
already look at in the list.

871
00:37:44,376 --> 00:37:46,256
So, questions on either
of these approaches,

872
00:37:46,256 --> 00:37:47,656
both of which are fine.

873
00:37:50,916 --> 00:37:53,046
So, because we haven't
seen recursion yet,

874
00:37:53,046 --> 00:37:55,286
I definitely recommend you know
trying the iterative and if,

875
00:37:55,286 --> 00:37:57,256
you know, you're
down to Pset early

876
00:37:57,256 --> 00:38:00,486
and you wanna do recursion, just
to see and learn it, go for that

877
00:38:00,866 --> 00:38:03,126
but definitely not required
to wait until we learn

878
00:38:03,126 --> 00:38:05,096
about recursion, wrap your
head around it and then use it,

879
00:38:05,176 --> 00:38:06,566
using the iterative
method is fine,

880
00:38:06,836 --> 00:38:09,046
and if you're starting
right now, go for it.

881
00:38:10,436 --> 00:38:14,846
So that was the Find
folder, that sort and search,

882
00:38:15,286 --> 00:38:20,916
so any final questions
on either one of those?

883
00:38:21,096 --> 00:38:23,346
Okay. Let's get to the fun part.

884
00:38:23,986 --> 00:38:26,336
So now, we're looking
at the game of Fifteen.

885
00:38:27,456 --> 00:38:30,796
So there are four functions
that we need to write in order

886
00:38:30,796 --> 00:38:31,766
for this game to work.

887
00:38:32,246 --> 00:38:34,636
The first is init which is
gonna initialize the game,

888
00:38:34,636 --> 00:38:37,736
we need to implement draw,
which is gonna output the state

889
00:38:37,736 --> 00:38:40,686
of the game onto the user,
we need to implement move

890
00:38:40,866 --> 00:38:43,886
and finally, which is gonna move
tiles around and then finally,

891
00:38:43,886 --> 00:38:45,646
we need to implement
a function that checks

892
00:38:45,646 --> 00:38:48,076
if the game has been won and
we can congratulate the user

893
00:38:48,076 --> 00:38:49,236
for doing something I can't do.

894
00:38:50,846 --> 00:38:54,186
So we have this file
15.c supplied for us

895
00:38:54,336 --> 00:38:56,096
and the main function
is already written.

896
00:38:56,636 --> 00:38:57,296
Woohoo, we're done.

897
00:38:57,926 --> 00:39:00,256
So this main function, what it's
gonna do is it's gonna accept

898
00:39:00,256 --> 00:39:02,656
and parse the command line
argument, create the board,

899
00:39:03,056 --> 00:39:04,876
check if the game
is won and exit,

900
00:39:04,876 --> 00:39:07,726
and it's gonna get input
and move the tiles.

901
00:39:07,786 --> 00:39:09,706
So, let's take a look at
what's going on there.

902
00:39:09,706 --> 00:39:10,806
It sounds like, you're
done right?

903
00:39:11,986 --> 00:39:16,016
So if we open up 15,
and scroll through this,

904
00:39:16,016 --> 00:39:18,396
we have this nice comment,

905
00:39:19,316 --> 00:39:22,626
don't worry about this
define open source 500 thing,

906
00:39:23,356 --> 00:39:25,736
so we're just including some
libraries here, the usual folks

907
00:39:25,826 --> 00:39:29,186
that you wanna include, and
so now we have some constants.

908
00:39:29,756 --> 00:39:31,536
So, as you saw, might
have seen a section,

909
00:39:31,756 --> 00:39:34,326
this define statement creates
what's called a constant.

910
00:39:34,596 --> 00:39:37,196
So, this is not a variable, it
doesn't have a type or a size,

911
00:39:37,746 --> 00:39:39,896
when you compile your code,
one of the first thing

912
00:39:39,896 --> 00:39:41,016
that compiler is gonna do,

913
00:39:41,016 --> 00:39:42,976
it is effectively gonna
do a find and replace.

914
00:39:43,276 --> 00:39:46,066
Every time it sees DIM_MIN,
it's gonna delete that

915
00:39:46,066 --> 00:39:47,106
and type in the number 3.

916
00:39:47,596 --> 00:39:49,796
So, these aren't variables,
but they're constants,

917
00:39:49,866 --> 00:39:52,076
and that usually leads
to better designed

918
00:39:52,076 --> 00:39:53,196
and easier to read code.

919
00:39:53,196 --> 00:39:55,896
So now, we have a couple
of global variables

920
00:39:56,256 --> 00:39:58,036
and now we have our
function prototypes,

921
00:39:58,036 --> 00:40:00,116
so these are all the
functions that exist so far.

922
00:40:00,226 --> 00:40:00,686
Question?

923
00:40:01,516 --> 00:40:05,516
[ Inaudible Remark ]

924
00:40:06,016 --> 00:40:06,083
.

925
00:40:06,166 --> 00:40:08,186
>> So what's the difference
between const and define?

926
00:40:08,556 --> 00:40:11,516
So if I say const that
is actually a variable.

927
00:40:11,996 --> 00:40:13,586
So it's gonna be
find and replace.

928
00:40:13,586 --> 00:40:16,356
It's actually gonna go somewhere
in RAM and you can read from it.

929
00:40:16,616 --> 00:40:18,676
When I say define it's
never actually gonna be put

930
00:40:18,676 --> 00:40:19,576
in the computer's memory.

931
00:40:19,926 --> 00:40:23,656
Instead before the executed was
created every time we see those

932
00:40:23,656 --> 00:40:26,286
two word, DIM_MIN or DIM_MAX,
they're just gonna be wiped out

933
00:40:26,286 --> 00:40:27,346
and replaced with
the number three.

934
00:40:27,846 --> 00:40:31,176
So they are the same in that you
can't change them but different

935
00:40:31,176 --> 00:40:34,296
in what the compiler
does with them.

936
00:40:34,466 --> 00:40:34,666
Yeah.

937
00:40:35,516 --> 00:40:43,396
[ Inaudible Remark ]

938
00:40:43,896 --> 00:40:46,696
>> Yeah so basically what
the function prototype is,

939
00:40:46,696 --> 00:40:49,526
is kinda the first
line of the function.

940
00:40:49,856 --> 00:40:52,306
So if I go down here
to the function clear

941
00:40:52,406 --> 00:40:54,006
which was written for us.

942
00:40:55,286 --> 00:40:59,536
Okay. Okay, so you
have void clear void.

943
00:41:00,106 --> 00:41:03,116
Remember the function prototype
just said what this first

944
00:41:03,116 --> 00:41:03,746
line was.

945
00:41:04,246 --> 00:41:06,386
So basic convention
is you should match--

946
00:41:06,386 --> 00:41:09,626
the function prototype should
match whatever the declaration

947
00:41:09,626 --> 00:41:12,146
of your-- the definition of
your function is down here.

948
00:41:12,546 --> 00:41:14,856
So, in this case, we're just
supplying void just like we did

949
00:41:14,856 --> 00:41:16,326
to main at the beginning
of the term,

950
00:41:17,076 --> 00:41:18,576
just as they don't
need any arguments.

951
00:41:18,606 --> 00:41:20,906
I can get rid of this
void and it would be fine.

952
00:41:20,906 --> 00:41:22,576
This is just one
style of writing

953
00:41:22,866 --> 00:41:24,776
that if there aren't any
arguments I can just say void.

954
00:41:25,326 --> 00:41:29,516
So after our function
prototypes, we have our main.

955
00:41:30,166 --> 00:41:31,766
So this function greet
is written for you.

956
00:41:31,766 --> 00:41:32,976
It's just gonna say hello.

957
00:41:33,506 --> 00:41:35,706
And as usual we make sure
they supply the right number

958
00:41:35,706 --> 00:41:37,376
of arguments like the
good programmers we are.

959
00:41:38,616 --> 00:41:40,926
Take that number and we're
to convert that number

960
00:41:40,926 --> 00:41:42,116
to the size of the board.

961
00:41:42,476 --> 00:41:45,816
So when I run Fifteen, I wanna
supply a number between 3 and 9.

962
00:41:46,936 --> 00:41:49,316
And that's going to be
the size of the board.

963
00:41:49,316 --> 00:41:53,466
So now I'm just gonna printf,
if they give me the wrong number

964
00:41:53,766 --> 00:41:56,986
that needs to be between 3
by 3 and 9 by 9 and return 2.

965
00:41:56,986 --> 00:41:58,596
So this is just a
different area code.

966
00:41:58,596 --> 00:42:01,076
So if I return 1, that means I
didn't supply the right number

967
00:42:01,076 --> 00:42:02,946
of arguments and if I return 2

968
00:42:02,946 --> 00:42:04,826
that means I supplied an
argument but it was wrong.

969
00:42:04,826 --> 00:42:07,516
So here's just the use of
as we saw in the last Pset,

970
00:42:07,516 --> 00:42:09,216
these different arrow
codes or return values.

971
00:42:09,456 --> 00:42:10,756
Here's one thing we
can use them for.

972
00:42:10,826 --> 00:42:13,146
Different things went wrong
so returning different things.

973
00:42:14,536 --> 00:42:16,136
So now we're calling
this function init

974
00:42:16,446 --> 00:42:18,096
which is not written
for you and this is

975
00:42:18,096 --> 00:42:20,076
as the comment says we
wanna initialize the board

976
00:42:20,076 --> 00:42:21,126
and get everything ready to go.

977
00:42:21,746 --> 00:42:24,526
So now, we're gonna enter
in this main loop that kind

978
00:42:25,086 --> 00:42:27,286
of is gonna keep looping
as you're playing the game.

979
00:42:27,286 --> 00:42:28,206
So while true.

980
00:42:28,506 --> 00:42:29,916
This is called an infinite loop.

981
00:42:30,026 --> 00:42:32,756
This is not going to exit
until we tell it to exit.

982
00:42:33,776 --> 00:42:36,616
So while true, we're
gonna clear the screen

983
00:42:36,616 --> 00:42:37,826
so we can redraw the board.

984
00:42:38,436 --> 00:42:39,236
Call draw.

985
00:42:39,366 --> 00:42:41,236
So now we're gonna have
the board on the screen

986
00:42:41,836 --> 00:42:44,876
and before we allow the user to
move we wanna check if they won.

987
00:42:44,876 --> 00:42:48,926
So if they did win, we want to
break out of this infinite loop

988
00:42:48,926 --> 00:42:50,426
because the user is
not playing anymore.

989
00:42:51,656 --> 00:42:55,536
So now, we're going to ask
the user what tile they want

990
00:42:55,536 --> 00:42:55,866
to move.

991
00:42:56,226 --> 00:42:57,956
So we're not gonna
prompt them infinitely,

992
00:42:58,066 --> 00:42:59,906
we're going to prompt
them once and then

993
00:42:59,906 --> 00:43:02,116
after they input we're gonna
go back and prompt them again.

994
00:43:02,906 --> 00:43:05,106
So after we get the tile
or the number of the tile,

995
00:43:05,296 --> 00:43:07,206
they want to move, we're
gonna try to move it.

996
00:43:07,796 --> 00:43:10,516
If we can't move it, never
gonna say illegal move.

997
00:43:10,896 --> 00:43:13,206
And just kinda wait a minute
so that it can animate okay.

998
00:43:13,206 --> 00:43:17,056
And after they do-- after
they select the tile to move

999
00:43:17,056 --> 00:43:19,646
and we move it then it's just
gonna slip again to enemy.

1000
00:43:20,346 --> 00:43:23,126
So even though this move is
inside of this it condition,

1001
00:43:23,126 --> 00:43:24,566
it's still calling
the function move.

1002
00:43:24,566 --> 00:43:27,146
Which means it's still
going to execute move

1003
00:43:27,146 --> 00:43:29,206
and if you wanna do something
in move like move a tile,

1004
00:43:29,206 --> 00:43:31,406
which sounds a good idea,
that's still gonna happen.

1005
00:43:31,876 --> 00:43:34,216
So even though it doesn't
just say move tiles semicolon

1006
00:43:34,216 --> 00:43:35,546
and it's inside of
this condition,

1007
00:43:35,686 --> 00:43:38,246
it's still being executed the
same way it would other wise.

1008
00:43:38,806 --> 00:43:41,476
So that's it for me.

1009
00:43:41,476 --> 00:43:45,986
And so now, this is
just the wait and see

1010
00:43:45,986 --> 00:43:48,756
to clear the screen,
don't worry about that.

1011
00:43:48,756 --> 00:43:51,796
Print the welcome message in
all caps 'cause we're yelling.

1012
00:43:52,436 --> 00:43:54,726
And so now here are the four
functions we have to do,

1013
00:43:55,826 --> 00:43:56,726
to do on all of them

1014
00:43:56,726 --> 00:43:59,016
and comments explaining
what we need to do.

1015
00:43:59,096 --> 00:44:03,426
So let's first take
a look at init.

1016
00:44:06,356 --> 00:44:08,516
So we saw these two
global variables.

1017
00:44:08,686 --> 00:44:12,536
One called board and it
specifies two dimensions.

1018
00:44:12,836 --> 00:44:14,856
So this means that we have
a two-dimensional array

1019
00:44:15,136 --> 00:44:16,386
which is basically a grid.

1020
00:44:16,996 --> 00:44:19,766
So this DIM_MAX and DIM_MAX
you remember are the defined

1021
00:44:19,836 --> 00:44:21,546
constants and may
have a value of 9.

1022
00:44:21,756 --> 00:44:22,946
So that means no matter what

1023
00:44:23,266 --> 00:44:28,276
when we start our game we have a
9 by 9 grid representing as big

1024
00:44:28,276 --> 00:44:29,806
as the board is allowed to be.

1025
00:44:30,716 --> 00:44:32,746
We also have a global
variable called D.

1026
00:44:33,136 --> 00:44:34,646
So this is the size
of the board.

1027
00:44:34,646 --> 00:44:36,916
So this is basically
what the user typed in,

1028
00:44:36,916 --> 00:44:39,116
so this is gonna
3, 4, 5, et cetera.

1029
00:44:40,156 --> 00:44:42,506
So because C can't
really resize a raise

1030
00:44:42,506 --> 00:44:44,636
and we don't wanna bother
dynamically creating a different

1031
00:44:44,636 --> 00:44:46,406
size array based on
what the user typed in,

1032
00:44:46,576 --> 00:44:49,056
we're just gonna create
this huge 9 by 9 array.

1033
00:44:49,756 --> 00:44:52,216
So even if we're only
working with the board of 3

1034
00:44:52,216 --> 00:44:54,946
by 3 we don't-- we still
have this 9 by 9 array

1035
00:44:54,946 --> 00:44:56,306
but we don't wanna look
at the whole thing.

1036
00:44:56,736 --> 00:44:58,116
We never really wanna go outside

1037
00:44:58,116 --> 00:45:00,766
of the first three squares
sideways or vertically

1038
00:45:00,886 --> 00:45:04,166
but they do exist because we've
created this array that's 9

1039
00:45:04,166 --> 00:45:05,616
by 9.

1040
00:45:06,816 --> 00:45:09,166
So board, after init
is complete,

1041
00:45:09,276 --> 00:45:12,136
board needs to contain the
starting state of the board.

1042
00:45:12,136 --> 00:45:14,366
So notice init doesn't
return anything,

1043
00:45:14,596 --> 00:45:17,286
that's because it's just going
to update this global variable.

1044
00:45:17,616 --> 00:45:20,136
So because this variable is
global it was declared outside

1045
00:45:20,136 --> 00:45:21,686
of main and outside
of any functions.

1046
00:45:21,886 --> 00:45:24,766
That means any function we want
can access it and change it.

1047
00:45:25,766 --> 00:45:27,816
So there are few ways you could
represent your game board.

1048
00:45:28,156 --> 00:45:31,526
Let's say you have board
XY so some first dimension

1049
00:45:31,526 --> 00:45:32,446
and some second dimension.

1050
00:45:32,686 --> 00:45:34,456
That could either
be the element XY

1051
00:45:34,806 --> 00:45:37,756
which should be column X row
Y or you might find it easier

1052
00:45:37,756 --> 00:45:39,836
to work with that
meaning row column.

1053
00:45:39,886 --> 00:45:42,526
So you often see row I and
column J or something like that.

1054
00:45:43,706 --> 00:45:44,846
So that decision is up to you.

1055
00:45:44,846 --> 00:45:46,686
How you wanna represent
the board is your call.

1056
00:45:47,516 --> 00:45:49,706
But you also wanna make
sure that regardless

1057
00:45:49,706 --> 00:45:51,896
of your representation
that the board starts off

1058
00:45:51,946 --> 00:45:53,016
in descending order.

1059
00:45:53,376 --> 00:45:56,736
So 15 should be first
if it's 4 by 4 and 14.

1060
00:45:57,406 --> 00:45:59,116
There's also this
condition to make sure

1061
00:45:59,116 --> 00:46:00,736
that the board is
actually solvable

1062
00:46:01,076 --> 00:46:05,106
that if there are an odd number
of total tiles like 15 tiles,

1063
00:46:05,106 --> 00:46:07,756
not counting the blank space, if
that number is odd then you need

1064
00:46:07,756 --> 00:46:09,296
to swap the 2 and the 1.

1065
00:46:09,296 --> 00:46:12,416
So the last row should
be 312 instead of 321.

1066
00:46:12,736 --> 00:46:14,226
That's just to make sure
the board is solvable.

1067
00:46:14,226 --> 00:46:16,036
321, you actually
couldn't solve it.

1068
00:46:16,256 --> 00:46:17,296
That'd be really meaningless.

1069
00:46:17,846 --> 00:46:21,996
So we also need to make
sure that we keep track

1070
00:46:21,996 --> 00:46:24,726
of the blank tile so that's
really important when moving

1071
00:46:24,726 --> 00:46:27,016
because we can only move
things into a blank space

1072
00:46:27,346 --> 00:46:28,836
or else we have a whole
new game if we can.

1073
00:46:29,576 --> 00:46:32,146
So you need to choose
some representation

1074
00:46:32,146 --> 00:46:33,736
of your blank tile.

1075
00:46:33,736 --> 00:46:37,226
However, we can't just use
a string blank or a letter B

1076
00:46:37,226 --> 00:46:38,466
for blank for something
like that

1077
00:46:38,966 --> 00:46:41,996
because our board needs
to contain only ints.

1078
00:46:42,316 --> 00:46:45,636
Now remember that we
declare this as int board 99.

1079
00:46:45,866 --> 00:46:47,166
So that means we
can't put anything

1080
00:46:47,166 --> 00:46:48,466
in there that's not an integer.

1081
00:46:48,886 --> 00:46:51,476
So you probably wanna
choose some integer value

1082
00:46:51,726 --> 00:46:54,666
that will never appear on the
boards that are given 'cause

1083
00:46:54,716 --> 00:46:56,986
if it did then you can
easily confuse the blank tile

1084
00:46:56,986 --> 00:46:58,216
for an actual numbered tile.

1085
00:46:58,786 --> 00:47:01,836
So here, this could be
where define comes in handy.

1086
00:47:02,276 --> 00:47:04,766
So instead of trying to remember
oh, I choose the number 1, 2, 3,

1087
00:47:04,766 --> 00:47:06,316
4, 6 as my blank space.

1088
00:47:06,366 --> 00:47:07,536
Instead of trying to remember

1089
00:47:07,536 --> 00:47:10,026
that everywhere I
probably wanna use define

1090
00:47:10,316 --> 00:47:13,236
to create some constant
representing my blank space

1091
00:47:13,636 --> 00:47:15,236
that everywhere in my
program I wanna use

1092
00:47:15,236 --> 00:47:18,766
that constant not the value of
the constant because let's say

1093
00:47:18,766 --> 00:47:23,856
that you chose the value
16 for your blank space.

1094
00:47:24,446 --> 00:47:28,526
So now I come along and I say
well, I want a larger board.

1095
00:47:28,526 --> 00:47:31,906
In that case 16 is now a
tile so if I had chosen 16

1096
00:47:31,906 --> 00:47:34,366
and just use the number 16
everywhere, I have to go through

1097
00:47:34,366 --> 00:47:37,026
and change every 16 to some
other number like a million.

1098
00:47:38,086 --> 00:47:40,886
If I use a define I only need
to change that at the top

1099
00:47:40,886 --> 00:47:42,506
of my program and
then everywhere else

1100
00:47:42,506 --> 00:47:44,966
in the code I've effectively
changed what the blank

1101
00:47:44,966 --> 00:47:45,556
tile means.

1102
00:47:46,146 --> 00:47:47,196
So it's a really good idea

1103
00:47:47,196 --> 00:47:49,436
to use define 'cause it also
makes your code a lot more

1104
00:47:49,436 --> 00:47:51,776
readable instead of just hitting
random numbers everywhere,

1105
00:47:51,976 --> 00:47:53,496
you'll see words
like blank space.

1106
00:47:54,206 --> 00:47:57,926
So questions on what we
need to do with init?

1107
00:48:02,416 --> 00:48:05,266
Okay, so basic idea, we're
just not gonna return anything,

1108
00:48:05,266 --> 00:48:07,856
just fill up some global array
that other people can use.

1109
00:48:08,606 --> 00:48:10,516
So now we need to
worry about draw.

1110
00:48:10,776 --> 00:48:14,396
So what draw is gonna do
is output the current state

1111
00:48:14,396 --> 00:48:15,926
of the board to the terminal.

1112
00:48:16,796 --> 00:48:20,176
So remember that board
IJ, so whether that means

1113
00:48:20,176 --> 00:48:23,426
like the coordinates XY or row
I column J, whatever that means,

1114
00:48:23,546 --> 00:48:25,026
that's going to give
you the value

1115
00:48:25,026 --> 00:48:26,856
of the tile that's
in that place.

1116
00:48:27,746 --> 00:48:29,496
So each tile has a
different number.

1117
00:48:29,496 --> 00:48:31,816
We probably wanna store
those numbers inside

1118
00:48:31,816 --> 00:48:33,266
of the board array.

1119
00:48:33,356 --> 00:48:35,846
So again, what this mean, what
I and J mean are up to you,

1120
00:48:36,066 --> 00:48:37,216
but depending on how you choose

1121
00:48:37,216 --> 00:48:39,996
to represent your board that's
gonna change how you output it.

1122
00:48:39,996 --> 00:48:42,456
So you need to make sure
that we output things

1123
00:48:42,456 --> 00:48:43,096
in the right order.

1124
00:48:43,096 --> 00:48:46,676
We wanna stay in one row at a
time and output every element

1125
00:48:46,676 --> 00:48:49,126
in one row before moving
on to the next row.

1126
00:48:49,776 --> 00:48:51,476
So you can't just print
out a column and then print

1127
00:48:51,476 --> 00:48:54,136
out another column just
because of the way printf works.

1128
00:48:54,136 --> 00:48:56,496
Right? We can print out a row
and once you print a new line,

1129
00:48:56,496 --> 00:48:58,796
we can't really easily go
back up to the previous line

1130
00:48:58,796 --> 00:48:59,666
and try to add something.

1131
00:49:00,106 --> 00:49:02,876
So we wanna make sure that
we print things row by row.

1132
00:49:04,676 --> 00:49:06,956
So some tips for writing draw,

1133
00:49:07,176 --> 00:49:08,786
make sure that you
only print the new line

1134
00:49:08,786 --> 00:49:09,896
at the end of the row.

1135
00:49:10,416 --> 00:49:11,276
So make sure-- you know,

1136
00:49:11,276 --> 00:49:13,396
print out all the columns then
print the new line to move

1137
00:49:13,396 --> 00:49:16,566
on to the next row and make
sure just for formatting

1138
00:49:16,566 --> 00:49:18,206
that you have some
spaces between columns

1139
00:49:18,546 --> 00:49:20,716
and maybe some other
characters like a pipe or a plus

1140
00:49:20,716 --> 00:49:22,706
or something just to
kinda create a grid.

1141
00:49:23,826 --> 00:49:26,606
And so there's a little
printf trick we can use.

1142
00:49:26,606 --> 00:49:27,846
See I noticed that if we wanted

1143
00:49:27,846 --> 00:49:30,106
to print 15, we wanted
to print 5.

1144
00:49:30,646 --> 00:49:33,016
Instead of our grid if we wanted
to make sure everything lines

1145
00:49:33,016 --> 00:49:36,206
up that's kinda messes up,
right, because 15 has two digits

1146
00:49:36,406 --> 00:49:38,486
and 5 has next digit
so we need to make sure

1147
00:49:38,486 --> 00:49:41,096
that we somehow compensate
for that by printing a space.

1148
00:49:41,096 --> 00:49:43,996
So printf, this is
really cool way to do this

1149
00:49:43,996 --> 00:49:46,086
if you just say present 2

1150
00:49:46,426 --> 00:49:49,676
so that 2 is gonna say what
the minimum number of digit is.

1151
00:49:50,056 --> 00:49:52,216
So if I just print a 5
there, it's actually going

1152
00:49:52,216 --> 00:49:57,216
to print space 5
instead of just 5.

1153
00:49:57,216 --> 00:49:59,556
So you can need to determine
you know what the best value

1154
00:49:59,556 --> 00:50:01,596
for your grid is depending
on what it looks like.

1155
00:50:01,596 --> 00:50:03,976
But just-- so you don't have to
worry about is it less than 9

1156
00:50:03,976 --> 00:50:05,546
and put the space
and put the number.

1157
00:50:05,546 --> 00:50:07,026
You know, it gets even
worse once you get

1158
00:50:07,026 --> 00:50:08,976
into three-digit numbers.

1159
00:50:09,116 --> 00:50:10,626
>> So you don't have
to worry about that,

1160
00:50:10,626 --> 00:50:12,986
there is that quick
little printf shortcut.

1161
00:50:13,916 --> 00:50:16,286
So questions on draw?

1162
00:50:16,896 --> 00:50:24,086
Okay, so now let's get into
actually playing the game.

1163
00:50:24,266 --> 00:50:26,996
So the Move function is
going to allow the user

1164
00:50:26,996 --> 00:50:28,916
to move tiles around
on the board.

1165
00:50:29,476 --> 00:50:32,376
So to move a tile
all we really need

1166
00:50:32,376 --> 00:50:34,666
to do is change the
board we're in, right?

1167
00:50:34,666 --> 00:50:39,056
If we wanna move 15 from the top
left corner into the space next

1168
00:50:39,056 --> 00:50:41,736
to it, we just need to take
the 15, put it into that slot

1169
00:50:41,736 --> 00:50:43,956
in the board array and take
our blank space and put it

1170
00:50:43,956 --> 00:50:45,696
into whatever slot
the 15 was in.

1171
00:50:46,376 --> 00:50:49,876
However, not all moves in the
game of Fifteen are legal.

1172
00:50:50,576 --> 00:50:52,976
So we can't-- if our blank
space is in the bottom right

1173
00:50:52,976 --> 00:50:54,736
and we wanna more a
tile in the top left,

1174
00:50:55,086 --> 00:50:57,906
we can't because we can't move
the tile over another tile.

1175
00:50:58,826 --> 00:51:00,656
So Move needs to determine

1176
00:51:00,656 --> 00:51:03,316
if a move is legal before
it actually makes it.

1177
00:51:03,686 --> 00:51:05,496
So you notice that
Move is a Boolean

1178
00:51:05,616 --> 00:51:07,196
which means it's gonna
return true or false

1179
00:51:07,576 --> 00:51:08,856
and if we can't make a move,

1180
00:51:09,296 --> 00:51:11,876
then you should leave the board
array alone and return false.

1181
00:51:12,546 --> 00:51:16,356
So remember in 15.c it's gonna
check if move was true or false.

1182
00:51:16,666 --> 00:51:19,346
And if it's false, meaning
the user can't make that move,

1183
00:51:19,346 --> 00:51:20,286
it's gonna say something.

1184
00:51:20,286 --> 00:51:22,396
So you need to make sure
that you're returning true

1185
00:51:22,396 --> 00:51:23,586
or false appropriately

1186
00:51:23,586 --> 00:51:25,826
and making sure not
to update the board.

1187
00:51:26,766 --> 00:51:29,786
So also with move, you notice
it only takes one argument.

1188
00:51:29,786 --> 00:51:32,846
And that's the number of the
tile that I want to move.

1189
00:51:33,396 --> 00:51:34,596
So the number of the tile

1190
00:51:34,666 --> 00:51:38,356
and where the tile is aren't
necessarily the same, right?

1191
00:51:38,356 --> 00:51:41,826
My tiles are in some 2D array
but I'm only getting a number.

1192
00:51:41,826 --> 00:51:45,276
So that means I need to
look for where that tile is.

1193
00:51:45,486 --> 00:51:48,576
And the only way to
do that is to search

1194
00:51:48,616 --> 00:51:51,236
through the board array
and look for the number

1195
00:51:51,236 --> 00:51:52,246
that the user specified.

1196
00:51:52,806 --> 00:51:56,526
So we can go through row
by row or column by column,

1197
00:51:56,526 --> 00:52:00,256
whatever you want, and get
some pairs, some XY or some IJ

1198
00:52:00,406 --> 00:52:02,786
that says, Mike, the tile
I wanna move is right here.

1199
00:52:03,806 --> 00:52:06,566
So we also need to determine
where the blank tile is

1200
00:52:06,876 --> 00:52:09,776
because a legal move is when
the blank tile is immediately

1201
00:52:09,776 --> 00:52:11,776
adjacent to the tile
that you wanna move.

1202
00:52:12,716 --> 00:52:16,416
So a little design question
here, we don't really need

1203
00:52:16,416 --> 00:52:18,936
to look at the entire
board every time

1204
00:52:18,936 --> 00:52:20,516
to find the blank space, right?

1205
00:52:20,516 --> 00:52:24,696
Once we move, once we move
a tile, we know exactly

1206
00:52:24,696 --> 00:52:25,866
where the blank space is.

1207
00:52:26,646 --> 00:52:29,196
It's not gonna change until
we try to make another move.

1208
00:52:29,746 --> 00:52:31,646
So we're searching over the
whole thing to find a number

1209
00:52:31,646 --> 00:52:32,706
and then searching
over the whole thing

1210
00:52:32,706 --> 00:52:34,836
to find a blank space
is little wasteful.

1211
00:52:35,246 --> 00:52:39,596
So you can think about what the
best way to avoid wasting that.

1212
00:52:39,596 --> 00:52:41,616
So now if the positions
are adjacent,

1213
00:52:41,966 --> 00:52:44,466
that means that the values
in the board can be swapped.

1214
00:52:45,026 --> 00:52:48,396
So basically four cases either,
you know there, one is to left

1215
00:52:48,396 --> 00:52:49,956
of the other, one is to
the right of the other,

1216
00:52:49,986 --> 00:52:51,856
one is above the other,
one is below the other.

1217
00:52:52,346 --> 00:52:54,766
So you need to consider that
case and you also need to think

1218
00:52:54,766 --> 00:52:56,166
about what the size
of the board is.

1219
00:52:56,166 --> 00:52:57,936
So you wanna make sure
that you never end

1220
00:52:57,936 --> 00:53:00,676
up somehow moving tiles off the
board or something like that.

1221
00:53:01,926 --> 00:53:05,516
So any questions on making sure
the move is legal in moving it?

1222
00:53:05,516 --> 00:53:05,626
Yeah

1223
00:53:05,626 --> 00:53:08,336
>> Is the size of the
board going to change?

1224
00:53:08,336 --> 00:53:10,176
>> So is the size of the
board going to change?

1225
00:53:10,206 --> 00:53:12,216
It will never change
within the same game

1226
00:53:12,586 --> 00:53:14,226
but it will change
among different games.

1227
00:53:14,456 --> 00:53:16,446
So when I run 15 and
then some number,

1228
00:53:16,726 --> 00:53:18,906
that number says how
big the board is.

1229
00:53:19,286 --> 00:53:21,936
So if I run 15, 4, I'm
gonna get the game of 15

1230
00:53:21,976 --> 00:53:25,716
because I have a 4 by 4
grid, that's 16 tiles minus 1

1231
00:53:25,716 --> 00:53:27,846
for the blank tile,
so that's 15 tiles.

1232
00:53:28,456 --> 00:53:30,806
So once I'm in that game,
I can't like convert

1233
00:53:30,806 --> 00:53:33,216
that to a 6 by 6 grid instead.

1234
00:53:33,876 --> 00:53:35,686
But when I run the
program again, I can run it

1235
00:53:35,686 --> 00:53:36,626
with a different number.

1236
00:53:37,066 --> 00:53:40,666
So your code needs to be able
to handle inputs from 3 to 9

1237
00:53:41,146 --> 00:53:43,596
as those defined constants say.

1238
00:53:44,086 --> 00:53:46,876
And also remember that even
though your board is 3 by 3,

1239
00:53:47,166 --> 00:53:49,816
your array is 9 by 9,
so you need to make sure

1240
00:53:49,816 --> 00:53:53,056
by hand you don't go outside
of the actual dimension

1241
00:53:53,056 --> 00:53:55,486
of the board regardless
of how big the array is.

1242
00:53:56,016 --> 00:53:59,196
Are there questions on moving?

1243
00:54:03,056 --> 00:54:09,196
Alright. So that's done, now
our last function is won.

1244
00:54:09,196 --> 00:54:13,746
So this is also a Boolean
and it's going to return true

1245
00:54:13,746 --> 00:54:14,986
if the game has been won.

1246
00:54:15,276 --> 00:54:18,616
So that means that all the
tiles are in increasing order.

1247
00:54:18,966 --> 00:54:21,576
That means there's a 1 in the
top left, there's a 2 next

1248
00:54:21,576 --> 00:54:24,406
to that, and there's a
3 next to that and then

1249
00:54:24,446 --> 00:54:26,796
on the next row there's a 4
or on the same row depending

1250
00:54:26,796 --> 00:54:28,696
on how big your board
is, and all the way

1251
00:54:28,696 --> 00:54:30,786
down until all the
numbers are in order

1252
00:54:30,786 --> 00:54:33,296
and the blank tile is
in the bottom right.

1253
00:54:33,486 --> 00:54:39,176
So in order to check if the game
has been won, we need to iterate

1254
00:54:39,176 --> 00:54:40,916
over the entire board
array, again,

1255
00:54:40,916 --> 00:54:41,756
just like when we're moving,

1256
00:54:41,756 --> 00:54:43,796
and we need to check
every single value.

1257
00:54:44,716 --> 00:54:47,886
And if each value matches up
to what we expect it to be,

1258
00:54:48,696 --> 00:54:50,046
that means that the
game has been won.

1259
00:54:50,766 --> 00:54:53,266
Now as soon as one
thing is out of order,

1260
00:54:53,456 --> 00:54:55,306
we know that the
entire game is not won.

1261
00:54:55,766 --> 00:54:58,506
So if we find the 2 in the
left, we don't need to go

1262
00:54:58,506 --> 00:55:00,406
through everything in order
to find out, you know,

1263
00:55:00,446 --> 00:55:02,236
how many tiles are left
or something like that.

1264
00:55:02,736 --> 00:55:04,996
Once one tile is wrong
the whole game is wrong.

1265
00:55:05,606 --> 00:55:07,936
So think about that when you're
implementing your won function.

1266
00:55:08,536 --> 00:55:09,776
And we also need to
make sure we look

1267
00:55:09,776 --> 00:55:10,866
at things in the right order.

1268
00:55:11,056 --> 00:55:12,096
You know we can't just look at--

1269
00:55:12,096 --> 00:55:13,676
we can't say the
columns are in order.

1270
00:55:13,676 --> 00:55:15,156
We need to make sure
that the row--

1271
00:55:15,156 --> 00:55:16,686
everything is in order in rows.

1272
00:55:16,686 --> 00:55:21,136
So 1, 2, 3, next row, 4, 5, 6,
next row, 7, 8, 9, et cetera.

1273
00:55:22,036 --> 00:55:24,936
So again, depending on how you
represented your board that's

1274
00:55:24,936 --> 00:55:27,626
going to change so
just one thing to think

1275
00:55:27,626 --> 00:55:30,866
about when you choose
your board representation,

1276
00:55:30,866 --> 00:55:32,846
just think about what
is actually being stored

1277
00:55:32,846 --> 00:55:35,596
in that array and if in
memory you drew a little grid

1278
00:55:35,596 --> 00:55:39,996
where the numbers would be if I
say something like board 2, 3.

1279
00:55:40,226 --> 00:55:47,506
So any questions on won or
any part of Fiftee or Find?

1280
00:55:47,706 --> 00:55:47,916
Yeah.

1281
00:55:48,516 --> 00:55:54,306
[ Inaudible Remark ]

1282
00:55:54,806 --> 00:55:58,536
>> Yes, so is there a default
structure so if we look at--

1283
00:55:58,986 --> 00:56:02,806
back into the Fifteen code.

1284
00:56:02,806 --> 00:56:05,196
So you noticed that it's
already declared for us.

1285
00:56:05,196 --> 00:56:06,256
We didn't even have
to declare it.

1286
00:56:06,796 --> 00:56:09,616
So we just know that there
are some 9 by 9 grid in memory

1287
00:56:09,616 --> 00:56:10,746
and we can do something with it.

1288
00:56:11,226 --> 00:56:15,466
So this is what you should be
using to save your board state.

1289
00:56:15,676 --> 00:56:17,016
So I mentioned that
variable board

1290
00:56:17,016 --> 00:56:19,006
and that's already
declared for us.

1291
00:56:21,026 --> 00:56:22,966
Other questions on anything?

1292
00:56:23,586 --> 00:56:23,866
Yeah.

1293
00:56:24,516 --> 00:56:28,696
[ Inaudible Remark ]

1294
00:56:29,196 --> 00:56:31,466
>> Yes, so the arrays
will always be square.

1295
00:56:31,466 --> 00:56:32,836
We can never have a 3 by 4.

1296
00:56:32,896 --> 00:56:35,546
We're just supplying one
number and that one number says

1297
00:56:35,546 --> 00:56:37,266
that many rows and
that many columns.

1298
00:56:37,266 --> 00:56:37,846
[ Inaudible Remark ]

1299
00:56:37,846 --> 00:56:44,966
>> Right. So if they entered
a 9 by 9 there'd be 80 tiles.

1300
00:56:44,966 --> 00:56:49,496
81 if you count the blank.

1301
00:56:49,646 --> 00:56:49,856
Yeah.

1302
00:56:50,516 --> 00:56:59,926
[ Inaudible Remark ]

1303
00:57:00,426 --> 00:57:02,536
>> Oh sure, so in section this
week you're gonna learn all

1304
00:57:02,536 --> 00:57:05,556
about GDB but what
GDB is a debugger.

1305
00:57:05,946 --> 00:57:08,136
So as you're writing your
Psets 1 and 2 you might have,

1306
00:57:08,196 --> 00:57:09,206
you know, oh, I'm stuck.

1307
00:57:09,206 --> 00:57:10,316
My program isn't working right.

1308
00:57:10,316 --> 00:57:12,736
Let's put a printf here and
see what this variable is.

1309
00:57:12,966 --> 00:57:14,176
That's a really common
debugging technique

1310
00:57:14,176 --> 00:57:15,036
and it definitely works.

1311
00:57:15,416 --> 00:57:18,346
What GDB is, is a way to kind
of make that a little easier.

1312
00:57:18,346 --> 00:57:20,276
What it will allow you
to do is say that "Okay,

1313
00:57:20,276 --> 00:57:22,606
once I get to this
function won I wanna stop.

1314
00:57:22,606 --> 00:57:24,116
My program is gonna
stop executing."

1315
00:57:24,516 --> 00:57:26,536
I'm not gonna like print
out variables and look

1316
00:57:26,536 --> 00:57:28,796
at where things are in memory
then I can actually step

1317
00:57:28,826 --> 00:57:31,026
through like line by
line of my program.

1318
00:57:31,716 --> 00:57:33,496
And so you see how to do that
in section but it's really,

1319
00:57:33,496 --> 00:57:35,576
really simple and
so if you say "Okay,

1320
00:57:35,896 --> 00:57:37,366
my game isn't working right.

1321
00:57:37,366 --> 00:57:40,276
I don't where it's
going wrong" so I can go

1322
00:57:40,276 --> 00:57:42,476
in to say the move function and
say "Okay, is this line right?"

1323
00:57:42,476 --> 00:57:43,656
Yup! Go to the next line.

1324
00:57:43,656 --> 00:57:44,166
Is that right?

1325
00:57:44,166 --> 00:57:46,136
Check my board array
and things like that.

1326
00:57:46,756 --> 00:57:48,976
So it is really, really helpful
as you're writing your code

1327
00:57:48,976 --> 00:57:51,076
to be able to step
through it line by line

1328
00:57:51,076 --> 00:57:52,806
without saying printf
a million times,

1329
00:57:52,806 --> 00:57:54,976
compile it then I gotta hand it
in, you know lay out printf's.

1330
00:57:55,686 --> 00:58:00,226
GDB is just a way of
making that faster.

1331
00:58:00,476 --> 00:58:00,906
Yeah.

1332
00:58:01,516 --> 00:58:25,796
[ Inaudible Remark ]

1333
00:58:26,296 --> 00:58:28,826
>> So to be clear this
problem set has two parts.

1334
00:58:29,246 --> 00:58:31,086
One is Find and one is Fifteen.

1335
00:58:31,526 --> 00:58:32,966
So they're not really
related to each other

1336
00:58:32,966 --> 00:58:34,356
like they're gonna
be run independently

1337
00:58:34,606 --> 00:58:35,796
but you do have to do them both.

1338
00:58:36,256 --> 00:58:38,176
You do have to comment,
generate, write sort,

1339
00:58:38,176 --> 00:58:41,316
write search and then in Fifteen
write those four functions.

1340
00:58:41,316 --> 00:58:42,786
So they're both parts
of the problem set,

1341
00:58:43,176 --> 00:58:45,906
you know find is not being
used by Fifteen anywhere

1342
00:58:45,906 --> 00:58:48,276
so they're independent, you
can start them in either order

1343
00:58:48,456 --> 00:58:50,036
but they're both part
of the assignment.

1344
00:58:50,036 --> 00:58:52,256
You need to do them both, sorry.

1345
00:58:52,816 --> 00:58:55,996
Other question on
the problem set?

1346
00:58:55,996 --> 00:58:56,066
Yeah.

1347
00:58:56,066 --> 00:59:05,026
>> How do we switch the blank
tile so somebody enters the game

1348
00:59:05,026 --> 00:59:09,996
of 80 then how do we know how
to switch them the same time?

1349
00:59:10,086 --> 00:59:11,856
>> So how do we switch
the blank tile?

1350
00:59:12,416 --> 00:59:16,086
So remember that our board
is just some array and inside

1351
00:59:16,086 --> 00:59:19,506
of that grid or that array
are values and inside one

1352
00:59:19,506 --> 00:59:21,686
of those spots in the
grid is the blank tile.

1353
00:59:22,396 --> 00:59:25,126
So when we make a move we're
switching the blank tile,

1354
00:59:25,126 --> 00:59:27,206
the position of the blank
tile and the position

1355
00:59:27,206 --> 00:59:28,626
of the tile we wanted to move.

1356
00:59:28,716 --> 00:59:31,136
So to determine that
we need to say "Okay,

1357
00:59:31,136 --> 00:59:34,446
given some number 80 I need
to find out where that 80 is."

1358
00:59:34,966 --> 00:59:36,966
So once I found that
80 I need to find

1359
00:59:36,966 --> 00:59:39,796
out where the blank space is
and say "Okay, if they're next

1360
00:59:39,796 --> 00:59:41,226
to each other somehow
I just need

1361
00:59:41,226 --> 00:59:44,116
to swap their locations
inside of that board array."

1362
00:59:44,586 --> 00:59:46,526
So it's up to you to find
out where the tile is,

1363
00:59:46,526 --> 00:59:48,296
where the blank space
is, if they're next

1364
00:59:48,296 --> 00:59:49,836
to each other and
then swap them.

1365
00:59:50,126 --> 00:59:52,466
So that now the board says
the blank space is no longer

1366
00:59:52,466 --> 00:59:54,636
in the bottom right but
it's the space left of that

1367
00:59:54,636 --> 00:59:59,756
because that's where the 80
was or something like that.

1368
00:59:59,756 --> 01:00:00,046
[ Inaudible Remark ]

1369
01:00:00,046 --> 01:00:02,986
>> So what-- how you represent
the blank space is up to you.

1370
01:00:03,126 --> 01:00:05,916
You can choose any constant
that makes sense to you

1371
01:00:06,336 --> 01:00:09,006
but just make sure that it's
not a number that's ever going

1372
01:00:09,006 --> 01:00:10,916
to be used by a tile.

1373
01:00:11,376 --> 01:00:14,296
So if I say my blank space
is 15 and I'm playing a 4

1374
01:00:14,296 --> 01:00:16,726
by 4 grid then I have
two things that are 15

1375
01:00:16,726 --> 01:00:18,136
and I'm probably
gonna get confused.

1376
01:00:18,636 --> 01:00:18,726
Yeah.

1377
01:00:20,916 --> 01:00:25,496
>> How do you get it to not
show the integer that you choose

1378
01:00:25,556 --> 01:00:27,936
to represent your blank
space in the array?

1379
01:00:28,126 --> 01:00:29,966
>> Okay, so the question
was how do we make sure

1380
01:00:29,966 --> 01:00:31,786
that we don't output the value

1381
01:00:32,206 --> 01:00:34,546
that that number we chose
represent the blank space

1382
01:00:34,546 --> 01:00:35,196
out on our grid.

1383
01:00:35,706 --> 01:00:37,276
So when we output
the grid we can't--

1384
01:00:37,496 --> 01:00:39,256
suddenly can't just
say printf board

1385
01:00:39,256 --> 01:00:41,806
and then it's gonna printf the
board with spacing and columns

1386
01:00:41,806 --> 01:00:42,646
and grid, stuff like that.

1387
01:00:43,036 --> 01:00:45,236
So when we print out the board
we actually need to iterate

1388
01:00:45,236 --> 01:00:46,796
through every space
of the board.

1389
01:00:47,406 --> 01:00:50,656
So we know what we chose as
our blank space representation.

1390
01:00:51,036 --> 01:00:54,296
So you can just say if it's our
blank space then we don't wanna

1391
01:00:54,326 --> 01:00:54,856
output that.

1392
01:00:54,856 --> 01:00:57,476
We probably don't wanna output
nothing 'cause that's gonna mess

1393
01:00:57,476 --> 01:01:00,506
up our grid but we definitely
don't wanna output that number.

1394
01:01:00,996 --> 01:01:02,956
So as long as that's defined
somewhere you can just check,

1395
01:01:03,326 --> 01:01:04,286
is it the blank space?

1396
01:01:04,286 --> 01:01:05,966
No, print the number
if it's not, okay,

1397
01:01:05,966 --> 01:01:11,006
I can print something else,
whatever you choose that to be.

1398
01:01:11,246 --> 01:01:11,906
Other questions?

1399
01:01:16,616 --> 01:01:18,796
Alright, so if there are no
final questions I'll be here

1400
01:01:18,796 --> 01:01:20,986
afterwards and good
luck on game Fifteen.