1 00:00:06,690 --> 00:00:11,001 So in this video I'm still working on the wish list for Sudoku and I'm at find 2 00:00:11,001 --> 00:00:14,407 blank. Let's see, what was it supposed to do? 3 00:00:14,407 --> 00:00:19,000 It consumes a board and it produces a pause, and it's supposed to produce the 4 00:00:19,000 --> 00:00:23,570 position of the first blank square. And it's allowed to assume the board has 5 00:00:23,570 --> 00:00:28,786 at least one blank square, so here we go. Let's do some examples. 6 00:00:28,786 --> 00:00:37,169 Let's see, check expect find blank. Now what was that board that's totally 7 00:00:37,169 --> 00:00:41,830 blank. Now that's board one. 8 00:00:41,830 --> 00:00:48,740 Board one is totally blank. Coming down here to find blank. 9 00:00:48,740 --> 00:00:56,989 So if I call find blank on board one Then the first blank position is zero, the 10 00:00:56,989 --> 00:01:03,062 position of the first cell. And let's see, check expect find blank. 11 00:01:03,062 --> 00:01:09,880 And if I say cons, I don't know, it doesn't matter really, two into rest of 12 00:01:09,880 --> 00:01:14,240 board one. So that's a board that only has it's 13 00:01:14,240 --> 00:01:21,300 upper left full. Then that's supposed to produce one. 14 00:01:21,300 --> 00:01:24,890 That's probably enough example, so I guess this is a list I should have two 15 00:01:24,890 --> 00:01:26,030 deep. Really should I? 16 00:01:27,310 --> 00:01:38,660 My guess, I don't know, let's try it. Check, expect find blank cons 2 cons 4 17 00:01:38,660 --> 00:01:43,332 rest rest of board 1. So that's a board that starts with a 2 18 00:01:43,332 --> 00:01:49,880 and a 4, then the whole rest is empty. Then in that case, the first blank is a 19 00:01:49,880 --> 00:01:55,760 position 2. That's my examples. 20 00:01:55,760 --> 00:02:00,130 So how are we going to template this. Define find blank. 21 00:02:00,130 --> 00:02:06,130 Well, it consumes a board and it seems like it kind has to work its way through 22 00:02:06,130 --> 00:02:08,840 a board. Yeah, so let's see. 23 00:02:08,840 --> 00:02:12,310 That template's according to board. And board, of course, is just a list of 24 00:02:12,310 --> 00:02:15,100 pos or val. So this is the list of template. 25 00:02:17,320 --> 00:02:29,877 Empty board, dot, dot, dot, then quickly remind myself what board is a list of. 26 00:02:34,630 --> 00:02:55,826 Board is a list of either val or false. So back down here, dot dot dot something 27 00:02:55,826 --> 00:03:02,410 First, a board. And this is going to be either bow or 28 00:03:02,410 --> 00:03:07,790 false. Rest of board. 29 00:03:07,790 --> 00:03:12,370 Let's see, rest of board is of course, the rest of the boards, so this is still 30 00:03:12,370 --> 00:03:20,293 under the list. So this is a natural recursion here, fine 31 00:03:20,293 --> 00:03:34,450 blank rest of board. And let's see. 32 00:03:34,450 --> 00:03:37,920 This case isn't supposed to happen. We've got an assumption that the board 33 00:03:37,920 --> 00:03:41,620 has at least one blank square. So we're never supposed to run out of 34 00:03:41,620 --> 00:03:47,994 board, before we find a blank. So this isn't suppose to happen. 35 00:03:47,994 --> 00:03:51,200 We can treat this a number of different ways. 36 00:03:51,200 --> 00:03:54,030 We can just return zero or something like that. 37 00:03:54,030 --> 00:03:56,590 I'll show you something that you haven't seen yet before in this course. 38 00:03:56,590 --> 00:04:01,200 It's not really a learning goal for this part of the course, but I'll just show it 39 00:04:01,200 --> 00:04:04,570 to you quickly. There is a thing called error that lets 40 00:04:04,570 --> 00:04:12,266 you say the board didn't have a blank space. 41 00:04:12,266 --> 00:04:18,170 And what that will do is, is it will cause an error, of the kind of error that 42 00:04:18,170 --> 00:04:23,620 you're used to seeing it's giving exactly that message, so you might want to do 43 00:04:23,620 --> 00:04:26,650 that in this case. Let's worry about the case we're really 44 00:04:26,650 --> 00:04:32,120 supposed to worry about. Let's see, now why is it that this board 45 00:04:32,120 --> 00:04:37,840 has the blank in it? Why does it have a blank at position 46 00:04:37,840 --> 00:04:39,720 zero? Well it has a blank at position zero, 47 00:04:39,720 --> 00:04:43,730 because the first element of the list is false. 48 00:04:43,730 --> 00:04:47,050 And in other cases we have to keep going. So let's see. 49 00:04:47,050 --> 00:04:57,320 If the first of the board is false, then that means the position we're at right 50 00:04:57,320 --> 00:05:05,432 now is a blank so let's produce 0. Otherwise we're going to do the natural 51 00:05:05,432 --> 00:05:08,970 recursion. Lets see that means we'll take the rest 52 00:05:08,970 --> 00:05:16,620 of the board and we'll go find a blank position relative to the rest of the 53 00:05:16,620 --> 00:05:17,980 board. And that's key. 54 00:05:17,980 --> 00:05:21,520 It's relative to the rest of the board. So because it's relative to the rest of 55 00:05:21,520 --> 00:05:30,610 the board, what we're going to do with that, is we're going to add one to it. 56 00:05:30,610 --> 00:05:35,520 And so that will find a value in the rest of the board. 57 00:05:35,520 --> 00:05:40,760 Let's try that. It's name was previously defined as, oh 58 00:05:40,760 --> 00:05:44,519 yeah, this is the usual I forget to comment out the stub problem. 59 00:05:44,519 --> 00:05:50,710 Let's run it. And let's see some tests are failing we 60 00:05:50,710 --> 00:05:53,890 need to see whether any of these are tests on find blank. 61 00:05:57,810 --> 00:06:04,990 And let's see that one isn't. It's these tests unsolved. 62 00:06:04,990 --> 00:06:07,270 You know what I'm going to do here at this point? 63 00:06:07,270 --> 00:06:09,410 These tests are going to keep failing for a while. 64 00:06:09,410 --> 00:06:12,170 Until the wish list is done. I've got them. 65 00:06:12,170 --> 00:06:15,332 I've validated them. They have a good, they're well formed. 66 00:06:15,332 --> 00:06:17,695 At this point I'm going to comment them out. 67 00:06:17,695 --> 00:06:21,560 And what I'll do is I'll put a little note here. 68 00:06:21,560 --> 00:06:23,820 Bang, bang, bang I'll put it on this line. 69 00:06:23,820 --> 00:06:27,450 Bang, bang, bang to remind me that they're still commented out. 70 00:06:27,450 --> 00:06:31,500 And now those tests will stop failing it will be easier for us to test other 71 00:06:31,500 --> 00:06:32,730 things. Let's run it again. 72 00:06:34,970 --> 00:06:38,100 Now, only one test is failing. And which one is that? 73 00:06:38,100 --> 00:06:43,560 Oh. It's next boards test. 74 00:06:43,560 --> 00:06:48,030 So find blank -- the three tests we have for find blank are working properly, and 75 00:06:48,030 --> 00:06:51,940 we never got to the air condition. That's why that line of code Is 76 00:06:51,940 --> 00:06:58,740 highlighted in black. So there we go, that's find-blank. 77 00:06:58,740 --> 00:07:00,750 Now I'm going to do filled with one to nine. 78 00:07:00,750 --> 00:07:05,930 Let's see, filled with one to nine consumes a position in a board. 79 00:07:05,930 --> 00:07:11,370 And it produces a list of boards. Oh, right, it has to produce nine boards. 80 00:07:11,370 --> 00:07:15,004 Where the blank is filled with one to nine. 81 00:07:15,004 --> 00:07:22,207 So for example, let's do an example. If we say check expect. 82 00:07:22,207 --> 00:07:31,256 Oh my goodness this is going to be long. Check expect fill with one to nine. 83 00:07:31,256 --> 00:07:40,476 It's even hard to type. Fill with 1 to 9, let's just say position 84 00:07:40,476 --> 00:07:47,090 0 and board 1. What are we going to get back, we'll 85 00:07:47,090 --> 00:07:57,710 we're going to get list cons 1 master board 1 cons 2 master board 1. 86 00:07:57,710 --> 00:08:00,340 And so on, right? All the way, there's going to be nine of 87 00:08:00,340 --> 00:08:05,050 them. Let's see 3, 4, 5, 6, 7, 8, 9. 88 00:08:05,050 --> 00:08:13,322 If you wanted to, rather than write that out, you could actually write the 89 00:08:13,322 --> 00:08:22,820 expected answer with buildless, or you can write it out if you find it more 90 00:08:22,820 --> 00:08:25,210 clear. Alright, let's make sure our test is 91 00:08:25,210 --> 00:08:25,360 well-formed. It is. 92 00:08:25,360 --> 00:08:32,231 Now form. Now let's see, how are we going to 93 00:08:32,231 --> 00:08:46,060 template this Well, we need to fill with one to nine and it's a board we need to 94 00:08:46,060 --> 00:08:49,960 fill. We have to produce nine results. 95 00:08:49,960 --> 00:08:52,510 And the nine results come from the one to nine. 96 00:08:54,190 --> 00:08:57,320 So we don't really want a template that's according to board because if we template 97 00:08:57,320 --> 00:09:00,630 it according to board that's going to get us to a certain position in the board and 98 00:09:00,630 --> 00:09:04,170 that'll be it. In fact there's a couple good ways to 99 00:09:04,170 --> 00:09:08,070 template this but one nice way to template it is with build list. 100 00:09:09,930 --> 00:09:14,800 So I'm going to template it that way. We need to fill the blank position with 101 00:09:14,800 --> 00:09:18,250 one and nine. We need to build nine boards. 102 00:09:18,250 --> 00:09:21,515 So we need to say, build list nine of something. 103 00:09:21,515 --> 00:09:30,770 'Cuz this build list is going to build us nine boards. 104 00:09:30,770 --> 00:09:35,094 Now let's see. We need to give build-list a function. 105 00:09:35,094 --> 00:09:41,550 Build-list is going to call this function nine times, with the numbers 0, 1, 2, 3, 106 00:09:41,550 --> 00:09:47,555 all the way up to 8. And that function needs to make a new 107 00:09:47,555 --> 00:09:53,080 board. It's based on this board, and at this 108 00:09:53,080 --> 00:09:57,330 position, it will put 1 plus the number build list gives it. 109 00:09:57,330 --> 00:10:01,190 So, because that function is going to access to both of these parameters of the 110 00:10:01,190 --> 00:10:05,970 enclosing function, it needs to be a closure, we need to define with a local. 111 00:10:07,780 --> 00:10:13,342 [SOUND] So this'll be called build one, and it's going to get a number from 0 112 00:10:13,342 --> 00:10:18,220 through 8 as its argument. Then what is it has to do? 113 00:10:18,220 --> 00:10:23,470 Well, it has to build a new board with 1 plus this number at position p. 114 00:10:23,470 --> 00:10:27,030 There is a function you might have forgotten it in all this time, but 115 00:10:27,030 --> 00:10:30,950 there's a function called fill-square that does exactly that. 116 00:10:30,950 --> 00:10:35,850 It consumes a board, a position and a value, and it produces a new board with 117 00:10:35,850 --> 00:10:39,340 that value at that position. So jumping back now [COUGH], to fill with 118 00:10:39,340 --> 00:10:47,750 one to nine and to build one in particular It's fill square, it consumes 119 00:10:47,750 --> 00:10:56,836 a board, which is that board, a position, which is that position and now n is 120 00:10:56,836 --> 00:11:04,074 going to be 0 through A. But in Sudoku, the values that we draw, 121 00:11:04,074 --> 00:11:11,100 people design Sudoku weren't computer scientists because they counted from 1 to 122 00:11:11,100 --> 00:11:16,440 9, rather than from 0 to 8, the way crazy computer scientists count. 123 00:11:16,440 --> 00:11:21,890 So this is going to be plus N and 1. As we're going to be called with numbers 124 00:11:21,890 --> 00:11:28,284 from 0 though 8, what we actually want to make boards that have values from 1 125 00:11:28,284 --> 00:11:35,090 though 9, so we just add 1. And let's see, that's what we want to 126 00:11:35,090 --> 00:11:36,650 call build list with. Let's try that. 127 00:11:36,650 --> 00:11:46,309 Oh, I keep forgetting to comment on the stubs today. 128 00:11:49,760 --> 00:11:53,000 One of the 11 tests failed. Hey, that's good because I think one was 129 00:11:53,000 --> 00:11:56,430 already failing, wasn't it? That's this test failed. 130 00:11:56,430 --> 00:12:01,546 That's not this one, great. Our test for fill with 1 to 9 is working. 131 00:12:01,546 --> 00:12:10,492 So our test for find blank, our test for fill with 1 to 9 is working, that only 132 00:12:10,492 --> 00:12:14,550 leaves Is keep only valid. If we do keep only valid I think next 133 00:12:14,550 --> 00:12:18,080 boards would work. I think right now if we do a search for 134 00:12:18,080 --> 00:12:24,300 bang, bang, bang, we don't need that, and we do a command U. 135 00:12:26,470 --> 00:12:31,740 Let's see. There's a bang, bang, bang there. 136 00:12:31,740 --> 00:12:36,140 Oh that's because in the end we need to uncomment those solve tests. 137 00:12:36,140 --> 00:12:40,810 And there's a bang, bang, bang, there. Hey, we're gettin close to the end of 138 00:12:40,810 --> 00:12:45,360 this thing. Unless of course, doing keep over valid 139 00:12:45,360 --> 00:12:47,420 causes us to make some more wishes. Okay. 140 00:12:47,420 --> 00:12:56,410 Let's work on keep over valid. It consumes list of board, and produces 141 00:12:56,410 --> 00:12:59,400 list of board. And it's supposed to produce a list 142 00:12:59,400 --> 00:13:03,402 containing only the valid boards. So let's see. 143 00:13:03,402 --> 00:13:05,914 Check. Expect. 144 00:13:05,914 --> 00:13:15,620 Keep only valid. See, this is a filtering function. 145 00:13:15,620 --> 00:13:18,800 Right, we're given a list of boards, some of which are valid, and some of which are 146 00:13:18,800 --> 00:13:22,120 not valid. You need to keep only the valid ones. 147 00:13:22,120 --> 00:13:25,240 That's a filtering function. So I know already that I'm going to 148 00:13:25,240 --> 00:13:28,874 template this to call filter. So I'm just going to have one test. 149 00:13:28,874 --> 00:13:36,060 I'll say list, and let's see, I'll make an invalid board. 150 00:13:36,060 --> 00:13:45,860 Cons 1, cons 2, rest, rest of board 1. So that's a board that has two, oop, not 151 00:13:45,860 --> 00:13:47,656 cons 1, cons 2. That's a valid board. 152 00:13:47,656 --> 00:13:54,080 Cons 1, cons 1. So that's a board that has two 1s right 153 00:13:54,080 --> 00:13:57,230 away in the first round. That one's a loser for sure. 154 00:13:57,230 --> 00:14:02,470 And we'll just have that as the only thing and the result of that is, of 155 00:14:02,470 --> 00:14:05,470 course, empty. We're told to keep only the valid boards. 156 00:14:05,470 --> 00:14:08,062 You only got a list with one invalid board. 157 00:14:08,062 --> 00:14:11,310 That's empty. Remember because I know I am calling 158 00:14:11,310 --> 00:14:17,560 filter, the task for keep-only-valid really needs to make sure did it pass an 159 00:14:17,560 --> 00:14:22,735 appropriate predicate to keep-only-valid. So I will quickly template 160 00:14:22,735 --> 00:14:34,835 keep-only-valid. [BLANK_AUDIO] that's filter something 161 00:14:34,835 --> 00:14:38,940 lobd. Let's see what's the something. 162 00:14:38,940 --> 00:14:44,662 Well the something has to be a predicate that consumes a board and produces true, 163 00:14:44,662 --> 00:14:48,495 if it should stay in the list It's gotta be some function. 164 00:14:48,495 --> 00:14:54,770 It doesn't have to be a closure because it doesn't have to see the LLBD argument, 165 00:14:56,010 --> 00:14:59,030 so I'll just wish for it as a new top level function. 166 00:15:03,960 --> 00:15:08,820 It'll be a predicate called valid board. And now let's do the wish list entry. 167 00:15:08,820 --> 00:15:13,110 Let's see this consumers a board and it produces a boolean. 168 00:15:13,110 --> 00:15:22,103 Produce true if board is valid, false otherwise... 169 00:15:22,103 --> 00:15:31,940 Valid means no unit contains a duplicate value. 170 00:15:31,940 --> 00:15:41,251 Let's see if I can say that a bit better. No unit on the board has the same value. 171 00:15:41,251 --> 00:15:48,231 Value twice. So now lets squeeze that into our rule. 172 00:15:48,231 --> 00:15:56,574 Produce true if no, unit on the board has the same value twice. 173 00:15:56,574 --> 00:16:02,080 False otherwise. There's an example of where working to 174 00:16:02,080 --> 00:16:07,100 collapse the purpose helps me start to figure out exactly what this function has 175 00:16:07,100 --> 00:16:11,010 to do. Bang, bang, bang. 176 00:16:11,010 --> 00:16:14,520 Oh let's get rid of this. And we'll get rid of this over here too. 177 00:16:14,520 --> 00:16:24,393 Define valid board? board. 178 00:16:24,393 --> 00:16:26,290 False. And now let's do some tests. 179 00:16:26,290 --> 00:16:40,190 Well, let's see. Board 1, which is all empty, is valid for 180 00:16:40,190 --> 00:16:47,320 sure. And all those boards At the top that 181 00:16:47,320 --> 00:16:55,532 actually work are valid. So all the way down through five. 182 00:16:55,532 --> 00:17:05,960 Now, right now I'm not generating tests based on any theory of how this functions 183 00:17:05,960 --> 00:17:09,270 going to work. I'm just generating tests because I have 184 00:17:09,270 --> 00:17:13,130 some examples lying around. And so I know all of those are valid so 185 00:17:13,130 --> 00:17:15,980 I'm going to to throw those at this. because this seems like a complicated 186 00:17:15,980 --> 00:17:19,490 function to me right now, I don't quite understand it, so I'm writing down some 187 00:17:19,490 --> 00:17:23,760 examples that I have. Let me also write down some examples that 188 00:17:23,760 --> 00:17:35,200 I know are troublesome. Let's go look at board 2, I think is a 189 00:17:35,200 --> 00:17:40,760 good one. Board 2 has this row in it. 190 00:17:42,980 --> 00:17:55,580 So, if we take board 2 and we replace the 1 at the beginning, what we've done there 191 00:17:55,580 --> 00:17:58,235 is, oops, I've missed a question mark in all of these. 192 00:17:58,235 --> 00:18:08,550 Is. What this does is it takes board 2 and it 193 00:18:08,550 --> 00:18:13,122 strips off the first value, the upper left cell, and now we're putting a 2 194 00:18:13,122 --> 00:18:14,480 there. Okay. 195 00:18:14,480 --> 00:18:19,400 I could do that with with fill square of course. 196 00:18:19,400 --> 00:18:21,030 It's just a bit simpler to do it this way. 197 00:18:21,030 --> 00:18:27,690 So that boards not valid because now it's gonan have two 2's. 198 00:18:27,690 --> 00:18:38,820 Let's do another eexample. [SOUND] Valid board question mark cons 2. 199 00:18:38,820 --> 00:18:44,820 You know, Board 3 is the one that just has that column down the left. 200 00:18:44,820 --> 00:18:48,650 Here's Board 3 and so now I've replaced the 1 in the upper left corner with a 2 201 00:18:48,650 --> 00:18:52,350 and of course that makes the board invalid 'cause it has two 2s in that 202 00:18:52,350 --> 00:18:54,580 column. There's two two's in the first column. 203 00:18:54,580 --> 00:19:01,479 There's also two twos in the first box. So that wasn't valid. 204 00:19:01,479 --> 00:19:06,200 And lets see if we can do another one. Check Expect val whoops. 205 00:19:06,200 --> 00:19:12,650 Valid board, board? Lets go look for another example up here. 206 00:19:12,650 --> 00:19:17,438 In our boards. See, what can we do with board 4? 207 00:19:17,438 --> 00:19:22,226 Board 4 is a bit more interesting, isn't it? 208 00:19:22,226 --> 00:19:30,190 If we change that 7 to a 6, then we'll have two 6's in the first the box, So 209 00:19:30,190 --> 00:19:33,270 that would be an invalid board. Let's try that. 210 00:19:33,270 --> 00:19:39,040 We'll take board four, and we need the second position, position one there to be 211 00:19:39,040 --> 00:19:48,320 a six. So now we will use fill square because 212 00:19:48,320 --> 00:19:55,870 it's a bit easier. Fill square board four position one is 213 00:19:55,870 --> 00:20:05,920 going to be a And that's gotta be false. Let's see if all of these are well 214 00:20:05,920 --> 00:20:08,359 formed. They are well formed, but they're, most 215 00:20:08,359 --> 00:20:09,198 of them are failing. The first one's failing I guess because 216 00:20:09,198 --> 00:20:19,990 the stub always produces, or the last one, one of these is. 217 00:20:19,990 --> 00:20:23,880 These three are passing because the stub always produces false. 218 00:20:23,880 --> 00:20:28,780 Those five are failing and we have an earlier test that's also failing. 219 00:20:28,780 --> 00:20:34,572 So let's see. Now how are we going to template this 220 00:20:34,572 --> 00:20:37,690 function? Now right here I'm going to stop this 221 00:20:37,690 --> 00:20:40,960 video and leave you to work on this one for a bit. 222 00:20:40,960 --> 00:20:44,850 It's a little bit complicated, but, I suggest you really work on it 223 00:20:44,850 --> 00:20:51,610 systematically and remember what the purpose statement says. 224 00:20:51,610 --> 00:20:57,970 We need to check all of the units and we have this constant called units. 225 00:20:59,550 --> 00:21:06,580 We need to check that for all of the units on the board, no unit has the same 226 00:21:06,580 --> 00:21:11,810 value twice. Paradoxically, this is actually the 227 00:21:11,810 --> 00:21:14,190 hardest function to write in this program. 228 00:21:15,290 --> 00:21:19,450 The solve function, which was the most interesting function Wasn't really the 229 00:21:19,450 --> 00:21:22,950 hardest function right and this function isn't that hard either if you just work 230 00:21:22,950 --> 00:21:28,170 systematically. There's lots of ways to do it, but I'll 231 00:21:28,170 --> 00:21:33,150 just let you know, that I have what I think is a pretty nice solution. 232 00:21:33,150 --> 00:21:42,052 It ends up using both n-map and map. So I'll stop this video here now.