Treasure Transcript

[00:00:00] Hey there! I’m going to walk you through how you can use decomposition to break down complex problems. First we’re going to start with the treasure problem, treasure.py. Here’s what it is. So Bit has to reach the cave.

Start visual description. Screen reads: Treasure!
treasure.py
To reach the cave, Bit must follow these instructions:
• Turn right on blue squares.
• Turn left on red squares.
Once in the cave, navigate through the passage to the treasure (red square).
Paint the path followed green.
End visual description.

[00:00:18] First, he has to follow the treasure map, which says turn right on blue squares and left on red squares. Following those instructions, you should reach the cave. And then at that point he needs to navigate through the cave to find the treasure, the red square. And we want to paint everything green as we go.

[00:00:35] So the first thing that you see here is a natural split in the problem right. There’s actually two sub problems: get to the cave, then navigate the cave. And we can start our program with that simple split and that’s the level we want to start on. We don’t want to get right into while loops, and if statements, and conditions.

[00:01:04] We want to talk about the pieces of the problem and to find those pieces and then slowly figure out what the what those pieces mean specifically. So if we’re going to say get to cave and navigate cave are it’s two big pieces then we just need to understand just a little bit where those pieces fit.

[00:01:20] So let’s draw this out. Somewhere, we’ve got a cave. An entrance to a cave right. And at some point you know Bit starts out here somewhere and he’s gonna wander around and then he’s going to arrive at the cave.

[00:01:35] So we need to decide: do we think that Bit should arrive here? Put that as position one right. Or do we think that Bit should arrive here? I’ll call that position two. Or maybe further in like you know down here, we could say he arrives here where he’s blocked in the front, you know. That’s position three. Various places we could think about.

[00:01:58] And as we’re trying to decide where the get to cave function ends, we’re thinking a little bit about what specific situation will Bit be in that tells us we’ve arrived? And position one sitting out in the open doesn’t have a lot to tell us that we’ve arrived in the cave.

[00:02:21] Whereas at position two we have a clear, you know, blocked on right and left condition that doesn’t happen at all while Bit’s out wandering around. This is the first time left and right are blocked so that seems promising.

[00:02:35] You say well what about you know where he comes shooting straight in and then eventually hits the wall and he’s blocked? That might work. You know, if we come back and look at our map, here we see though that there are a number of situations as he comes up or comes over or up that he’ll be blocked in front. And maybe if we get the order of the turns right then that’ll work fine.

Start visual description. Instructor sketches out the thought process for the problem. End visual description.

[00:03:03] But seeing as that one’s a little more nuanced in how we do it versus just checking whether it’s blocked on the left and on the right it is unique, let’s just go with position two right. That makes a clear obvious end to get to the cave, right. So Bit starts out here. We’ve got some cave and Bit’s going to end right there.

[00:03:31] And that’s when you get to the cave stop. So with just this little piece, right, we can already start to break things down. Let’s come over to PyCharm and do just that much.

[00:03:40] Get to cave, bit. And then we’ll say navigate cave, bit. Right. If get to Cave works and does the right thing and navigate cave works and does the right thing, then go works. Right? And this is the concept of abstraction. The idea of defining new words and, assuming those words are correct, putting those words together to solve a bigger problem. We’ll worry about the details of these individual words or functions in a minute.

[00:04:19] But when you’re breaking problems down, this is the way you want to do it. First, create an abstraction around the bigger pieces and figure out how those pieces fit together and work your way in.

[00:04:33] We know a little bit more details around get to cave, right? So I’m going to create that function and I’m going to add a doc string here. Bit ends just inside the mouth of the cave, blocked on the left and the right. That was what we decided is how get to cave ends. We could also mention here Bit turns left on red and right on blue.

Start visual description. Instructor types the following code:
@Bit.worlds(‘treasure’)
def go(bit):
get_to_cave (bit)
navigate cave(bit)
End visual description.

[00:05:11] Bit paints every square green. Right, so this little doc string helps to capture the contract. And it doesn’t mean anything to the computer but it helps me as a human reading this and understanding oh what does get cave, what is it supposed to do? It’s supposed to do this. Navigate cave we can now create a little function and add a little doc string right. Bit starts just inside the mouth of the cave.

[00:05:42] Bit ends on the red square. Bit paints every square green. And that helps us know what navigate cave is supposed to do. So now that we’ve figured this out, let’s implement just the first part get to cave.

[00:06:02] And in fact here, let’s just put a little bit.snapshot right here Arrived at cave, with some enthusiasm, that we can jump to see, are we where we thought we would be when we get to cave finishes? And if that’s correct then we’ll move on to the navigating cave part. So up here. Bit ends inside the mouth of the cave, blocked on left and right, great.

[00:06:29] Let’s take another look at our picture and look at this process right. We’ve seen this pattern before in the homework and in the labs where we just move Bit towards that final goal and we respond to these individual events with a turn.

[00:06:47] So we can follow a similar pattern. We can say while not in cave, bit. bit dot move, bit dot paint green, And what’s the other idea that we need? Maybe turn bit. Right, so if we’re not in the cave, we’re going to move, we’re going to paint, and maybe we’re going to turn. And again we’re doing the same thing we just did in the go function.

[00:07:16] Instead of jumping all the way down into the details, we’re just talking about the high level ideas. Right? If this while loop keeps going until Bit’s in the cave and Bit moves, paints, and turns when necessary it’ll work. So let’s state that here and then go worry about those details later.

[00:07:36] The other question is: does it matter which order we do the moves, the paints, and the turns in? So we can come back to our picture here and think through, right, this idea. If I move and then I paint and maybe turn it’ll be on a green square. Right, if I move and then paint and now it’s green I’m not going to know to turn. That’s going to be a problem, right? So just simulating for a moment this idea on paper of what would happen with our instructions already reveals to us that the order does matter just a little bit.

[00:08:10] We need to handle the turns before we paint over the square. So either we need to paint, then move, and then turn or we need to turn before we paint, right. So just switching this order here right where we paint a square green, then we move off of that square, and now we handle a turn. Let’s see if that works right. So if I’m right here, I paint this green, I move, I don’t have to turn, I paint the square green, I move, and then I turn, and then I paint it green but I’m already faced in the right direction and I move.

[00:08:44] That looks like that’ll work. So let’s try that and if we got it wrong, we’ll see it in the steps and we’ll go back and fix it. So now we just need to define what does it mean to be in the cave? So I’m going to just bring up create a new function, in cave, great. And we’ve already defined this before.

Start visual description. Instructor types the following code:
def get_to_cave (bit):
Bit ends just inside the mouth of the cave, blocked on the left and the right
Bit turns left on red and right on blue. Bit points every square green.
while not in_cave(bit):
bit.paint(‘green’)
bit.move()
maybe turn(bit)
End visual description.

[00:09:03] It’s got to be blocked on the left and the right, that’s what it means. Now, in cave here, because it’s being used with not and being used with while it’s supposed to return a Boolean value. A true or a false. Right, so that’s what we’re going to return from here. Return bit dot left clear, except we don’t want left clear we want it blocked, right?

[00:09:28] So if it’s not left clear and not bit dot right clear then we’re in the cave. That’s what that means. In the cave means that the left is not clear and the right is not clear. It’s that simple. Note these parentheses right here, I’ve noticed a few students will leave this off and just put the parentheses at the end. That won’t work. It will run but it won’t do what you expect it to do.

[00:09:51] You want the parentheses after every function that you’re trying to call, right. So left clear needs its parentheses. Right clear needs its parentheses. So there’s in cave. How about maybe turn? Let’s create a function maybe turn. And in this case we’re just trying to capture this simple little concept: turn right on blue squares, turn left on red squares. So, if bit dot is red bit dot left. Elif bit dot is blue bit dot right.

[00:10:30] Now, does it matter if it’s elif in this situation versus if or versus else? Right? What if we had instead said, you know, else bit dot right? And not that? Well, if it was red, we’d turn. Otherwise we’d turn the other way. So every clear square would turn into a turn.

[00:10:55] We don’t want that. We only want it to check that other turn if it’s not red. And if, you know, we wanted to do the other turn if it’s blue, actually is blue.

[00:11:07] Right, so we’re going to use an elif to say okay if it wasn’t red, well then if it’s blue do this, right. Now in this specific situation, we could have done an if, right. If it’s red left, if it’s blue right. Because these two conditions of being red or blue are already mutually exclusive.

[00:11:27] But because we really only intend for this to get checked if that wasn’t, elif is a good example. The subtle difference now is only doing it like this, it will call is red and it will call is blue every time. Putting an elif, it will only call is blue if it wasn’t already red. So just one less function call most of the time.

Start visual description. Instructor types the following code:
def in cave (bit):
return not bit.left_clear() and not bit.right_clear()
def maybe_turn(bit):
if bit.is_red():
bit.left()
elif bit.is_blue():
bit.right()
End visual description.

[00:11:52] Alright, that’s maybe turn. So here we’ve defined all the pieces that get cave needs. Let’s run it and see if we actually made it to the cave. Give it a second to load. There it is. Alright. Let’s jump to our snapshot. And there! Right where we thought we would be at the end of arriving at the cave we’ve arrived.

[00:12:24] Excellent! Half the problem is already solved. So now we just need to navigate the cave to the end. Same problem as before, ultimately, right? We’re moving along towards a goal. In this case the goal is that…well let’s not even worry about the goal, right?

Start visual description. Instructor runs the code and a window appears with the grid to show the output of the current code. End visual description.

[00:12:41] Let’s just look at this high level piece. We’ve got to get to some finish point, the treasure, we’ll say we’ll call it found treasure. And we maybe have to turn and we have to move and paint while we do it. So let’s just do that. While not at treasure, bit. bit dot move bit dot paint green and maybe turn.

[00:13:07] Now, if I try to say maybe turn, maybe turn is going to…is already defined and that looks at reds and greens. This maybe turn has to do with corners, right, being blocked and making a decision. So instead, let’s maybe call it navigate turn for example. They’ll have to be different names because they mean slightly different ideas, but the purpose is the same within this little block, right. If we’re not at the treasure, we got to move, we got to paint, we’ve got a turn.

[00:13:42] What does it mean to be at the treasure? Well let’s give it a meaning. Create a function at treasure bit return bit dot is red. That means we’re at the treasure. Okay, great. Now I come down here, what does it mean to navigate the turn? Well, if you come look at our picture here, right. If we’re moving along we have this idea of if we’re blocked we have to turn.

Start visual description. Instructor types the following code:
def navigate_cave (bit):
Bit starts just inside the mouth of the cave.
Bit ends on the red square.
Bit points every square green.
while not at treasure(bit):
bit.move()
bit.paint(‘green’)
navigate turn(bit)
End visual description.

[00:14:14] We also notice… so we could we could check and see you know if the front is blocked we got to look left versus right and figure out which way to go. Okay, that’s an option. The other idea here is just simply looking if at any point in time one of these turns is available we just take it.

[00:14:33] We don’t have to check whether the front is blocked we just have to check if right is clear versus left is clear. So let’s try that. If bit dot right clear, bit dot right. Elif bit dot left clear bit dot left. Now, like before, does it matter if it’s an else uh versus an elif? Right, so if it’s just an else, if the right’s not clear it’s going to end up turning left that’s no good.

[00:15:05] We want to check if the left is clear. What if it was just simply an if? Well if the right clear, if a turn to the right now makes the left open, doing it in sequence, it will now turn back. That’s no good, right? We only want to check on the left side if the right side wasn’t clear. So we do an elif.

[00:15:29] So now they’re mutually exclusive. This will run or that will run. Never both. That’s what we want. Let’s navigate a turn. Now we’re great. Last thing to check, does it matter the order that we move, we paint, and we navigate? Well, just like before, you know, when we were looking here, if we had recognized if I move and then paint I’m going to have a problem.

Start visual description. Instructor types the following code:
def navigate turn(bit): if bit.right_clear():
bit.right()
elif bit.left_clear():
bit.left()
End visual description.

[00:15:52] Well in here we’re looking for red, and if I end up moving on to the red and then painting it and then checking to see if I’m red, I’m never going to find a red, right. So we want to make sure that my at treasure question finds a red square and if I paint green first that’s not going to work, right. So let’s just do what we did on the last. Let’s just take this line cut, paste and paint to green, now move, now figure out if we need to turn. I’m going to go from there. Let’s see how that’s working.

[00:16:34] Treasure. Really close right? What’s missing? The last square didn’t get painted. And that’s just the move paint problem right. You can either move then paint or paint then move. And when you do that, at some end you’re going to have to have that extra paint. So let’s just add an extra paint. Don’t overthink this. Bit dot paint green.

Start visual description. Instructor adds bit.paint(‘green’) in go function. End visual description.

[00:17:00] Goal! Okay, we found the treasure. So the key ideas when you approach a complex problem, train yourself to start with the big ideas, right. Functions for those big ideas. In some sense, solve the bigger problem just using these big idea words that you’ve come up with and then go figure out how to…what the actual meanings of those big ideas are. Talk about how those big ideas fit together, like we figured out where did get to cave actually end.

Start visual description. Instructor runs code and a window pops up with the output grid showing the correct output for the exercise. End visual description.

[00:17:37] Work out the interfaces of those ideas and document them, right. Doc strings that help make it clear where things are supposed to…what they’re supposed to do. How they fit. Right, and then work your way down from the top. So I figured out the top piece and you’ll have little red squiggles, right, for all these words you just made up and haven’t defined. Then you go to define all those little functions.

[00:17:59] And another function may, in itself, get to cave, you know, we had new ideas. In cave, maybe turn. Again, taking a simpler problem but still a complex problem and breaking it down into basic ideas.

[00:18:15] And then going from there. You want the code that you write to be obvious, right. Reading through this, while not in cave, paint green, move, and maybe turn almost sounds obvious but that’s good. You want obvious code. You want the intent and function of your code to be obvious.

[00:18:38] You don’t want to spend time trying to interpret your code. Let the computer do the interpreting. You want to just read it and as quickly as possible understand it so that you can change it or fix it. Do whatever you need to do.

[00:18:51] And so writing code that feels obvious is actually a good sign. That means that you’ve captured the essence of the ideas and figured out how those ideas fit together. It takes practice but it’s good practice and I invite you to do that practice now. Maybe you can fit the whole bit problem into one function.

[00:19:09] Don’t do that. Force yourself to start from the very beginning of the problem with these bigger ideas and it will pay huge dividends later on as you learn to program more and more and more complex programs. And thank you for watching. Have fun with homework!