1
00:00:00,000 --> 00:00:13,070

2
00:00:13,070 --> 00:00:13,715
>> ROB BOWDEN: Hi.

3
00:00:13,715 --> 00:00:17,800
I'm Rob, and I hope your
game for game of 15.

4
00:00:17,800 --> 00:00:22,040
Now, there are four functions you need
to implement in this program--init,

5
00:00:22,040 --> 00:00:24,650
draw, move, and won.

6
00:00:24,650 --> 00:00:27,230
So, let's look at init.

7
00:00:27,230 --> 00:00:32,930
>> Here, we see the first thing we're
going to do is declare a variable

8
00:00:32,930 --> 00:00:34,600
called counter.

9
00:00:34,600 --> 00:00:37,620
It's going to be initialized
to d times d minus 1.

10
00:00:37,620 --> 00:00:40,200
Remember that d is the dimension
of our board.

11
00:00:40,200 --> 00:00:43,840
How init is going to work is it's going
to iterate over the entire board

12
00:00:43,840 --> 00:00:46,050
and we're going to start
at the top left.

13
00:00:46,050 --> 00:00:48,570
>> And let's just say we
have a 4 by 4 board.

14
00:00:48,570 --> 00:00:51,220
So the top left we're
going to say is 15.

15
00:00:51,220 --> 00:00:53,960
And then we're just going to count
through the boards, saying 15, 14, 13,

16
00:00:53,960 --> 00:00:58,510
12, 11, 10, 9, 8, 7,
6, 5, 4, and so on.

17
00:00:58,510 --> 00:01:03,780
So the top left, we expect to be d times
d minus 1, which in the 4 by 4

18
00:01:03,780 --> 00:01:08,290
case is going to be 16 minus
1, which is correctly 15.

19
00:01:08,290 --> 00:01:10,885
>> And now here's where we're going to
iterate over the entire board.

20
00:01:10,885 --> 00:01:14,720
And we're going to set each position in
the board to the current value of

21
00:01:14,720 --> 00:01:19,090
our counter, and then counter is going
to decrement, so that the next

22
00:01:19,090 --> 00:01:22,300
position we reach is going to have
counter be one less than

23
00:01:22,300 --> 00:01:23,690
the previous position.

24
00:01:23,690 --> 00:01:26,970
So we initially had 15 and
decrement counter.

25
00:01:26,970 --> 00:01:30,065
So then we're going to assign 14 to the
next position, decrement counter,

26
00:01:30,065 --> 00:01:33,710
and we're going to assigned
13, and so on.

27
00:01:33,710 --> 00:01:37,620
>> Finally, we need to handle that corner
case where, if the board has an even

28
00:01:37,620 --> 00:01:44,450
dimension, then just doing 15, 14, 13,
12, all the way down to 3, 2, 1, is

29
00:01:44,450 --> 00:01:46,780
going to leave us with
an unsolvable board.

30
00:01:46,780 --> 00:01:49,390
And we have to swap the 1 and the 2.

31
00:01:49,390 --> 00:01:52,930
So, if d mod 2 equals 0, that's
how we're going to check

32
00:01:52,930 --> 00:01:54,410
to see if it's even.

33
00:01:54,410 --> 00:01:59,810
If d mod 2 equals 0, then in row d minus
1, which is the bottom row, and

34
00:01:59,810 --> 00:02:05,430
position d minus 2, or column d minus
2, we're going to set that to 2, and

35
00:02:05,430 --> 00:02:07,860
column d minus 3 we're
going to set to 1.

36
00:02:07,860 --> 00:02:12,170
So that's just reversing where
the 1 and 2 currently are.

37
00:02:12,170 --> 00:02:16,270
>> Finally, we're going to set the very
bottom right equal to blank, where

38
00:02:16,270 --> 00:02:20,700
blank has been hash defined
at the top as 0.

39
00:02:20,700 --> 00:02:26,785
So, that wasn't strictly necessary,
since this for loop is going to have

40
00:02:26,785 --> 00:02:30,610
set the bottom right to 0, since
counter will naturally reach 0.

41
00:02:30,610 --> 00:02:34,610
But that relies on us knowing that
blank was hashed to find a 0.

42
00:02:34,610 --> 00:02:38,280
If I go into this program and later
change blank at the top to 100, it

43
00:02:38,280 --> 00:02:39,770
should still work.

44
00:02:39,770 --> 00:02:43,180
>> So this is just making sure that the
bottom right is actually equal to our

45
00:02:43,180 --> 00:02:44,870
blank value.

46
00:02:44,870 --> 00:02:50,270
Finally, we have two global variables,
so blank i and blank j, and we see

47
00:02:50,270 --> 00:02:53,360
those declared at the top.

48
00:02:53,360 --> 00:02:56,270
And we're going to use those two global
variables to keep track of the

49
00:02:56,270 --> 00:02:59,040
position of the blank, so that we don't
need to look through the entire

50
00:02:59,040 --> 00:03:03,890
board to find the blank every single
time we try to make a move.

51
00:03:03,890 --> 00:03:08,450
So the position of the blank always is
going to start at the bottom right.

52
00:03:08,450 --> 00:03:13,270
So the bottom right is given by
indices d minus 1, d minus 1.

53
00:03:13,270 --> 00:03:14,880
So, that's init.

54
00:03:14,880 --> 00:03:17,040
>> Now we move on to draw.

55
00:03:17,040 --> 00:03:19,370
So, draw is going to be similar
where we're going to iterate

56
00:03:19,370 --> 00:03:20,970
over the entire board.

57
00:03:20,970 --> 00:03:25,400
And we just want to print the value
that's in each position of the board.

58
00:03:25,400 --> 00:03:29,580
So here, we're printing the value that's
in each position of the board.

59
00:03:29,580 --> 00:03:32,280
And notice that we're doing -.

60
00:03:32,280 --> 00:03:37,410
And that's just telling printf that
regardless of if it's a one digit or

61
00:03:37,410 --> 00:03:42,010
two digit number, we still want it to
take up two columns in the print out,

62
00:03:42,010 --> 00:03:46,290
so that if we have two digit and one
digit numbers in the same board, our

63
00:03:46,290 --> 00:03:49,450
board will still look nice and square.

64
00:03:49,450 --> 00:03:54,190
>> So we want to do that for every value
in the board, except for the blank.

65
00:03:54,190 --> 00:03:58,260
So, if the position in the board equals
the blank, then we specifically

66
00:03:58,260 --> 00:04:01,730
want to print out just an underscore
to represent the blank, instead of

67
00:04:01,730 --> 00:04:05,150
whatever the value of the
blank actually is.

68
00:04:05,150 --> 00:04:08,500
>> Finally, we want to print
out a new line.

69
00:04:08,500 --> 00:04:11,970
Notice that this is still inside
the outer for loop, but outside

70
00:04:11,970 --> 00:04:13,200
the inner for loop.

71
00:04:13,200 --> 00:04:17,930
Since this outer for loop is iterating
over all rows, and so this printf is

72
00:04:17,930 --> 00:04:22,130
going to just print a new line, so we
move on to print out the next row.

73
00:04:22,130 --> 00:04:23,910
And that's it for draw.

74
00:04:23,910 --> 00:04:27,770
>> So, now let's move on to move.

75
00:04:27,770 --> 00:04:32,590
Now, we pass move, the tile that the
user is entered in the game--they

76
00:04:32,590 --> 00:04:36,360
enter the tile they want to move--and
you're supposed to return a bool, so

77
00:04:36,360 --> 00:04:39,300
either true or false, depending on
whether that move was actually

78
00:04:39,300 --> 00:04:43,360
valid--whether that tile can be
moved into the blank space.

79
00:04:43,360 --> 00:04:48,340
>> So here, we declare a local variable,
tile_1 and tile_j, which are going to

80
00:04:48,340 --> 00:04:52,150
be similar to blank_i and blank_j,
except it's going to keep track of the

81
00:04:52,150 --> 00:04:54,910
position of the tile.

82
00:04:54,910 --> 00:05:00,370
Now here, we're going to use blank_i
and blank_j and say all right, so

83
00:05:00,370 --> 00:05:01,930
here's the blank on the board.

84
00:05:01,930 --> 00:05:04,420
>> Now, is the tile above the blank?

85
00:05:04,420 --> 00:05:06,210
Is the tile to the left of the blank?

86
00:05:06,210 --> 00:05:07,420
Is the tile to the right of the blank?

87
00:05:07,420 --> 00:05:08,970
Is the tile below the blank?

88
00:05:08,970 --> 00:05:13,330
So, if the tile is in any of those
positions, then we know that the tile

89
00:05:13,330 --> 00:05:16,390
can be moved into the blank spot and
the blank can be moved to where the

90
00:05:16,390 --> 00:05:18,240
tile currently is.

91
00:05:18,240 --> 00:05:26,400
>> So here, we say if board at position
blank_i minus 1 blank_j.

92
00:05:26,400 --> 00:05:31,120
So this is saying is the tile
above the current blank?

93
00:05:31,120 --> 00:05:34,350
And if so, we're going to remember
that is the position of the tile.

94
00:05:34,350 --> 00:05:37,870
The tile is in position blank_i
minus 1 and blank_j.

95
00:05:37,870 --> 00:05:40,660
now first, we also have this check
right here, so blank_i is

96
00:05:40,660 --> 00:05:41,760
greater than 0.

97
00:05:41,760 --> 00:05:43,410
>> Why do we want to do that?

98
00:05:43,410 --> 00:05:47,290
Well, if the blank is in the top row
of the board, then we don't want to

99
00:05:47,290 --> 00:05:51,240
look above the blank for the tile since
there is nothing above the top

100
00:05:51,240 --> 00:05:52,430
row of the board.

101
00:05:52,430 --> 00:05:55,950
This is how you might end up getting
something like a segmentation fault or

102
00:05:55,950 --> 00:05:59,030
your program might just work
in unexpected ways.

103
00:05:59,030 --> 00:06:04,310
So, this is making sure that we don't
look in places that aren't valid.

104
00:06:04,310 --> 00:06:08,470
>> Now we're going to do the same thing for
all other possible combinations.

105
00:06:08,470 --> 00:06:13,250
So here, we're looking below the blank
to see if that's the tile.

106
00:06:13,250 --> 00:06:16,950
And we also have to make sure we're
not on the bottom row, or else we

107
00:06:16,950 --> 00:06:18,910
shouldn't look for the tile.

108
00:06:18,910 --> 00:06:25,040
Here, we're going to look to the left of
the blank to see if it's the tile.

109
00:06:25,040 --> 00:06:27,860
And we shouldn't look to the left
if we're in the leftmost column.

110
00:06:27,860 --> 00:06:30,100
And here we're going to look to the
right of the blank, and we shouldn't

111
00:06:30,100 --> 00:06:33,340
look to the right if we're
in the rightmost column.

112
00:06:33,340 --> 00:06:37,820
>> So, if none of those things were true,
that means the tile was not adjacent

113
00:06:37,820 --> 00:06:39,640
to the blank and we can return false.

114
00:06:39,640 --> 00:06:41,230
The move was not valid.

115
00:06:41,230 --> 00:06:47,010
But, if one of those were true, then at
this point, we know that tile_i and

116
00:06:47,010 --> 00:06:50,540
tile_j are equal to the
position of the tile.

117
00:06:50,540 --> 00:06:55,210
And so, we can update the board at
positions tile_i and tile_j.

118
00:06:55,210 --> 00:06:59,820
We know the new value will be the blank
and that the position blank_i

119
00:06:59,820 --> 00:07:02,950
blank_j , which was the original
blank--we know the tile is going to

120
00:07:02,950 --> 00:07:04,030
move there.

121
00:07:04,030 --> 00:07:07,610
>> Notice we don't actually have to do a
real swap here, since we know the

122
00:07:07,610 --> 00:07:09,850
values that need to be inserted
into those positions.

123
00:07:09,850 --> 00:07:13,780
We don't need a temporary
variable around.

124
00:07:13,780 --> 00:07:16,920
>> Finally, we need to remember that we
have our global variables that are

125
00:07:16,920 --> 00:07:18,980
keeping track of the position
of the blank.

126
00:07:18,980 --> 00:07:22,780
So we want to update the position of
the blank to be where the tile

127
00:07:22,780 --> 00:07:24,190
originally was.

128
00:07:24,190 --> 00:07:27,680
Finally, we return true since
the move was successful.

129
00:07:27,680 --> 00:07:31,110
We successfully swap the
blank with the tile.

130
00:07:31,110 --> 00:07:34,890
>> All right, so last we
need to check won.

131
00:07:34,890 --> 00:07:39,900
So, won similarly returns a bool where
true is going to indicate that the

132
00:07:39,900 --> 00:07:41,460
user has won the game.

133
00:07:41,460 --> 00:07:43,780
And false is indicating that
the game is still going.

134
00:07:43,780 --> 00:07:46,340
The user has not won.

135
00:07:46,340 --> 00:07:52,100
So, this is going to be pretty much
the opposite of init, where init,

136
00:07:52,100 --> 00:07:56,920
remember, we initialize the board
to 15, 14, 13, 12, so on.

137
00:07:56,920 --> 00:08:03,000
Whereas won, we want to check if the
board is 1, 2, 3, 4, 5, and so on.

138
00:08:03,000 --> 00:08:06,600
>> So, we're going to initialize our
counter to 1 since that's what the top

139
00:08:06,600 --> 00:08:08,400
left of the board should be.

140
00:08:08,400 --> 00:08:10,860
And then we're going to loop
over the entire board.

141
00:08:10,860 --> 00:08:13,690
Let's ignore this condition
for a second.

142
00:08:13,690 --> 00:08:18,410
And this condition is just going to
check is the board at this position

143
00:08:18,410 --> 00:08:20,790
equal to the current counts?

144
00:08:20,790 --> 00:08:27,040
If so, increment the count so that the
next position we look at is one higher

145
00:08:27,040 --> 00:08:29,690
than the position we are at right now.

146
00:08:29,690 --> 00:08:32,700
>> So that's how we get the
top left should be 1.

147
00:08:32,700 --> 00:08:33,950
Increment the count to 2.

148
00:08:33,950 --> 00:08:35,010
Look at the next position.

149
00:08:35,010 --> 00:08:35,690
Is this 2?

150
00:08:35,690 --> 00:08:37,659
If so, increment the count to 3.

151
00:08:37,659 --> 00:08:39,179
Next position, is this 3?

152
00:08:39,179 --> 00:08:42,440
If so, increment the count
to 4, and so on.

153
00:08:42,440 --> 00:08:49,190
So, if there is any position on the
board that does not equal our count,

154
00:08:49,190 --> 00:08:52,640
then we want to return false since that
means there's some tile that is

155
00:08:52,640 --> 00:08:55,490
not in the correct position.

156
00:08:55,490 --> 00:08:58,810
>> So here, what is this condition doing?

157
00:08:58,810 --> 00:09:02,170
Well, remember that the blank is
supposed to go on the bottom right.

158
00:09:02,170 --> 00:09:06,180
And the blank's value might not
necessarily equal the value of the

159
00:09:06,180 --> 00:09:11,080
counter that is going to be reached
at the bottom right.

160
00:09:11,080 --> 00:09:15,760
So we specifically want to check if i
equals equals d minus 1 and j equals

161
00:09:15,760 --> 00:09:19,470
equals d minus 1--which is saying if we
are looking at the bottom right of

162
00:09:19,470 --> 00:09:22,050
the board--then we just
want to continue.

163
00:09:22,050 --> 00:09:26,200
We want to skip this particular
iteration of the for loop.

164
00:09:26,200 --> 00:09:31,250
>> And so, if we manage to get through this
nested for loop, that means that

165
00:09:31,250 --> 00:09:34,690
there was no tile that was in
the incorrect position.

166
00:09:34,690 --> 00:09:38,900
And we break out of the loop and come
here, where we can return true.

167
00:09:38,900 --> 00:09:41,800
All tiles were in the correct positions
and that means the user has

168
00:09:41,800 --> 00:09:43,230
won the game.

169
00:09:43,230 --> 00:09:44,460
And that's it.

170
00:09:44,460 --> 00:09:46,550
My name is Rob Bowden, and this was 15.

171
00:09:46,550 --> 00:09:52,726