0:00:00.000,0:00:11.000 0:00:11.000,0:00:14.000 This presentation is delivered by the Stanford Center for Professional Development. 0:00:23.000,0:00:27.000 Today I'm gonna keep talking a little bit more about another procedural [br]recursion example and 0:00:27.000,0:00:31.000 then go on to talk about, kind of, [br]the approach for recursive backtracking, 0:00:31.000,0:00:36.000 which is taking those procedural recursion examples and kind of twisting them around and doing new things with them. Okay. 0:00:36.000,0:00:39.000 This is the last problem I did at the end of 0:00:39.000,0:00:42.000 Wednesday's lecture. It's a very, very important problem, so I don't actually 0:00:42.000,0:00:46.000 want to move away from it until I feel that I'm getting some signs from you 0:00:46.000,0:00:47.000 guys that we're 0:00:47.000,0:00:49.000 0:00:49.000,0:00:51.000 getting some understanding of this because it turns out it forms the basis of a lot of 0:00:51.000,0:00:55.000 other solutions end up just becoming permutations, you know, at the core of it. 0:00:55.000,0:00:56.000 So it's 0:00:56.000,0:01:01.000 a pretty useful pattern to have [inaudible] 0:01:01.000,0:01:05.000 list the permutations of a string. So you've got the string, you know, A B C D, and it's 0:01:05.000,0:01:07.000 gonna print all the A C D A B C D 0:01:07.000,0:01:12.000 A variations that you can get by rearranging all the letters. 0:01:12.000,0:01:15.000 It's a deceptively short piece of 0:01:15.000,0:01:17.000 code that does what's being done here 0:01:17.000,0:01:20.000 -is that it breaks it down in terms of there being the permutation that's 0:01:20.000,0:01:24.000 assembled so far, and then the remaining characters that haven't yet been looked 0:01:24.000,0:01:25.000 at, and so 0:01:25.000,0:01:27.000 at each recursive call it's gonna 0:01:27.000,0:01:30.000 shuffle one character from the 0:01:30.000,0:01:33.000 remainder onto the thing that's been chosen so far. So chose the next 0:01:33.000,0:01:37.000 character in the permutation, and eventually, when the rest is empty, 0:01:37.000,0:01:41.000 then all of the characters have been moved over, and have been laid down in 0:01:41.000,0:01:44.000 permutation, then what I have is a full permutation of the length end. 0:01:44.000,0:01:48.000 In the case where rest is not empty, I've still got some choices to make. The number of 0:01:48.000,0:01:52.000 choices is exactly equal to the number of characters I have left in 0:01:52.000,0:01:53.000 rest, 0:01:53.000,0:01:55.000 and for each of the remaining characters at this point, maybe there's just C 0:01:55.000,0:01:56.000 and D left, 0:01:56.000,0:01:58.000 then I'm gonna try each of them 0:01:58.000,0:02:03.000 as the next character in the permutation, and then permute what remains after 0:02:03.000,0:02:04.000 having made that choice. 0:02:04.000,0:02:05.000 And so this is 0:02:05.000,0:02:07.000 [inaudible] operations here of 0:02:07.000,0:02:09.000 attaching that [inaudible] 0:02:09.000,0:02:13.000 into the existing so far, and then subtracting it 0:02:13.000,0:02:14.000 out of the rest 0:02:14.000,0:02:18.000 to set up the arguments for that recursive call. A 0:02:18.000,0:02:21.000 little bit at the end we talked about this idea of a wrapper function where 0:02:21.000,0:02:24.000 the interface to list permutations from a client point of view probably just wants to 0:02:24.000,0:02:26.000 be, here's a string to permute 0:02:26.000,0:02:27.000 the fact that [inaudible] 0:02:27.000,0:02:31.000 keep this housekeeping of what I've built so far is really any internal management 0:02:31.000,0:02:34.000 issue, and isn't what I want to expose as part of the interface, 0:02:34.000,0:02:37.000 so we in turn have just a really simple one line translation that the outer 0:02:37.000,0:02:40.000 call just sets up and makes the call to the real recursive function setting up 0:02:40.000,0:02:44.000 the right state for the housekeeping in this case, which is the 0:02:44.000,0:02:47.000 permutation we've assembled at this point. 0:02:47.000,0:02:50.000 So 0:02:50.000,0:02:53.000 I'd like to ask you a few questions about this 0:02:53.000,0:02:56.000 to see if we're kind of seeing the same things. Can 0:02:56.000,0:03:00.000 someone tell me what is the first permutation that's printed by this 0:03:00.000,0:03:14.000 if I put in the string A B C D? 0:03:14.000,0:03:17.000 Anyone want to help me? 0:03:17.000,0:03:21.000 A B C D. A B C D. So the exact string I gave it, right, is the one that it picks, right, 0:03:21.000,0:03:23.000 the very first time, and that's because, 0:03:23.000,0:03:26.000 if you look at the way the for loop is structured, the idea is that it's gonna make a 0:03:26.000,0:03:29.000 choice and it's gonna move through the recursion. Well, the choice it always makes is to take 0:03:29.000,0:03:32.000 the next character of rest and attach it to the permutation 0:03:32.000,0:03:36.000 as its first time through the for loop. So the first time through the very first 0:03:36.000,0:03:38.000 for loop it's got A B C D to chose, it chooses A, 0:03:38.000,0:03:43.000 and now it recurs on A in the permutation and B C D to go. Well, the 0:03:43.000,0:03:46.000 next call does exactly the same thing, chooses the first of what remains, which 0:03:46.000,0:03:49.000 is B, attaches it to the permutation and keeps going. 0:03:49.000,0:03:50.000 So the kind of 0:03:50.000,0:03:53.000 deep arm of the recursion making that first choice and working its way down to 0:03:53.000,0:03:57.000 the base case, right, right remember the recursion always goes deep. It goes down to the end of 0:03:57.000,0:03:57.000 the 0:03:57.000,0:04:01.000 -and bottoms on the recursion before it comes back and revisits any previous 0:04:01.000,0:04:03.000 decision, will go A B C D, 0:04:03.000,0:04:04.000 and then 0:04:04.000,0:04:08.000 eventually come back and start trying other things, but that very first one, 0:04:08.000,0:04:11.000 right, is all just the sequence there. 0:04:11.000,0:04:13.000 The next one that's after it, right, 0:04:13.000,0:04:14.000 is A B D C, 0:04:14.000,0:04:17.000 which involved unmaking those last couple decisions. 0:04:17.000,0:04:19.000 If I look at 0:04:19.000,0:04:22.000 the tree that I have here that may help to sort of identify it. 0:04:22.000,0:04:24.000 That permute of emptying A B C, 0:04:24.000,0:04:27.000 the first choice it makes is go with A, and then the 0:04:27.000,0:04:30.000 first choice it makes here is go with B, and so on, so that the first thing that we can see 0:04:30.000,0:04:34.000 printed our here will be A B C D, we get to the base case. 0:04:34.000,0:04:36.000 Once it's tried this, it'll come back to this one, and on this 0:04:36.000,0:04:39.000 one it'll say, well, try the other characters. Well, there's no other 0:04:39.000,0:04:41.000 characters. In fact, this one also finishes. 0:04:41.000,0:04:46.000 It'll get back to here as it unwinds the stack the way the stack 0:04:46.000,0:04:49.000 gets back to where it was previously in these recursive calls. And now it says, okay, 0:04:49.000,0:04:51.000 and now try the ones that have, 0:04:51.000,0:04:54.000 on the second iteration of that for loop, D in the front, 0:04:54.000,0:04:56.000 and so it ends up putting A B D together, 0:04:56.000,0:04:58.000 leaving C, and then getting A B D C. And 0:04:58.000,0:05:02.000 then, so on kind of over here, the other variations, it will print all of the ones that have A 0:05:02.000,0:05:03.000 in the front. 0:05:03.000,0:05:06.000 There are eight of them. 0:05:06.000,0:05:07.000 I believe three, two 0:05:07.000,0:05:10.000 -no, six. Six of them 0:05:10.000,0:05:14.000 that have A in the front, and we'll do all of those. And only after having done all of 0:05:14.000,0:05:18.000 working out that whole part, which involves kind of the [inaudible] of this whole arm, 0:05:18.000,0:05:21.000 will eventually unwind back to the initial permute call, 0:05:21.000,0:05:22.000 0:05:22.000,0:05:26.000 and then say, okay, now try again. Go with B in the front and work your way 0:05:26.000,0:05:28.000 down from reading the A C D behind it. 0:05:28.000,0:05:30.000 So we'll see all the As 0:05:30.000,0:05:33.000 then the bunch that lead with B, then the bunch that leads with C, and then finally the 0:05:33.000,0:05:36.000 bunch that leads with D. 0:05:36.000,0:05:39.000 It doesn't turn out -matter, actually, what order it visits them in because, in fact, all we 0:05:39.000,0:05:42.000 cared about was seeing all of them. But part of what I'm trying to get with you 0:05:42.000,0:05:44.000 is the sense of being 0:05:44.000,0:05:46.000 able to look at that recursive code, 0:05:46.000,0:05:50.000 and use your mind to kind of trace its activity and think about the 0:05:50.000,0:05:54.000 progress that is made through those recursive calls. Just 0:05:54.000,0:05:57.000 let me look at that code just for a second more and see if there's any else that I want to 0:05:57.000,0:05:59.000 highlight for you. 0:05:59.000,0:06:05.000 0:06:05.000,0:06:08.000 I think that's about what 0:06:08.000,0:06:08.000 it's gonna do. 0:06:08.000,0:06:11.000 So if you don't understand this cost, if there's something about it that confuses you, now 0:06:11.000,0:06:15.000 would be an excellent time for you to ask a question that I could help 0:06:15.000,0:06:17.000 kind of get your understanding 0:06:17.000,0:06:19.000 made more clear. So 0:06:19.000,0:06:24.000 when you look at this code, you feel like you believe it works? You understand it? [Inaudible]. I have a question. 0:06:24.000,0:06:29.000 Is there a simple change you can make to this 0:06:29.000,0:06:29.000 code 0:06:29.000,0:06:32.000 so that it does combinations [inaudible]? 0:06:32.000,0:06:36.000 Does combinations -you mean, like, will skip letters? 0:06:36.000,0:06:42.000 Right. Yes. It turns out we're gonna make that change in not five minutes. 0:06:42.000,0:06:45.000 In effect, what you would do -and there's a pretty simple change with 0:06:45.000,0:06:47.000 this form. I'm gonna show you a slightly different way of doing it, 0:06:47.000,0:06:48.000 but one way of doing it would be to say, 0:06:48.000,0:06:52.000 well, give me the letter, don't attach it to next right? So right now, the 0:06:52.000,0:06:56.000 choices are pick one of the letters that remain and then attach it to 0:06:56.000,0:07:00.000 the permutation. Another option you could do was pick a letter and just discard it, 0:07:00.000,0:07:03.000 right? And so, in which case, I wouldn't add it into so far. 0:07:03.000,0:07:06.000 I would still subtract it from here, and I'd make another recursive call 0:07:06.000,0:07:07.000 saying, now 0:07:07.000,0:07:10.000 how about the permutations that don't involve A at all? And 0:07:10.000,0:07:14.000 I would just drop it from the thing and I would recurs on just the B C D part. So 0:07:14.000,0:07:17.000 a pretty simple change right here. I'm gonna show you there's a slightly different way to 0:07:17.000,0:07:21.000 formulate the same thing in a little bit, but 0:07:21.000,0:07:27.000 -anybody want to own up to having something that confuses them? [Inaudible] ask how you, like, 0:07:27.000,0:07:29.000 what you would set up to test it? 0:07:29.000,0:07:30.000 So [inaudible] one of 0:07:30.000,0:07:33.000 the, you know, the easiest thing to do here, and I have the code kind of actually sitting over 0:07:33.000,0:07:35.000 here just in case, right, 0:07:35.000,0:07:38.000 hoping you would 0:07:38.000,0:07:41.000 ask because right now I just have the most barebones sort of testing. It's like, yeah, what if I just, 0:07:41.000,0:07:44.000 you know, throw some strings at it and see what happens, right? 0:07:44.000,0:07:45.000 And so 0:07:45.000,0:07:49.000 the easiest strings to throw at it would be things like, well what happens if I give it the empty 0:07:49.000,0:07:49.000 string, 0:07:49.000,0:07:52.000 right? You know, so it takes some really simple cases to start because you want to see, well what happens 0:07:52.000,0:07:55.000 when, you know, you give it an empty input. Is it gonna blow up? And it's, like, the empty input, 0:07:55.000,0:07:58.000 right, immediately realizes there's no choices and it says, well, look, there's nothing to 0:07:58.000,0:08:00.000 print other than that empty string. 0:08:00.000,0:08:02.000 What if I give it a single character string? 0:08:02.000,0:08:04.000 Right? I get that string back. I'm like, 0:08:04.000,0:08:07.000 okay, gives me a little bit of inspiration that it made one recursive call, right, and then hit 0:08:07.000,0:08:09.000 the base case on the subsequent one. 0:08:09.000,0:08:12.000 Now I start doing better ones. A and B, 0:08:12.000,0:08:16.000 and I'm seeing A B B A. Okay, so I feel like, you know, I got this, so if I put a C in 0:08:16.000,0:08:17.000 the front, 0:08:17.000,0:08:20.000 and I put the B A behind, 0:08:20.000,0:08:21.000 then hopefully what I believe is that 0:08:21.000,0:08:24.000 it's gonna try, you know, C in the front, and then it's gonna permute A and B 0:08:24.000,0:08:27.000 behind it, and then similarly on down. 0:08:27.000,0:08:30.000 So some simple cases that I can see 0:08:30.000,0:08:34.000 verifying that it does produce, kind of, the input string as itself, and then it does the 0:08:34.000,0:08:37.000 back end rearrangement, leaving this in the front, and then it makes the next choice for what can 0:08:37.000,0:08:40.000 go in the front, and then the back end rearrangement. And kind of seeing the 0:08:40.000,0:08:44.000 pattern that matches my belief about how the code works, right, 0:08:44.000,0:08:45.000 helps me to feel good. What happens if I 0:08:45.000,0:08:48.000 put in 0:08:48.000,0:08:50.000 something that has double letters in it? 0:08:50.000,0:08:53.000 So I put A P P L E in there. 0:08:53.000,0:08:56.000 And all the way back at the beginning, right, I can 0:08:56.000,0:08:58.000 plot more of them, right, that grows quite 0:08:58.000,0:09:02.000 quickly right as we add more and more letters, right? Seeing the apple, appel, 0:09:02.000,0:09:02.000 and stuff like that. 0:09:02.000,0:09:05.000 There's a point where it starts picking the P to go in the front, 0:09:05.000,0:09:10.000 and the code as it's written, right, doesn't actually make it a combination for this P 0:09:10.000,0:09:11.000 and this P really being different. 0:09:11.000,0:09:13.000 So it goes through a whole sequence of 0:09:13.000,0:09:17.000 pull the second character to the front, and then permute the remaining four. 0:09:17.000,0:09:20.000 And then it says, and now pull the third character to the front and permute 0:09:20.000,0:09:22.000 the remaining four, which turns out to be exactly the same thing. So there should be 0:09:22.000,0:09:25.000 this whole sequence in the middle, right, 0:09:25.000,0:09:27.000 of the same Ps 0:09:27.000,0:09:29.000 repeated twice 0:09:29.000,0:09:31.000 because we haven't gone over a way to do anything about that, right? 0:09:31.000,0:09:33.000 So 0:09:33.000,0:09:36.000 -but it is reassuring to know that it did somehow didn't get, you know, confused by the idea of 0:09:36.000,0:09:38.000 there being two double letters. [Inaudible] if I do this -if I just say A 0:09:38.000,0:09:41.000 B A, right? 0:09:41.000,0:09:44.000 Something a little bit smaller to look at, right? 0:09:44.000,0:09:47.000 A in the front. A in the front goes permuted, B in the front, and then it ends up permuting 0:09:47.000,0:09:50.000 these two ways that ends up being exactly the same, and then I get a duplicate of those in 0:09:50.000,0:09:51.000 the front. 0:09:51.000,0:09:53.000 So right now, it doesn't know that there's anything to worry about in terms 0:09:53.000,0:09:55.000 of duplicates? 0:09:55.000,0:09:57.000 What's a really easy way to get rid of duplicates? 0:09:57.000,0:09:59.000 Don't think recursively, think -use a set. 0:09:59.000,0:10:01.000 Right? I could just stuff them in a set, right? 0:10:01.000,0:10:04.000 And then if it comes across the same one again it's like, yeah, 0:10:04.000,0:10:07.000 whatever. So it would still do the extra work of finding those down, 0:10:07.000,0:10:11.000 but would actually, like, I could print the set at the end having coalesced any of the duplicates. 0:10:11.000,0:10:13.000 To 0:10:13.000,0:10:15.000 actually change it in the code, 0:10:15.000,0:10:18.000 it's actually not that hard either. 0:10:18.000,0:10:19.000 The idea here is that 0:10:19.000,0:10:21.000 for all of the characters that remain, right, 0:10:21.000,0:10:25.000 and sometimes what I want to choose from is of the remaining characters 0:10:25.000,0:10:25.000 uniqued, 0:10:25.000,0:10:27.000 right? Pick one to move to the front. 0:10:27.000,0:10:29.000 So if there's three more Ps 0:10:29.000,0:10:31.000 that remain in rest, 0:10:31.000,0:10:34.000 I don't need to try each of those Ps individually in the front, right? They'll produce 0:10:34.000,0:10:37.000 the same result -pulling one and leaving the other two behind 0:10:37.000,0:10:39.000 is completely irrelevant. 0:10:39.000,0:10:42.000 So an easy way to actually stop it from even generating them, 0:10:42.000,0:10:46.000 is when looking at the character here is to make sure that it is -that it 0:10:46.000,0:10:50.000 doesn't duplicate anything else in the rest. And so 0:10:50.000,0:10:53.000 probably the easiest way to do that is to either pick the first of the Ps or the last 0:10:53.000,0:10:57.000 of the Ps, right, and to recur on and ignore the other ones. 0:10:57.000,0:11:00.000 So, for example, if right here I did a find on the rest 0:11:00.000,0:11:02.000 after I -do you see any more of these? 0:11:02.000,0:11:04.000 And if you do, 0:11:04.000,0:11:07.000 then skip it and just let those go. Or, you know, 0:11:07.000,0:11:10.000 do the first. Don't do the remaining ones. You can either look to the left of look to the 0:11:10.000,0:11:13.000 right and see if you see any more, and if so, 0:11:13.000,0:11:14.000 skip the, 0:11:14.000,0:11:19.000 you know, early or later ones depending on what your strategy is. 0:11:19.000,0:11:25.000 Any questions about permute here? [Inaudible]. 0:11:25.000,0:11:27.000 So the [inaudible] can be just -look down here, right, it just looks like that, right? 0:11:27.000,0:11:31.000 This is a very common thing. You'll see this again, and again, and it tends to be that the 0:11:31.000,0:11:33.000 outer call, right, it tends to have this sort of 0:11:33.000,0:11:34.000 this, you know, solve this problem, 0:11:34.000,0:11:37.000 and then it turns out during the recursive calls you need to maintain some state 0:11:37.000,0:11:40.000 about where you are in the problem. You know, like, how many letters you moved, or 0:11:40.000,0:11:44.000 what permutation you've built so far, or where you are in the maze, or whatever it is you're 0:11:44.000,0:11:45.000 trying to solve. 0:11:45.000,0:11:49.000 And so typically that wrapper call is just gonna be setting up the initial call in a 0:11:49.000,0:11:52.000 way that has the initial form of that state 0:11:52.000,0:11:52.000 present 0:11:52.000,0:11:56.000 that the client to the function didn't need to know about. It's just our own housekeeping that we're 0:11:56.000,0:11:58.000 setting up. 0:11:58.000,0:12:01.000 Seems almost kind of silly to write down the function that has just line that just turns it 0:12:01.000,0:12:04.000 into, basically, it's just exchanging 0:12:04.000,0:12:06.000 -setting up the 0:12:06.000,0:12:11.000 other parameters. 0:12:11.000,0:12:13.000 I 0:12:13.000,0:12:17.000 am going to show you the other kind of master patter, and 0:12:17.000,0:12:20.000 then we're gonna go on to kind of use them to solve other problems. 0:12:20.000,0:12:24.000 This is the one that was already alluded to, this idea of a combinations. Instead 0:12:24.000,0:12:26.000 of actually producing all of the four character strings that involve 0:12:26.000,0:12:28.000 rearrangements of A B C D, 0:12:28.000,0:12:32.000 what if I were to [inaudible] in kind of the subgroups, or the way I could chose certain 0:12:32.000,0:12:34.000 characters out of that 0:12:34.000,0:12:35.000 initial input, and 0:12:35.000,0:12:39.000 potentially exclude some, potentially include some? So if I have A B C, 0:12:39.000,0:12:41.000 then the subsets of the subgroups of that 0:12:41.000,0:12:45.000 would be the single characters A B and C. The empty string A B and C itself the 0:12:45.000,0:12:50.000 full one, and then the combinations of two, A B, A C, and B C. 0:12:50.000,0:12:53.000 Now, in this case we're gonna say that order doesn't matter. We're not -whereas permutations was all 0:12:53.000,0:12:54.000 about order, I'm 0:12:54.000,0:12:57.000 gonna use -I'm gonna structure this one where I don't care. If it's A B or 0:12:57.000,0:12:59.000 B A I'm gonna consider it the same subset. 0:12:59.000,0:13:05.000 So I'm just interested in inclusion. Is A in or out? Is B in or out? Is C in or out? 0:13:05.000,0:13:09.000 And so the recursive strategy we're gonna take is exactly what I have just 0:13:09.000,0:13:12.000 kind of alluded to in my English description there, 0:13:12.000,0:13:15.000 is that I've got an input, A B C. 0:13:15.000,0:13:18.000 Each of those elements has either the opportunity of being in the subset or 0:13:18.000,0:13:19.000 not. 0:13:19.000,0:13:21.000 And I need to make that decision for everyone 0:13:21.000,0:13:25.000 -every single element, and then I need to kind of explore all the possible 0:13:25.000,0:13:26.000 combinations of that, right? 0:13:26.000,0:13:29.000 When A is in, what if B is out? When A is in, what if B is in? 0:13:29.000,0:13:32.000 So the recursion that I'm gonna use here 0:13:32.000,0:13:35.000 is that at each step of the way, I'm gonna separate one element from the 0:13:35.000,0:13:36.000 input, 0:13:36.000,0:13:39.000 and probably the easiest way to do that is just to kind of take the front 0:13:39.000,0:13:40.000 most element off the input 0:13:40.000,0:13:42.000 and sort of 0:13:42.000,0:13:45.000 separate it into this character by itself and then the remainder. Similarly, the way 0:13:45.000,0:13:46.000 I did with permute, 0:13:46.000,0:13:49.000 and then given that element I have 0:13:49.000,0:13:51.000 earmarked here, I can 0:13:51.000,0:13:54.000 try putting it in the current subset or not. I need to try both, so I'm gonna make 0:13:54.000,0:13:56.000 two recursive calls here, 0:13:56.000,0:13:58.000 one recursive call where I've added it in, 0:13:58.000,0:14:02.000 one recursive call where I haven't added it in. In both cases, right, I will have 0:14:02.000,0:14:04.000 removed it from the rest, 0:14:04.000,0:14:08.000 so what's being chosen from to complete that subset 0:14:08.000,0:14:10.000 always is a little bit smaller, a little bit easier. 0:14:10.000,0:14:14.000 So this is very, very much like the problem I described as the chose 0:14:14.000,0:14:18.000 problem. Trying to choose four people from a dorm to go to flicks was 0:14:18.000,0:14:19.000 picking Bob 0:14:19.000,0:14:21.000 and then -[inaudible] to Bob and not Bob, and then 0:14:21.000,0:14:25.000 saying, well, Bob could go, in which I need to pick three people to go with him, 0:14:25.000,0:14:29.000 or Bob could not go and I need to pick four people to go without Bob. 0:14:29.000,0:14:34.000 This is very much that same pattern. Two recursive calls. Identify one in or out. 0:14:34.000,0:14:36.000 The base case becomes when there's nothing left 0:14:36.000,0:14:39.000 to check out. 0:14:39.000,0:14:41.000 So I start with the input A B C -A 0:14:41.000,0:14:42.000 B C D let's say. 0:14:42.000,0:14:45.000 I look at that first element -I just need to pick one. Might as well pick the front one, it's the 0:14:45.000,0:14:47.000 easy one to get to. 0:14:47.000,0:14:48.000 I add it to the subset, 0:14:48.000,0:14:52.000 remove it from the input, and make a recursive call. 0:14:52.000,0:14:54.000 When that recursion completely terminates, 0:14:54.000,0:14:56.000 I get back to this call, 0:14:56.000,0:14:58.000 and I do the same thing again. 0:14:58.000,0:15:02.000 Remaining input is B C D again but now the subset that I've been building doesn't 0:15:02.000,0:15:03.000 include. 0:15:03.000,0:15:05.000 So inclusion exclusion 0:15:05.000,0:15:13.000 are the two things that I'm trying. So the 0:15:13.000,0:15:16.000 subset problem, right, very similar in structure to the way that I set 0:15:16.000,0:15:20.000 up permutations, right, as I'm gonna keep track of two strings as I'm working my way 0:15:20.000,0:15:20.000 down 0:15:20.000,0:15:24.000 the remainder in the rest, right, things that I haven't yet explored 0:15:24.000,0:15:28.000 so far is what characters I've chosen to place into the subset that I'm building. 0:15:28.000,0:15:32.000 If I get to the end where there's nothing left in the rest, so there's no 0:15:32.000,0:15:33.000 more choices to make, 0:15:33.000,0:15:37.000 then what I have in the subset is what I have in the subset, and I go ahead and print it. 0:15:37.000,0:15:38.000 In the case that there's still something to look at 0:15:38.000,0:15:41.000 I make these two calls, 0:15:41.000,0:15:44.000 one where I've appended it in, where I haven't, and then both cases, right, where I 0:15:44.000,0:15:47.000 have subtracted it off of the 0:15:47.000,0:15:49.000 rest by using the subster to 0:15:49.000,0:15:55.000 truncate that front character off. 0:15:55.000,0:15:56.000 So the way that 0:15:56.000,0:15:57.000 permute was making calls, right, was in a loop, 0:15:57.000,0:16:00.000 and so sometimes it's a little bit misleading. You look at it and you think there's 0:16:00.000,0:16:03.000 only one recursive call, but in fact it's in inside a loop, and so it's making, 0:16:03.000,0:16:06.000 potentially, end recursive calls where end is the length of 0:16:06.000,0:16:08.000 the input. 0:16:08.000,0:16:10.000 It gets a little bit shorter each time through but there's always, you know, however many 0:16:10.000,0:16:13.000 characters are in rest is how many recursive calls it makes. 0:16:13.000,0:16:17.000 The subsets code actually makes exactly two recursive calls at any given stage, in or out, 0:16:17.000,0:16:21.000 and then recurs on that and what is one remaining. 0:16:21.000,0:16:23.000 It also needs a wrapper 0:16:23.000,0:16:26.000 for the same exact reason that permutations did. It's 0:16:26.000,0:16:28.000 just that we are trying to 0:16:28.000,0:16:29.000 0:16:29.000,0:16:32.000 list the subsets of a particular string, in fact, there's some housekeeping that's going along 0:16:32.000,0:16:36.000 with it. We're just trying the subset so far is something we don't necessarily 0:16:36.000,0:16:38.000 want to put into the public interface in the way that somebody would have to 0:16:38.000,0:16:44.000 know what to pass to that to get the right thing. Anybody have 0:16:44.000,0:16:48.000 a question about this? 0:16:48.000,0:16:50.000 So given the way this code is written, 0:16:50.000,0:17:05.000 what is the first subset that is printed if I give it the input A B C D? 0:17:05.000,0:17:07.000 A B C D. Just like it was with permute, right? Everything went in. 0:17:07.000,0:17:19.000 What is the second one printed after that? 0:17:19.000,0:17:20.000 A B C, right? So I'm 0:17:20.000,0:17:22.000 gonna look at my little diagram with you 0:17:22.000,0:17:27.000 to help kind of trace this process of the recursive call, right, is that 0:17:27.000,0:17:31.000 the leftmost arm is the inclusion arm, the right arm is the exclusion arm. 0:17:31.000,0:17:34.000 At every level of the tree, right, we're looking at the next character of 0:17:34.000,0:17:36.000 the rest and deciding whether to go in or out, 0:17:36.000,0:17:38.000 the first call it makes is always in, 0:17:38.000,0:17:41.000 so at the beginning it says, I'm choosing about A. Is A in? Sure. 0:17:41.000,0:17:44.000 And then it gets back to the level of recursion. It says, okay, look at the first 0:17:44.000,0:17:48.000 thing of rest, that's B. Is B in? Sure. Goes down the right arm, right? 0:17:48.000,0:17:52.000 Is C in? Sure. Is D in? Sure. It gets to here and now we have nothing left, so we 0:17:52.000,0:17:54.000 have [inaudible] A B C D. 0:17:54.000,0:17:58.000 With the rest being empty, we go ahead and print it [inaudible] there's no more choices to 0:17:58.000,0:18:01.000 make. We've looked at every letter and decided whether it was in or out. 0:18:01.000,0:18:05.000 It will come back to here, and I'll say, okay, I've finished all the things I can make 0:18:05.000,0:18:06.000 with D in, 0:18:06.000,0:18:09.000 how about we try it with D out. And so then D out 0:18:09.000,0:18:11.000 gives us just the A B C. 0:18:11.000,0:18:13.000 After it's done everything it can do with 0:18:13.000,0:18:17.000 A B C in, it comes back to here and says, okay, well now do this arm, 0:18:17.000,0:18:21.000 and this will drop C off, and then try D in, D out. 0:18:21.000,0:18:25.000 And so it will go from the biggest sets to the smaller sets, not quite 0:18:25.000,0:18:26.000 monotonically though. 0:18:26.000,0:18:28.000 The very last set printed will be the empty set, 0:18:28.000,0:18:31.000 and that will be the one where it was excluded all the way down, which after it kind of tried 0:18:31.000,0:18:34.000 all these combinations of in out, in out, in out, it 0:18:34.000,0:18:37.000 eventually got to the out, out, out, out, out, out, out case which will give me the 0:18:37.000,0:18:40.000 empty set on that arm. 0:18:40.000,0:18:43.000 Again, if I reverse the calls, right, I'd still see all the same subsets in 0:18:43.000,0:18:46.000 the end. They just come out in a different order. 0:18:46.000,0:18:50.000 But it is worthwhile to model the recursion in your own head to have this 0:18:50.000,0:18:54.000 idea of understanding about how it goes deep, right? That 0:18:54.000,0:18:57.000 it always makes that recursive call and has to work its way all the way to the 0:18:57.000,0:19:00.000 base case and terminate that recursion before it will unfold 0:19:00.000,0:19:03.000 and revisit the second call that was made, and 0:19:03.000,0:19:11.000 then fully explore where it goes before it completes that whole sequence. 0:19:11.000,0:19:16.000 Anybody want to ask me a question about these guys? These are 0:19:16.000,0:19:21.000 just really, really important pieces of code, and so I'm trying to 0:19:21.000,0:19:25.000 make sure that I don't move past something that still feels a little bit 0:19:25.000,0:19:27.000 mystical or confusing to you because 0:19:27.000,0:19:29.000 everything I want to do for the rest of today 0:19:29.000,0:19:30.000 builds on this. 0:19:30.000,0:19:33.000 So now if there's something about either of these pieces of code 0:19:33.000,0:19:38.000 that would help you -yeah. What would 0:19:38.000,0:19:40.000 be the simplest way to do that? 0:19:40.000,0:19:43.000 So probably the simplest way, like, if you said, oh, I just really want it to be in alphabetical order, 0:19:43.000,0:19:45.000 would be to put them in a set, right, and then 0:19:45.000,0:19:47.000 have the set be the order for you. So you said 0:19:47.000,0:19:49.000 order doesn't matter? Oh, you 0:19:49.000,0:19:53.000 did care about how they got ordered. So, like, let's say you 0:19:53.000,0:19:57.000 didn't want B C D to equal C D B. 0:19:57.000,0:20:00.000 So in that case, right, you would be more likely to kind of add a permutation step into 0:20:00.000,0:20:04.000 it, right? So if B C D was not the same thing as A B C, right, it would be, like, 0:20:04.000,0:20:05.000 well 0:20:05.000,0:20:07.000 I'm gonna chose -so in this case, right, 0:20:07.000,0:20:11.000 it always -well the subsets will always be printed as kind of a subsequence. So -and let's 0:20:11.000,0:20:14.000 say if the input was the alphabet, just easy way 0:20:14.000,0:20:15.000 to describe it, 0:20:15.000,0:20:19.000 all of the subsets I'm choosing will always be in alphabetical order because I'm always choosing A in or not, B in 0:20:19.000,0:20:19.000 or not. 0:20:19.000,0:20:23.000 If I really wanted B Z to be distinct from Z B, 0:20:23.000,0:20:27.000 then really what I want to be doing at each step is picking the next character to go, 0:20:27.000,0:20:28.000 0:20:28.000,0:20:29.000 and not 0:20:29.000,0:20:32.000 always assuming the next one had to be the next one in sequence, so I would do more like a 0:20:32.000,0:20:36.000 permute kind of loop that's like pick the next one that goes, remove it from what 0:20:36.000,0:20:38.000 remains and recur, 0:20:38.000,0:20:40.000 and that I need that separate step we talked about of -and 0:20:40.000,0:20:42.000 in addition to kind of 0:20:42.000,0:20:43.000 0:20:43.000,0:20:45.000 picking, we also have to 0:20:45.000,0:20:48.000 leave open the opportunity that we didn't pick anything and we just kind of left the subject as is, right, so we 0:20:48.000,0:20:50.000 could [inaudible] or not. And 0:20:50.000,0:20:54.000 so permute always assumes we have to have picked everything. The subset code 0:20:54.000,0:20:57.000 would also allow for 0:20:57.000,0:20:58.000 some of them just being entirely skipped. 0:20:58.000,0:21:02.000 So we pick the next one, right, and then eventually 0:21:02.000,0:21:04.000 stopped picking. 0:21:04.000,0:21:07.000 [Inaudible] just in your wrapper function 0:21:07.000,0:21:13.000 then [inaudible] put a for loop or something like that, right? When you're through changing your string? Yeah, you can certainly do that, like in a permute from the outside too, right. 0:21:13.000,0:21:16.000 So there's often very, you know, 0:21:16.000,0:21:19.000 multiple different ways you can get it the same thing whether you want to put it in the recursion or 0:21:19.000,0:21:20.000 outside the recursion, 0:21:20.000,0:21:22.000 have the set help you do it or not, 0:21:22.000,0:21:26.000 that can get you the same result. 0:21:26.000,0:21:28.000 So let me try to 0:21:28.000,0:21:32.000 identify what's the same about these to try to kind of back away from it and 0:21:32.000,0:21:33.000 kind of 0:21:33.000,0:21:36.000 move just to see how these are more similar than they are different, right, 0:21:36.000,0:21:40.000 even though the code ends up kind of being -having some details in it 0:21:40.000,0:21:43.000 that -if you kind of look at it from far away these are both problems that are 0:21:43.000,0:21:45.000 about 0:21:45.000,0:21:45.000 choice. 0:21:45.000,0:21:50.000 That the recursive calls that we see have kind of a branching structure and a depth factor 0:21:50.000,0:21:53.000 that actually relates to the problem if you think about it in terms of decisions, 0:21:53.000,0:21:57.000 that in making a permutation your decision is what character goes next, right? In the 0:21:57.000,0:22:01.000 subset it's like, well, whether this character goes in or not 0:22:01.000,0:22:05.000 that the recursive tree that I was drawing that it shows all those calls, 0:22:05.000,0:22:09.000 the depths of it represents the number of choices you make. Each 0:22:09.000,0:22:13.000 recursive call makes a choice, right? A yes, no, or a next letter to go, and then recurs from 0:22:13.000,0:22:15.000 there. So I make, you know, 0:22:15.000,0:22:18.000 one of those calls, and then there's N minus 1 beneath it that represent 0:22:18.000,0:22:22.000 the further decisions I make that builds on that. And so, in the case of permutation, once I've 0:22:22.000,0:22:23.000 picked the, you 0:22:23.000,0:22:25.000 know, N minus 1 0:22:25.000,0:22:29.000 things to go, there's only one thing left, right? And so in some sense the tree is 0:22:29.000,0:22:31.000 N because I have to pick N things that go in the permutation and then I'm 0:22:31.000,0:22:32.000 done. 0:22:32.000,0:22:35.000 In the subsets, it's also N, and that's because for each of the characters I'm deciding 0:22:35.000,0:22:37.000 whether it's in or out. So I 0:22:37.000,0:22:40.000 looked at A and decided in or out. I looked at B and decided in or out. And I did that all the 0:22:40.000,0:22:41.000 way down. 0:22:41.000,0:22:42.000 That was the life of the input. 0:22:42.000,0:22:44.000 The branching 0:22:44.000,0:22:48.000 represents how many recursive calls were made 0:22:48.000,0:22:52.000 at each level of the recursion. In the case of subsets, it's always exactly two. 0:22:52.000,0:22:54.000 In, out, all the way down, 0:22:54.000,0:22:59.000 restarts at 1, branches to 2, goes to 4, goes to 8, 16, and so on. 0:22:59.000,0:23:01.000 In the permute case, right, 0:23:01.000,0:23:05.000 there are N calls at the beginning. I have N different letters to choose from, so 0:23:05.000,0:23:10.000 it's a very wide spread there, and that at that next level, it's N minus 1. 0:23:10.000,0:23:12.000 Still very wide. And N minus 2. And 0:23:12.000,0:23:16.000 so the overall tree has kind of an N times N minus 1 times N minus 0:23:16.000,0:23:19.000 2 all the way down to the bottom, which the factorial function 0:23:19.000,0:23:22.000 -which grows very, very quickly. 0:23:22.000,0:23:26.000 Even for small inputs, right, the number of permutations is enormous. 0:23:26.000,0:23:28.000 The number of subsets is to the end 0:23:28.000,0:23:29.000 0:23:29.000,0:23:30.000 in or out, right, all the way across. 0:23:30.000,0:23:32.000 Also, a very, 0:23:32.000,0:23:34.000 you know, 0:23:34.000,0:23:37.000 resource intensive problem to solve, not nearly as bad as permutation, but both of 0:23:37.000,0:23:41.000 them, even for small sizes of N, start to become pretty quickly intractable. 0:23:41.000,0:23:44.000 This is not the fault of recursion, right, these problems are not hard to solve because 0:23:44.000,0:23:48.000 we're solving them in the wrong way. It's because there are N factorial permutations. There are 0:23:48.000,0:23:49.000 [inaudible] different subsets, 0:23:49.000,0:23:52.000 right? Anything that's going to print to the N things, or N factorial things is going 0:23:52.000,0:23:56.000 to do N factorial work to do so. You can't avoid it. 0:23:56.000,0:23:59.000 There's a big amount of work to be done in there. 0:23:59.000,0:24:02.000 But what we're trying to look at here is this idea that those trees, right, 0:24:02.000,0:24:04.000 represent decisions. 0:24:04.000,0:24:08.000 There's some decisions that are made, you know, a decision is made at each level of recursion, 0:24:08.000,0:24:09.000 which then 0:24:09.000,0:24:11.000 is kind of a little bit closer 0:24:11.000,0:24:14.000 to having no more decisions to make. You have so many decisions to make, which is 0:24:14.000,0:24:18.000 the depth of the recursion. Once you've made all those decisions, you hit your base case 0:24:18.000,0:24:19.000 and you're done. The 0:24:19.000,0:24:23.000 tree being very wide and very deep makes for expensive exploration. 0:24:23.000,0:24:27.000 What we're gonna look at is a way that we can take the same structure of the 0:24:27.000,0:24:31.000 problem, one that fundamentally could be exhaustive, exhaustive meaning tried every 0:24:31.000,0:24:35.000 possible combination, every possible rearrangement and option, 0:24:35.000,0:24:38.000 and only explore some part of the tree. 0:24:38.000,0:24:41.000 So only look around in some region, 0:24:41.000,0:24:43.000 and as soon as we find something that's good enough. 0:24:43.000,0:24:46.000 So in the case, for example, of a search problem, it might be that we're searching 0:24:46.000,0:24:50.000 this space that could potentially cause us to look at every option, 0:24:50.000,0:24:54.000 but we're also willing to say if we make some decisions that turn out good enough, 0:24:54.000,0:24:57.000 that get us to our goal, or whatever it is we're looking for, 0:24:57.000,0:25:00.000 we won't have to keep working any farther. So I'm gonna show 0:25:00.000,0:25:03.000 you how we can take an exhaustive recursion problem and turn it into 0:25:03.000,0:25:06.000 what's called a recursive backtracker. So 0:25:06.000,0:25:07.000 there's 0:25:07.000,0:25:10.000 a lot of text on this slide but let me just tell you in English what we're trying to 0:25:10.000,0:25:12.000 get at. 0:25:12.000,0:25:13.000 That 0:25:13.000,0:25:14.000 0:25:14.000,0:25:17.000 the idea behind permutations or subsets is that at every level there's all 0:25:17.000,0:25:20.000 these choices and we're gonna try every single one of them. 0:25:20.000,0:25:25.000 Now imagine we were gonna make a little bit less a guarantee about that. 0:25:25.000,0:25:26.000 Let's design the function 0:25:26.000,0:25:30.000 to return some sort of state that's like I succeeded or I failed. Did 0:25:30.000,0:25:33.000 I find what I was looking for? 0:25:33.000,0:25:33.000 0:25:33.000,0:25:38.000 At each call, I still have the possibility of multiple calls of in out, or a choice 0:25:38.000,0:25:40.000 from what's there. 0:25:40.000,0:25:42.000 I'm gonna go ahead and make the choice, 0:25:42.000,0:25:44.000 make the recursive call, 0:25:44.000,0:25:47.000 and then catch the result from that recursive call, and see whether it 0:25:47.000,0:25:51.000 succeeded. Was that a good choice? Did that choice get me to where I wanted to be? 0:25:51.000,0:25:52.000 If it did, 0:25:52.000,0:25:53.000 then I'm done. 0:25:53.000,0:25:56.000 I won't try anything else. So I'll stop early, 0:25:56.000,0:25:59.000 quite going around the for loop, quit making other recursive calls, 0:25:59.000,0:26:02.000 and just immediately [inaudible] say I'm done. 0:26:02.000,0:26:03.000 If it didn't 0:26:03.000,0:26:07.000 -it came back with a failure, some sort of code that said it didn't get where I 0:26:07.000,0:26:10.000 want to do, then I'll try a different choice. 0:26:10.000,0:26:14.000 And, again, I'll be optimistic. It's a very optimistic way of doing stuff. It says 0:26:14.000,0:26:17.000 make a choice, assume it's a good one, and go with it. 0:26:17.000,0:26:19.000 Only when you learn it didn't work out 0:26:19.000,0:26:23.000 do you revisit that decision and back up and try again. 0:26:23.000,0:26:27.000 So let me show you the code. I think it's gonna make more sense, actually, if 0:26:27.000,0:26:28.000 I 0:26:28.000,0:26:30.000 do it in terms of looking at what the code looks like. 0:26:30.000,0:26:35.000 This is the pseudo code at which all recursive backtrackers at their heart 0:26:35.000,0:26:37.000 come down to this pattern. 0:26:37.000,0:26:41.000 So what I -I tried to be abstract [inaudible] so what does it mean to solve a 0:26:41.000,0:26:44.000 problem, and what's the configuration? That depends on the domain and the problem 0:26:44.000,0:26:45.000 we're trying to solve. 0:26:45.000,0:26:48.000 But the structure of them all looks the same in that sense that 0:26:48.000,0:26:53.000 if there are choices to be made -so the idea is that we cast the problem as a decision 0:26:53.000,0:26:54.000 problem. 0:26:54.000,0:26:56.000 There are a bunch of choices to be made. 0:26:56.000,0:26:58.000 Each [inaudible] will make one choice 0:26:58.000,0:27:00.000 and then attempt to recursively solve it. So 0:27:00.000,0:27:04.000 there's some available choices, in or out, or one of next, or where to place a 0:27:04.000,0:27:07.000 tile on a board, or whether to take a left or right turn and go straight in a 0:27:07.000,0:27:10.000 maze. Any of these things could be the choices here. 0:27:10.000,0:27:11.000 We make a choice, 0:27:11.000,0:27:13.000 we feel good about it, we commit to it, 0:27:13.000,0:27:16.000 and we say, well, if we can solve from here -so we kind of update our statement so we've made 0:27:16.000,0:27:19.000 that term, or, 0:27:19.000,0:27:21.000 you know, chosen that letter, whatever it is we're doing. 0:27:21.000,0:27:24.000 If that recursive call returned true 0:27:24.000,0:27:25.000 then we return true, 0:27:25.000,0:27:28.000 so we don't do any unwinding. We don't try all the other choices. We stop that for 0:27:28.000,0:27:29.000 loop early. 0:27:29.000,0:27:32.000 We say that worked. That was good enough. 0:27:32.000,0:27:35.000 If the solve came back with a negative result, 0:27:35.000,0:27:36.000 that causes us to unmake that choice, 0:27:36.000,0:27:39.000 and then we come back around here and we try another one. 0:27:39.000,0:27:42.000 Again, we're optimistic. Okay, left didn't work, go straight. 0:27:42.000,0:27:46.000 If straight doesn't work, okay, go right. If right didn't work and we don't have any 0:27:46.000,0:27:50.000 more choices, then we return false, and 0:27:50.000,0:27:55.000 this false is the one that then causes some earlier decision to get unmade 0:27:55.000,0:28:00.000 which allows us to revisit some earlier optimistic choice, undo it, and 0:28:00.000,0:28:01.000 try again. 0:28:01.000,0:28:04.000 The base case is hit when we run out of choices 0:28:04.000,0:28:08.000 where we've -whatever configuration we're at is, like, okay, we're at a dead end, or we're at 0:28:08.000,0:28:10.000 the goal, or we've 0:28:10.000,0:28:14.000 run out of letters to try. Whatever it is, right, that tells us, okay, we didn't 0:28:14.000,0:28:17.000 -there's nothing more to decide. Is this where we wanted to be? 0:28:17.000,0:28:18.000 Did it solve the problem? 0:28:18.000,0:28:23.000 And I'm being kind of very deliberate today about what does it mean [inaudible] update the configuration, or what does it 0:28:23.000,0:28:25.000 mean for it to be the goal state because for different problems it definitely means different 0:28:25.000,0:28:29.000 things. But the code for them all looks the same 0:28:29.000,0:28:30.000 kind of in 0:28:30.000,0:28:33.000 its skeletal form. 0:28:33.000,0:28:38.000 So let me take a piece of code and turn it into a recursive backtracker with you. 0:28:38.000,0:28:40.000 So I've got recursive permute up 0:28:40.000,0:28:44.000 here. So as it is, recursive permute tries every possible permutation, prints them all. 0:28:44.000,0:28:47.000 What I'm interested in is is 0:28:47.000,0:28:51.000 this sequence a letters an anagram. Meaning, it is -can be rearranged into 0:28:51.000,0:28:54.000 something that's an English word. Okay. 0:28:54.000,0:28:56.000 So what I'm gonna do is I'm gonna go in and edit it. The 0:28:56.000,0:28:59.000 first thing I'm gonna do is I'm gonna change it to where it's gonna return some 0:28:59.000,0:29:00.000 information. 0:29:00.000,0:29:08.000 That information's gonna be yes it works, no it didn't. Okay? Now I'm gonna do this. 0:29:08.000,0:29:10.000 I'm 0:29:10.000,0:29:13.000 gonna 0:29:13.000,0:29:17.000 add a parameter to this because I -in order to tell that it's a word I have to 0:29:17.000,0:29:19.000 have someplace to look it up. I'm gonna use the lexicon that actually we're using on this 0:29:19.000,0:29:22.000 assignment. 0:29:22.000,0:29:24.000 And so 0:29:24.000,0:29:26.000 when I get to the bottom 0:29:26.000,0:29:30.000 and I have no more choices, I've got some permutation I've assembled here in -so 0:29:30.000,0:29:31.000 far. 0:29:31.000,0:29:35.000 And I'm going to check and see if it's in the dictionary. 0:29:35.000,0:29:38.000 If the dictionary says that that's a word then 0:29:38.000,0:29:41.000 I'm gonna say this was good. That permutation was good. 0:29:41.000,0:29:44.000 You don't need to look at any more permutations. Otherwise I'll return false which will 0:29:44.000,0:29:46.000 say, well, this thing isn't a word. Why don't you try again? 0:29:46.000,0:29:48.000 I'm gonna 0:29:48.000,0:29:53.000 change the name of the function while I'm at it to be a little more descriptive, and we'll call it is anagram. 0:29:53.000,0:29:58.000 And then when I make the call here [inaudible] 0:29:58.000,0:30:00.000 third argument. 0:30:00.000,0:30:03.000 I'm not just gonna make the call and let it go away. I really want to know did that 0:30:03.000,0:30:06.000 work, so I'm gonna say, well, if 0:30:06.000,0:30:08.000 it's an anagram 0:30:08.000,0:30:11.000 then return true. 0:30:11.000,0:30:16.000 So if given the choice I made -I've got these letters X J Q P A B C, 0:30:16.000,0:30:16.000 right? 0:30:16.000,0:30:20.000 It'll pick a letter and it'll say, well if, you know, put that letter in the front 0:30:20.000,0:30:23.000 and then go for it. If you can make a word out of having made that 0:30:23.000,0:30:26.000 choice, out of what remains, then you're done. You don't need to try anything else. Otherwise 0:30:26.000,0:30:29.000 we'll come back around and make some of the further calls in that loop 0:30:29.000,0:30:32.000 to see if it worked out. 0:30:32.000,0:30:34.000 At the bottom, I also need 0:30:34.000,0:30:36.000 another failure case here, 0:30:36.000,0:30:38.000 and that comes when 0:30:38.000,0:30:43.000 the earlier choices, right -so I got, let's say somebody has given me X J, 0:30:43.000,0:30:46.000 and then it says, given X J, can you permute A and B to make a word? Well, it turns out 0:30:46.000,0:30:47.000 that 0:30:47.000,0:30:50.000 you can -you know this ahead of time. It doesn't have the same vision 0:30:50.000,0:30:54.000 you do. But it says X J? A B? There's just nothing you can do but it'll try them all 0:30:54.000,0:30:57.000 dutifully. Tried A in the front and then B behind, and then tried B in the front and A behind it, and 0:30:57.000,0:31:01.000 after it says that, it says, you know what, okay, that just isn't working, right? 0:31:01.000,0:31:02.000 It must be some 0:31:02.000,0:31:05.000 earlier decision that was really at fault. 0:31:05.000,0:31:08.000 This returned false is going to cause 0:31:08.000,0:31:09.000 the, you 0:31:09.000,0:31:13.000 know, sort of stacked up previous anagram calls to say, oh yeah, that 0:31:13.000,0:31:16.000 choice of X for the first letter was really 0:31:16.000,0:31:19.000 questionable. So imagine I've had, like, E X, you know, 0:31:19.000,0:31:21.000 T I. I'm trying to 0:31:21.000,0:31:24.000 spell the word exit -is a possibility of it. That once I have that X in the 0:31:24.000,0:31:27.000 front it turns out nothing is going to work out, but it's gonna go through and try X 0:31:27.000,0:31:30.000 E I T, X E T I, and so on. 0:31:30.000,0:31:33.000 Well, after all those things have been tried it says, you know what, X in the front wasn't it, 0:31:33.000,0:31:37.000 right? Let's try again with I in the front. Well after it does that it won't get anywhere either. 0:31:37.000,0:31:38.000 Eventually it'll try E in the front 0:31:38.000,0:31:41.000 and then it won't have to try anything else after that because that will eventually 0:31:41.000,0:31:44.000 work out. 0:31:44.000,0:31:47.000 So if I put this guy in like that, 0:31:47.000,0:31:49.000 and I 0:31:49.000,0:31:59.000 build myself a lexicon, and then 0:31:59.000,0:32:01.000 I change this to 0:32:01.000,0:32:04.000 0:32:04.000,0:32:09.000 anagram word. I 0:32:09.000,0:32:13.000 can't spell. I'd better 0:32:13.000,0:32:16.000 pass my lexicon because I'm gonna need that to 0:32:16.000,0:32:18.000 do my word lookups. 0:32:18.000,0:32:20.000 [Inaudible]. And down here. 0:32:20.000,0:32:23.000 Whoops. 0:32:23.000,0:32:28.000 Okay. I 0:32:28.000,0:32:33.000 think 0:32:33.000,0:32:36.000 that looks like it's okay. Well, no 0:32:36.000,0:32:43.000 -finish this thing off here. 0:32:43.000,0:32:47.000 And so if I type in, you know, a word that I know is a word to begin 0:32:47.000,0:32:47.000 with, 0:32:47.000,0:32:49.000 like 0:32:49.000,0:32:52.000 boat, I happen to know the way the permutations work [inaudible] try that right away and find 0:32:52.000,0:32:52.000 that. 0:32:52.000,0:32:56.000 What if I get it toab, you know, which is a rearrangement of that, it eventually did find them. 0:32:56.000,0:32:59.000 What if I give it something like this, 0:32:59.000,0:33:02.000 which there's just no way you can get that in there. So it seems to [inaudible] it's 0:33:02.000,0:33:04.000 not telling us where the word is. I can actually go and change it. 0:33:04.000,0:33:07.000 Maybe that'd be a nice thing to say. Why don't I print the word 0:33:07.000,0:33:11.000 when it finds it? If 0:33:11.000,0:33:14.000 lex dot contains 0:33:14.000,0:33:16.000 -words so far 0:33:16.000,0:33:20.000 -then print it. That 0:33:20.000,0:33:25.000 way I can find out what word it thinks it made out of it. So if I 0:33:25.000,0:33:27.000 type toab -now 0:33:27.000,0:33:30.000 look at that, bota. Who would know? That dictionary's full of some really ridiculous 0:33:30.000,0:33:33.000 words. 0:33:33.000,0:33:37.000 Now I'll get back with exit. Let's type some other words. 0:33:37.000,0:33:40.000 Query. So it's finding some 0:33:40.000,0:33:44.000 words, and then if I give it some word that I know is just nonsense 0:33:44.000,0:33:46.000 it won't print anything 0:33:46.000,0:33:47.000 [inaudible] false. 0:33:47.000,0:33:51.000 And so in this case, what it's doing is its come to a partial exploration, right, 0:33:51.000,0:33:53.000 of the permutation tree 0:33:53.000,0:33:55.000 based on 0:33:55.000,0:34:00.000 this notion of being able to stop early on success. So in the case of this one, right, 0:34:00.000,0:34:03.000 even six nonsense characters, it really did do the full permutation, in this case, 0:34:03.000,0:34:06.000 the six factorial permutations, and discover that none of them worked. 0:34:06.000,0:34:08.000 But in the case of exit or the 0:34:08.000,0:34:10.000 boat that, 0:34:10.000,0:34:13.000 you know, early in the process it may have kind of made a decision, okay so [inaudible] 0:34:13.000,0:34:16.000 in this case it will try all the permutations with Q in the front, 0:34:16.000,0:34:17.000 right? 0:34:17.000,0:34:20.000 Which means, okay, we'll go with it, and then it'll do them in order to start with, but it'll 0:34:20.000,0:34:23.000 start kind of rearranging and jumbling them up, and eventually, right, 0:34:23.000,0:34:26.000 it will find something that did work with putting in the front, and it will never unmake that 0:34:26.000,0:34:30.000 decision about Q. It will just sort of have -made that decision early, 0:34:30.000,0:34:34.000 committed to it, and worked out, and then it covers a whole space of the tree that never got 0:34:34.000,0:34:38.000 explored of R in front, and Y in the front, and E in the front 0:34:38.000,0:34:40.000 because it had a notion of 0:34:40.000,0:34:43.000 what is a satisfactory outcome. So the base case that it finally got to in 0:34:43.000,0:34:47.000 this case met the standard for being a word was all it wanted to find, so it just 0:34:47.000,0:34:49.000 had to work through the base cases 0:34:49.000,0:34:50.000 until it found one, 0:34:50.000,0:35:00.000 and potentially that could be very few of them relative the huge space. All right. 0:35:00.000,0:35:02.000 I have this code 0:35:02.000,0:35:05.000 actually on this slide. So it's 0:35:05.000,0:35:08.000 permute, and that is turning into is anagram. And so, in blue, trying to highlight 0:35:08.000,0:35:11.000 the things that changed in the process, right, that 0:35:11.000,0:35:15.000 the structure of kind of how it's exploring, and making the recursive calls is exactly 0:35:15.000,0:35:16.000 the same. 0:35:16.000,0:35:19.000 But what we're using now is some return information from the function to 0:35:19.000,0:35:22.000 tell us how the progress went, 0:35:22.000,0:35:23.000 and then 0:35:23.000,0:35:28.000 having our base case return some sense of did we get where we wanted to be, 0:35:28.000,0:35:32.000 and then when we make the recursive call, if it did succeed, right, 0:35:32.000,0:35:35.000 we immediately return true and unwind out of the recursion, 0:35:35.000,0:35:37.000 doing no further exploration, 0:35:37.000,0:35:40.000 and in the case where all of our choices 0:35:40.000,0:35:41.000 0:35:41.000,0:35:45.000 gave us no success, right, we will return the call that says, well that was unworkable how we got 0:35:45.000,0:35:49.000 to where we were. 0:35:49.000,0:35:51.000 So this is the transformation that 0:35:51.000,0:35:54.000 you want to feel like you could actually sort of apply again and again, taking 0:35:54.000,0:35:58.000 something that was exhaustive, and looked at a whole space, 0:35:58.000,0:36:01.000 and then had -change it into a form where it's like, okay, well I wanted to stop 0:36:01.000,0:36:04.000 early when I get to something that's good enough. 0:36:04.000,0:36:07.000 A lot of problems, right, that are recursive backtrackers just end up being 0:36:07.000,0:36:08.000 procedural code 0:36:08.000,0:36:11.000 that got turned into this 0:36:11.000,0:36:15.000 based on a goal that you wanted to get to being one of the possibilities of the 0:36:15.000,0:36:18.000 exploration. 0:36:18.000,0:36:22.000 Anybody have any questions of what we got there? Okay. 0:36:22.000,0:36:24.000 I'm gonna show you some more 0:36:24.000,0:36:26.000 just because they are 0:36:26.000,0:36:29.000 -there are a million problems in this space, and the more of them you see, I 0:36:29.000,0:36:32.000 think, the more the patterns will start to emerge. 0:36:32.000,0:36:35.000 Each of these, right, we're gonna think of as decision problems, right, that we have some number 0:36:35.000,0:36:37.000 of decisions to make, 0:36:37.000,0:36:39.000 and we're gonna try to 0:36:39.000,0:36:42.000 make a decision in each recursive call 0:36:42.000,0:36:45.000 knowing that that gives us fewer decisions that we have to make in the 0:36:45.000,0:36:48.000 smaller form of the sub problem that we've built that way, 0:36:48.000,0:36:51.000 and then the decisions that we have open 0:36:51.000,0:36:53.000 to us, the options there 0:36:53.000,0:36:56.000 represent the different recursive calls we can make. Maybe it's a for loop, or 0:36:56.000,0:36:59.000 maybe a list of the explicit alternatives that we have 0:36:59.000,0:37:03.000 that will be open to us in any particular call. 0:37:03.000,0:37:06.000 This is a CS kind of classic problem. It's one that, you know, it doesn't seem like 0:37:06.000,0:37:09.000 it has a lot of utility but it's still interesting to think about, which is if 0:37:09.000,0:37:12.000 you have an eight by eight chessboard, which is the standard chessboard size, 0:37:12.000,0:37:14.000 and you had eight queen pieces, 0:37:14.000,0:37:18.000 could you place those eight queens on the board 0:37:18.000,0:37:21.000 in such a way that no queen is threatened by any other? The queen is 0:37:21.000,0:37:23.000 the most powerful 0:37:23.000,0:37:24.000 player on the board, right, can move 0:37:24.000,0:37:27.000 any number of spaces horizontally, vertically, or diagonally on any 0:37:27.000,0:37:29.000 straight line basically, 0:37:29.000,0:37:32.000 and so it does seem like, you know, that there's a lot of contention on the 0:37:32.000,0:37:35.000 board to get them all in there in such a way that they can't 0:37:35.000,0:37:37.000 go after each other. 0:37:37.000,0:37:41.000 And so if we think of this as a decision problem, 0:37:41.000,0:37:44.000 each call's gonna make one decision and recur on the rest. The decisions we have to 0:37:44.000,0:37:45.000 make are 0:37:45.000,0:37:50.000 we need to place, you know, eight queens let's say, if the board is an eight by eight board. 0:37:50.000,0:37:54.000 So at each call we could place one queen, leaving us with M minus 1 to 0:37:54.000,0:37:55.000 go. 0:37:55.000,0:37:59.000 The choices for that queen might be that one way to kind of 0:37:59.000,0:38:02.000 keep our problem 0:38:02.000,0:38:04.000 -just to manage the logistics of it is to say, well, we know that there's going to be a 0:38:04.000,0:38:07.000 queen in each column, 0:38:07.000,0:38:08.000 right, 0:38:08.000,0:38:10.000 it certainly can't be that there's two in one column. So 0:38:10.000,0:38:13.000 we can just do the problem column by column and say, well, the first thing we'll do is place 0:38:13.000,0:38:16.000 a queen in the leftmost column. 0:38:16.000,0:38:18.000 The next call will make a queen 0:38:18.000,0:38:21.000 -place a queen in the column to the right of that, and then so on. So we'll work our way 0:38:21.000,0:38:23.000 across the board from left to right, 0:38:23.000,0:38:25.000 and then the choices for that queen 0:38:25.000,0:38:27.000 will be any of the [inaudible] 0:38:27.000,0:38:32.000 and some of those actually are -we may be able to easily eliminate as 0:38:32.000,0:38:35.000 possibilities. So, for example, once this queen is down here in the bottommost row, and 0:38:35.000,0:38:40.000 we move on to this next column, there's no reason to even try placing the queen 0:38:40.000,0:38:43.000 right next to it because we can see that that immediately threatens. 0:38:43.000,0:38:46.000 So what we'll try is, is there a spot in this column that 0:38:46.000,0:38:48.000 works given the previous decisions I've made, 0:38:48.000,0:38:51.000 and if so, make that decision and move on. 0:38:51.000,0:38:54.000 And only if we learned that that decision, right, 0:38:54.000,0:39:00.000 that we just made optimistically isn't successful will we back up and try again. 0:39:00.000,0:39:10.000 So let me do a little demo with you. 0:39:10.000,0:39:12.000 Kind of shows this 0:39:12.000,0:39:14.000 doing its job. 0:39:14.000,0:39:17.000 Okay. 0:39:17.000,0:39:20.000 So [inaudible] I'm gonna do it as I said, kind of column by column. 0:39:20.000,0:39:24.000 [Inaudible] is that I'm placing the queen in the leftmost column to begin, and the question 0:39:24.000,0:39:27.000 mark here says this is a spot under consideration. I look at the 0:39:27.000,0:39:29.000 configuration I'm in, 0:39:29.000,0:39:32.000 and I say, is this a plausible place to put the queen? 0:39:32.000,0:39:34.000 And there's no reason not to, 0:39:34.000,0:39:38.000 so I go ahead and let the queen sit there. 0:39:38.000,0:39:42.000 Okay, so now I'm going to make my second recursive call. I say I've placed one queen, now there's three 0:39:42.000,0:39:43.000 more queens to go. 0:39:43.000,0:39:47.000 Why don't we go ahead and place the queens that remain to the right of this. And so 0:39:47.000,0:39:50.000 the next recursive call comes in and says, if you can place the queens given the 0:39:50.000,0:39:54.000 decision I've already made, then tell me yes, and then I'll know all is good. 0:39:54.000,0:39:58.000 So it looks at the bottommost row, and it says, oh, no, that won't work, 0:39:58.000,0:40:00.000 right? There's a queen right there. 0:40:00.000,0:40:03.000 It looks at the next one and then sees the diagonal attack. Okay. Moves up to 0:40:03.000,0:40:05.000 here and says, okay, that's good. 0:40:05.000,0:40:06.000 That'll work, 0:40:06.000,0:40:08.000 right? Looks at all of them and it's okay. 0:40:08.000,0:40:12.000 So now it says, okay, well I've made two decision. There's just two to go. I'm 0:40:12.000,0:40:16.000 feeling good about it. Go ahead and make the recursive call. 0:40:16.000,0:40:19.000 The third call comes in, looks at that row, not good, 0:40:19.000,0:40:21.000 looks at that row, not good, 0:40:21.000,0:40:25.000 looks at that row, not good, looks at that row, not good. Now this one -there weren't any 0:40:25.000,0:40:28.000 options at all that were viable. 0:40:28.000,0:40:30.000 We got here, 0:40:30.000,0:40:35.000 and given the earlier decisions, and so the idea is that, given our optimism, right, we 0:40:35.000,0:40:39.000 sort of made the calls and just sort of moved on. And now we've got in the situation where we 0:40:39.000,0:40:42.000 have tried all the possibilities in this third recursive call and there was 0:40:42.000,0:40:46.000 no way to make progress. It's gonna hit the return false at the bottom of the 0:40:46.000,0:40:47.000 backtracking that says, 0:40:47.000,0:40:50.000 you know what, there was some earlier problem. 0:40:50.000,0:40:50.000 0:40:50.000,0:40:54.000 There was no way I could have solved it given the two choices -or, you know, whatever 0:40:54.000,0:40:56.000 -we don't even know what choices were made, but there were some previous choices made, and 0:40:56.000,0:40:58.000 given the state that was passed to this call, 0:40:58.000,0:41:01.000 there's no way to solve it from here. 0:41:01.000,0:41:03.000 And so this is gonna trigger the backtracking. So 0:41:03.000,0:41:06.000 that backtracking is coming back to an earlier decision that you made and unmaking 0:41:06.000,0:41:07.000 it. 0:41:07.000,0:41:12.000 It's a return false coming out of that third call that then causes the second call to 0:41:12.000,0:41:13.000 try again. 0:41:13.000,0:41:17.000 And it goes up and it says okay, well where did I leave off? I tried the first couple of ones. 0:41:17.000,0:41:21.000 Okay, let's try moving it up a notch and see how that goes. 0:41:21.000,0:41:22.000 Then, again, 0:41:22.000,0:41:25.000 optimistic, makes the call and goes for it. 0:41:25.000,0:41:28.000 Can't do this one. That looks good. 0:41:28.000,0:41:31.000 And now we're on our way to placing the last queen, feeling really comfortable and 0:41:31.000,0:41:33.000 confidant, 0:41:33.000,0:41:34.000 but 0:41:34.000,0:41:35.000 discovering quickly, 0:41:35.000,0:41:39.000 right, that there was no possible. So it turns out this configuration with these three 0:41:39.000,0:41:42.000 queens, not solvable. Something must be wrong. 0:41:42.000,0:41:46.000 Back up to the most immediate decision. She knows it doesn't unmake, you know, 0:41:46.000,0:41:50.000 earlier decisions until it really has been proven that that can't work, so 0:41:50.000,0:41:52.000 at this point it says, okay, well let's try finding 0:41:52.000,0:41:53.000 something else in this 0:41:53.000,0:41:54.000 column. 0:41:54.000,0:41:55.000 No go. 0:41:55.000,0:41:58.000 That says, okay, well that one failed so it must be that I made the wrong decision in 0:41:58.000,0:42:01.000 the second column. Well, it turns out the second column -that was the last choice 0:42:01.000,0:42:05.000 it had. So in fact it really was my first decision 0:42:05.000,0:42:08.000 that got us off to the wrong foot. 0:42:08.000,0:42:11.000 And now, having tried everything that there was possible, given the queen in the 0:42:11.000,0:42:14.000 lower left in realizing none of them worked out, it comes back and says, okay, let's 0:42:14.000,0:42:18.000 try again, and at this point it actually will go fairly quickly. 0:42:18.000,0:42:21.000 Making that initial first decision 0:42:21.000,0:42:22.000 was 0:42:22.000,0:42:24.000 the magic that 0:42:24.000,0:42:26.000 got it solved. And 0:42:26.000,0:42:30.000 then we have a complete solution to the queens. 0:42:30.000,0:42:32.000 We put it onto eight, 0:42:32.000,0:42:34.000 and let it go. 0:42:34.000,0:42:38.000 You can see it kind of checking the board, backing up, and you notice that it 0:42:38.000,0:42:42.000 made that lower left decision kind of in -it's sticking to it, and so the idea is 0:42:42.000,0:42:46.000 that it always backs up to the most recent decision point 0:42:46.000,0:42:47.000 when it fails, 0:42:47.000,0:42:50.000 and only after kind of that one has kind of tried all its options will it actually 0:42:50.000,0:42:54.000 back up and consider a previous decision as being unworthy 0:42:54.000,0:43:01.000 and revisiting it. 0:43:01.000,0:43:04.000 In this case that first decision did work out, 0:43:04.000,0:43:06.000 the queen being in the lower left. 0:43:06.000,0:43:09.000 It turns out there were -you know, you saw the second one had to kind of slowly get 0:43:09.000,0:43:12.000 inched up in the second row. Right? It wasn't gonna work with the third row. It tried 0:43:12.000,0:43:15.000 that for a while. Tried the fourth row for a while. 0:43:15.000,0:43:18.000 All the possibilities after that, but eventually it was that fifth row 0:43:18.000,0:43:22.000 that then kind of gave it the breathing room to get those other queens out there. 0:43:22.000,0:43:25.000 But it did not end up trying, for example, all the other positions for the queen in 0:43:25.000,0:43:30.000 the first row, so it actually -it really looked at a much more constrained part of the entire 0:43:30.000,0:43:32.000 search tree than 0:43:32.000,0:43:34.000 an exhaustive recursion 0:43:34.000,0:43:39.000 of the whole thing would have done. 0:43:39.000,0:43:46.000 The code for that ?whoops 0:43:46.000,0:43:48.000 -looks something like this. 0:43:48.000,0:43:49.000 And 0:43:49.000,0:43:51.000 one of the things that I'll strongly encourage you to do when you're writing 0:43:51.000,0:43:54.000 a recursive backtracking routine, 0:43:54.000,0:43:58.000 something I learned from Stuart Regis, who long ago was my mentor, 0:43:58.000,0:43:59.000 was the idea that 0:43:59.000,0:44:03.000 when -trying to make this code look as simple as possible, that one of the things 0:44:03.000,0:44:06.000 you want to do is try to move away the details of the problem. For example, 0:44:06.000,0:44:08.000 like, is safe 0:44:08.000,0:44:12.000 -given the current placement of queens, and the row you're trying, and the column you're at, 0:44:12.000,0:44:15.000 trying to decide that there's not some existing conflict on the board with the 0:44:15.000,0:44:19.000 queen already being threatened by an existing queen just involves us 0:44:19.000,0:44:22.000 kind of traipsing across the grid and looking at different things. 0:44:22.000,0:44:26.000 But putting in its own helper function makes this code much easier to read, right? 0:44:26.000,0:44:28.000 Similarly, placing the queen in the board, removing the queen from the board, 0:44:28.000,0:44:32.000 there are things they need to do. Go up to state and draw some things on the 0:44:32.000,0:44:34.000 graphical display. 0:44:34.000,0:44:37.000 Put all that code somewhere else so you don't have to look at it, and then this 0:44:37.000,0:44:41.000 algorithm can be very easy to read. It's like for all of the row. So given 0:44:41.000,0:44:44.000 the column we're trying to place a queen in, we've got this grid 0:44:44.000,0:44:46.000 of boolean that shows where the queens are so far, 0:44:46.000,0:44:50.000 that for all of the rows across the board, if, 0:44:50.000,0:44:54.000 right, it's safe to place a queen in that row and this column, then place the 0:44:54.000,0:44:56.000 queen and see if you can solve 0:44:56.000,0:44:59.000 starting from the column to the right, given this new update to the board. If it 0:44:59.000,0:45:03.000 worked out, great, nothing more we need to do. Otherwise we need to take back that 0:45:03.000,0:45:05.000 queen, unmake that decision, 0:45:05.000,0:45:06.000 and try again. 0:45:06.000,0:45:09.000 Try a higher row. Try a higher row, right. 0:45:09.000,0:45:13.000 Again, assume it's gonna work out. If it does, great. If it doesn't, unmake it, try 0:45:13.000,0:45:16.000 it again. If we tried all the rows that were open to us, 0:45:16.000,0:45:21.000 and we never got to this case where this returned true, then we return false, which 0:45:21.000,0:45:22.000 causes some 0:45:22.000,0:45:26.000 previous one -we're backing up to a column behind it. So if we were currently trying to 0:45:26.000,0:45:27.000 put a queen in column two, 0:45:27.000,0:45:31.000 and we end up returning false, it's gonna cause column one to unmake a decision 0:45:31.000,0:45:33.000 and move the queen up a little bit higher. 0:45:33.000,0:45:38.000 If all of the options for column one fail, it'll back up to column zero. 0:45:38.000,0:45:41.000 The base case here at the end, is if we ever get to where 0:45:41.000,0:45:45.000 the column is past the number of columns on the board, then that means we placed a queen 0:45:45.000,0:45:47.000 all the way across the board and 0:45:47.000,0:45:50.000 we're in success land. So all 0:45:50.000,0:45:54.000 this code kind of looks the same kind of standing back from it, right, it's 0:45:54.000,0:45:54.000 like, 0:45:54.000,0:45:57.000 for each choice, if you can make that choice, make it. 0:45:57.000,0:46:02.000 If you solved it from here, great, otherwise, unmake that choice. 0:46:02.000,0:46:06.000 Here's my return false when I ran out of options. There's my base case -it says 0:46:06.000,0:46:09.000 if I have gotten to where there's no more decisions to make, I've placed all the 0:46:09.000,0:46:10.000 queens, 0:46:10.000,0:46:14.000 I've chosen all the letters, whatever, did I -am I where I wanted to be? There's no 0:46:14.000,0:46:17.000 some sort of true or false analysis that comes out there about 0:46:17.000,0:46:21.000 being in the right state. How do you feel 0:46:21.000,0:46:24.000 about that? You guys look 0:46:24.000,0:46:24.000 tired today, and 0:46:24.000,0:46:28.000 I didn't even give you an assignment due today, so this can't be my fault, 0:46:28.000,0:46:30.000 right? 0:46:30.000,0:46:33.000 I got a couple more examples, and I'm probably actually just gonna go ahead and try to spend some time on 0:46:33.000,0:46:36.000 them on Monday because I really don't want to -I 0:46:36.000,0:46:37.000 want 0:46:37.000,0:46:38.000 to 0:46:38.000,0:46:41.000 give you a little bit more practice though. So we'll see. We'll see. I'll do at 0:46:41.000,0:46:44.000 least one or two more of them on Monday before we start talking about pointers and linked lists, and so 0:46:44.000,0:47:00.000 I will see you then. But having a good weekend. Come and hang out in Turbine with me.