Recitation 22: Dynamic Programming: Dance Dance Revolution

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

Description: This recitation looks at player positions in the Dance Dance Revolution game, along the lines of the guitar fingering example shown in lecture.

Instructor: Victor Costan

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation, or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu.

PROFESSOR: So we're going to do a problem that looks like the guitar problem. But it's a bit cooler. At the same time, there are fewer states, so I think it's easier to manage. How many people know how to play DDR?

AUDIENCE: Well.

PROFESSOR: Yeah. OK. How many people know the rules of playing DDR? Because otherwise I won't be able to lift my hand up. OK. OK, so let's go through an algorithmic model.

So, you have a board that basically looks like this. And you have four touch sensitive pads. Up, down, left, right. And then you have a center position.

You also have a sheet of notes that looks something like this. Say, up, up down, down, up down, up, up down, left right, left, left right, right. So on and so forth.

So when you see an arrow of up, that's a constraint that says one of your feet has to be on the up arrow. Has to tap the up arrow, actually. There's no constraint for the other foot. So your other foot can be anywhere else on the board. It doesn't matter.

You are also allowed to tap the board some extra times. So if you don't have a note showing up, you can still hit the board. And there's no penalty. So you can hop around as many times as you want, or as many times as you can, until you run out of breath.

So up basically means, it's actually one foot has to be up. The other one center. Also, of course, because of the design of the board, it doesn't matter what foot is where. So what are possible goals for this game?

AUDIENCE: Not to get an F.

PROFESSOR: OK.

AUDIENCE: Hit all the arrows when they line up with the top row.

PROFESSOR: OK. So there are two different ways of doing it. One, you said, "not to get an F." So I would say, given some limited set of skills. So given a set of skills, or your skill level maximizes your score. right?

AUDIENCE: Yeah.

PROFESSOR: This is dynamic programming, so we always want to maximize something. Now, if you're really good, then another possible goal is hit all the notes with a minimum amount of effort. If you're going to be in a competition, and you're going to be doing 10 songs, you don't want to die after the first song, right? So, assuming you can do everything reasonably well, this is another possible goal.

Any other goals? So we're brainstorming here. This isn't set in stone. We've already seen the formal solution for this problem. So I want to play with it for a little bit, right? We brought a DDR pad, so I want to play with it. What else could you hope to maximize or minimize for with dynamic programming?

AUDIENCE: Not look ridiculous.

PROFESSOR: OK.

AUDIENCE: I guess we're looking at the cost of each move, right?

PROFESSOR: So, hit all the notes. Minimum effort, or otherwise say best appearance. So every move looks somewhat good or somewhat bad. And you want to do the moves that look as good as possible.

So this maximizes entertainment, right? if you're on TV, you probably want this. Now suppose you are in a competition and you only have one track to play.

AUDIENCE: Well, you know where all the notes are.

PROFESSOR: Sure. Like, we assume that we know this ahead of time. So you've memorized this. And you're trying to compute the best strategy, so you can memorize that. Then when you go and play, you dominate.

AUDIENCE: Yeah.

PROFESSOR: So, if you have one track, then I would say that what you'd want to do is minimize your probability of failure. Right? So given the probability of failure for each possible move. You want to minimize the overall probability of failure so your teammates won't hate you. So, hit all the notes and minimize.

So this one's a little bit different from the other ones because all the other ones are already set up as a nice problem where you add up things. So you can solve them with graphs or with dynamic programming. If you want to minimize the probability of failure, then you want to maximize the probability of success.

The probability of succeeding on all your moves is the product of the probability of succeeding on each move. All right? So if you have five moves, then you have five individual probabilities.

You multiply them up. And that's the probability that you execute the whole sequence correctly, and not stumble. So we have products instead of sums. Yes?

AUDIENCE: Isn't it related to the maximizing score goal?

PROFESSOR: You can. Well, not necessarily because this one says that you only have some possible moves. I think in the end, all of them, except for this last one, can be solved using the recursion depth we have for it. The last one, you have to do a bit of massaging. And we're going over that right now.

So, you have products instead of sums. How do you turn products into sums?

AUDIENCE: Logs?

PROFESSOR: Yep. So, for this one, I would want to use logs, so that I can say that I want to maximize the log probability of success. Which is just the sum of the log probabilities for each move. And then it looks like dynamic programming, as usual.

Now, if I wouldn't want to use logs, if I'm using the DP formulation, where I'm doing recursion, I can incorporate products there. But it turns out, I didn't practice. If you have a lot of numbers that are close to 1, or that are close to 0, so all the easy moves are going to be really close to 1, for example.

If you have a lot of numbers that are close to 1 or close to 0, if you multiply them up, you get numerical instabilities. So we get the number that's really close to 1. So for example, if I'm choosing whether to do, say I'm here, and I'm thinking, do I want to move like this? Or do I want to move like this, and then like this?

These are both pretty easy moves. So, in both cases, we're looking at probabilities of success of 99.991%. And maybe 99.992%. So if you have numbers with probabilities that are really close to 1, and if you have a lot of them and you try to multiply them, you're going to get a bad result.

So all the products are going to start looking the same. So we're going to get a random solution, instead of what you want. This is a practical thing.

It's called numerical instability. And it's a practical reason why you'd want to use logs, instead of multiplying things up. So it's not just a theoretical thing. It also makes life nice in practice.

OK. So we have a goal that looks like this. Say, let's go for this one. Hit all the notes, minimize the effort. And all the other ones can be reduced to this one.

We need to define effort, right? Let's say that we have a function called delta, that takes two foot locations-- so, where both of my feet are-- from and to. And it gives me a number from 0 to 1, where 0 is really easy. And 1 is really hard.

So from would look something like, my left foot is up. My right foot is centered. To would look something like, my left foot is centered and my right foot is up. So basically going from here to here. So from left foot up. Right foot center. To here.

So there is some difficulty there, right? We have to jump, so it's not 0. I'm burning some calories here. So any move that I make has some difficulty. And I want to solve the game so that overall I have a reasonably small total difficulty. OK, are we understanding the problem?

So we have three possible avenues here. We can start solving it using dynamic programming. We can start solving it using graphs. Or we can have someone else play the DDR again so that we can get more hands on experience, and look at what a good strategy or a bad strategy looks like.

So you guys get to vote. Who wants to solve this using the dynamic programming? Who wants to solve this using graphs? Who wants to get more hands on experience? Damn. I was hoping that DDR would win. You guys are boring.

So, graphs, right? We're going to have notes. Notes represent states, right? So a state is where you are at some point in the game. And we'll have to define what where you are means.

And then, when you jump, you make a move. So moves go between states. So in any game, you have states and moves. A state is very hard to put in time. And then you make a move.

Like in chess. Your state is your board position. And whether you're moving, or your opponent is the next to move. And the move is when you take a piece and put it from one place to another.

So your vertices are states. And your edges are moves. So what's in a state? This is our problem. Whether we're solving it with graphs or with dynamic programming, this is what everything comes down to. What's in the state?

AUDIENCE: So your current state is how much difficulty have you-- what is the problem? Are those representing the probabilities, the difficulties? Or.

PROFESSOR: So this is the difficulty for one move. Does it depend on previous moves?

AUDIENCE: No, but.

PROFESSOR: No. So it's a nice thing to note that the difficulties for each move are independent.

AUDIENCE: Would it be dependent in real life? You'll get tired at the end. And he's able to have less energy.

PROFESSOR: Yep. So, in real life, we might want to say that this actually depends on how much energy you've expended so far. And if we have time, let's solve that problem. So the nice thing about this problem is there are many directions in which we can take it. This is one of them.

I'm fine. And I think we'll learn a lot by doing that. So back to the original problem.

Suppose that it doesn't matter how tired you are. You're pretty good, so you're not going to be tired enough to go [GASP]. So, mostly independent difficulties for each move. What's in a state?

AUDIENCE: The sum of the difficulties up to that point.

PROFESSOR: OK. So.

AUDIENCE: Your appearance factor, if we're including that. Or are we only doing--

PROFESSOR: So we're doing this.

AUDIENCE: Oh, I was just. Oh, effort. OK, we're minimizing effort.

PROFESSOR: So the way I like to think of this is, what is does a solution look like? It's made up of decisions, right? What are the decisions?

AUDIENCE: To make that move or don't make that move?

PROFESSOR: We'll see. But once you know what the decisions are, then you have to think, what do I need to make a decision?

AUDIENCE: The note.

PROFESSOR: So, a note is one of these. For some reason, they're called notes.

AUDIENCE: So you know that somehow you have to hit all of them? Like, you can have steps in between.

PROFESSOR: Yep.

AUDIENCE: Moves in between. You have to hit all of them.

PROFESSOR: OK, so I like this. So, every one of these is going to have to generate a move. And there might be some moves in between. Well, each move is going to map to some edge. And I'm going to need vertices.

So, as an algorithms program where when I hear that, oh. I can have some moves in between, I get really uneasy. Like, what is this? How many moves am I going to have? Is this going to become really huge? And am I not going to be able to run any algorithm on it?

So let's think about that. How many moves would I have in between? And, what would I achieve with them?

AUDIENCE: I guess you'd have a max of, like, four, right? I mean, you can put your right leg someplace, and you can put your left leg someplace. That's like a max of two. Right? Or no?

PROFESSOR: So, let's think of an example. You want to go, say, I want to go, what? From here to here, right?

AUDIENCE: Um-hmm.

PROFESSOR: And you're thinking what? They can do this, oh sorry. So I can do this as one move. And this is one move.

AUDIENCE: Yeah. Or you can just do one jump, right? So it's-- oh, yeah. I guess that's more than one.

PROFESSOR: OK. So looking at this, if I'm considering whether to go from here to here. If I want to go either this way, or if I want to go this way. So let's write this down on the board.

So I'm going from up down to left right. And I'm considering, do I want to go directly or do I want to go up right first. And then left right. Let's not do these arrows because they're confusing.

So, do I want to transition like this? Or do I want to transition like this? Well, I claim that, since my moves are independent, going from here to here, if it's beneficial to go this way instead of this way, I would want to go this way all the time.

So I would just say that, look. Inside my delta here, I would say that, actually, if you know what you're doing, whenever you have to go from here to here, you're going to go like this. And the delta is going to report to the total delta for this. So, if the problem is that they have one note, and then I have my next note like this, between these two notes, I can always go in one move.

AUDIENCE: So you're saying 1 would like, including in our difficulty function, it'll also tell us, like, what move we should make to get there?

PROFESSOR: How to get there. The best way to get from one state to another. Well, like when you're learning DDR, these are the basic steps, right? Like, you practice until you know how to get from one place to another. There is something else where you need intermediate steps.

AUDIENCE: Or if you're holding one and then you've got to move to another. Right?

PROFESSOR: So, let's not worry about holds. Let's say that we would just represent holds as-- so if you have a hold in a game, then we're just going to represent it like this. We're going to cheat. So we don't have to deal with it. In real life, you would have to deal with it. Like if you're actually writing a program that trains people.

AUDIENCE: What happens if you have, like, right, left, up or something. So let's say you start off hitting your right foot on the top, and then you have to hit the right one again. And then you have to hit up again and then you have to transfer. So I guess anytime you have to through the middle. You have move your foot.

PROFESSOR: So I like the idea of going through the middle. Why or how do you, why would you go through the middle?

AUDIENCE: To avoid crossing your leg over or something.

PROFESSOR: Well, what if I have something like this? If there are DDR experts, I know this isn't the right way to do it. But one way of doing it is left, right, left, right, left, right. So then, I have some states that account for the fact that I'm centering.

So, some people like to do this, right? Some people like to go to the center as much as possible, if they have time between the moves. So then, I would need at least one state in between where I'm allowed to center, right? In order to represent what I just did there, I need one move.

So, one way I could meet this is I have left center. And then left right. And then left right, left right, left right. So on and so forth.

But this would mean that instead of doing this, which is reasonably easy, I would have to do this. This. And then jump, jump, jump, jump every time. Harder. Not good. Not good for my knees. Not good for my score.

So I don't want to do this. I want to have an intermediate state so I can say, I start here and then I get back here. Then I do this. Then I get back here. Then I go here. And then I go back here. And then go back. Do guys see how this works?

AUDIENCE: You could also rock back and forth to because they don't require both feet to be on the ground the entire time.

PROFESSOR: Rock back and forth. Hold that thought. That might come in handy. Assuming we have enough time. So, if we only do one move every time we see a note, we're stuck with this. In our to allow re-centering, we have to add states between the notes.

We need to add an intermediary state. And you can either think about it, or take my word for it, but if you represent the notes using the trick that I said above, and you want to represent centering, then all you need is one extra state. So one extra move between every two states. Between two notes.

And that's enough. Because that one extra state allows you to center. And it allows you to do pretty much everything a beginner like me would know how to do.

AUDIENCE: So you only need one extra state between each note?

PROFESSOR: Yep. That is the inside. That is where I'm thinking, right? So I have to do both this trick, to see that I don't need an infinite number of steps. And come up with the need for centering to see why I need one intermediate step.

By the way, does anyone know what's the right way of doing that? What's the right way of doing this move? You said, rock back and forth. So I wouldn't rock back and forth in this case, right? Because that wouldn't be helpful. How would I rock?

AUDIENCE: Well, you hold down one and then you go to the other one.

PROFESSOR: Yeah, so rock left and right. OK.

AUDIENCE: I said back and forth, I meant rocking--

PROFESSOR: Sorry. I thought back, forth. So, the optimal way of doing this is left, right, left, right, left, right. So what am I doing?

AUDIENCE: You have another move. You have, like, one state for your foot where it's not touching the ground.

PROFESSOR: OK. It's an interesting, and important, distinction. So if I wanted to hit both of them, if I'm here, and I need to hit both of them, I need to hit them. If I only need to hit one of them, if I'm here, I can hit it like this. If I'm here, though, and I want to hit it, I have to lift myself up.

So the difference is whether I'm like this. Or like this. Where is my weight? So if I want to allow for these moves, if I want to go past the stage of very beginner, aside from keeping track of where my feet are, I have to keep track of whether my weight is on my left foot or on my right foot. So, I would actually have l, r, and W, where W is either l or r.

AUDIENCE: So your state now has what you're currently putting more weight on.

PROFESSOR: And where each of the feet are.

AUDIENCE: Yeah. Where your two feet are. And then also, the song difficulty. So it's everything in your state, right?

PROFESSOR: Ah, yes. I didn't think about it. I was just talking about foot position. But we need to get back to the state thing. So that's a good point. So before we get to that, how many feet positions do we have? If we don't include where do I have my weight, how many possible positions for both of my feet do I have?

So I have two feet. Each of them can be in any of these five squares, right? So how many total positions?

AUDIENCE: 5 choose 2. Using 2.

PROFESSOR: So I can do this.

AUDIENCE: Sure. Why not?

PROFESSOR: Well, if I have 5 choose 2, then you--

AUDIENCE: Oh, then that doesn't quite work.

PROFESSOR: Yeah.

AUDIENCE: Yeah, no.

PROFESSOR: So flip.

AUDIENCE: Times 2.

PROFESSOR: Yeah. So you have two feet. Each foot, five possibilities. Now, what if we have weight? If we are tracking on where I keep my weight. How many possible positions?

AUDIENCE: [INAUDIBLE]? Oh no, because there's only two.

PROFESSOR: So, for each of these, there's two possibilities now. So 50.

AUDIENCE: You also have to be so your weight is like this.

PROFESSOR: In the middle?

AUDIENCE: Yeah.

PROFESSOR: You can. Based on that what I've been reading, you never want to. Because if you're weight is in the middle, then you're extending a lot of effort to move either foot. So you always want to have your weight somewhere. So that, at least for one of your feet, it's easy to move it.

AUDIENCE: Could it be the back?

PROFESSOR: If that's not true, then yeah. We'd need to have a center. Oh, so, like, whether I'm like this or like this?

AUDIENCE: Yeah. If you were, like, doing the same thing. Rocking back and forth.

PROFESSOR: So, if I have two feet, then this says my weight is on my left foot. My weight is on my right foot. So l and r is which foot, not where on the board.

AUDIENCE: So, did you not do center because it was optimal?

PROFESSOR: Because I claim that, in an optimal strategy, you wouldn't have it. But you don't have to take my word for it. If you don't believe me, then you add center. And you just have more possibilities. And if it happens to not be an optimal thing, then the dynamic programming will ignore it.

So how many positions do I have if I add center? So if I have left, center, right for each position.

AUDIENCE: 75.

PROFESSOR: Cool. Yes.

AUDIENCE: So why is it 25? You wouldn't actually have both of your feet on the right.

PROFESSOR: Why? Maybe, well especially, for maximizing this one actually. Especially for maximizing entertainment. Then it's way cooler to do this, right?

[LAUGHTER]

You get the point.

AUDIENCE: --possible weight. Like combinations for like, where is you should have your feet at one time. Like, not necessarily what the game is asking you to do.

PROFESSOR: Yeah. So this is where my feet are. The game will always ask something like this. So the game won't always care about both of my feet. Sometimes it'll only care about one foot.

So, yeah. There are two different concepts, right? There's the position of my feet. And then there's the note on the screen. And my feet have to match the note on the screen. And we'll have to capture that somehow.

So what's in a state? What are my decisions? Come on, now. We should be in a good shape to know what my decisions are. What do I decide every time?

AUDIENCE: What move to make?

PROFESSOR: Yeah. How am I going to jump, right? Where my feet are going to be in the new position. So every time, I'm deciding what's the new foot position.

AUDIENCE: Aren't you also deciding weight position, where you're going to hold to, right?

PROFESSOR: OK. So when I say foot position, it's a cheat for everything. So yeah. Good observation. OK. What do I need to know, in order to make this decision?

OK. I would need to know where I was before if I want to compute the difficulties. But aside from that-- what?

AUDIENCE: Sir, it came up with this polynomial.

PROFESSOR: All right.

AUDIENCE: Is that a hint to what the run time of this will be?

PROFESSOR: It's not on purpose. But yes. So, yeah. That makes sense. Probably not good. I should probably not have my screen up without me looking at it. OK, so. Back to decisions.

I think I want to know what's going to be on the screen when I land, right? Because if the screen says, yo, you need to go up and down. Then maybe I shouldn't do this, right? That would not be good. So I need to know what the note is going to be when I land. Note.

AUDIENCE: Is that the same as the next?

PROFESSOR: Yep. Next note. Yes. So the next note here on the screen. So, my position in this list, basically.

AUDIENCE: So it's kind of like the knapsack problem, where it's like which thing we're considering picking up. But in this case, it's coming [INAUDIBLE].

PROFESSOR: So it's close to knapsack. But the difference is, in knapsack, I have to decide, do I choose this or do I ignore it. So, if I'd be like, if I can only do a few things and I want to maximize my score, then maybe I would choose, all right.

This is easy. I'm going to do it. This is hard. Screw it. This is easy. I'm going to do it. So then my decisions are 0, 1. Pick or not pick. In this case, every time my decision is a new state of my feet. So it's not 0, 1.

AUDIENCE: OK.

PROFESSOR: That's the difference. And then, because of that, the state is going to look different. And the recursion's will look a bit different.

OK. So I want to know the note that I'm landing at. I want to know the sum of-- well, we'll see if I want to know the sum of difficulties up to this point. And I want to know one more thing, so.

If this is going to be my new state, and I know what note I'm landing at, I'm making a decision. The decision tells me where my feet are going to be. Right?

The move decides where my feet are going to be. What do I need to do? What else do I need to know for my total solution?

So what do I need to know to consider between decisions? So say I'm considering the state of-- I'm at note two. Note two says, left right. And I'm considering of coming here from note one, where my foot position was up down. Or come here from note one, where my foot position was left right.

I need to know where my foot position was, to choose between these, right? If I don't know that, then I can't choose.

AUDIENCE: That's not from your state, though?

PROFESSOR: Not yet. It's not here, so it's not part of my state. We've been talking about it a lot, but we didn't put it here. So let's say that the state is going to have the note that I'm landing at. And my foot position after landing.

So, if I know that I'm going to land like this, then I know where I was here. l r. Say, l r. I can compute the costs here, right? This is delta of going from this to this. And this is the delta for going from this to this. Can you see? Is that too small?

Delta wants to know where my feet were before. And where they're going to be now. So when I call it, I need to know where I was before. And I need to know where I'm going to be now. So this should be part of my state.

So our decision says, what's my new position going to be? So when I make a move, I influence my new foot position. They're going to be in someplace.

And independently of that, the note-- the position here-- the position of the note, increases all the time, right? Because time can only go forwards. How are we going to account for these extra moves?

AUDIENCE: [INAUDIBLE].

PROFESSOR: So, we said that between every two notes, we might want to make one extra move.

AUDIENCE: Like, a potential new note in between your destination note?

PROFESSOR: Yep.

AUDIENCE: And then just fill in the difficulties for that and see which ones--

PROFESSOR: So, if I want to use the algorithm that I already have, that compares my landing position to my note, to see whether I can go there or not, what note would I want to put in that intermediate note? So, you're basically saying that between every two notes, I'm going to have one more note. And my feet can be wherever here.

AUDIENCE: Oh. I mean, you'll also have the edge originally connecting them. So, you'd have it going to the intermediate note, but also from the destination. Yeah, like that. You'd have to--

PROFESSOR: So, what note would I have here?

AUDIENCE: It makes you go to the center.

PROFESSOR: Do I have to be at the center?

AUDIENCE: Well, you can be anywhere.

PROFESSOR: Yeah. So I'm going to invent the blank note. That's a big O. That means you can do whatever you want. There are no constraints. So that is just an intermediary state. So then I'm going to take this input, and I'm going to add these blank notes here. And these map to adding notes in the graph.

AUDIENCE: Well, then, when you just run through your difficulty function between each two notes and see if, for all the potential moves, which one minimizes that path.

PROFESSOR: Yep. So basically, I'm assuming I don't need this. I'm assuming that. This is going to be where there's at least one choice where this is going to have the same cost as a direct note. And then I'm going to say that instead of having more complex shapes in the graph, I'm going to insert extra moves here.

AUDIENCE: OK. I would think that, if you have an intermediate move that might be less expensive, you should, like, just hop to that new position than to have an intermediate move, right?

PROFESSOR: Yeah. And I'm going to assume that either that's not the case, or that I can always find an intermediate move that makes my life better.

AUDIENCE: Every case?

PROFESSOR: Yeah.

PROFESSOR: These results do work. You'll have to take my word for it that this works. And this makes your dynamic programming easy. And it makes your graph building easy. So the advantage of this is you're changing the input. And then, when you're building your graph or when you're doing the DP, you only worry about an input that looks like this.

You don't care about any intermediate stuff. You have notes, and you have to transition between the notes. Period. So we reduce the complexity of the problem.

So whenever you can get away with that, it's really nice. We can do that for centering. We might not be able to do it for other more complicated stuff. OK.

So, we sort of know what we want in a state. Now we want to build a graph, so that the path from some source to some destination has a cost that's equivalent to the sum of these difficulties. Right? Because then I can run the shortest path. And my solution will be right there.

I know. You guys seem awfully sad. Do you want to take a break and play for a little bit more? Yes? How many people want to play, instead of. You don't have to play yourself.

You can just rest for these two or three minutes. And you can watch someone else play. And get more intuition about how you're supposed to play. OK. So one person wants to take a break. Everyone else wants to keep going? Or are you guys passed out already?

AUDIENCE: Can we get out early?

PROFESSOR: Sort of. Yeah. You'll get out three minutes early, if we don't do another round. So who wants to keep going?

AUDIENCE: No. Let's play.

PROFESSOR: OK. So who wants to keep going? You can only vote on one thing. Who wants to play?

AUDIENCE: OK.

AUDIENCE: Five.

AUDIENCE: Four.

AUDIENCE: Victor, go.

PROFESSOR: OK. Who wants to go? So we decided what we're going to have in notes. And we're going to build a graph, where the notes are the states. And the edges are the moves. Right?

So a note tells me, just like there, what note I'm at. Say I'm at note two. And where my feet are on. So, left foot left. Right foot right.

So, given a state, what outgoing edges do I build? Where can I go to? So let's say I have a state that says I'm at note n and my left foot is in some position. My right foot is in some position. What are my outgoing edges from here?

AUDIENCE: Is there an outgoing edge to every move? Because there's a point.

PROFESSOR: OK. Well, actually, the blank is a note, right? So if the next note, if note three's a blank, then the note is a blank. And then I can have.

AUDIENCE: I guess, isn't the difficulty of the move dependent on what note that blank actually is?

PROFESSOR: So, it doesn't depend on what the screen says. It depends on where my feet are.

AUDIENCE: Oh, OK. I see.

PROFESSOR: So I have a number that tells me what's on my screen. This number is enough for me to know what's going to be on my screen from now on until forever. Because I have the list ahead of time.

And then I have the position of my feet. So these are both part of the state. So I have notes for all the notes. And all the positions of the feet.

AUDIENCE: Right. But the blank note is just one position of feet?

PROFESSOR: No.

AUDIENCE: Or, it's all positions.

PROFESSOR: Yeah.

AUDIENCE: Isn't the difficulty dependent on what position your feet end up?

PROFESSOR: Yeah. So it's from where I start to where I land. So, if I decide to start from here, and go here, the difficulty of this move is-- so it doesn't depend on whether I have a blank there.

And this was OK. Or, if I had an up down, then I just missed the note. But the difficulty, the effort I'm expending, is the same.

AUDIENCE: OK. But if you start from that other move and go to a different position, that's--

PROFESSOR: If I go from this to this, then that's a different difficulty.

AUDIENCE: But it still could be a blank note?

PROFESSOR: Yeah. So, a blank note will let me go wherever I want.

AUDIENCE: I see. But there are different kinds of blank notes, with different-- I guess I'm confused as to what--

PROFESSOR: OK. So let's go through them again.

AUDIENCE: Is it kind of like it's, like, spreading, so really when you have your source note, it's actually connecting to every possible move. And every possible move is connecting to your next-- so it's kind of like a diamond shaped thing?

PROFESSOR: Not quite. Not quite. So, let's go through the notes again. And then let's go through that. So the source move will be connected to some notes. And then those notes will be connected to other notes.

And it looks more like you have a big, outgoing degree. Then you have a big network. Then the big, incoming degree. It looks like a messed up sorting network.

So, notes are constraints. This accepts any possible feet combination, right? So this accepts this.

AUDIENCE: Is the first combination contained in that note? In that blank note?

PROFESSOR: No. The blank is a constraint. So, if I have a note that looks like this, then if one of my feet is here and the other one is in the center, then that's fine. The constraint is met. If one of my feet is up and the other one is down, then the constraint is met.

AUDIENCE: But the edge running into that blank note, depending on how your feet land, is different difficulty. Is that right?

PROFESSOR: Yep. But when I compute the edge width, I need to know where I'm landing exactly. Not just where the note is because the note might admit multiple positions.

AUDIENCE: I see.

PROFESSOR: So this guy admits all positions.

AUDIENCE: OK.

PROFESSOR: This guy admits some positions, right? These are l r, l r. If I have up down, how many feet positions does it admit?

AUDIENCE: Just one.

PROFESSOR: Not great.

AUDIENCE: No.

PROFESSOR: How many?

AUDIENCE: As an intermediate?

PROFESSOR: If it's up down, then it's on the screen. My intermediates are all blank.

AUDIENCE: Oh, oh. I thought you were saying start with that.

PROFESSOR: So up down. If you see up down on the screen, how many feet positions?

AUDIENCE: Left to right what it could have.

PROFESSOR: Yep. So, if the screen says up down, the only two ways I can do that is this. Or this. Right? So, two positions.

AUDIENCE: I see.

AUDIENCE: Well, I mean, but you could have intermediate where you step in the first one, then back.

PROFESSOR: But I don't care because I've added these blank notes. And they take care of my intermediates for me.

AUDIENCE: But so, we're saying where the feet land aren't part of the note.

PROFESSOR: Nope. They're just states. So they're a decision I'm making.

AUDIENCE: So, do we have the multiple-- no, we don't because they're not part of the--

PROFESSOR: For each note position here, for every position in the screen thing, I have multiple feet positions that I could be in.

AUDIENCE: Right. Right. But then, are there multiple moves to get to those?

PROFESSOR: Yep.

AUDIENCE: OK. So there's multiple moves connecting each.

PROFESSOR: Yeah. So for example, if I want to get to l r, up down here, I can go from l r, up down in the blank. Or, I could have l r be like this. And then transition. So I can have a lot of possible foot positions that I'm transitioning from in order to get here.

AUDIENCE: But those aren't actually separate notes on the graph.

PROFESSOR: They are. They have to be. So these all have to be separate notes. Because the edges are going to have separate weights. Right? This edge is going to have one weight. This edge is going to have another weight.

AUDIENCE: OK. That's what I thought. But then you said there was only one blank. Don't there have to be multiple blank notes for every foot thing. If you're approaching a note from different--

PROFESSOR: So, I'm not sure what you're asking. So, if you want to care about centering, if you want to have intermediate moves, you need one blank note between every real note. So that you're allowed to make one intermediate move between.

AUDIENCE: Right. I get that that's talking about the on the screen.

PROFESSOR: Yeah. That's the screen.

AUDIENCE: That's the screen.

PROFESSOR: Yep.

AUDIENCE: OK. So, that's not the graph, though. Here, we're talking about the screen on the graph.

PROFESSOR: Here, we're talking about the graph. So two tells me that the screen is at note two. Whatever that happens to be. And my feet are in this position. OK. So that's very important. Thanks for asking because that's very important. So, a state has the note that I'm landing at. So, where the screen is. And where my feet are.

AUDIENCE: OK.

PROFESSOR: OK.

AUDIENCE: The state corresponds to the nodes that you're on.

PROFESSOR: A note. A note is a state. So, a note is a state. And a move goes between two states. This is how we represent all the graph problems. OK.

AUDIENCE: So, you need multiple blank.

PROFESSOR: Yeah. So here, I'm just drawing one example. Yeah. Yeah. So for example, here I would need-- sorry. Oh, OK. I get your confusion now. So, yeah. This would be one move. This would be another move.

AUDIENCE: That's all for a single thing on the screen.

PROFESSOR: Yep.

AUDIENCE: OK. OK. That makes sense.

AUDIENCE: So the next note would have a really large end degree, right? I guess they always have--

AUDIENCE: Well, no. It'd have lots of--

PROFESSOR: So, this note has a huge out degree.

AUDIENCE: Yeah. But I'm saying the ones that all those intermediates connect to.

PROFESSOR: Yeah.

AUDIENCE: So, then, they would connect with some note that have, like, really large degree.

PROFESSOR: Yep.

AUDIENCE: But there's two of them after that, right? Because there would be two different--

PROFESSOR: So, what's next? Next, is position, hmm. How did U number them? I guess, crap. No. It's not going to match that, so. Whatever we do, it's not going to match that. Say the next note, 4, is just an up.

4 is up down. And then I have two notes for it, right? Wild One note, l r. So this is note 4. That happens to be up down. And then I have this. And every one of these connects to every one of these.

AUDIENCE: If the next move is up down, how can notes have down up? Oh, because you can switch the feet.

PROFESSOR: Yep.

AUDIENCE: Oh.

PROFESSOR: Yeah. So, I aimed to ask you guys, how am I going to draw the edges? But you guys made me do it with questions. So, suppose I met note n, l, r. What edges do I draw going out of it?

So, note n, left foot at some position. Right foot at some position. What are my outgoing edges?

AUDIENCE: This is a note on the screen. Or--

PROFESSOR: In the graph.

AUDIENCE: --the new one or intermediate one?

PROFESSOR: Doesn't matter. So, intermediate notes have a note blank.

AUDIENCE: That's just everything.

PROFESSOR: It doesn't matter. Yeah, we're looking at all of them at the same time.

AUDIENCE: Wait, so you're asking what are--

PROFESSOR: So, given this note, who am I connecting it to? Let's draw the outgoing edges. So, if you're solving this as a graph problem, you build the notes. You draw the edges. You're on some algorithm. So let's draw the edges.

AUDIENCE: I think it depends if you're an intermediate note or not.

PROFESSOR: Nope. So the note tells you what your constraints are. And that covers intermediate notes. If you're note is a blank, then, well, there's no constraints. If the note is not a blank, then there are constraints.

AUDIENCE: Oh, note. I thought that was referring to the note, not the--

PROFESSOR: No. So this is a note. Maybe n is not good. Let's use i, instead, then. If n is hard. So, i is the position here, in this guy. Right?

Say for example, i equals 1 here. I equals 2 here. I equals 3 here. So and so forth. And that doesn't match this, so.

AUDIENCE: We're talking about note--

PROFESSOR: Yep.

AUDIENCE: --not--

PROFESSOR: If one note is represented by these three numbers, right? Each note has this tuple in it.

AUDIENCE: Then i is the note.

PROFESSOR: Yep.

AUDIENCE: So i connects to i plus 1. And then all possibilities known.

PROFESSOR: OK. So this connects to i plus 1. And then all possible destinations, right? So I'm going to say left. This is after the jump. So, left after the jump, and right after the jump. And this is for all possible left after a jump, right after the jump. And lost a weight on this edge.

AUDIENCE: The way that it's from--

AUDIENCE: l r to

AUDIENCE: --l r to l r.

AUDIENCE: l j-- l sub j r.

AUDIENCE: l r.

PROFESSOR: So you want to say from l r to l j, r j. But what?

AUDIENCE: Difficulty level?

PROFESSOR: Yeah. Where is that?

AUDIENCE: Your difficulty function.

PROFESSOR: Which is?

AUDIENCE: Delta.

PROFESSOR: Delta. So, yeah. The weight is delta. I drew d. Delta of these two foot positions. Almost. If I want to minimize the difficulty, then this is right.

If I want to maximize a score, then I would have to add a minus sign. But if you're minimizing the difficulty, this is exactly the way because it maps the shortest path. Usually, in dynamic programming, things are maximized.

AUDIENCE: Wait, why would you add a minus if it's--

PROFESSOR: So, if we're maximizing something, we have to flip-- we have to add a minus to the edge costs because--

AUDIENCE: Right.

PROFESSOR: Yeah. But this time we're minimizing something.

AUDIENCE: Oh. Right, right, right.

PROFESSOR: I promised you that we'll maximize something all the time. Well, I guess I lied.

AUDIENCE: OK. Right, right, right.

AUDIENCE: You don't want to maximize d. Then you're dead.

PROFESSOR: No. You want to maximize show offs. So if we have the entertainment thing, then that would be maximized. And then you'd have minus.

AUDIENCE: Then you'd have everything you need.

PROFESSOR: Yep.

AUDIENCE: OK.

PROFESSOR: OK, so we're almost good. Source notes and destination notes.

AUDIENCE: Well, I guess source, we know that means start in the middle. Right? Like, you would start off with--

PROFESSOR: What's the source? You want to start at the first note, right?

AUDIENCE: Yeah.

PROFESSOR: But in which position?

AUDIENCE: Well, in the center, right? I mean, the [INAUDIBLE] start. Or, I guess you could start--

AUDIENCE: Wherever you want.

AUDIENCE: Could you add a source note going to a bunch of intermediate notes?

PROFESSOR: Yeah. Yeah. So what I'm going to do is I'm going to say there is a note 0. That let's me choose how I'm going to start.

AUDIENCE: Oh, it could be any position. It's like an intermediate note itself.

PROFESSOR: Yep. So I'm going to have a note 0, with all possible foot positions. And then this is going to be connected to a source, by edges of weight 0. So the intuition is that I get to choose my starting position, right?

Starting position. I see the first note. I make a move. So I want to be able to choose the starting position. That's why I have all those notes. And then make a move to touch the first note.

AUDIENCE: The starting position is also a note.

PROFESSOR: Yep. Because, if the first note is here, I don't necessarily want to start like this because maybe this is harder than this. All right. What's the destination?

AUDIENCE: The last note.

PROFESSOR: OK. So, all the notes that are at note n, and have any position, would be connected to a destination note, using an edge of weight 0. Or I can consider them as destinations. And then choose the destination that has the shortest path.

AUDIENCE: Oh, I see. The final destination is going to be, like, two notes. Right? It's going to be that last position, and then--

PROFESSOR: Or it might be more than two if the note is just a simple note. Because that wouldn't constrain my feet too much. OK. And last, last question. Dijkstra or Bellman-Ford?

AUDIENCE: Bellman-Ford, because you have negative edges, negative weight, as if you were going to maximize to death.

PROFESSOR: So, this is always going to be from 0 to 1. So I could possibly use Dijkstra. The answer is neither. The answer is, we're building a DAG, so.

AUDIENCE: Dijkstra.

AUDIENCE: We don't use that.

PROFESSOR: DAG, shortest path. Every time we have dynamic programming, DAG, shortest path. OK?

AUDIENCE: Question.

PROFESSOR: Yeah. Come on, last question. You can't get away that easily. OK, so. Who wants to play?