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