[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:09.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:09.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:14.00,0:00:23.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:23.00,0:00:25.00,Default,,0000,0000,0000,,Hi there. Good afternoon.
Dialogue: 0,0:00:25.00,0:00:27.00,Default,,0000,0000,0000,,Welcome to Monday.
Dialogue: 0,0:00:27.00,0:00:28.00,Default,,0000,0000,0000,,Today's a big day.
Dialogue: 0,0:00:28.00,0:00:31.00,Default,,0000,0000,0000,,A big day, right? We've got a couple of recursive backtracking examples that we
Dialogue: 0,0:00:31.00,0:00:35.00,Default,,0000,0000,0000,,didn't get to on Friday that I'm gonna
Dialogue: 0,0:00:35.00,0:00:36.00,Default,,0000,0000,0000,,talk you through today,
Dialogue: 0,0:00:36.00,0:00:40.00,Default,,0000,0000,0000,,and then we're gonna talk a little bit about pointers, the long anticipated introduction to
Dialogue: 0,0:00:40.00,0:00:42.00,Default,,0000,0000,0000,,one of the scarier parts of the C++ language
Dialogue: 0,0:00:42.00,0:00:47.00,Default,,0000,0000,0000,,as kind of a step toward building linked lists and the recursive data idea
Dialogue: 0,0:00:47.00,0:00:49.00,Default,,0000,0000,0000,,that we will study today and
Dialogue: 0,0:00:49.00,0:00:51.00,Default,,0000,0000,0000,,continue into Wednesday.
Dialogue: 0,0:00:51.00,0:00:54.00,Default,,0000,0000,0000,,So the two samples I want to do are both based on the same backtracking pseudocode that we
Dialogue: 0,0:00:54.00,0:00:56.00,Default,,0000,0000,0000,,were using on Friday. I
Dialogue: 0,0:00:56.00,0:00:59.00,Default,,0000,0000,0000,,just want to go through them. I'm gonna do a little bit less attention to the code and
Dialogue: 0,0:00:59.00,0:01:03.00,Default,,0000,0000,0000,,a little bit more attention to the problem solving because at some point I think the problem
Dialogue: 0,0:01:03.00,0:01:03.00,Default,,0000,0000,0000,,solving
Dialogue: 0,0:01:03.00,0:01:05.00,Default,,0000,0000,0000,,is really where the tricky stuff comes on.
Dialogue: 0,0:01:05.00,0:01:08.00,Default,,0000,0000,0000,,And then the kind of - turning it into code, there's some details there but
Dialogue: 0,0:01:08.00,0:01:11.00,Default,,0000,0000,0000,,they're not actually as important, so I'm gonna de-emphasize that just a little bit here and
Dialogue: 0,0:01:11.00,0:01:13.00,Default,,0000,0000,0000,,think more about solving it.
Dialogue: 0,0:01:13.00,0:01:16.00,Default,,0000,0000,0000,,So this is the pseudocode for any form of a backtracker, right, that has
Dialogue: 0,0:01:16.00,0:01:17.00,Default,,0000,0000,0000,,some sort of,
Dialogue: 0,0:01:17.00,0:01:20.00,Default,,0000,0000,0000,,you know, failure and success cases, like when we run out of choices, we've hit a
Dialogue: 0,0:01:20.00,0:01:24.00,Default,,0000,0000,0000,,dead end, or we've hit a goal state, we've - you know, there's no more decisions to make,
Dialogue: 0,0:01:24.00,0:01:26.00,Default,,0000,0000,0000,,right, is this want to be, yes or no,
Dialogue: 0,0:01:26.00,0:01:28.00,Default,,0000,0000,0000,,and then otherwise there are some decisions to make.
Dialogue: 0,0:01:28.00,0:01:33.00,Default,,0000,0000,0000,,And for all the possible decisions we could make, we're gonna try one, be optimistic
Dialogue: 0,0:01:33.00,0:01:37.00,Default,,0000,0000,0000,,about it working out, make that recursive call that says that choice was where I
Dialogue: 0,0:01:37.00,0:01:42.00,Default,,0000,0000,0000,,wanted to be. If it returns true, or whatever the success return value is,
Dialogue: 0,0:01:42.00,0:01:44.00,Default,,0000,0000,0000,,then we return true,
Dialogue: 0,0:01:44.00,0:01:47.00,Default,,0000,0000,0000,,right? No need to look any further. That choice was good enough.
Dialogue: 0,0:01:47.00,0:01:51.00,Default,,0000,0000,0000,,If it didn't work then we gotta unmake - try some other choices. If we try all the
Dialogue: 0,0:01:51.00,0:01:55.00,Default,,0000,0000,0000,,things available to us and no case, right, did solve ever return true,
Dialogue: 0,0:01:55.00,0:01:59.00,Default,,0000,0000,0000,,then we can only conclude that the configuration as given to this call was
Dialogue: 0,0:01:59.00,0:02:00.00,Default,,0000,0000,0000,,unsolvable,
Dialogue: 0,0:02:00.00,0:02:02.00,Default,,0000,0000,0000,,which is where that return false
Dialogue: 0,0:02:02.00,0:02:06.00,Default,,0000,0000,0000,,causes it to back up to some earlier call and start unmaking
Dialogue: 0,0:02:06.00,0:02:08.00,Default,,0000,0000,0000,,that next layer of decisions,
Dialogue: 0,0:02:08.00,0:02:11.00,Default,,0000,0000,0000,,and then recur further down, eventually either
Dialogue: 0,0:02:11.00,0:02:15.00,Default,,0000,0000,0000,,unwinding the entire recursive [inaudible] all the way back to the beginning and saying it
Dialogue: 0,0:02:15.00,0:02:18.00,Default,,0000,0000,0000,,was totally unsolvable no matter what, or eventually finding
Dialogue: 0,0:02:18.00,0:02:21.00,Default,,0000,0000,0000,,some sequence of decisions that will lead to one that will get us to a success
Dialogue: 0,0:02:21.00,0:02:23.00,Default,,0000,0000,0000,,case.
Dialogue: 0,0:02:23.00,0:02:27.00,Default,,0000,0000,0000,,So the one I'm gonna show you here is the sudoku,
Dialogue: 0,0:02:27.00,0:02:31.00,Default,,0000,0000,0000,,which is those little puzzles that show up in
Dialogue: 0,0:02:31.00,0:02:34.00,Default,,0000,0000,0000,,newspapers everywhere. They're actually not
Dialogue: 0,0:02:34.00,0:02:37.00,Default,,0000,0000,0000,,attributed to - apparently, to the Japanese, but it apparently got a lot more popular
Dialogue: 0,0:02:37.00,0:02:40.00,Default,,0000,0000,0000,,under its Japanese name than it did under the original
Dialogue: 0,0:02:40.00,0:02:41.00,Default,,0000,0000,0000,,English name for it.
Dialogue: 0,0:02:41.00,0:02:44.00,Default,,0000,0000,0000,,And the goal of a sudoku, if you haven't ever done one, right, is it's
Dialogue: 0,0:02:44.00,0:02:48.00,Default,,0000,0000,0000,,a nine by nine grid in which you're trying to place numbers,
Dialogue: 0,0:02:48.00,0:02:51.00,Default,,0000,0000,0000,,and the requirement for the numbers is such that
Dialogue: 0,0:02:51.00,0:02:53.00,Default,,0000,0000,0000,,within any particular row,
Dialogue: 0,0:02:53.00,0:02:56.00,Default,,0000,0000,0000,,or any particular column, or any particular block, which is a three by
Dialogue: 0,0:02:56.00,0:02:58.00,Default,,0000,0000,0000,,three subsection of that,
Dialogue: 0,0:02:58.00,0:03:00.00,Default,,0000,0000,0000,,the numbers one through nine each appear once.
Dialogue: 0,0:03:00.00,0:03:02.00,Default,,0000,0000,0000,,So you can never have more than two ones in a row,
Dialogue: 0,0:03:02.00,0:03:04.00,Default,,0000,0000,0000,,two twos in a column,
Dialogue: 0,0:03:04.00,0:03:06.00,Default,,0000,0000,0000,,three threes in a block, or anything like that.
Dialogue: 0,0:03:06.00,0:03:09.00,Default,,0000,0000,0000,,And so there has to be some rearrangement, or, in fact,
Dialogue: 0,0:03:09.00,0:03:11.00,Default,,0000,0000,0000,,permutation
Dialogue: 0,0:03:11.00,0:03:14.00,Default,,0000,0000,0000,,of the numbers one through nine in each row, in each column, and each block,
Dialogue: 0,0:03:14.00,0:03:17.00,Default,,0000,0000,0000,,such that the whole puzzle kind of works out logically.
Dialogue: 0,0:03:17.00,0:03:22.00,Default,,0000,0000,0000,,So when it's given to you, you know, usually some fraction of the
Dialogue: 0,0:03:22.00,0:03:23.00,Default,,0000,0000,0000,,slots are already filled in,
Dialogue: 0,0:03:23.00,0:03:27.00,Default,,0000,0000,0000,,and the goal for you is to fill in those remaining slots without violating any of
Dialogue: 0,0:03:27.00,0:03:29.00,Default,,0000,0000,0000,,these rules. Now
Dialogue: 0,0:03:29.00,0:03:33.00,Default,,0000,0000,0000,,the sort of pure sudoku solvers
Dialogue: 0,0:03:33.00,0:03:35.00,Default,,0000,0000,0000,,don't really use guessing.
Dialogue: 0,0:03:35.00,0:03:37.00,Default,,0000,0000,0000,,It's considered, actually, poor form,
Dialogue: 0,0:03:37.00,0:03:39.00,Default,,0000,0000,0000,,you know, that you're supposed to actually logically work it out by constraints
Dialogue: 0,0:03:39.00,0:03:43.00,Default,,0000,0000,0000,,about what has to be true here versus what has to be true there to kind of
Dialogue: 0,0:03:43.00,0:03:44.00,Default,,0000,0000,0000,,realize that
Dialogue: 0,0:03:44.00,0:03:46.00,Default,,0000,0000,0000,,- what choices you have. We're
Dialogue: 0,0:03:46.00,0:03:48.00,Default,,0000,0000,0000,,actually not gonna be a pure,
Dialogue: 0,0:03:48.00,0:03:51.00,Default,,0000,0000,0000,,artistic, you know, sudoku solver. What we're gonna do is we're actually gonna use a brute force
Dialogue: 0,0:03:51.00,0:03:54.00,Default,,0000,0000,0000,,recursive algorithm that's just gonna try recursive backtracking, which is to
Dialogue: 0,0:03:54.00,0:03:55.00,Default,,0000,0000,0000,,say,
Dialogue: 0,0:03:55.00,0:03:56.00,Default,,0000,0000,0000,,make an assignment,
Dialogue: 0,0:03:56.00,0:03:59.00,Default,,0000,0000,0000,,be optimistic about it, and if it works out, great, and if not,
Dialogue: 0,0:03:59.00,0:04:02.00,Default,,0000,0000,0000,,we'll eventually come back to that decision and revisit it.
Dialogue: 0,0:04:02.00,0:04:04.00,Default,,0000,0000,0000,,So what we have here basically is a big decision problem.
Dialogue: 0,0:04:04.00,0:04:06.00,Default,,0000,0000,0000,,You know, of the
Dialogue: 0,0:04:06.00,0:04:08.00,Default,,0000,0000,0000,,81 squares on here,
Dialogue: 0,0:04:08.00,0:04:10.00,Default,,0000,0000,0000,,you know, about 50 of them, right, need to be
Dialogue: 0,0:04:10.00,0:04:12.00,Default,,0000,0000,0000,,chosen.
Dialogue: 0,0:04:12.00,0:04:15.00,Default,,0000,0000,0000,,For each of those 50 squares, right, we're gonna do them one at a time and recur
Dialogue: 0,0:04:15.00,0:04:19.00,Default,,0000,0000,0000,,on the remaining ones. So, you know, choose one then we'll just go left to right from the
Dialogue: 0,0:04:19.00,0:04:20.00,Default,,0000,0000,0000,,top.
Dialogue: 0,0:04:20.00,0:04:23.00,Default,,0000,0000,0000,,Choose that one at the top, make an assignment that works, and so that's what
Dialogue: 0,0:04:23.00,0:04:26.00,Default,,0000,0000,0000,,we'll use the context we have in problem here. So, for example, if you look at
Dialogue: 0,0:04:26.00,0:04:28.00,Default,,0000,0000,0000,,this first row,
Dialogue: 0,0:04:28.00,0:04:31.00,Default,,0000,0000,0000,,there's a one in this column so we can't use one. There's
Dialogue: 0,0:04:31.00,0:04:33.00,Default,,0000,0000,0000,,a two in that block so we can't use two,
Dialogue: 0,0:04:33.00,0:04:37.00,Default,,0000,0000,0000,,but there's not a three in either that row, or that column, or that block, so we'll say, well, three looks good, you
Dialogue: 0,0:04:37.00,0:04:39.00,Default,,0000,0000,0000,,know, just trying the numbers in order.
Dialogue: 0,0:04:39.00,0:04:43.00,Default,,0000,0000,0000,,We'll be optimistic, say that works, and say, well if we planted a three here, could
Dialogue: 0,0:04:43.00,0:04:46.00,Default,,0000,0000,0000,,we recursively solve the remaining 49 holes
Dialogue: 0,0:04:46.00,0:04:48.00,Default,,0000,0000,0000,,and work it out?
Dialogue: 0,0:04:48.00,0:04:49.00,Default,,0000,0000,0000,,And so
Dialogue: 0,0:04:49.00,0:04:51.00,Default,,0000,0000,0000,,we get to that next one - we look at this one and say, okay, well
Dialogue: 0,0:04:51.00,0:04:53.00,Default,,0000,0000,0000,,we could put a one here,
Dialogue: 0,0:04:53.00,0:04:57.00,Default,,0000,0000,0000,,right, because there's not a one in this column, not a one in that row, not a one in
Dialogue: 0,0:04:57.00,0:05:01.00,Default,,0000,0000,0000,,that block, so we'll kind of move on. I'm gonna do a little demo of that for you. And maybe it's
Dialogue: 0,0:05:01.00,0:05:05.00,Default,,0000,0000,0000,,to kind of keep moving our way across, and only when
Dialogue: 0,0:05:05.00,0:05:06.00,Default,,0000,0000,0000,,we get to a dead end
Dialogue: 0,0:05:06.00,0:05:08.00,Default,,0000,0000,0000,,based on some of our earlier decisions will we unmake
Dialogue: 0,0:05:08.00,0:05:10.00,Default,,0000,0000,0000,,and come back. So
Dialogue: 0,0:05:10.00,0:05:15.00,Default,,0000,0000,0000,,let me - okay.
Dialogue: 0,0:05:15.00,0:05:20.00,Default,,0000,0000,0000,,So that's the same set of numbers there. So I put the three up in the corner.
Dialogue: 0,0:05:20.00,0:05:20.00,Default,,0000,0000,0000,,
Dialogue: 0,0:05:20.00,0:05:23.00,Default,,0000,0000,0000,,And so it puts the one here thinking, okay, that looks good. So it gets to the
Dialogue: 0,0:05:23.00,0:05:25.00,Default,,0000,0000,0000,,next square over here
Dialogue: 0,0:05:25.00,0:05:26.00,Default,,0000,0000,0000,,and then
Dialogue: 0,0:05:26.00,0:05:29.00,Default,,0000,0000,0000,,the one can't be used because it's actually already in use both in that column and
Dialogue: 0,0:05:29.00,0:05:33.00,Default,,0000,0000,0000,,in the row we're building so far, but two can be used. Two doesn't conflict with anything we
Dialogue: 0,0:05:33.00,0:05:34.00,Default,,0000,0000,0000,,have so far.
Dialogue: 0,0:05:34.00,0:05:36.00,Default,,0000,0000,0000,,And so it just keeps going optimistically,
Dialogue: 0,0:05:36.00,0:05:39.00,Default,,0000,0000,0000,,right? At that stage over there it turns out almost all the numbers are in
Dialogue: 0,0:05:39.00,0:05:43.00,Default,,0000,0000,0000,,use. Most of the numbers all the way up through seven and nine are there, and seven's
Dialogue: 0,0:05:43.00,0:05:46.00,Default,,0000,0000,0000,,in its column. So, in fact, the only number that that could possibly be is nine, so
Dialogue: 0,0:05:46.00,0:05:49.00,Default,,0000,0000,0000,,the only choice we have here to try is nine,
Dialogue: 0,0:05:49.00,0:05:51.00,Default,,0000,0000,0000,,and then we'll place the seven next
Dialogue: 0,0:05:51.00,0:05:54.00,Default,,0000,0000,0000,,to it. And so now we have a whole row that doesn't conflict with any of its blocks this
Dialogue: 0,0:05:54.00,0:05:56.00,Default,,0000,0000,0000,,way, and then we just keep moving on, right,
Dialogue: 0,0:05:56.00,0:05:57.00,Default,,0000,0000,0000,,so that is to keep kind of
Dialogue: 0,0:05:57.00,0:05:59.00,Default,,0000,0000,0000,,going from top to bottom, left to right.
Dialogue: 0,0:05:59.00,0:06:01.00,Default,,0000,0000,0000,,We'll place that four. We'll
Dialogue: 0,0:06:01.00,0:06:04.00,Default,,0000,0000,0000,,place another one. Place a three.
Dialogue: 0,0:06:04.00,0:06:07.00,Default,,0000,0000,0000,,So it's actually choosing them - it's actually going in order from one to nine just picking
Dialogue: 0,0:06:07.00,0:06:09.00,Default,,0000,0000,0000,,the first one that fits,
Dialogue: 0,0:06:09.00,0:06:11.00,Default,,0000,0000,0000,,right, so
Dialogue: 0,0:06:11.00,0:06:13.00,Default,,0000,0000,0000,,when we get to the next square here, right,
Dialogue: 0,0:06:13.00,0:06:17.00,Default,,0000,0000,0000,,it can't use one, it can't use two, it can't use three, it can't use four, it can't use five because they're all in
Dialogue: 0,0:06:17.00,0:06:18.00,Default,,0000,0000,0000,,that row. It can't
Dialogue: 0,0:06:18.00,0:06:20.00,Default,,0000,0000,0000,,use six because it's in the column. It
Dialogue: 0,0:06:20.00,0:06:22.00,Default,,0000,0000,0000,,can't use seven
Dialogue: 0,0:06:22.00,0:06:24.00,Default,,0000,0000,0000,,because it's in that row, but it should be able to use eight,
Dialogue: 0,0:06:24.00,0:06:26.00,Default,,0000,0000,0000,,and so it'll place an eight there.
Dialogue: 0,0:06:26.00,0:06:29.00,Default,,0000,0000,0000,,So it just kind of examines them in sequence until it finds the first one that
Dialogue: 0,0:06:29.00,0:06:32.00,Default,,0000,0000,0000,,doesn't violate any things already decided,
Dialogue: 0,0:06:32.00,0:06:35.00,Default,,0000,0000,0000,,and then kind of moves optimistically forward.
Dialogue: 0,0:06:35.00,0:06:38.00,Default,,0000,0000,0000,,So about this point, right, we're doing pretty well, but we're starting to
Dialogue: 0,0:06:38.00,0:06:40.00,Default,,0000,0000,0000,,run into some troubles if you look at
Dialogue: 0,0:06:40.00,0:06:42.00,Default,,0000,0000,0000,,the next one over here.
Dialogue: 0,0:06:42.00,0:06:44.00,Default,,0000,0000,0000,,It'll place the six there,
Dialogue: 0,0:06:44.00,0:06:46.00,Default,,0000,0000,0000,,but then it will -
Dialogue: 0,0:06:46.00,0:06:50.00,Default,,0000,0000,0000,,once the six is placed there, then it looks to the right and it says, oh, I need to put a
Dialogue: 0,0:06:50.00,0:06:52.00,Default,,0000,0000,0000,,nine there. That's the only number left. It tries all the numbers one, two,
Dialogue: 0,0:06:52.00,0:06:53.00,Default,,0000,0000,0000,,three, four,
Dialogue: 0,0:06:53.00,0:06:55.00,Default,,0000,0000,0000,,and it says that isn't gonna work.
Dialogue: 0,0:06:55.00,0:06:59.00,Default,,0000,0000,0000,,And so it actually fails on the rightmost column,
Dialogue: 0,0:06:59.00,0:07:02.00,Default,,0000,0000,0000,,which causes it to back up to the one right before and it says, well, why don't you try
Dialogue: 0,0:07:02.00,0:07:05.00,Default,,0000,0000,0000,,something else here? Well, it looks at seven, eight, and nine, none of those can work either,
Dialogue: 0,0:07:05.00,0:07:07.00,Default,,0000,0000,0000,,so it's actually gonna back up even further
Dialogue: 0,0:07:07.00,0:07:10.00,Default,,0000,0000,0000,,and then say, well what if we try to put a nine here? That also doesn't work. So now it's
Dialogue: 0,0:07:10.00,0:07:14.00,Default,,0000,0000,0000,,gonna start seeing that it's kind of unwinding as the constraints we have made have kind of
Dialogue: 0,0:07:14.00,0:07:17.00,Default,,0000,0000,0000,,got us down a dead end and it's slowly working its way back out to where the
Dialogue: 0,0:07:17.00,0:07:21.00,Default,,0000,0000,0000,,original bad decision was made.
Dialogue: 0,0:07:21.00,0:07:24.00,Default,,0000,0000,0000,,So it tries again on moving nine in here, and moving across, right,
Dialogue: 0,0:07:24.00,0:07:26.00,Default,,0000,0000,0000,,but again, kind of,
Dialogue: 0,0:07:26.00,0:07:27.00,Default,,0000,0000,0000,,
Dialogue: 0,0:07:27.00,0:07:30.00,Default,,0000,0000,0000,,you know, working its way forward but then kind of backing its way up. And
Dialogue: 0,0:07:30.00,0:07:32.00,Default,,0000,0000,0000,,let me go ahead
Dialogue: 0,0:07:32.00,0:07:37.00,Default,,0000,0000,0000,,and just run it faster so you can kind of see it.
Dialogue: 0,0:07:37.00,0:07:41.00,Default,,0000,0000,0000,,But, you know, it's working on that row for a while, but essentially to note that the top row stays
Dialogue: 0,0:07:41.00,0:07:44.00,Default,,0000,0000,0000,,relatively constant. It kind of believes that, well, that first three must have been good because, you
Dialogue: 0,0:07:44.00,0:07:47.00,Default,,0000,0000,0000,,know, we're getting somewhere on that, and it keeps kind of going. You can see
Dialogue: 0,0:07:47.00,0:07:50.00,Default,,0000,0000,0000,,that the activity is kind of always at the kind of
Dialogue: 0,0:07:50.00,0:07:54.00,Default,,0000,0000,0000,,tail end of that decision making, which eventually, right,
Dialogue: 0,0:07:54.00,0:07:56.00,Default,,0000,0000,0000,,worked its way out. And so it turns out, like, those three ones that we did put in the
Dialogue: 0,0:07:56.00,0:07:59.00,Default,,0000,0000,0000,,first spots were fine.
Dialogue: 0,0:07:59.00,0:08:01.00,Default,,0000,0000,0000,,That is, choices, right, it did work out.
Dialogue: 0,0:08:01.00,0:08:04.00,Default,,0000,0000,0000,,We didn't know that when we started, right, but it was optimistic, right, it put it down
Dialogue: 0,0:08:04.00,0:08:05.00,Default,,0000,0000,0000,,and then kept moving, and
Dialogue: 0,0:08:05.00,0:08:08.00,Default,,0000,0000,0000,,then eventually, right,
Dialogue: 0,0:08:08.00,0:08:12.00,Default,,0000,0000,0000,,worked out how the other things that had to get placed to make the whole puzzle
Dialogue: 0,0:08:12.00,0:08:13.00,Default,,0000,0000,0000,,be solvable.
Dialogue: 0,0:08:13.00,0:08:18.00,Default,,0000,0000,0000,,And so this thing can solve, actually, any solvable sudoku, right, and if it's not animating,
Dialogue: 0,0:08:18.00,0:08:19.00,Default,,0000,0000,0000,,instantaneously,
Dialogue: 0,0:08:19.00,0:08:21.00,Default,,0000,0000,0000,,even though it is really doing it in a fairly crude way,
Dialogue: 0,0:08:21.00,0:08:24.00,Default,,0000,0000,0000,,right, it's basically just trying everything it can,
Dialogue: 0,0:08:24.00,0:08:27.00,Default,,0000,0000,0000,,moving forward, and only when it kind of reaches a contradiction
Dialogue: 0,0:08:27.00,0:08:30.00,Default,,0000,0000,0000,,based on some of those choices that they will - that can't possibly be because at
Dialogue: 0,0:08:30.00,0:08:33.00,Default,,0000,0000,0000,,this point I'm forced into a situation where there's nothing that works in this
Dialogue: 0,0:08:33.00,0:08:33.00,Default,,0000,0000,0000,,square,
Dialogue: 0,0:08:33.00,0:08:36.00,Default,,0000,0000,0000,,so it must be that some earlier decision was wrong.
Dialogue: 0,0:08:36.00,0:08:39.00,Default,,0000,0000,0000,,And you notice that when it backs up, it backs up to the most immediate decision.
Dialogue: 0,0:08:39.00,0:08:42.00,Default,,0000,0000,0000,,So if you think of it in terms of recursive call, here's your first decision, your second
Dialogue: 0,0:08:42.00,0:08:44.00,Default,,0000,0000,0000,,decision, your third decision, your fourth decision, your fifth decision. If you get down
Dialogue: 0,0:08:44.00,0:08:47.00,Default,,0000,0000,0000,,here and you're, like, trying to make your eighth decision,
Dialogue: 0,0:08:47.00,0:08:49.00,Default,,0000,0000,0000,,and there's nothing that works, right,
Dialogue: 0,0:08:49.00,0:08:53.00,Default,,0000,0000,0000,,the decision that you come back to will be your seventh one. The one right
Dialogue: 0,0:08:53.00,0:08:56.00,Default,,0000,0000,0000,,before it. You don't go throw everything away and start over. You don't go all the way
Dialogue: 0,0:08:56.00,0:08:59.00,Default,,0000,0000,0000,,back to the beginning and say, oh, well that didn't work, let's try again.
Dialogue: 0,0:08:59.00,0:09:01.00,Default,,0000,0000,0000,,It's that you actually use the kind of context to say, well,
Dialogue: 0,0:09:01.00,0:09:04.00,Default,,0000,0000,0000,,the last decision I made was probably the one that needs a little fixing. Let me
Dialogue: 0,0:09:04.00,0:09:08.00,Default,,0000,0000,0000,,just back right up to that one. That's the way the calls unwind, and it says we'll pick up
Dialogue: 0,0:09:08.00,0:09:11.00,Default,,0000,0000,0000,,trying some other options there. Which ones have we not tried on that one? And
Dialogue: 0,0:09:11.00,0:09:15.00,Default,,0000,0000,0000,,then go forward again, and again, if you get down to that eighth decision and you're still
Dialogue: 0,0:09:15.00,0:09:18.00,Default,,0000,0000,0000,,stuck, you come back to the seventh decision again, and only after kind of the seventh decision
Dialogue: 0,0:09:18.00,0:09:21.00,Default,,0000,0000,0000,,has gone back and forth with the eighth unsuccessfully
Dialogue: 0,0:09:21.00,0:09:25.00,Default,,0000,0000,0000,,through all its options would we eventually return to that sixth decision, and
Dialogue: 0,0:09:25.00,0:09:29.00,Default,,0000,0000,0000,,potentially back to the fifth, and fourth, and so on.
Dialogue: 0,0:09:29.00,0:09:31.00,Default,,0000,0000,0000,,The code for this guy,
Dialogue: 0,0:09:31.00,0:09:32.00,Default,,0000,0000,0000,,
Dialogue: 0,0:09:32.00,0:09:36.00,Default,,0000,0000,0000,,a little abstracted
Dialogue: 0,0:09:36.00,0:09:39.00,Default,,0000,0000,0000,,that should very much fit the pattern of what you think recursive backtracking
Dialogue: 0,0:09:39.00,0:09:40.00,Default,,0000,0000,0000,,looks like, and then the kind of
Dialogue: 0,0:09:40.00,0:09:43.00,Default,,0000,0000,0000,,sort of goofier parts that are about, well, what does it mean to test a
Dialogue: 0,0:09:43.00,0:09:47.00,Default,,0000,0000,0000,,sudoku for being a sign of having conflicts is actually then
Dialogue: 0,0:09:47.00,0:09:50.00,Default,,0000,0000,0000,,passed out into these helper functions that manage the more
Dialogue: 0,0:09:50.00,0:09:52.00,Default,,0000,0000,0000,,domain specific parts of the problem.
Dialogue: 0,0:09:52.00,0:09:55.00,Default,,0000,0000,0000,,So at the very beginning it's like, find an unassigned location on the grid, and
Dialogue: 0,0:09:55.00,0:09:58.00,Default,,0000,0000,0000,,it returns the row and column by reference. It turns out in this case
Dialogue: 0,0:09:58.00,0:10:01.00,Default,,0000,0000,0000,,those are reference parameters. So [inaudible] searches from top to bottom to find the
Dialogue: 0,0:10:01.00,0:10:05.00,Default,,0000,0000,0000,,first slot that actually does not have a value currently in it.
Dialogue: 0,0:10:05.00,0:10:08.00,Default,,0000,0000,0000,,If it never finds one, so exhaustively searched the grid and didn't find one, then it
Dialogue: 0,0:10:08.00,0:10:11.00,Default,,0000,0000,0000,,must be that we have a working sudoku because we never put a number in
Dialogue: 0,0:10:11.00,0:10:17.00,Default,,0000,0000,0000,,unless it worked for us, and so if we've managed to assign them all, we're done.
Dialogue: 0,0:10:17.00,0:10:19.00,Default,,0000,0000,0000,,If this didn't return true,
Dialogue: 0,0:10:19.00,0:10:21.00,Default,,0000,0000,0000,,that meant it found one, and it assigned them a row and column,
Dialogue: 0,0:10:21.00,0:10:24.00,Default,,0000,0000,0000,,and then what we're gonna go through the process of is assigning that row and
Dialogue: 0,0:10:24.00,0:10:24.00,Default,,0000,0000,0000,,column.
Dialogue: 0,0:10:24.00,0:10:26.00,Default,,0000,0000,0000,,So we look at the numbers one through nine.
Dialogue: 0,0:10:26.00,0:10:28.00,Default,,0000,0000,0000,,If there are no conflicts for that number,
Dialogue: 0,0:10:28.00,0:10:32.00,Default,,0000,0000,0000,,so it doesn't conflict with the row, column, or block,
Dialogue: 0,0:10:32.00,0:10:35.00,Default,,0000,0000,0000,,that number isn't already in use in one of those places, then we go ahead and make
Dialogue: 0,0:10:35.00,0:10:36.00,Default,,0000,0000,0000,,the assignment,
Dialogue: 0,0:10:36.00,0:10:40.00,Default,,0000,0000,0000,,and then we see if we can solve it from here. So having updated the grid
Dialogue: 0,0:10:40.00,0:10:42.00,Default,,0000,0000,0000,,to show that new number's in play,
Dialogue: 0,0:10:42.00,0:10:46.00,Default,,0000,0000,0000,,you know, if we move on, the next [inaudible] of sudoku will then do a
Dialogue: 0,0:10:46.00,0:10:50.00,Default,,0000,0000,0000,,search for find unassigned location. This time the one that we previously found, right,
Dialogue: 0,0:10:50.00,0:10:52.00,Default,,0000,0000,0000,,has been assigned, so it actually won't get triggered on that one.
Dialogue: 0,0:10:52.00,0:10:55.00,Default,,0000,0000,0000,,It'll look past it further down into the puzzle,
Dialogue: 0,0:10:55.00,0:10:57.00,Default,,0000,0000,0000,,and eventually either find
Dialogue: 0,0:10:57.00,0:11:00.00,Default,,0000,0000,0000,,the next one to make a call on, and kind of work its way through, or to - you have to
Dialogue: 0,0:11:00.00,0:11:02.00,Default,,0000,0000,0000,,solve the whole thing.
Dialogue: 0,0:11:02.00,0:11:06.00,Default,,0000,0000,0000,,If it didn't work, so we made that assignment to the number nine, and we went to solve,
Dialogue: 0,0:11:06.00,0:11:07.00,Default,,0000,0000,0000,,and eventually this
Dialogue: 0,0:11:07.00,0:11:11.00,Default,,0000,0000,0000,,tried all its possibilities from here and nothing came up good, then this
Dialogue: 0,0:11:11.00,0:11:13.00,Default,,0000,0000,0000,,unassigned
Dialogue: 0,0:11:13.00,0:11:15.00,Default,,0000,0000,0000,,constant is used to unmake that decision,
Dialogue: 0,0:11:15.00,0:11:18.00,Default,,0000,0000,0000,,and come back around, and try
Dialogue: 0,0:11:18.00,0:11:21.00,Default,,0000,0000,0000,,assigning it a different number. If we try all of our examples, so for
Dialogue: 0,0:11:21.00,0:11:25.00,Default,,0000,0000,0000,,example, if we never find one that doesn't already conflict, or
Dialogue: 0,0:11:25.00,0:11:29.00,Default,,0000,0000,0000,,if we try each one and it comes back false, right, that this return false here is
Dialogue: 0,0:11:29.00,0:11:30.00,Default,,0000,0000,0000,,what's triggering
Dialogue: 0,0:11:30.00,0:11:33.00,Default,,0000,0000,0000,,the backtracking up to the previous recursive call
Dialogue: 0,0:11:33.00,0:11:37.00,Default,,0000,0000,0000,,to reconsider some earlier decision - the most recent early decision
Dialogue: 0,0:11:37.00,0:11:38.00,Default,,0000,0000,0000,,for this one,
Dialogue: 0,0:11:38.00,0:11:40.00,Default,,0000,0000,0000,,and say that was really our mistake, right,
Dialogue: 0,0:11:40.00,0:11:42.00,Default,,0000,0000,0000,,we've got to unmake that one.
Dialogue: 0,0:11:42.00,0:11:45.00,Default,,0000,0000,0000,,So it should look like kind of all the recursive backtracking all through looks the same,
Dialogue: 0,0:11:45.00,0:11:47.00,Default,,0000,0000,0000,,right? You know, if
Dialogue: 0,0:11:47.00,0:11:48.00,Default,,0000,0000,0000,,we're at the end,
Dialogue: 0,0:11:48.00,0:11:49.00,Default,,0000,0000,0000,,here's our base cases
Dialogue: 0,0:11:49.00,0:11:53.00,Default,,0000,0000,0000,,for all our options. If we can make this choice, make it, try to solve it, be
Dialogue: 0,0:11:53.00,0:11:56.00,Default,,0000,0000,0000,,optimistic, if it works out, return.
Dialogue: 0,0:11:56.00,0:11:59.00,Default,,0000,0000,0000,,Otherwise, unmake it, allow the loop to iterate a
Dialogue: 0,0:11:59.00,0:12:02.00,Default,,0000,0000,0000,,few more times trying again. If all of those things
Dialogue: 0,0:12:02.00,0:12:06.00,Default,,0000,0000,0000,,fail to find a solution then that return false here will cause the backtracking
Dialogue: 0,0:12:06.00,0:12:12.00,Default,,0000,0000,0000,,out of this decision. I just let it
Dialogue: 0,0:12:12.00,0:12:15.00,Default,,0000,0000,0000,,become constant. You know, I made it up. I used negative one, in fact,
Dialogue: 0,0:12:15.00,0:12:16.00,Default,,0000,0000,0000,,just to know that
Dialogue: 0,0:12:16.00,0:12:20.00,Default,,0000,0000,0000,,it has no contents.
Dialogue: 0,0:12:20.00,0:12:26.00,Default,,0000,0000,0000,,Just specific to sudoku in this case. Now would be a great time
Dialogue: 0,0:12:26.00,0:12:30.00,Default,,0000,0000,0000,,to ask a question. You guys kind of have that sort of half-okay
Dialogue: 0,0:12:30.00,0:12:34.00,Default,,0000,0000,0000,,look on your face. It could be I'm totally bored. It could be I'm totally lost. Where do row and column
Dialogue: 0,0:12:34.00,0:12:35.00,Default,,0000,0000,0000,,get assigned? So they
Dialogue: 0,0:12:35.00,0:12:38.00,Default,,0000,0000,0000,,- finding assigned location takes [inaudible] reference.
Dialogue: 0,0:12:38.00,0:12:41.00,Default,,0000,0000,0000,,So if you look at the full code for this - this is actually in the handout I gave out last time, and so
Dialogue: 0,0:12:41.00,0:12:44.00,Default,,0000,0000,0000,,there's a pass by reference in that function, and it returns true if it assigned
Dialogue: 0,0:12:44.00,0:12:46.00,Default,,0000,0000,0000,,them something, and then they have the
Dialogue: 0,0:12:46.00,0:12:49.00,Default,,0000,0000,0000,,coordinates of that
Dialogue: 0,0:12:49.00,0:12:51.00,Default,,0000,0000,0000,,unassigned location. Question over here. How'd you know
Dialogue: 0,0:12:51.00,0:12:55.00,Default,,0000,0000,0000,,to write sol sudoku as a bool rather than as, like, a void function? Well, in this
Dialogue: 0,0:12:55.00,0:12:57.00,Default,,0000,0000,0000,,case - that's a great question, right,
Dialogue: 0,0:12:57.00,0:13:01.00,Default,,0000,0000,0000,,in most cases in recursive backtracking I am trying to
Dialogue: 0,0:13:01.00,0:13:05.00,Default,,0000,0000,0000,,discover the success or failure of an operation, and so that's a good way to tell
Dialogue: 0,0:13:05.00,0:13:07.00,Default,,0000,0000,0000,,because otherwise I need to know did it work.
Dialogue: 0,0:13:07.00,0:13:10.00,Default,,0000,0000,0000,,And so if I made it void then there had to be some other way I figured it out. Maybe,
Dialogue: 0,0:13:10.00,0:13:13.00,Default,,0000,0000,0000,,you know, that you have to check the grid when you're done and see that it has - no longer has
Dialogue: 0,0:13:13.00,0:13:16.00,Default,,0000,0000,0000,,any unassigned locations, but the bool is actually just the easiest way to get that
Dialogue: 0,0:13:16.00,0:13:17.00,Default,,0000,0000,0000,,information out.
Dialogue: 0,0:13:17.00,0:13:19.00,Default,,0000,0000,0000,,So typically your recursive backtracking machine
Dialogue: 0,0:13:19.00,0:13:21.00,Default,,0000,0000,0000,,will probably return something.
Dialogue: 0,0:13:21.00,0:13:22.00,Default,,0000,0000,0000,,
Dialogue: 0,0:13:22.00,0:13:25.00,Default,,0000,0000,0000,,Often it's a true or false. It could be, you know, in some other case, just some other
Dialogue: 0,0:13:25.00,0:13:27.00,Default,,0000,0000,0000,,good know value, and some other
Dialogue: 0,0:13:27.00,0:13:31.00,Default,,0000,0000,0000,,sentinel that says, you know, bad value. So, for example, in the finding an anagram of the
Dialogue: 0,0:13:31.00,0:13:34.00,Default,,0000,0000,0000,,words it might be that it returned the word if it found one, or returned an empty string if
Dialogue: 0,0:13:34.00,0:13:36.00,Default,,0000,0000,0000,,it didn't. So using some sort of state that says
Dialogue: 0,0:13:36.00,0:13:39.00,Default,,0000,0000,0000,,here's how - if you made the call, you'll know whether it worked because we
Dialogue: 0,0:13:39.00,0:13:40.00,Default,,0000,0000,0000,,really do need to know.
Dialogue: 0,0:13:40.00,0:13:44.00,Default,,0000,0000,0000,,Make the call and find out whether it worked. Well, how are we gonna find out? One of the best ways to
Dialogue: 0,0:13:44.00,0:13:47.00,Default,,0000,0000,0000,,get that information is from a return value. Way in
Dialogue: 0,0:13:47.00,0:13:52.00,Default,,0000,0000,0000,,the back? Exactly does the return calls trigger in the backtracking
Dialogue: 0,0:13:52.00,0:13:52.00,Default,,0000,0000,0000,,[inaudible]?
Dialogue: 0,0:13:52.00,0:13:56.00,Default,,0000,0000,0000,,So think about this as that, you know, it's hard to think about because you have to kind of have kind of
Dialogue: 0,0:13:56.00,0:13:58.00,Default,,0000,0000,0000,,both sides of the recursion in your head, but
Dialogue: 0,0:13:58.00,0:14:00.00,Default,,0000,0000,0000,,when - let's say we're on
Dialogue: 0,0:14:00.00,0:14:02.00,Default,,0000,0000,0000,,the fifth decision, right?
Dialogue: 0,0:14:02.00,0:14:05.00,Default,,0000,0000,0000,,We make the call to solve the sudoku that's gonna look at the sixth
Dialogue: 0,0:14:05.00,0:14:06.00,Default,,0000,0000,0000,,decision, right?
Dialogue: 0,0:14:06.00,0:14:10.00,Default,,0000,0000,0000,,If the sixth decision fails, it says, I looked at all my choices and none of them
Dialogue: 0,0:14:10.00,0:14:11.00,Default,,0000,0000,0000,,worked, right?
Dialogue: 0,0:14:11.00,0:14:12.00,Default,,0000,0000,0000,,It's that
Dialogue: 0,0:14:12.00,0:14:15.00,Default,,0000,0000,0000,,that causes the fifth decision to say, well I - here go solve for the sixth decision
Dialogue: 0,0:14:15.00,0:14:18.00,Default,,0000,0000,0000,,down. Well the sixth decision came back with a false. It got to this case after
Dialogue: 0,0:14:18.00,0:14:19.00,Default,,0000,0000,0000,,trying all its options,
Dialogue: 0,0:14:19.00,0:14:23.00,Default,,0000,0000,0000,,then it's the fifth decision that then says, okay, well then I'd better unmake the decision I
Dialogue: 0,0:14:23.00,0:14:24.00,Default,,0000,0000,0000,,made and try again.
Dialogue: 0,0:14:24.00,0:14:28.00,Default,,0000,0000,0000,,And so at any given stage you can think about the caller and the callee, it's saying,
Dialogue: 0,0:14:28.00,0:14:31.00,Default,,0000,0000,0000,,I'm making a decision. You tell me if you can make it work from here.
Dialogue: 0,0:14:31.00,0:14:35.00,Default,,0000,0000,0000,,If the delegate that you passed on the smaller form of the recursive problem comes
Dialogue: 0,0:14:35.00,0:14:39.00,Default,,0000,0000,0000,,back with a return false, and then I've tried everything I could possibly do, but
Dialogue: 0,0:14:39.00,0:14:42.00,Default,,0000,0000,0000,,there was no way. The situation you gave me was unworkable.
Dialogue: 0,0:14:42.00,0:14:46.00,Default,,0000,0000,0000,,And that says, oh, okay, well you know what, it must have been my fault, right? I put
Dialogue: 0,0:14:46.00,0:14:49.00,Default,,0000,0000,0000,,the wrong number in my box. Let me try a different number and now you try again.
Dialogue: 0,0:14:49.00,0:14:52.00,Default,,0000,0000,0000,,And so they're constantly kind of these - you have to keep active in your mind the
Dialogue: 0,0:14:52.00,0:14:52.00,Default,,0000,0000,0000,,idea
Dialogue: 0,0:14:52.00,0:14:55.00,Default,,0000,0000,0000,,that there's this whole chain of these things being stacked up, each of them
Dialogue: 0,0:14:55.00,0:14:59.00,Default,,0000,0000,0000,,being optimistic and then delegating down. And if your delegate comes back
Dialogue: 0,0:14:59.00,0:15:00.00,Default,,0000,0000,0000,,with the -
Dialogue: 0,0:15:00.00,0:15:02.00,Default,,0000,0000,0000,,there was nothing I could do,
Dialogue: 0,0:15:02.00,0:15:06.00,Default,,0000,0000,0000,,then you have to revisit your earlier optimistic decision, unmake it, and
Dialogue: 0,0:15:06.00,0:15:07.00,Default,,0000,0000,0000,,try again.
Dialogue: 0,0:15:07.00,0:15:09.00,Default,,0000,0000,0000,,And so
Dialogue: 0,0:15:09.00,0:15:12.00,Default,,0000,0000,0000,,that - this is the return false to the outer call,
Dialogue: 0,0:15:12.00,0:15:16.00,Default,,0000,0000,0000,,the one that made the solved call
Dialogue: 0,0:15:16.00,0:15:17.00,Default,,0000,0000,0000,,that unwinds from.
Dialogue: 0,0:15:17.00,0:15:21.00,Default,,0000,0000,0000,,Way over here? [Inaudible]?
Dialogue: 0,0:15:21.00,0:15:26.00,Default,,0000,0000,0000,,Pretty much any recursive piece of thing can be reformed into a backtracking form, right?
Dialogue: 0,0:15:26.00,0:15:29.00,Default,,0000,0000,0000,,You need to - to do a little bit like the [inaudible] we tried last time,
Dialogue: 0,0:15:29.00,0:15:32.00,Default,,0000,0000,0000,,we'll take a void returning thing and make it return some true or false, and there's kind of,
Dialogue: 0,0:15:32.00,0:15:36.00,Default,,0000,0000,0000,,like, make a decision and be optimistic, see if it worked out.
Dialogue: 0,0:15:36.00,0:15:40.00,Default,,0000,0000,0000,,But that kind of rearrangement of the code should work with pretty much all
Dialogue: 0,0:15:40.00,0:15:43.00,Default,,0000,0000,0000,,your standard recursion stuff. So any kind of puzzle that actually,
Dialogue: 0,0:15:43.00,0:15:46.00,Default,,0000,0000,0000,,like, all these kind of jumble puzzles, and crossword puzzles, and things
Dialogue: 0,0:15:46.00,0:15:48.00,Default,,0000,0000,0000,,that involve kind of choosing, right,
Dialogue: 0,0:15:48.00,0:15:52.00,Default,,0000,0000,0000,,can be solved with recursive backtracking. It's not necessarily the fastest, right, way
Dialogue: 0,0:15:52.00,0:15:56.00,Default,,0000,0000,0000,,to get to a solution, but it will exhaustively try all the options until
Dialogue: 0,0:15:56.00,0:16:00.00,Default,,0000,0000,0000,,a sequence of decisions, right, leads you to a goal if there is a goal to be found.
Dialogue: 0,0:16:00.00,0:16:03.00,Default,,0000,0000,0000,,And so that if you can think of it as - if you can think of your problem as a
Dialogue: 0,0:16:03.00,0:16:04.00,Default,,0000,0000,0000,,decision problem -
Dialogue: 0,0:16:04.00,0:16:07.00,Default,,0000,0000,0000,,I need to make some decisions, and then from there make some more decisions and so
Dialogue: 0,0:16:07.00,0:16:09.00,Default,,0000,0000,0000,,on, and eventually, right, I will bottom out
Dialogue: 0,0:16:09.00,0:16:11.00,Default,,0000,0000,0000,,either at a goal or dead end,
Dialogue: 0,0:16:11.00,0:16:14.00,Default,,0000,0000,0000,,then you can write a recursive problem solving -
Dialogue: 0,0:16:14.00,0:16:18.00,Default,,0000,0000,0000,,backtracker to solve it. Way in
Dialogue: 0,0:16:18.00,0:16:23.00,Default,,0000,0000,0000,,the back? This doesn't have anything to do with recursion, but how did you slow down the simulation? How did I slow it down? I'm just using pause. There's a pause
Dialogue: 0,0:16:23.00,0:16:28.00,Default,,0000,0000,0000,,function in our stenographics library, and you just give it a time. You say one second, half a second, and
Dialogue: 0,0:16:28.00,0:16:29.00,Default,,0000,0000,0000,,just - I
Dialogue: 0,0:16:29.00,0:16:31.00,Default,,0000,0000,0000,,use that a lot in our demos, for example, for the maze, so that you can actually see what's
Dialogue: 0,0:16:31.00,0:16:35.00,Default,,0000,0000,0000,,going on, and that way it just animates a little more. Stenographics, CSTgraph.h. [Inaudible] me
Dialogue: 0,0:16:35.00,0:16:42.00,Default,,0000,0000,0000,,show you
Dialogue: 0,0:16:42.00,0:16:43.00,Default,,0000,0000,0000,,one more
Dialogue: 0,0:16:43.00,0:16:45.00,Default,,0000,0000,0000,,kind
Dialogue: 0,0:16:45.00,0:16:47.00,Default,,0000,0000,0000,,of just in the same theme. The idea of taking
Dialogue: 0,0:16:47.00,0:16:50.00,Default,,0000,0000,0000,,sort of some, you know, puzzle that somebody might give you,
Dialogue: 0,0:16:50.00,0:16:53.00,Default,,0000,0000,0000,,trying to cast it in terms of a decision problem, right, where you make decisions
Dialogue: 0,0:16:53.00,0:16:55.00,Default,,0000,0000,0000,,and then you move on,
Dialogue: 0,0:16:55.00,0:16:58.00,Default,,0000,0000,0000,,can I solve something like these little cryptographic puzzles?
Dialogue: 0,0:16:58.00,0:17:01.00,Default,,0000,0000,0000,,So here's send plus more equals money.
Dialogue: 0,0:17:01.00,0:17:03.00,Default,,0000,0000,0000,,I've got eight
Dialogue: 0,0:17:03.00,0:17:08.00,Default,,0000,0000,0000,,digits in there - eight letters in there. You know, D E M N O R S
Dialogue: 0,0:17:08.00,0:17:10.00,Default,,0000,0000,0000,,Y across all of them,
Dialogue: 0,0:17:10.00,0:17:13.00,Default,,0000,0000,0000,,and the goal of this puzzle is to assign these letters -
Dialogue: 0,0:17:13.00,0:17:17.00,Default,,0000,0000,0000,,eight letters to the digits zero through nine without replacement
Dialogue: 0,0:17:17.00,0:17:18.00,Default,,0000,0000,0000,,so that
Dialogue: 0,0:17:18.00,0:17:21.00,Default,,0000,0000,0000,,if D's assigned to three, it's assigned to three in all places. For example, O shows up
Dialogue: 0,0:17:21.00,0:17:24.00,Default,,0000,0000,0000,,two places in the puzzle. Both of those are either a two or both are three.
Dialogue: 0,0:17:24.00,0:17:27.00,Default,,0000,0000,0000,,There's not one that's one and one that's another. And each
Dialogue: 0,0:17:27.00,0:17:33.00,Default,,0000,0000,0000,,digit is used once. So, like, if I assigned two to O, then I will not assign two to D. So
Dialogue: 0,0:17:33.00,0:17:35.00,Default,,0000,0000,0000,,what we've got here is eight letters.
Dialogue: 0,0:17:35.00,0:17:38.00,Default,,0000,0000,0000,,We've got 10 digits.
Dialogue: 0,0:17:38.00,0:17:41.00,Default,,0000,0000,0000,,We want to make an assignment.
Dialogue: 0,0:17:41.00,0:17:44.00,Default,,0000,0000,0000,,What we've got here is some choices. The choices are,
Dialogue: 0,0:17:44.00,0:17:48.00,Default,,0000,0000,0000,,for each letter, what digit are we gonna map it to?
Dialogue: 0,0:17:48.00,0:17:51.00,Default,,0000,0000,0000,,Another way to think about it is if you took these eight letters, and then you
Dialogue: 0,0:17:51.00,0:17:53.00,Default,,0000,0000,0000,,attach two dashes on the end,
Dialogue: 0,0:17:53.00,0:17:56.00,Default,,0000,0000,0000,,then you considered that the letter's position in the string was - the index
Dialogue: 0,0:17:56.00,0:17:58.00,Default,,0000,0000,0000,,of it was its digit.
Dialogue: 0,0:17:58.00,0:18:00.00,Default,,0000,0000,0000,,It's really just like trying the permutations,
Dialogue: 0,0:18:00.00,0:18:02.00,Default,,0000,0000,0000,,right, rearranging those
Dialogue: 0,0:18:02.00,0:18:06.00,Default,,0000,0000,0000,,letters in any of those sequences. So right now, for example, maybe D is assigned
Dialogue: 0,0:18:06.00,0:18:09.00,Default,,0000,0000,0000,,zero, and one, and two, and so on, and these guys are eight, nine. Well, if
Dialogue: 0,0:18:09.00,0:18:12.00,Default,,0000,0000,0000,,you rearrange the letters into some other permutation then you've made a
Dialogue: 0,0:18:12.00,0:18:13.00,Default,,0000,0000,0000,,different assignment.
Dialogue: 0,0:18:13.00,0:18:16.00,Default,,0000,0000,0000,,So in effect, right, what you're looking at is a problem that has a lot in common with
Dialogue: 0,0:18:16.00,0:18:17.00,Default,,0000,0000,0000,,permutations, right?
Dialogue: 0,0:18:17.00,0:18:21.00,Default,,0000,0000,0000,,I'm gonna make an assignment, take a letter off, decide what index it's gonna
Dialogue: 0,0:18:21.00,0:18:24.00,Default,,0000,0000,0000,,be placed at, so it's kind of like deciding where it would go in the permutation,
Dialogue: 0,0:18:24.00,0:18:27.00,Default,,0000,0000,0000,,and then that leaves us with a smaller form of the problem
Dialogue: 0,0:18:27.00,0:18:30.00,Default,,0000,0000,0000,,which has one fewer letters to be assigned,
Dialogue: 0,0:18:30.00,0:18:33.00,Default,,0000,0000,0000,,and then recursively explore the options from there to see if we can make
Dialogue: 0,0:18:33.00,0:18:37.00,Default,,0000,0000,0000,,something that makes the addition add up correctly that D plus E equals Y
Dialogue: 0,0:18:37.00,0:18:37.00,Default,,0000,0000,0000,,means that
Dialogue: 0,0:18:37.00,0:18:39.00,Default,,0000,0000,0000,,if D was assigned five,
Dialogue: 0,0:18:39.00,0:18:43.00,Default,,0000,0000,0000,,and E was three, then Y better be eight for this to work out.
Dialogue: 0,0:18:43.00,0:18:47.00,Default,,0000,0000,0000,,So the first form I'm gonna show you is actually just the dumb,
Dialogue: 0,0:18:47.00,0:18:49.00,Default,,0000,0000,0000,,exhaustive recursive backtracking
Dialogue: 0,0:18:49.00,0:18:53.00,Default,,0000,0000,0000,,that works very much like the sudoku problem where it just - it finds the next unassigned
Dialogue: 0,0:18:53.00,0:18:57.00,Default,,0000,0000,0000,,letter, it assigns it a digit of the next auto sign digits, right, and then just
Dialogue: 0,0:18:57.00,0:18:59.00,Default,,0000,0000,0000,,optimistically figures that'll work out.
Dialogue: 0,0:18:59.00,0:19:02.00,Default,,0000,0000,0000,,After it makes an assignment for all the letters it says,
Dialogue: 0,0:19:02.00,0:19:07.00,Default,,0000,0000,0000,,take the puzzle, convert all the letters into their digit equivalents, and see if it adds
Dialogue: 0,0:19:07.00,0:19:08.00,Default,,0000,0000,0000,,together correctly.
Dialogue: 0,0:19:08.00,0:19:10.00,Default,,0000,0000,0000,,If so, we're done. If not,
Dialogue: 0,0:19:10.00,0:19:13.00,Default,,0000,0000,0000,,then let's backtrack.
Dialogue: 0,0:19:13.00,0:19:16.00,Default,,0000,0000,0000,,So let me - I mean, actually, I'll show you
Dialogue: 0,0:19:16.00,0:19:18.00,Default,,0000,0000,0000,,the code first
Dialogue: 0,0:19:18.00,0:19:20.00,Default,,0000,0000,0000,,because it's actually quite easy to
Dialogue: 0,0:19:20.00,0:19:21.00,Default,,0000,0000,0000,,take a look at.
Dialogue: 0,0:19:21.00,0:19:25.00,Default,,0000,0000,0000,,Again, it has helper routines that kind of
Dialogue: 0,0:19:25.00,0:19:29.00,Default,,0000,0000,0000,,try to abstract the pieces of the puzzle that actually aren't interesting
Dialogue: 0,0:19:29.00,0:19:31.00,Default,,0000,0000,0000,,from kind of looking at just the core of the recursive algorithm, so it looks a
Dialogue: 0,0:19:31.00,0:19:33.00,Default,,0000,0000,0000,,lot like sudoku
Dialogue: 0,0:19:33.00,0:19:36.00,Default,,0000,0000,0000,,in that if letters do assign, so it actually keeps the string of the letters that
Dialogue: 0,0:19:36.00,0:19:38.00,Default,,0000,0000,0000,,haven't yet been assigned.
Dialogue: 0,0:19:38.00,0:19:41.00,Default,,0000,0000,0000,,If there are no more letters in that string, we take one off at each time we
Dialogue: 0,0:19:41.00,0:19:42.00,Default,,0000,0000,0000,,assign it,
Dialogue: 0,0:19:42.00,0:19:45.00,Default,,0000,0000,0000,,then we check and see if the puzzle's solved. So that kind of does the substitution, and does
Dialogue: 0,0:19:45.00,0:19:48.00,Default,,0000,0000,0000,,the math, and comes back saying yes or no.
Dialogue: 0,0:19:48.00,0:19:50.00,Default,,0000,0000,0000,,
Dialogue: 0,0:19:50.00,0:19:53.00,Default,,0000,0000,0000,,If it worked out, we'll get a true. If it didn't work out we get a false.
Dialogue: 0,0:19:53.00,0:19:57.00,Default,,0000,0000,0000,,If we still have letters to assign then it goes through the process of making a choice, and
Dialogue: 0,0:19:57.00,0:19:59.00,Default,,0000,0000,0000,,that choice is looking at the
Dialogue: 0,0:19:59.00,0:20:00.00,Default,,0000,0000,0000,,
Dialogue: 0,0:20:00.00,0:20:04.00,Default,,0000,0000,0000,,digits zero through nine if we can assign it. So looking at that first letter in
Dialogue: 0,0:20:04.00,0:20:07.00,Default,,0000,0000,0000,,that digit, and then that's making sure that we don't already have an assignment for
Dialogue: 0,0:20:07.00,0:20:10.00,Default,,0000,0000,0000,,that letter, that we don't have an assignment for that digit. Sort of make sure that just the
Dialogue: 0,0:20:10.00,0:20:12.00,Default,,0000,0000,0000,,constraints of the problem are being met.
Dialogue: 0,0:20:12.00,0:20:14.00,Default,,0000,0000,0000,,If we're able to make that assignment
Dialogue: 0,0:20:14.00,0:20:16.00,Default,,0000,0000,0000,,then we go ahead and make a recursive call,
Dialogue: 0,0:20:16.00,0:20:18.00,Default,,0000,0000,0000,,having one fewer letters
Dialogue: 0,0:20:18.00,0:20:20.00,Default,,0000,0000,0000,,to make a decision for, and
Dialogue: 0,0:20:20.00,0:20:23.00,Default,,0000,0000,0000,,if that worked out true, otherwise we do an unassignment and come back around
Dialogue: 0,0:20:23.00,0:20:24.00,Default,,0000,0000,0000,,that loop
Dialogue: 0,0:20:24.00,0:20:27.00,Default,,0000,0000,0000,,and then eventually the same return false at the bottom, which said, well
Dialogue: 0,0:20:27.00,0:20:31.00,Default,,0000,0000,0000,,given the previous assignments of the letters before we got to this call,
Dialogue: 0,0:20:31.00,0:20:33.00,Default,,0000,0000,0000,,there was nothing I could do from here
Dialogue: 0,0:20:33.00,0:20:36.00,Default,,0000,0000,0000,,to make this work out. So
Dialogue: 0,0:20:36.00,0:20:40.00,Default,,0000,0000,0000,,let me show you this guy working because you're gonna see that it is actually
Dialogue: 0,0:20:40.00,0:20:42.00,Default,,0000,0000,0000,,a crazy way to try to solve this problem
Dialogue: 0,0:20:42.00,0:20:45.00,Default,,0000,0000,0000,,in terms of what you know about
Dialogue: 0,0:20:45.00,0:20:48.00,Default,,0000,0000,0000,,stuff. So I say C S plus U equals fun,
Dialogue: 0,0:20:48.00,0:20:54.00,Default,,0000,0000,0000,,a well-known equation.
Dialogue: 0,0:20:54.00,0:20:57.00,Default,,0000,0000,0000,,So I did this little animation to try to get you visualized what's going on at any
Dialogue: 0,0:20:57.00,0:20:59.00,Default,,0000,0000,0000,,given stage.
Dialogue: 0,0:20:59.00,0:21:00.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:21:00.00,0:21:03.00,Default,,0000,0000,0000,,it has the letters down across the bottom, S U N C O Y F.
Dialogue: 0,0:21:03.00,0:21:06.00,Default,,0000,0000,0000,,That's the string of letters to assign.
Dialogue: 0,0:21:06.00,0:21:08.00,Default,,0000,0000,0000,,It's gonna assign it the next available digit
Dialogue: 0,0:21:08.00,0:21:11.00,Default,,0000,0000,0000,,when it makes that recursive call, so the first recursive call is
Dialogue: 0,0:21:11.00,0:21:12.00,Default,,0000,0000,0000,,gonna be about assigning S,
Dialogue: 0,0:21:12.00,0:21:16.00,Default,,0000,0000,0000,,and then the next call will be assign U, and the next call - and so on. So it always
Dialogue: 0,0:21:16.00,0:21:18.00,Default,,0000,0000,0000,,gets up to seven deep
Dialogue: 0,0:21:18.00,0:21:19.00,Default,,0000,0000,0000,,on any particular thing.
Dialogue: 0,0:21:19.00,0:21:21.00,Default,,0000,0000,0000,,And so it says, okay, well
Dialogue: 0,0:21:21.00,0:21:25.00,Default,,0000,0000,0000,,first digit available is zero, go ahead and assign that to S. So it's gonna make a
Dialogue: 0,0:21:25.00,0:21:28.00,Default,,0000,0000,0000,,call there. And then it says, okay, well look at U. Well we can't use
Dialogue: 0,0:21:28.00,0:21:33.00,Default,,0000,0000,0000,,zero because zero's already in use. What don't we assign U to be one? Okay. Sounds good. Keep going. And
Dialogue: 0,0:21:33.00,0:21:36.00,Default,,0000,0000,0000,,then it'll say, okay, let's get to N. Let's make an assignment for N. It says I'll look around.
Dialogue: 0,0:21:36.00,0:21:40.00,Default,,0000,0000,0000,,Okay, well zero's in use, one's in use, how about two? Okay. Good.
Dialogue: 0,0:21:40.00,0:21:41.00,Default,,0000,0000,0000,,And then it assigns
Dialogue: 0,0:21:41.00,0:21:44.00,Default,,0000,0000,0000,,this to three, this to four, this to five,
Dialogue: 0,0:21:44.00,0:21:47.00,Default,,0000,0000,0000,,and this to six. Okay. It gets to here and it says,
Dialogue: 0,0:21:47.00,0:21:48.00,Default,,0000,0000,0000,,hey, does that work,
Dialogue: 0,0:21:48.00,0:21:50.00,Default,,0000,0000,0000,,30 plus 541 equals
Dialogue: 0,0:21:50.00,0:21:52.00,Default,,0000,0000,0000,,612? No?
Dialogue: 0,0:21:52.00,0:21:55.00,Default,,0000,0000,0000,,Okay. Well, you know what the problem was? It was F,
Dialogue: 0,0:21:55.00,0:22:01.00,Default,,0000,0000,0000,,right? I assigned F to six. How stupid of me. It can't be six. Let's make it seven.
Dialogue: 0,0:22:01.00,0:22:02.00,Default,,0000,0000,0000,,
Dialogue: 0,0:22:02.00,0:22:05.00,Default,,0000,0000,0000,,And then it says, oh, oh no, oh I'm sorry. I'm sorry, 30 plus 541 that's not
Dialogue: 0,0:22:05.00,0:22:07.00,Default,,0000,0000,0000,,712. How silly.
Dialogue: 0,0:22:07.00,0:22:09.00,Default,,0000,0000,0000,,I need to assign F to be eight.
Dialogue: 0,0:22:09.00,0:22:11.00,Default,,0000,0000,0000,,And it's gonna do this for a little while.
Dialogue: 0,0:22:11.00,0:22:12.00,Default,,0000,0000,0000,,A long while [inaudible].
Dialogue: 0,0:22:12.00,0:22:13.00,Default,,0000,0000,0000,,And then it says, oh, okay. Well,
Dialogue: 0,0:22:13.00,0:22:17.00,Default,,0000,0000,0000,,you know what, given the letters you'd assigned to the first six things, when you got to
Dialogue: 0,0:22:17.00,0:22:20.00,Default,,0000,0000,0000,,F, I tried everything I could and there was nothing I could do to fix this.
Dialogue: 0,0:22:20.00,0:22:23.00,Default,,0000,0000,0000,,You know what the problem was? It's not me. It's not me. I'm not the problem. You're the
Dialogue: 0,0:22:23.00,0:22:24.00,Default,,0000,0000,0000,,problem.
Dialogue: 0,0:22:24.00,0:22:26.00,Default,,0000,0000,0000,,So it returns false
Dialogue: 0,0:22:26.00,0:22:29.00,Default,,0000,0000,0000,,from this call at the bottom, having tried all its options,
Dialogue: 0,0:22:29.00,0:22:31.00,Default,,0000,0000,0000,,which causes Y to say, oh, yeah, yeah,
Dialogue: 0,0:22:31.00,0:22:36.00,Default,,0000,0000,0000,,I know. I know I said five. Did I said five? I didn't meant to say five. I meant to say six.
Dialogue: 0,0:22:36.00,0:22:39.00,Default,,0000,0000,0000,,And so it moves up to the six option.
Dialogue: 0,0:22:39.00,0:22:43.00,Default,,0000,0000,0000,,Again, optimistically saying that's good. Go for it. See what you can do.
Dialogue: 0,0:22:43.00,0:22:44.00,Default,,0000,0000,0000,,So it picks five.
Dialogue: 0,0:22:44.00,0:22:44.00,Default,,0000,0000,0000,,That won't work,
Dialogue: 0,0:22:44.00,0:22:46.00,Default,,0000,0000,0000,,right? It picks seven. It's gonna
Dialogue: 0,0:22:46.00,0:22:48.00,Default,,0000,0000,0000,,go for a long time, right, because it turns out, right,
Dialogue: 0,0:22:48.00,0:22:52.00,Default,,0000,0000,0000,,this is one of those cases where that very first decision, that was one of your problems,
Dialogue: 0,0:22:52.00,0:22:52.00,Default,,0000,0000,0000,,right?
Dialogue: 0,0:22:52.00,0:22:54.00,Default,,0000,0000,0000,,If you assign S to be zero,
Dialogue: 0,0:22:54.00,0:22:58.00,Default,,0000,0000,0000,,there's nothing you can assign U and N to be that are gonna work out.
Dialogue: 0,0:22:58.00,0:23:01.00,Default,,0000,0000,0000,,So what it's gonna be going through is this process though of
Dialogue: 0,0:23:01.00,0:23:05.00,Default,,0000,0000,0000,,having, you know, committed to this early decision and kind of moving on it's gonna try
Dialogue: 0,0:23:05.00,0:23:10.00,Default,,0000,0000,0000,,every other variation over here before it gives up on that. So let me
Dialogue: 0,0:23:10.00,0:23:13.00,Default,,0000,0000,0000,,
Dialogue: 0,0:23:13.00,0:23:16.00,Default,,0000,0000,0000,,set it to going.
Dialogue: 0,0:23:16.00,0:23:22.00,Default,,0000,0000,0000,,Even though C S plus U does equal fun. I guarantee it. We'll
Dialogue: 0,0:23:22.00,0:23:23.00,Default,,0000,0000,0000,,let it do some work for a while.
Dialogue: 0,0:23:23.00,0:23:26.00,Default,,0000,0000,0000,,So those bars is they grow up are desperation.
Dialogue: 0,0:23:26.00,0:23:29.00,Default,,0000,0000,0000,,You can think of that as, like, it's running out of options. It's running out of
Dialogue: 0,0:23:29.00,0:23:30.00,Default,,0000,0000,0000,,time, you know, and it's like oh,
Dialogue: 0,0:23:30.00,0:23:33.00,Default,,0000,0000,0000,,oh, wait, earlier, back up, back up. And so, okay, you can kind of see
Dialogue: 0,0:23:33.00,0:23:36.00,Default,,0000,0000,0000,,how far its backed up but sort of how tall
Dialogue: 0,0:23:36.00,0:23:40.00,Default,,0000,0000,0000,,some of the deeper recursive calls, right, the earlier ones in the sequence. And
Dialogue: 0,0:23:40.00,0:23:41.00,Default,,0000,0000,0000,,so
Dialogue: 0,0:23:41.00,0:23:44.00,Default,,0000,0000,0000,,it doesn't, you know, revisit any of these decisions because it's really busy over
Dialogue: 0,0:23:44.00,0:23:47.00,Default,,0000,0000,0000,,here, but you can see that C is now up to seven.
Dialogue: 0,0:23:47.00,0:23:49.00,Default,,0000,0000,0000,,It'll get up to eight. It'll get up to nine.
Dialogue: 0,0:23:49.00,0:23:52.00,Default,,0000,0000,0000,,And that was when it will cause itself to say, you know, I tried everything that was
Dialogue: 0,0:23:52.00,0:23:54.00,Default,,0000,0000,0000,,possible from C on down,
Dialogue: 0,0:23:54.00,0:23:58.00,Default,,0000,0000,0000,,and there was no way to make this thing work out. It must be that the bad
Dialogue: 0,0:23:58.00,0:24:00.00,Default,,0000,0000,0000,,decision was made earlier.
Dialogue: 0,0:24:00.00,0:24:04.00,Default,,0000,0000,0000,,Let's back up and look at that. And so it'll come back to the decision N,
Dialogue: 0,0:24:04.00,0:24:09.00,Default,,0000,0000,0000,,bump it up by one, and then go again. It's gonna do this a long time, right?
Dialogue: 0,0:24:09.00,0:24:12.00,Default,,0000,0000,0000,,Go through all the options for N and its neighbors before it comes back and revisits
Dialogue: 0,0:24:12.00,0:24:14.00,Default,,0000,0000,0000,,the U. It's gonna have to get U all the way up,
Dialogue: 0,0:24:14.00,0:24:18.00,Default,,0000,0000,0000,,right, through having tried one, two, three, four. So adding zero to one, and two, and three,
Dialogue: 0,0:24:18.00,0:24:19.00,Default,,0000,0000,0000,,and four,
Dialogue: 0,0:24:19.00,0:24:21.00,Default,,0000,0000,0000,,and discovering it can never make a match over there
Dialogue: 0,0:24:21.00,0:24:24.00,Default,,0000,0000,0000,,before it will eventually decide that the S
Dialogue: 0,0:24:24.00,0:24:25.00,Default,,0000,0000,0000,,is really where
Dialogue: 0,0:24:25.00,0:24:27.00,Default,,0000,0000,0000,,we got ourselves in trouble.
Dialogue: 0,0:24:27.00,0:24:29.00,Default,,0000,0000,0000,,So this is kind of in its most naive
Dialogue: 0,0:24:29.00,0:24:32.00,Default,,0000,0000,0000,,form, right? The recursive backtracking is doing basically permutations,
Dialogue: 0,0:24:32.00,0:24:34.00,Default,,0000,0000,0000,,right? You can see this is actually just
Dialogue: 0,0:24:34.00,0:24:37.00,Default,,0000,0000,0000,,permuting the digits as they're assigned to the numbers, and there are, in this
Dialogue: 0,0:24:37.00,0:24:41.00,Default,,0000,0000,0000,,case, you know, seven factorial different ways that we can make this assignment,
Dialogue: 0,0:24:41.00,0:24:45.00,Default,,0000,0000,0000,,and there are a lot of them that are wrong, right? It's not being at all clever
Dialogue: 0,0:24:45.00,0:24:46.00,Default,,0000,0000,0000,,about
Dialogue: 0,0:24:46.00,0:24:49.00,Default,,0000,0000,0000,,how to pick and choose among which to explore.
Dialogue: 0,0:24:49.00,0:24:51.00,Default,,0000,0000,0000,,So in
Dialogue: 0,0:24:51.00,0:24:52.00,Default,,0000,0000,0000,,its most naive form, right,
Dialogue: 0,0:24:52.00,0:24:54.00,Default,,0000,0000,0000,,recursive backtracking can be very expensive because often you're looking
Dialogue: 0,0:24:54.00,0:24:59.00,Default,,0000,0000,0000,,at things that have very high branching, and very long depth to them,
Dialogue: 0,0:24:59.00,0:25:02.00,Default,,0000,0000,0000,,which can add up to a lot of different things tried.
Dialogue: 0,0:25:02.00,0:25:04.00,Default,,0000,0000,0000,,Just using some simple - in this case, heuristics,
Dialogue: 0,0:25:04.00,0:25:08.00,Default,,0000,0000,0000,,sort of information you know about the domain
Dialogue: 0,0:25:08.00,0:25:11.00,Default,,0000,0000,0000,,can help you to guide your choices instead of just making the choices in order, trying the
Dialogue: 0,0:25:11.00,0:25:14.00,Default,,0000,0000,0000,,numbers zero through nine as though they're equally likely,
Dialogue: 0,0:25:14.00,0:25:16.00,Default,,0000,0000,0000,,or
Dialogue: 0,0:25:16.00,0:25:19.00,Default,,0000,0000,0000,,kind of waiting to make all the assignments before you look at
Dialogue: 0,0:25:19.00,0:25:21.00,Default,,0000,0000,0000,,anything to see if it's actually good. There's actually some ways we can kind of
Dialogue: 0,0:25:21.00,0:25:24.00,Default,,0000,0000,0000,,shape our decision making to look at the most likely options before we look at
Dialogue: 0,0:25:24.00,0:25:26.00,Default,,0000,0000,0000,,these more
Dialogue: 0,0:25:26.00,0:25:30.00,Default,,0000,0000,0000,,first. Finding the problem instead of niggling around this dead end.
Dialogue: 0,0:25:30.00,0:25:33.00,Default,,0000,0000,0000,,So I'm gonna let that guy work for a little bit
Dialogue: 0,0:25:33.00,0:25:34.00,Default,,0000,0000,0000,,while I
Dialogue: 0,0:25:34.00,0:25:36.00,Default,,0000,0000,0000,,show you another slide over here.
Dialogue: 0,0:25:36.00,0:25:39.00,Default,,0000,0000,0000,,So what the smarter solver does,
Dialogue: 0,0:25:39.00,0:25:43.00,Default,,0000,0000,0000,,is that it doesn't really consider all permutations equally plausible. We're
Dialogue: 0,0:25:43.00,0:25:47.00,Default,,0000,0000,0000,,gonna use a little grade school addition knowledge. If I look at the rightmost column, the
Dialogue: 0,0:25:47.00,0:25:49.00,Default,,0000,0000,0000,,least significant digit,
Dialogue: 0,0:25:49.00,0:25:51.00,Default,,0000,0000,0000,,I'm gonna assign D first.
Dialogue: 0,0:25:51.00,0:25:52.00,Default,,0000,0000,0000,,I assign D to zero. I assign
Dialogue: 0,0:25:52.00,0:25:53.00,Default,,0000,0000,0000,,E to one,
Dialogue: 0,0:25:53.00,0:25:54.00,Default,,0000,0000,0000,,and then I look at Y -
Dialogue: 0,0:25:54.00,0:25:59.00,Default,,0000,0000,0000,,I don't try Y is five, or seven, or anything like that. I say there's
Dialogue: 0,0:25:59.00,0:26:01.00,Default,,0000,0000,0000,,exactly one thing Y has to be, right, if
Dialogue: 0,0:26:01.00,0:26:04.00,Default,,0000,0000,0000,,D is zero and E is one, then Y has to be one, and I can say, well that won't work
Dialogue: 0,0:26:04.00,0:26:06.00,Default,,0000,0000,0000,,because I already used one for E.
Dialogue: 0,0:26:06.00,0:26:07.00,Default,,0000,0000,0000,,So it'll say,
Dialogue: 0,0:26:07.00,0:26:10.00,Default,,0000,0000,0000,,well that's impossible. Something must be wrong
Dialogue: 0,0:26:10.00,0:26:13.00,Default,,0000,0000,0000,,early. Rather than keep going on this kind of dumb
Dialogue: 0,0:26:13.00,0:26:15.00,Default,,0000,0000,0000,,dead end, it's to realize right away
Dialogue: 0,0:26:15.00,0:26:18.00,Default,,0000,0000,0000,,that one of the decisions I've already made, D and E, has gotta be wrong. So it'll back up
Dialogue: 0,0:26:18.00,0:26:22.00,Default,,0000,0000,0000,,to E. It'll try two, three, four, very quickly realizing
Dialogue: 0,0:26:22.00,0:26:25.00,Default,,0000,0000,0000,,that of all the things you could assign to E, once you have assigned D to
Dialogue: 0,0:26:25.00,0:26:29.00,Default,,0000,0000,0000,,zero, you're in trouble. And so it will quickly unmake that decision about D and work its way
Dialogue: 0,0:26:29.00,0:26:30.00,Default,,0000,0000,0000,,down.
Dialogue: 0,0:26:30.00,0:26:34.00,Default,,0000,0000,0000,,So using the kind of structure of the problem. So it makes it a little bit more
Dialogue: 0,0:26:34.00,0:26:37.00,Default,,0000,0000,0000,,housekeeping about where I'm at, and what I'm doing, and
Dialogue: 0,0:26:37.00,0:26:37.00,Default,,0000,0000,0000,,
Dialogue: 0,0:26:37.00,0:26:38.00,Default,,0000,0000,0000,,what's going on,
Dialogue: 0,0:26:38.00,0:26:43.00,Default,,0000,0000,0000,,but it is using some real smarts about what part of the tree to explore,
Dialogue: 0,0:26:43.00,0:26:45.00,Default,,0000,0000,0000,,rather than letting it kind of just go
Dialogue: 0,0:26:45.00,0:26:49.00,Default,,0000,0000,0000,,willy nilly across the whole thing. Let me get that
Dialogue: 0,0:26:49.00,0:26:52.00,Default,,0000,0000,0000,,out of the way. And I'll
Dialogue: 0,0:26:52.00,0:27:00.00,Default,,0000,0000,0000,,run this one. I say C S plus U equals fun. Okay.
Dialogue: 0,0:27:00.00,0:27:03.00,Default,,0000,0000,0000,,So it goes zero here, and
Dialogue: 0,0:27:03.00,0:27:04.00,Default,,0000,0000,0000,,tries the one, and it
Dialogue: 0,0:27:04.00,0:27:06.00,Default,,0000,0000,0000,,says no, that won't work. How about the two?
Dialogue: 0,0:27:06.00,0:27:09.00,Default,,0000,0000,0000,,No, that won't work, right, because there's nothing you can assign the N that'll
Dialogue: 0,0:27:09.00,0:27:13.00,Default,,0000,0000,0000,,make this work. And so it immediately is kind of failing on this,
Dialogue: 0,0:27:13.00,0:27:16.00,Default,,0000,0000,0000,,and even after it tries kind of all nine of these, it
Dialogue: 0,0:27:16.00,0:27:18.00,Default,,0000,0000,0000,,says none of these are looking good,
Dialogue: 0,0:27:18.00,0:27:22.00,Default,,0000,0000,0000,,then it comes back to this decision and says, no, no, actually, S's a zero. That wasn't so
Dialogue: 0,0:27:22.00,0:27:24.00,Default,,0000,0000,0000,,hot. How about we try S as one?
Dialogue: 0,0:27:24.00,0:27:27.00,Default,,0000,0000,0000,,And then kind of works its way
Dialogue: 0,0:27:27.00,0:27:32.00,Default,,0000,0000,0000,,further down.
Dialogue: 0,0:27:32.00,0:27:34.00,Default,,0000,0000,0000,,Hello? Okay. So let me try this again. Let me get it
Dialogue: 0,0:27:34.00,0:27:40.00,Default,,0000,0000,0000,,to just go. Okay.
Dialogue: 0,0:27:40.00,0:27:42.00,Default,,0000,0000,0000,,So it took 30 assignments
Dialogue: 0,0:27:42.00,0:27:44.00,Default,,0000,0000,0000,,- 30 different things it tried
Dialogue: 0,0:27:44.00,0:27:47.00,Default,,0000,0000,0000,,before it was able to come up with 41 plus 582 equals 623,
Dialogue: 0,0:27:47.00,0:27:49.00,Default,,0000,0000,0000,,which does add correctly.
Dialogue: 0,0:27:49.00,0:27:53.00,Default,,0000,0000,0000,,It didn't have to unmake once it decided that S was one. It turns out that was a
Dialogue: 0,0:27:53.00,0:27:57.00,Default,,0000,0000,0000,,workable solution so it didn't have to go very far once it made that commitment,
Dialogue: 0,0:27:57.00,0:27:59.00,Default,,0000,0000,0000,,and then you can see it kind of working its way up.
Dialogue: 0,0:27:59.00,0:28:03.00,Default,,0000,0000,0000,,So 30 assignments, right, across this tree that has, you know,
Dialogue: 0,0:28:03.00,0:28:05.00,Default,,0000,0000,0000,,hundreds of thousands in the factorial, very large number,
Dialogue: 0,0:28:05.00,0:28:08.00,Default,,0000,0000,0000,,but very quickly kind of pruning down those things that aren't worth looking
Dialogue: 0,0:28:08.00,0:28:09.00,Default,,0000,0000,0000,,at, and
Dialogue: 0,0:28:09.00,0:28:12.00,Default,,0000,0000,0000,,so focusing its attention on those things that are more likely to
Dialogue: 0,0:28:12.00,0:28:14.00,Default,,0000,0000,0000,,work out using information about the problem.
Dialogue: 0,0:28:14.00,0:28:17.00,Default,,0000,0000,0000,,It doesn't really change what the recursion does. It's kind of interesting if you
Dialogue: 0,0:28:17.00,0:28:20.00,Default,,0000,0000,0000,,think that the same backtracking and recursive strategy's the same in all these
Dialogue: 0,0:28:20.00,0:28:23.00,Default,,0000,0000,0000,,problems, but what you're trying to do is pick your options, like,
Dialogue: 0,0:28:23.00,0:28:24.00,Default,,0000,0000,0000,,looking at the choices you have
Dialogue: 0,0:28:24.00,0:28:28.00,Default,,0000,0000,0000,,and trying to decide what are the more likely ones, which ones are not worth trying, right, so
Dialogue: 0,0:28:28.00,0:28:29.00,Default,,0000,0000,0000,,sort of directing
Dialogue: 0,0:28:29.00,0:28:32.00,Default,,0000,0000,0000,,your decision making
Dialogue: 0,0:28:32.00,0:28:33.00,Default,,0000,0000,0000,,from the
Dialogue: 0,0:28:33.00,0:28:36.00,Default,,0000,0000,0000,,standpoint of trying to make sure you don't violate constraints that later will come
Dialogue: 0,0:28:36.00,0:28:38.00,Default,,0000,0000,0000,,back to bite you, and things like that.
Dialogue: 0,0:28:38.00,0:28:40.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:40.00,0:28:41.00,Default,,0000,0000,0000,,This one's back here.
Dialogue: 0,0:28:41.00,0:28:43.00,Default,,0000,0000,0000,,It's at
Dialogue: 0,0:28:43.00,0:28:47.00,Default,,0000,0000,0000,,13,000 and working hard. Getting desperate. Doing its thing. Still has not unmade the
Dialogue: 0,0:28:47.00,0:28:52.00,Default,,0000,0000,0000,,decision about S is zero, so you can get an idea of how much longer it's gonna take. We'll
Dialogue: 0,0:28:52.00,0:28:53.00,Default,,0000,0000,0000,,just let it keep going.
Dialogue: 0,0:28:53.00,0:28:55.00,Default,,0000,0000,0000,,I'm in no hurry - and let
Dialogue: 0,0:28:55.00,0:28:56.00,Default,,0000,0000,0000,,it
Dialogue: 0,0:28:56.00,0:29:07.00,Default,,0000,0000,0000,,do its thing.
Dialogue: 0,0:29:07.00,0:29:11.00,Default,,0000,0000,0000,,So let me - before I move away from talking about recursion, just try
Dialogue: 0,0:29:11.00,0:29:12.00,Default,,0000,0000,0000,,
Dialogue: 0,0:29:12.00,0:29:15.00,Default,,0000,0000,0000,,to get you thinking just a little bit about how the patterns we're seeing,
Dialogue: 0,0:29:15.00,0:29:16.00,Default,,0000,0000,0000,,right,
Dialogue: 0,0:29:16.00,0:29:18.00,Default,,0000,0000,0000,,are more alike than they are different.
Dialogue: 0,0:29:18.00,0:29:21.00,Default,,0000,0000,0000,,That solving a sudoku, solving the eight queens,
Dialogue: 0,0:29:21.00,0:29:26.00,Default,,0000,0000,0000,,you know, solving the find an anagram in a sequence of letters, that
Dialogue: 0,0:29:26.00,0:29:31.00,Default,,0000,0000,0000,,they all have this general idea of there being these decisions that you're making,
Dialogue: 0,0:29:31.00,0:29:33.00,Default,,0000,0000,0000,,and you're working your way down to where there's, you know
Dialogue: 0,0:29:33.00,0:29:37.00,Default,,0000,0000,0000,,- fewer and fewer of those decisions until eventually you end up, sort of, okay, I'm done. I've
Dialogue: 0,0:29:37.00,0:29:41.00,Default,,0000,0000,0000,,made all the decisions I can. What letter goes next, or whether something goes in or out.
Dialogue: 0,0:29:41.00,0:29:44.00,Default,,0000,0000,0000,,And the two problems that I call the kind of master or mother problems,
Dialogue: 0,0:29:44.00,0:29:46.00,Default,,0000,0000,0000,,right, of permutations and subsets
Dialogue: 0,0:29:46.00,0:29:49.00,Default,,0000,0000,0000,,are kind of fundamental to
Dialogue: 0,0:29:49.00,0:29:52.00,Default,,0000,0000,0000,,adapting them to these other domains. And so I'm gonna give you a couple
Dialogue: 0,0:29:52.00,0:29:55.00,Default,,0000,0000,0000,,examples of some things that come up that actually are just kind of permutations,
Dialogue: 0,0:29:55.00,0:29:58.00,Default,,0000,0000,0000,,or subsets, or some variation that you can help me think about a little bit.
Dialogue: 0,0:29:58.00,0:30:03.00,Default,,0000,0000,0000,,One that the CS people are fond of is this idea of knapsack feeling.
Dialogue: 0,0:30:03.00,0:30:07.00,Default,,0000,0000,0000,,It's often cast as someone breaking into your house. All criminals at
Dialogue: 0,0:30:07.00,0:30:09.00,Default,,0000,0000,0000,,heart apparently in computer science.
Dialogue: 0,0:30:09.00,0:30:12.00,Default,,0000,0000,0000,,And you've got this sack, and you can put 50 pounds of stuff in it,
Dialogue: 0,0:30:12.00,0:30:15.00,Default,,0000,0000,0000,,right, and you're looking around, you know, at all the stuff that's
Dialogue: 0,0:30:15.00,0:30:18.00,Default,,0000,0000,0000,,up for grabs in this house that you've broken into,
Dialogue: 0,0:30:18.00,0:30:22.00,Default,,0000,0000,0000,,and you want to try to pack your sack, right, so that you've got 50 pounds of the high value
Dialogue: 0,0:30:22.00,0:30:23.00,Default,,0000,0000,0000,,stuff.
Dialogue: 0,0:30:23.00,0:30:26.00,Default,,0000,0000,0000,,So let's say there's, like, 100 things, right, you could pick up, right,
Dialogue: 0,0:30:26.00,0:30:29.00,Default,,0000,0000,0000,,and they weigh different amounts, and they're worth different amounts.
Dialogue: 0,0:30:29.00,0:30:33.00,Default,,0000,0000,0000,,What's the strategy for going about finding the optimal
Dialogue: 0,0:30:33.00,0:30:35.00,Default,,0000,0000,0000,,combination of things to stick into your sack, right,
Dialogue: 0,0:30:35.00,0:30:38.00,Default,,0000,0000,0000,,so that you got the maximum value from your heist?
Dialogue: 0,0:30:38.00,0:30:44.00,Default,,0000,0000,0000,,What problem does that look like that you've seen?
Dialogue: 0,0:30:44.00,0:30:47.00,Default,,0000,0000,0000,,It's a subset. It's a subset. [Inaudible].
Dialogue: 0,0:30:47.00,0:30:48.00,Default,,0000,0000,0000,,Right? So if you look at the,
Dialogue: 0,0:30:48.00,0:30:52.00,Default,,0000,0000,0000,,you know, the Wii, and you say, oh, should I take the Wii? You know, it weighs this much, and it's this much
Dialogue: 0,0:30:52.00,0:30:53.00,Default,,0000,0000,0000,,value, well
Dialogue: 0,0:30:53.00,0:30:56.00,Default,,0000,0000,0000,,let's try it in and see what happens, right, and see what else I can stuff in the sack with
Dialogue: 0,0:30:56.00,0:30:59.00,Default,,0000,0000,0000,,that, right, and then see how well that works out. I should also try it with it out.
Dialogue: 0,0:30:59.00,0:31:02.00,Default,,0000,0000,0000,,So while you're standing there trying to decide what to
Dialogue: 0,0:31:02.00,0:31:05.00,Default,,0000,0000,0000,,steal, you have to type in all the values of things in every computer program.
Dialogue: 0,0:31:05.00,0:31:08.00,Default,,0000,0000,0000,,Go through the kind of machinations of well, try this with that because some things
Dialogue: 0,0:31:08.00,0:31:10.00,Default,,0000,0000,0000,,are big, but have a lot of value,
Dialogue: 0,0:31:10.00,0:31:13.00,Default,,0000,0000,0000,,but they only leave a little bit of odd space left over you might not be able to
Dialogue: 0,0:31:13.00,0:31:15.00,Default,,0000,0000,0000,,use well, or something.
Dialogue: 0,0:31:15.00,0:31:18.00,Default,,0000,0000,0000,,But what we're looking for is the optimal combination, the optimal subset. So
Dialogue: 0,0:31:18.00,0:31:21.00,Default,,0000,0000,0000,,trying the different subsets tells you how much value and weight
Dialogue: 0,0:31:21.00,0:31:25.00,Default,,0000,0000,0000,,you can get in a combination, and then you're looking for that best value you can get.
Dialogue: 0,0:31:25.00,0:31:27.00,Default,,0000,0000,0000,,You're the traveling salesman.
Dialogue: 0,0:31:27.00,0:31:29.00,Default,,0000,0000,0000,,You've got 10 cities to visit.
Dialogue: 0,0:31:29.00,0:31:33.00,Default,,0000,0000,0000,,Boston, New York, Phoenix, Minneapolis, right?
Dialogue: 0,0:31:33.00,0:31:36.00,Default,,0000,0000,0000,,You want to cover them in such a way that you spend the minimal amount of time,
Dialogue: 0,0:31:36.00,0:31:40.00,Default,,0000,0000,0000,,you know, in painful air travel across the U.S. Well you certainly don't want to be
Dialogue: 0,0:31:40.00,0:31:41.00,Default,,0000,0000,0000,,going
Dialogue: 0,0:31:41.00,0:31:47.00,Default,,0000,0000,0000,,Boston, New York, right, like, Boston, to L.A., to New York, to Seattle, to
Dialogue: 0,0:31:47.00,0:31:48.00,Default,,0000,0000,0000,,D.C.,
Dialogue: 0,0:31:48.00,0:31:51.00,Default,,0000,0000,0000,,to Los Angeles back and forth, right? There's gotta be a pattern where you
Dialogue: 0,0:31:51.00,0:31:55.00,Default,,0000,0000,0000,,kind of visit the close cities and work your way to the far cities to kind of
Dialogue: 0,0:31:55.00,0:31:58.00,Default,,0000,0000,0000,,minimize your total distance overall.
Dialogue: 0,0:31:58.00,0:32:02.00,Default,,0000,0000,0000,,What problem was that really in disguise? We've
Dialogue: 0,0:32:02.00,0:32:06.00,Default,,0000,0000,0000,,got 10 cities. What are you trying to do?
Dialogue: 0,0:32:06.00,0:32:08.00,Default,,0000,0000,0000,,Help me out a little. I hear it almost. Louder.
Dialogue: 0,0:32:08.00,0:32:12.00,Default,,0000,0000,0000,,Permutations. You've got a permutation problem there, all right?
Dialogue: 0,0:32:12.00,0:32:14.00,Default,,0000,0000,0000,,You got 10 cities. They all have to show up,
Dialogue: 0,0:32:14.00,0:32:17.00,Default,,0000,0000,0000,,right? And it's a permutation. Where do you start, where do you end, where do you go in the
Dialogue: 0,0:32:17.00,0:32:20.00,Default,,0000,0000,0000,,middle, right? What sequencing, right, do you need to take?
Dialogue: 0,0:32:20.00,0:32:21.00,Default,,0000,0000,0000,,So what you're looking at is
Dialogue: 0,0:32:21.00,0:32:24.00,Default,,0000,0000,0000,,try the permutations, tell me which ones come up short.
Dialogue: 0,0:32:24.00,0:32:27.00,Default,,0000,0000,0000,,There are things, right, about heuristics that can help this, right?
Dialogue: 0,0:32:27.00,0:32:28.00,Default,,0000,0000,0000,,So the idea that
Dialogue: 0,0:32:28.00,0:32:31.00,Default,,0000,0000,0000,,certainly, like, the ones that are closer to you are likely to make a better
Dialogue: 0,0:32:31.00,0:32:33.00,Default,,0000,0000,0000,,choice than the longer one. So kind of using
Dialogue: 0,0:32:33.00,0:32:36.00,Default,,0000,0000,0000,,some information about the problem can help you decide which ones are more
Dialogue: 0,0:32:36.00,0:32:40.00,Default,,0000,0000,0000,,promising avenues to explore. But in the end it's a permutation problem.
Dialogue: 0,0:32:40.00,0:32:43.00,Default,,0000,0000,0000,,I'm trying to divide you guys into fair teams. I want to, you know, divide you up into
Dialogue: 0,0:32:43.00,0:32:46.00,Default,,0000,0000,0000,,10 teams to have a kind of head-to-head programming competition. I happen to know
Dialogue: 0,0:32:46.00,0:32:48.00,Default,,0000,0000,0000,,all your Iqs.
Dialogue: 0,0:32:48.00,0:32:50.00,Default,,0000,0000,0000,,I don't know. Some other, you know, useless fact that
Dialogue: 0,0:32:50.00,0:32:53.00,Default,,0000,0000,0000,,perhaps we could use as some judge of your worth.
Dialogue: 0,0:32:53.00,0:32:54.00,Default,,0000,0000,0000,,
Dialogue: 0,0:32:54.00,0:32:58.00,Default,,0000,0000,0000,,And I want to make sure that each time has kind of
Dialogue: 0,0:32:58.00,0:33:01.00,Default,,0000,0000,0000,,a fair amount of IQ power in it
Dialogue: 0,0:33:01.00,0:33:03.00,Default,,0000,0000,0000,,relative to the others that I didn't put,
Dialogue: 0,0:33:03.00,0:33:09.00,Default,,0000,0000,0000,,you know, all the superstars on one team. What am I doing? How do
Dialogue: 0,0:33:09.00,0:33:12.00,Default,,0000,0000,0000,,I divide you guys up? It's a subset problem, right? So
Dialogue: 0,0:33:12.00,0:33:14.00,Default,,0000,0000,0000,,if -
Dialogue: 0,0:33:14.00,0:33:17.00,Default,,0000,0000,0000,,in this case it's a subset that's not just in or out. It's like which team am I gonna
Dialogue: 0,0:33:17.00,0:33:21.00,Default,,0000,0000,0000,,put you in? So I've got 10 subsets to build. But in the end it's an in out
Dialogue: 0,0:33:21.00,0:33:22.00,Default,,0000,0000,0000,,problem that looks like, well,
Dialogue: 0,0:33:22.00,0:33:23.00,Default,,0000,0000,0000,,I have the next student.
Dialogue: 0,0:33:23.00,0:33:27.00,Default,,0000,0000,0000,,Which of the 10 teams can I try them in? I can try them in each of them, right? So
Dialogue: 0,0:33:27.00,0:33:30.00,Default,,0000,0000,0000,,in some sense it's trying in the first team, the second team, the third team,
Dialogue: 0,0:33:30.00,0:33:32.00,Default,,0000,0000,0000,,right, and then pull the next student, try him in those teams,
Dialogue: 0,0:33:32.00,0:33:35.00,Default,,0000,0000,0000,,and then see whether I can come up with something that appears to get a balance ratio when I'm
Dialogue: 0,0:33:35.00,0:33:37.00,Default,,0000,0000,0000,,done.
Dialogue: 0,0:33:37.00,0:33:41.00,Default,,0000,0000,0000,,It turns out you can take the letters from Richard Millhouse Dickson and you can
Dialogue: 0,0:33:41.00,0:33:44.00,Default,,0000,0000,0000,,extract and rearrange them to spell the word criminal. I
Dialogue: 0,0:33:44.00,0:33:48.00,Default,,0000,0000,0000,,am making no conclusion about anything, having done that,
Dialogue: 0,0:33:48.00,0:33:48.00,Default,,0000,0000,0000,,just
Dialogue: 0,0:33:48.00,0:33:50.00,Default,,0000,0000,0000,,an observation of fact.
Dialogue: 0,0:33:50.00,0:33:51.00,Default,,0000,0000,0000,,
Dialogue: 0,0:33:51.00,0:33:55.00,Default,,0000,0000,0000,,But that sort of process, right, I'm trying to find, well what is the longest word
Dialogue: 0,0:33:55.00,0:33:58.00,Default,,0000,0000,0000,,that you can extract from a sequence of letters?
Dialogue: 0,0:33:58.00,0:34:05.00,Default,,0000,0000,0000,,What kind of things is it using?
Dialogue: 0,0:34:05.00,0:34:13.00,Default,,0000,0000,0000,,Anything you've seen before?
Dialogue: 0,0:34:13.00,0:34:18.00,Default,,0000,0000,0000,,Oh, somebody come on. I hear the whispering but no one wants to just stand up and be
Dialogue: 0,0:34:18.00,0:34:20.00,Default,,0000,0000,0000,,committed.
Dialogue: 0,0:34:20.00,0:34:23.00,Default,,0000,0000,0000,,How about
Dialogue: 0,0:34:23.00,0:34:24.00,Default,,0000,0000,0000,,a
Dialogue: 0,0:34:24.00,0:34:27.00,Default,,0000,0000,0000,,little of both, right? The what? Like the sudoku puzzle? It's a little bit like the sudoku, right? It's got a permutation sort of backing, and it's got a little bit of
Dialogue: 0,0:34:27.00,0:34:29.00,Default,,0000,0000,0000,,a subset backing, right? That is that
Dialogue: 0,0:34:29.00,0:34:32.00,Default,,0000,0000,0000,,I'm not choosing all the letters from this. And in fact there's a subset process,
Dialogue: 0,0:34:32.00,0:34:35.00,Default,,0000,0000,0000,,which is deciding whether it's in or out, and then there's a permutation problem,
Dialogue: 0,0:34:35.00,0:34:37.00,Default,,0000,0000,0000,,which is actually rearranging them, right?
Dialogue: 0,0:34:37.00,0:34:40.00,Default,,0000,0000,0000,,That picking the C, and the R, and the I, and the M, and then kind of rearranging them. So in fact it
Dialogue: 0,0:34:40.00,0:34:44.00,Default,,0000,0000,0000,,has kind of a little bit of both, right? Which is what sequence of letters can I
Dialogue: 0,0:34:44.00,0:34:46.00,Default,,0000,0000,0000,,extract and then rearrange to make a word - would
Dialogue: 0,0:34:46.00,0:34:50.00,Default,,0000,0000,0000,,end up using kind of elements of both of those kinds of recursions sort of
Dialogue: 0,0:34:50.00,0:34:51.00,Default,,0000,0000,0000,,mixed together
Dialogue: 0,0:34:51.00,0:34:55.00,Default,,0000,0000,0000,,so that when you look at a lot of recursion problems, they end up actually just mapping down to
Dialogue: 0,0:34:55.00,0:34:59.00,Default,,0000,0000,0000,,one or the other, or maybe a little bit of both. And so feeling very comfortable with
Dialogue: 0,0:34:59.00,0:35:00.00,Default,,0000,0000,0000,,those problems,
Dialogue: 0,0:35:00.00,0:35:03.00,Default,,0000,0000,0000,,how you turn them into a recursive backtracker,
Dialogue: 0,0:35:03.00,0:35:05.00,Default,,0000,0000,0000,,and how you can recognize, right,
Dialogue: 0,0:35:05.00,0:35:08.00,Default,,0000,0000,0000,,their roots inside these other problems, it's kind of a really good first step to
Dialogue: 0,0:35:08.00,0:35:12.00,Default,,0000,0000,0000,,becoming kind of a journeyman, in a way, or recursion.
Dialogue: 0,0:35:12.00,0:35:14.00,Default,,0000,0000,0000,,So just whenever you see a new problem you start thinking, okay,
Dialogue: 0,0:35:14.00,0:35:17.00,Default,,0000,0000,0000,,is it permutations? Is it subset? Or is it something totally new?
Dialogue: 0,0:35:17.00,0:35:21.00,Default,,0000,0000,0000,,It's probably much more likely to be the first two then the third, and so
Dialogue: 0,0:35:21.00,0:35:24.00,Default,,0000,0000,0000,,trying to use the ones that you feel really comfortable with to kind of branch
Dialogue: 0,0:35:24.00,0:35:25.00,Default,,0000,0000,0000,,out to solve
Dialogue: 0,0:35:25.00,0:35:29.00,Default,,0000,0000,0000,,similar problems, right, where the domain is a little different - the structure
Dialogue: 0,0:35:29.00,0:35:35.00,Default,,0000,0000,0000,,of the code is still very much the same. All right.
Dialogue: 0,0:35:35.00,0:35:37.00,Default,,0000,0000,0000,,I've got 10 minutes to teach you about pointers.
Dialogue: 0,0:35:37.00,0:35:39.00,Default,,0000,0000,0000,,This should be no problem. Let's
Dialogue: 0,0:35:39.00,0:35:42.00,Default,,0000,0000,0000,,go see what that guy back there's doing. Oh, look at
Dialogue: 0,0:35:42.00,0:35:47.00,Default,,0000,0000,0000,,that, 38,000 assignments, still has not given up on that S is zero.
Dialogue: 0,0:35:47.00,0:35:53.00,Default,,0000,0000,0000,,It's a trooper. Okay.
Dialogue: 0,0:35:53.00,0:35:57.00,Default,,0000,0000,0000,,So this is definitely gonna be your first introduction on kind of the first
Dialogue: 0,0:35:57.00,0:36:01.00,Default,,0000,0000,0000,,day of talking about this. This is not the only day. So
Dialogue: 0,0:36:01.00,0:36:03.00,Default,,0000,0000,0000,,don't get to worried about me trying to do it in 10 minutes. What I'm gonna do is give you
Dialogue: 0,0:36:03.00,0:36:07.00,Default,,0000,0000,0000,,the kind of - a little bit of the basics today, and we're gonna follow up with
Dialogue: 0,0:36:07.00,0:36:10.00,Default,,0000,0000,0000,,some more stuff tomorrow where we start kind of making use of them and doing something
Dialogue: 0,0:36:10.00,0:36:11.00,Default,,0000,0000,0000,,kind of interesting with them.
Dialogue: 0,0:36:11.00,0:36:13.00,Default,,0000,0000,0000,,So there is this notion
Dialogue: 0,0:36:13.00,0:36:17.00,Default,,0000,0000,0000,,in C++, which is inherited from the C language in fact,
Dialogue: 0,0:36:17.00,0:36:20.00,Default,,0000,0000,0000,,of using a variable type called a pointer
Dialogue: 0,0:36:20.00,0:36:22.00,Default,,0000,0000,0000,,as part of the things that you operate on.
Dialogue: 0,0:36:22.00,0:36:26.00,Default,,0000,0000,0000,,Okay. People tend to have a lot of trepidation. Just the word pointer causes a little bit
Dialogue: 0,0:36:26.00,0:36:28.00,Default,,0000,0000,0000,,of fear, kind of
Dialogue: 0,0:36:28.00,0:36:30.00,Default,,0000,0000,0000,,to immediately rise in a new programmer.
Dialogue: 0,0:36:30.00,0:36:34.00,Default,,0000,0000,0000,,But hopefully we can demystify a little bit, and then also get a little bit of understanding
Dialogue: 0,0:36:34.00,0:36:38.00,Default,,0000,0000,0000,,of why there are reasons to be a little bit
Dialogue: 0,0:36:38.00,0:36:40.00,Default,,0000,0000,0000,,wary of working with pointers.
Dialogue: 0,0:36:40.00,0:36:42.00,Default,,0000,0000,0000,,A pointer is actually an address.
Dialogue: 0,0:36:42.00,0:36:45.00,Default,,0000,0000,0000,,So here's a couple things we have to kind of think about a little bit how the
Dialogue: 0,0:36:45.00,0:36:48.00,Default,,0000,0000,0000,,machine works to have a vision of what's going on here,
Dialogue: 0,0:36:48.00,0:36:52.00,Default,,0000,0000,0000,,that when you declare variables, you
Dialogue: 0,0:36:52.00,0:36:54.00,Default,,0000,0000,0000,,know, here I am in main.
Dialogue: 0,0:36:54.00,0:36:56.00,Default,,0000,0000,0000,,
Dialogue: 0,0:36:56.00,0:36:58.00,Default,,0000,0000,0000,,And I declare,
Dialogue: 0,0:36:58.00,0:37:02.00,Default,,0000,0000,0000,,you know, int Num,
Dialogue: 0,0:37:02.00,0:37:04.00,Default,,0000,0000,0000,,and string S,
Dialogue: 0,0:37:04.00,0:37:05.00,Default,,0000,0000,0000,,that there
Dialogue: 0,0:37:05.00,0:37:09.00,Default,,0000,0000,0000,,is space set aside as part of the working memory of this program
Dialogue: 0,0:37:09.00,0:37:13.00,Default,,0000,0000,0000,,that is gonna record whatever I assign to Num or S. So if I say Num equals
Dialogue: 0,0:37:13.00,0:37:19.00,Default,,0000,0000,0000,,45, what is that? S equals hello, that there
Dialogue: 0,0:37:19.00,0:37:20.00,Default,,0000,0000,0000,,has to be memory
Dialogue: 0,0:37:20.00,0:37:22.00,Default,,0000,0000,0000,,that's being used to hold onto that.
Dialogue: 0,0:37:22.00,0:37:27.00,Default,,0000,0000,0000,,
Dialogue: 0,0:37:27.00,0:37:28.00,Default,,0000,0000,0000,,
Dialogue: 0,0:37:28.00,0:37:32.00,Default,,0000,0000,0000,,And as you declare variables, right, more of the space is set aside, and, you know, when
Dialogue: 0,0:37:32.00,0:37:36.00,Default,,0000,0000,0000,,you initialize it, when you read to it, when you write to it, right, that
Dialogue: 0,0:37:36.00,0:37:40.00,Default,,0000,0000,0000,,space is being accessed and updated as you go through. When you open
Dialogue: 0,0:37:40.00,0:37:44.00,Default,,0000,0000,0000,,a new scope, right, new variables come in a scope. When you close that scope, really that
Dialogue: 0,0:37:44.00,0:37:47.00,Default,,0000,0000,0000,,function, that space gets de-allocated. All this happens on your behalf without you
Dialogue: 0,0:37:47.00,0:37:50.00,Default,,0000,0000,0000,,actually taking a really active role in it, but in fact you do have to have a little
Dialogue: 0,0:37:50.00,0:37:53.00,Default,,0000,0000,0000,,bit of understanding of that to kind of idea of what a pointer's about,
Dialogue: 0,0:37:53.00,0:37:56.00,Default,,0000,0000,0000,,is that there is this just big sequence of
Dialogue: 0,0:37:56.00,0:37:57.00,Default,,0000,0000,0000,,data,
Dialogue: 0,0:37:57.00,0:38:00.00,Default,,0000,0000,0000,,starting from an address zero. You can think of these things as actually
Dialogue: 0,0:38:00.00,0:38:02.00,Default,,0000,0000,0000,,having a little number on them.
Dialogue: 0,0:38:02.00,0:38:06.00,Default,,0000,0000,0000,,So maybe this is number 1,000, and this is number
Dialogue: 0,0:38:06.00,0:38:08.00,Default,,0000,0000,0000,,1,004. In this case, assuming that
Dialogue: 0,0:38:08.00,0:38:10.00,Default,,0000,0000,0000,,we're numbering by the byte,
Dialogue: 0,0:38:10.00,0:38:11.00,Default,,0000,0000,0000,,which is
Dialogue: 0,0:38:11.00,0:38:12.00,Default,,0000,0000,0000,,
Dialogue: 0,0:38:12.00,0:38:15.00,Default,,0000,0000,0000,,the smallest chunk of memory we can talk about,
Dialogue: 0,0:38:15.00,0:38:19.00,Default,,0000,0000,0000,,and that an integer requires four of those bytes to store all the different
Dialogue: 0,0:38:19.00,0:38:20.00,Default,,0000,0000,0000,,patterns for different kinds of numbers
Dialogue: 0,0:38:20.00,0:38:24.00,Default,,0000,0000,0000,,so that the bytes from 1,000 to 1,003 are reserved for holding
Dialogue: 0,0:38:24.00,0:38:27.00,Default,,0000,0000,0000,,onto the information about 45. And then from 1,000 forward -
Dialogue: 0,0:38:27.00,0:38:31.00,Default,,0000,0000,0000,,to however big the string is, which we don't even really know how big it is, so we'll
Dialogue: 0,0:38:31.00,0:38:33.00,Default,,0000,0000,0000,,kind of leave it a little bit vague here -
Dialogue: 0,0:38:33.00,0:38:37.00,Default,,0000,0000,0000,,is gonna be set aside for storing information about that string.
Dialogue: 0,0:38:37.00,0:38:38.00,Default,,0000,0000,0000,,Okay.
Dialogue: 0,0:38:38.00,0:38:41.00,Default,,0000,0000,0000,,So usually it's of interest to the compiler, right, to know where things are being
Dialogue: 0,0:38:41.00,0:38:43.00,Default,,0000,0000,0000,,stored and what's going on.
Dialogue: 0,0:38:43.00,0:38:47.00,Default,,0000,0000,0000,,But it also turns out to be somewhat useful for us to be able to talk about
Dialogue: 0,0:38:47.00,0:38:50.00,Default,,0000,0000,0000,,something by address. Instead of saying the variable
Dialogue: 0,0:38:50.00,0:38:51.00,Default,,0000,0000,0000,,whose name is Num,
Dialogue: 0,0:38:51.00,0:38:56.00,Default,,0000,0000,0000,,I can talk about the variable who lives at location 1,000. And say
Dialogue: 0,0:38:56.00,0:38:58.00,Default,,0000,0000,0000,,there's an integer, and
Dialogue: 0,0:38:58.00,0:39:01.00,Default,,0000,0000,0000,,I can point to it, or refer to it
Dialogue: 0,0:39:01.00,0:39:05.00,Default,,0000,0000,0000,,by saying go look at memory address 1,000, and read or write the contents
Dialogue: 0,0:39:05.00,0:39:09.00,Default,,0000,0000,0000,,there that are of integer type. Okay.
Dialogue: 0,0:39:09.00,0:39:13.00,Default,,0000,0000,0000,,It seems a little bit odd at first. You're like, well I already have other ways to get to Num.
Dialogue: 0,0:39:13.00,0:39:16.00,Default,,0000,0000,0000,,Why is it I want to go out of my way to find another different mechanism that can
Dialogue: 0,0:39:16.00,0:39:18.00,Default,,0000,0000,0000,,get me access to that same variable?
Dialogue: 0,0:39:18.00,0:39:21.00,Default,,0000,0000,0000,,And we're gonna see that actually there's a lot of flexibility
Dialogue: 0,0:39:21.00,0:39:23.00,Default,,0000,0000,0000,,that is being bought by us
Dialogue: 0,0:39:23.00,0:39:27.00,Default,,0000,0000,0000,,adding this to our feature set. We can say, well, I could actually have
Dialogue: 0,0:39:27.00,0:39:29.00,Default,,0000,0000,0000,,one copy of something.
Dialogue: 0,0:39:29.00,0:39:32.00,Default,,0000,0000,0000,,So imagine that you have
Dialogue: 0,0:39:32.00,0:39:32.00,Default,,0000,0000,0000,,
Dialogue: 0,0:39:32.00,0:39:33.00,Default,,0000,0000,0000,,a system,
Dialogue: 0,0:39:33.00,0:39:37.00,Default,,0000,0000,0000,,like, an access system where you have student records, and they're enrolled in a bunch of different
Dialogue: 0,0:39:37.00,0:39:38.00,Default,,0000,0000,0000,,courses, that your
Dialogue: 0,0:39:38.00,0:39:41.00,Default,,0000,0000,0000,,enrolled in four, five different courses,
Dialogue: 0,0:39:41.00,0:39:44.00,Default,,0000,0000,0000,,that when it comes time for a class to know who's in their list, it might be
Dialogue: 0,0:39:44.00,0:39:45.00,Default,,0000,0000,0000,,handy for them,
Dialogue: 0,0:39:45.00,0:39:48.00,Default,,0000,0000,0000,,instead of actually having a copy of that student's information to have a pointer
Dialogue: 0,0:39:48.00,0:39:52.00,Default,,0000,0000,0000,,to one student record, and have a lot of different placers where there are
Dialogue: 0,0:39:52.00,0:39:55.00,Default,,0000,0000,0000,,additional pointers taken out to that same location and says, go look at the student who's
Dialogue: 0,0:39:55.00,0:39:56.00,Default,,0000,0000,0000,,at address 1,000.
Dialogue: 0,0:39:56.00,0:39:59.00,Default,,0000,0000,0000,,I have the students at address 1,000, at 1,026,
Dialogue: 0,0:39:59.00,0:40:02.00,Default,,0000,0000,0000,,at, you know, 1,035,
Dialogue: 0,0:40:02.00,0:40:05.00,Default,,0000,0000,0000,,whatever those places are, and that that's one way I can talk about what
Dialogue: 0,0:40:05.00,0:40:09.00,Default,,0000,0000,0000,,students I have, and those same student addresses might show up in someone else's
Dialogue: 0,0:40:09.00,0:40:11.00,Default,,0000,0000,0000,,class list in math 51, or
Dialogue: 0,0:40:11.00,0:40:13.00,Default,,0000,0000,0000,,physics, you know, 43 or whatever,
Dialogue: 0,0:40:13.00,0:40:15.00,Default,,0000,0000,0000,,and that we are
Dialogue: 0,0:40:15.00,0:40:18.00,Default,,0000,0000,0000,,all referring to one copy of the student data without duplicating it.
Dialogue: 0,0:40:18.00,0:40:22.00,Default,,0000,0000,0000,,So this idea of being able to refer to stuff not just by name, but by where it lives,
Dialogue: 0,0:40:22.00,0:40:28.00,Default,,0000,0000,0000,,is gonna give us some flexibility in terms of how we build things out of that.
Dialogue: 0,0:40:28.00,0:40:31.00,Default,,0000,0000,0000,,So let me kind of show you a little bit of the basic operations,
Dialogue: 0,0:40:31.00,0:40:35.00,Default,,0000,0000,0000,,and then - and I'll talk a little bit along the way about this thing about why they're
Dialogue: 0,0:40:35.00,0:40:36.00,Default,,0000,0000,0000,,scary
Dialogue: 0,0:40:36.00,0:40:37.00,Default,,0000,0000,0000,,because
Dialogue: 0,0:40:37.00,0:40:40.00,Default,,0000,0000,0000,,using, you know, memory access as your way to get to something is a little
Dialogue: 0,0:40:40.00,0:40:44.00,Default,,0000,0000,0000,,bit more error prone and a little bit harder to deal with than
Dialogue: 0,0:40:44.00,0:40:47.00,Default,,0000,0000,0000,,some of the more - other operations we have.
Dialogue: 0,0:40:47.00,0:40:50.00,Default,,0000,0000,0000,,So what I'm gonna show you here is a little piece of code.
Dialogue: 0,0:40:50.00,0:40:57.00,Default,,0000,0000,0000,,It shows some simple use of pointers. All right.
Dialogue: 0,0:40:57.00,0:40:58.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:40:58.00,0:40:59.00,Default,,0000,0000,0000,,
Dialogue: 0,0:40:59.00,0:41:02.00,Default,,0000,0000,0000,,I'm gonna draw some of the variables that are going on here. This
Dialogue: 0,0:41:02.00,0:41:04.00,Default,,0000,0000,0000,,is main and it declared
Dialogue: 0,0:41:04.00,0:41:05.00,Default,,0000,0000,0000,,an integer
Dialogue: 0,0:41:05.00,0:41:08.00,Default,,0000,0000,0000,,whose name is Num, so I
Dialogue: 0,0:41:08.00,0:41:09.00,Default,,0000,0000,0000,,draw a box for that, and it
Dialogue: 0,0:41:09.00,0:41:13.00,Default,,0000,0000,0000,,declares two pointer variables. So the addition of the asterisk by the name
Dialogue: 0,0:41:13.00,0:41:14.00,Default,,0000,0000,0000,,there
Dialogue: 0,0:41:14.00,0:41:19.00,Default,,0000,0000,0000,,says that P and Q are pointers to integers.
Dialogue: 0,0:41:19.00,0:41:23.00,Default,,0000,0000,0000,,So P and Q themselves are variables
Dialogue: 0,0:41:23.00,0:41:26.00,Default,,0000,0000,0000,,that live in the stack. So all the local variables we say
Dialogue: 0,0:41:26.00,0:41:30.00,Default,,0000,0000,0000,,live in the stack.
Dialogue: 0,0:41:30.00,0:41:33.00,Default,,0000,0000,0000,,They are automatically allocated and de-allocated when you enter a routine. The space for
Dialogue: 0,0:41:33.00,0:41:36.00,Default,,0000,0000,0000,,them comes into being. When you leave it, it goes away,
Dialogue: 0,0:41:36.00,0:41:40.00,Default,,0000,0000,0000,,and that P and Q are designed not to hold integers themselves. They don't hold numbers,
Dialogue: 0,0:41:40.00,0:41:44.00,Default,,0000,0000,0000,,but they hold the address of a number somewhere else.
Dialogue: 0,0:41:44.00,0:41:47.00,Default,,0000,0000,0000,,And so the first thing I did with
Dialogue: 0,0:41:47.00,0:41:48.00,Default,,0000,0000,0000,,P there was to assign it
Dialogue: 0,0:41:48.00,0:41:52.00,Default,,0000,0000,0000,,the address of a new integer variable that came out of the heap. So the
Dialogue: 0,0:41:52.00,0:41:55.00,Default,,0000,0000,0000,,new operator is like the new operator in Java.
Dialogue: 0,0:41:55.00,0:41:59.00,Default,,0000,0000,0000,,It takes the thing you want to create one of, it makes one of those in the heap,
Dialogue: 0,0:41:59.00,0:42:02.00,Default,,0000,0000,0000,,and it returns to you its address. In that way it works exactly like in Java. So, in
Dialogue: 0,0:42:02.00,0:42:04.00,Default,,0000,0000,0000,,fact, Java actually
Dialogue: 0,0:42:04.00,0:42:07.00,Default,,0000,0000,0000,,has pointers despite what anybody ever told you,
Dialogue: 0,0:42:07.00,0:42:11.00,Default,,0000,0000,0000,,that the way you create objects and you use new to access them and stuff like that
Dialogue: 0,0:42:11.00,0:42:15.00,Default,,0000,0000,0000,,is exactly the same as it is in C++ as it is
Dialogue: 0,0:42:15.00,0:42:16.00,Default,,0000,0000,0000,,pointers behind the scene.
Dialogue: 0,0:42:16.00,0:42:18.00,Default,,0000,0000,0000,,So I say P
Dialogue: 0,0:42:18.00,0:42:20.00,Default,,0000,0000,0000,,gets the value of a new integer.
Dialogue: 0,0:42:20.00,0:42:24.00,Default,,0000,0000,0000,,This memory over here is called the heap.
Dialogue: 0,0:42:24.00,0:42:27.00,Default,,0000,0000,0000,,So this is not
Dialogue: 0,0:42:27.00,0:42:29.00,Default,,0000,0000,0000,,to confuse you with the idea of
Dialogue: 0,0:42:29.00,0:42:32.00,Default,,0000,0000,0000,,the stack ADT. We've been using the [inaudible]
Dialogue: 0,0:42:32.00,0:42:35.00,Default,,0000,0000,0000,,but it does kind of - it helps you to remember that the stack actually kind of, like, by
Dialogue: 0,0:42:35.00,0:42:38.00,Default,,0000,0000,0000,,the virtue of the way function calls get made, main calls A, which
Dialogue: 0,0:42:38.00,0:42:42.00,Default,,0000,0000,0000,,calls B, which calls C, that that memory actually kind of is laid out like a stack.
Dialogue: 0,0:42:42.00,0:42:46.00,Default,,0000,0000,0000,,The heap is just this unordered crazy pile of stuff.
Dialogue: 0,0:42:46.00,0:42:49.00,Default,,0000,0000,0000,,I ask for new integer, so this might be address 1,000.
Dialogue: 0,0:42:49.00,0:42:52.00,Default,,0000,0000,0000,,This might be address 1,004. This might be address 1,008. Typically
Dialogue: 0,0:42:52.00,0:42:56.00,Default,,0000,0000,0000,,the stack variables are laid out right next to each other. This could be, like,
Dialogue: 0,0:42:56.00,0:42:56.00,Default,,0000,0000,0000,,address
Dialogue: 0,0:42:56.00,0:42:59.00,Default,,0000,0000,0000,,32,016 or something over here.
Dialogue: 0,0:42:59.00,0:43:02.00,Default,,0000,0000,0000,,Some other larger address. So I've
Dialogue: 0,0:43:02.00,0:43:03.00,Default,,0000,0000,0000,,assigned P to be that
Dialogue: 0,0:43:03.00,0:43:07.00,Default,,0000,0000,0000,,thing. So what I actually gotten written into P's box is behind the scenes there really is the number,
Dialogue: 0,0:43:07.00,0:43:10.00,Default,,0000,0000,0000,,you know, the address, 32,016. What
Dialogue: 0,0:43:10.00,0:43:14.00,Default,,0000,0000,0000,,I'm gonna draw is an arrow to remind myself that what it is is it's a
Dialogue: 0,0:43:14.00,0:43:18.00,Default,,0000,0000,0000,,location of an integer stored elsewhere.
Dialogue: 0,0:43:18.00,0:43:20.00,Default,,0000,0000,0000,,The de-reference operator,
Dialogue: 0,0:43:20.00,0:43:22.00,Default,,0000,0000,0000,,which is the first thing we see on this next line,
Dialogue: 0,0:43:22.00,0:43:25.00,Default,,0000,0000,0000,,says to follow P
Dialogue: 0,0:43:25.00,0:43:26.00,Default,,0000,0000,0000,,and assign it a 10.
Dialogue: 0,0:43:26.00,0:43:29.00,Default,,0000,0000,0000,,So this is taking that address that's in P,
Dialogue: 0,0:43:29.00,0:43:33.00,Default,,0000,0000,0000,,using it as a location to go look up something, and it says, and go write to that
Dialogue: 0,0:43:33.00,0:43:35.00,Default,,0000,0000,0000,,location in address 32,016
Dialogue: 0,0:43:35.00,0:43:42.00,Default,,0000,0000,0000,,the number 10.
Dialogue: 0,0:43:42.00,0:43:47.00,Default,,0000,0000,0000,,And I said Q equals no int. So Q gets an
Dialogue: 0,0:43:47.00,0:43:47.00,Default,,0000,0000,0000,,[inaudible]
Dialogue: 0,0:43:47.00,0:43:53.00,Default,,0000,0000,0000,,maybe this is at 23,496.
Dialogue: 0,0:43:53.00,0:43:55.00,Default,,0000,0000,0000,,Some other place out there. And so
Dialogue: 0,0:43:55.00,0:43:58.00,Default,,0000,0000,0000,,that's actually kind of what's being stored here,
Dialogue: 0,0:43:58.00,0:44:00.00,Default,,0000,0000,0000,,23,496.
Dialogue: 0,0:44:00.00,0:44:03.00,Default,,0000,0000,0000,,And then I did this thing where I assigned from
Dialogue: 0,0:44:03.00,0:44:05.00,Default,,0000,0000,0000,,D referencing P
Dialogue: 0,0:44:05.00,0:44:09.00,Default,,0000,0000,0000,,to get an integer, and assign that onto what Q is that has the effect of kind of
Dialogue: 0,0:44:09.00,0:44:15.00,Default,,0000,0000,0000,,following P, reading its 10, and then writing it over here. So copying the integers
Dialogue: 0,0:44:15.00,0:44:19.00,Default,,0000,0000,0000,,at the end of those two pointers to make them point to the same value.
Dialogue: 0,0:44:19.00,0:44:22.00,Default,,0000,0000,0000,,So they point to two different locations, but those locations hold the same integer
Dialogue: 0,0:44:22.00,0:44:23.00,Default,,0000,0000,0000,,value
Dialogue: 0,0:44:23.00,0:44:25.00,Default,,0000,0000,0000,,that is different
Dialogue: 0,0:44:25.00,0:44:27.00,Default,,0000,0000,0000,,than the next line.
Dialogue: 0,0:44:27.00,0:44:29.00,Default,,0000,0000,0000,,Without the stars,
Dialogue: 0,0:44:29.00,0:44:34.00,Default,,0000,0000,0000,,where I said Q equals P,
Dialogue: 0,0:44:34.00,0:44:37.00,Default,,0000,0000,0000,,without the stars on it,
Dialogue: 0,0:44:37.00,0:44:43.00,Default,,0000,0000,0000,,it's saying take the address that's in P, and assign it to Q,
Dialogue: 0,0:44:43.00,0:44:45.00,Default,,0000,0000,0000,,causing Q and P now to be aliases
Dialogue: 0,0:44:45.00,0:44:48.00,Default,,0000,0000,0000,,for the same location.
Dialogue: 0,0:44:48.00,0:44:52.00,Default,,0000,0000,0000,,So now I have two different ways of getting to that same piece of memory,
Dialogue: 0,0:44:52.00,0:44:55.00,Default,,0000,0000,0000,,either by reaching through P and de-referencing, or reaching through Q and de-referencing
Dialogue: 0,0:44:55.00,0:44:57.00,Default,,0000,0000,0000,,it - both of them
Dialogue: 0,0:44:57.00,0:45:01.00,Default,,0000,0000,0000,,are reading and writing to that same location in the heap, where the 10 is,
Dialogue: 0,0:45:01.00,0:45:05.00,Default,,0000,0000,0000,,and then this one down here's no longer accessible. I sort of lost track of it
Dialogue: 0,0:45:05.00,0:45:06.00,Default,,0000,0000,0000,,when I
Dialogue: 0,0:45:06.00,0:45:08.00,Default,,0000,0000,0000,,overwrote Q with the
Dialogue: 0,0:45:08.00,0:45:10.00,Default,,0000,0000,0000,,copy of P.
Dialogue: 0,0:45:10.00,0:45:12.00,Default,,0000,0000,0000,,When I am done
Dialogue: 0,0:45:12.00,0:45:14.00,Default,,0000,0000,0000,,in C++ it is my job
Dialogue: 0,0:45:14.00,0:45:15.00,Default,,0000,0000,0000,,to delete things
Dialogue: 0,0:45:15.00,0:45:20.00,Default,,0000,0000,0000,,that are coming out of the heap.
Dialogue: 0,0:45:20.00,0:45:24.00,Default,,0000,0000,0000,,Yes, it should. I'll take that one at 32,016.
Dialogue: 0,0:45:24.00,0:45:28.00,Default,,0000,0000,0000,,Whereas in Java, when you say new, and then you stop using something,
Dialogue: 0,0:45:28.00,0:45:30.00,Default,,0000,0000,0000,,it figures it out and it does what's called garbage collection to kind of clean up
Dialogue: 0,0:45:30.00,0:45:31.00,Default,,0000,0000,0000,,behind you.
Dialogue: 0,0:45:31.00,0:45:35.00,Default,,0000,0000,0000,,In C++, things that you new out of the heap are your responsibility to
Dialogue: 0,0:45:35.00,0:45:36.00,Default,,0000,0000,0000,,delete.
Dialogue: 0,0:45:36.00,0:45:40.00,Default,,0000,0000,0000,,So you delete something when you're done with it. If I'm no longer using this
Dialogue: 0,0:45:40.00,0:45:42.00,Default,,0000,0000,0000,,new integer I created in the heap,
Dialogue: 0,0:45:42.00,0:45:44.00,Default,,0000,0000,0000,,I say to delete P
Dialogue: 0,0:45:44.00,0:45:47.00,Default,,0000,0000,0000,,to allow that memory to be reclaimed.
Dialogue: 0,0:45:47.00,0:45:51.00,Default,,0000,0000,0000,,And so that causes this piece of memory to get marked as freed,
Dialogue: 0,0:45:51.00,0:45:56.00,Default,,0000,0000,0000,,or reusable, so that a subsequent new call can have that space again
Dialogue: 0,0:45:56.00,0:45:58.00,Default,,0000,0000,0000,,and use it for things.
Dialogue: 0,0:45:58.00,0:46:01.00,Default,,0000,0000,0000,,I will note that right now, the code as written
Dialogue: 0,0:46:01.00,0:46:05.00,Default,,0000,0000,0000,,has a little bit of an error in it because it says delete P. And
Dialogue: 0,0:46:05.00,0:46:09.00,Default,,0000,0000,0000,,delete P says we'll follow out to 32 [inaudible] and mark it as
Dialogue: 0,0:46:09.00,0:46:10.00,Default,,0000,0000,0000,,available.
Dialogue: 0,0:46:10.00,0:46:13.00,Default,,0000,0000,0000,,The next thing I did was said delete Q. Well Q points to the same
Dialogue: 0,0:46:13.00,0:46:17.00,Default,,0000,0000,0000,,place P did. So in fact I'm saying take that piece of freed memory and mark it freed
Dialogue: 0,0:46:17.00,0:46:17.00,Default,,0000,0000,0000,,again.
Dialogue: 0,0:46:17.00,0:46:19.00,Default,,0000,0000,0000,,
Dialogue: 0,0:46:19.00,0:46:22.00,Default,,0000,0000,0000,,There is no real guarantee about whether that's gonna do something
Dialogue: 0,0:46:22.00,0:46:25.00,Default,,0000,0000,0000,,sensible, or whether it's just gonna ignore me. One thing it could do is just say, well look, that
Dialogue: 0,0:46:25.00,0:46:27.00,Default,,0000,0000,0000,,memory's already freed, so
Dialogue: 0,0:46:27.00,0:46:29.00,Default,,0000,0000,0000,,you saying to free it twice is kind of stupid.
Dialogue: 0,0:46:29.00,0:46:33.00,Default,,0000,0000,0000,,On the other hand, it could still cause some more problems depending on how the
Dialogue: 0,0:46:33.00,0:46:37.00,Default,,0000,0000,0000,,heap allocater works, and there's no guarantee. So it becomes very [inaudible] on the
Dialogue: 0,0:46:37.00,0:46:39.00,Default,,0000,0000,0000,,programmer to be very careful about this matching, that
Dialogue: 0,0:46:39.00,0:46:41.00,Default,,0000,0000,0000,,if you make a new call,
Dialogue: 0,0:46:41.00,0:46:43.00,Default,,0000,0000,0000,,you make a delete call. And
Dialogue: 0,0:46:43.00,0:46:45.00,Default,,0000,0000,0000,,if you already made a delete call, you don't make another one
Dialogue: 0,0:46:45.00,0:46:49.00,Default,,0000,0000,0000,,accidentally. So I really should have that line out of there.
Dialogue: 0,0:46:49.00,0:46:54.00,Default,,0000,0000,0000,,The piece of memory that Q originally pointed to, right, I no longer have any way to get to,
Dialogue: 0,0:46:54.00,0:46:57.00,Default,,0000,0000,0000,,and so I have no way of making a delete call to it and freeing it. And so this little
Dialogue: 0,0:46:57.00,0:47:01.00,Default,,0000,0000,0000,,piece of memory we call an orphan.
Dialogue: 0,0:47:01.00,0:47:03.00,Default,,0000,0000,0000,,He's stranded out there in the heap,
Dialogue: 0,0:47:03.00,0:47:04.00,Default,,0000,0000,0000,,no way to get back to it,
Dialogue: 0,0:47:04.00,0:47:09.00,Default,,0000,0000,0000,,and C++ will not automatically reclaim it for us. So we have
Dialogue: 0,0:47:09.00,0:47:12.00,Default,,0000,0000,0000,,created a little bit of a mess for ourselves. If we did that a lot, right,
Dialogue: 0,0:47:12.00,0:47:16.00,Default,,0000,0000,0000,,we could end up clogging our heap filled with these orphans,
Dialogue: 0,0:47:16.00,0:47:19.00,Default,,0000,0000,0000,,and have to keep getting new memory because the old memory, right, was not
Dialogue: 0,0:47:19.00,0:47:22.00,Default,,0000,0000,0000,,being properly reclaimed.
Dialogue: 0,0:47:22.00,0:47:24.00,Default,,0000,0000,0000,,We're gonna talk more about this, so this is not
Dialogue: 0,0:47:24.00,0:47:27.00,Default,,0000,0000,0000,,the all - end all of pointers, but just a little bit to think about today. We'll
Dialogue: 0,0:47:27.00,0:47:30.00,Default,,0000,0000,0000,,come back on Wednesday, talk more about it, and then talk about how we can use
Dialogue: 0,0:47:30.00,0:47:33.00,Default,,0000,0000,0000,,this to build linked lists, and that will be
Dialogue: 0,0:47:33.00,0:47:36.00,Default,,0000,0000,0000,,fun times for all.