Coding with Dynamic Programming

[00:00:00]
>> Okay, here we are in the code editor. First things, we need to undo the work we did in option 3. We're gonna get rid of the memoization stuff. That was a cool trick, but for this particular problem, there was a much better option. If you try tabulation and that ends up not working, I think the next best one is often memoization, but again, you have to make sure you're using something in the appropriate way.

[00:00:25]
Okay, so what are we going to do to do countPaths? So basically, I'm going to delete what's currently in countPaths. Actually, I guess I should have probably kept that first one, because that base condition stays the same. The base condition is still if we call countPaths with a hopCount is 0, the base condition is still the only thing that you can do is stay on that digit, so that's a count of 1.

[00:00:57]
All right, remember in the slides, and if you want to have the slides up while I'm typing, sometimes that's a little more helpful for folks to kind of visually connect or have the slides on a separate window side by side. But the first step that we wanted to do was have, An array that was initialized to all 1s.

[00:01:21]
That was our priorPathCount. That basically represents calling each one of these functions with hopCount 0. We're just gonna go ahead and pre-fill a set of buckets with all those ones. So our trick in JavaScript for creating an array of ten elements long with 1s in it is to do array of ten and then fill with the one value.

[00:01:43]
So that's our little temporary priorPathCounts that we will replace each time as we go. We're gonna set ourselves up a loop. This loop is the hopCount. Remember I told you we had an iteration count that was just decrementing hops, so I'm gonna have it counting upward rather than counting downward, but only because it's a little bit more convenient to write the terminating condition.

[00:02:11]
But it's basically the same thing, we're gonna do our six iterations because if we pass in hopCount of six, we're gonna do six iterations here. So hops = 0, hops less than hopCount, and hops++. That's our outer loop. And whatever our loop ends up computing, the thing that we're going to return is whatever is in prior pathCounts at the position startingDigit.

[00:02:44]
We're taking advantage of the fact that our digits are zero-based and our arrays are zero-based. If your problem had a different set of values for the buckets, then you'd need to do a translation here. But in our case, it's quite convenient that the digits on the dialpad happened to be zero-based, just like our arrays are indexed.

[00:03:05]
But that ends up selecting that bucket. For example, 4 would have 168 in it, and that's what we return. For each hopCount, remember that we did a loop through all ten digits. I'm sorry, the first thing that we did was set up a bucket of 0s, so that will call pathCount, With ten buckets all filled with 0s.

[00:03:34]
That's our actual buckets that we're gonna be filling into. And then we will replace priorPathCounts with pathCounts when we slide it up. All right, now we need to set up a loop to go through all the ten digits. It's pretty straightforward. Hopefully, that makes sense. We need to go through the ten digits, so we set up a plain old normal for loop to go through.

[00:04:01]
And what was the last thing that we did? For each digit, what did we do? We visited the other digits that we could have been at to get to that digit, so we need one more loop inside. I'll say n is the digit of the nearby key, Of the digit that we're on.

[00:04:30]
So if we are on digit 0, the nearby keys of digit will give us an array of 4 and 6, so we will go visit 4 and 6, and we will take into our current count at digitPosition. We will simply add in or append in the value that is in the priorPathCount,, Of n.

[00:04:57]
So remember when we reached out to the other two and we grabbed their priorPathCounts and added them together and made our own bucket? So we're going through all these ten buckets and grabbing in the two or the three from the other places, adding them together to create pathCount.

[00:05:12]
And our last step in this algorithm is at the end of each hop iteration, so on the outside of the digits, we simply replace priorPathCount with pathCount. This is 11 lines of code and the recursive implementation was 6 lines of code, so yes, this is a little bit more code.

[00:05:38]
But let's take a step back and realize that this is not hundreds of lines of complex code, is it? It's a set of for loops. And most of us have enough familiarity with programming and with JavaScript that we can manage to reason about for loops. The real key here is not the code that we could write.

[00:06:01]
I mean, yes, that's a thing, we need to be able to translate what we've planned out into code. But I figured out on the slides what the algorithm was, and then I simply wrote a line of code for each slide. That's it, it's not like I had to come up with some whole new theory or whole new algorithm.

[00:06:20]
I just figured out on those slides, well, what would I need to do? I would need to do a loop for all the hopCounts, and then for each of those hopCounts, I need to do a loop for all of the digits, and for each of those digits, a loop for all of the nearby keys that they could have been at.

[00:06:35]
And that's it, so I needed three loops and I needed two arrays. I wrote it out on the slides just like you could write it out on a sheet of paper, coming up with a plan for how to solve it. The translation to code is almost the trivial part.

[00:06:51]
And I know that we as engineers kinda feel like maybe it's the reverse. We kinda feel like, no, the really hard part is the writing of the code. The big takeaway that I hope you're getting from this workshop, and I keep repeating myself over and over, you've got to first think the problem before you can code the problem.

[00:07:10]
If you can solve thinking the problem, the code is probably gonna shake itself out pretty straightforward. I mean that's not entirely true, because, yes, there are complexities depending on our language, depending on the mechanisms that we use. Sometimes we do face these challenges, but the vast majority of the problem here is getting our brains to think about the problem correctly.

[00:07:34]
We have to think algorithms before we can code algorithms. As I've said multiple times in this course, there's no way that anybody could expect you to now be an expert on bottom-up dynamic programming tabulation because you just simply saw one problem that one guy helped you write code for.

[00:07:59]
That's not sufficient. But hopefully, there's enough from the way I've described it, cuz when I was trying to learn this stuff, there was not a lot of great material out there. The only material I found was, if you wanna compute Fibonacci with tabulation or something, this is very toy problems and the solutions end up looking very, very specific to the problem.

[00:08:22]
And this one is a solution that's very, very specific to the problem, but there are pieces of this that I do see as generalizable. If I can think about a problem as having a very specific defined set of inputs, if I can figure out what those would be, then I can figure out how to count each of them in the reverse order that I would go through it when I was doing a recursive approach.

[00:08:47]
So maybe the first step is to write the recursive version, so that I have my brain in tune with what the order is, if I would do it recursively in this order, do the reverse order, to do a bottom-up tabulation. Those are things that are generalizable principles and hopefully will help you attempt this technique the next time you're trying to write a recursive counting solution.

[00:09:13]
Questions, I see questions.
>> Having three nested loops here, is this acceptable in this scenario, because the iterations do not grow much as n grows?
>> The iterations don't grow any. [LAUGH] This is all fixed work. Look at the values that are returning here. We have a fixed for loop of 10, that never changes no matter how many hopCounts there are.

[00:09:41]
And we have this for loop, this inner for loop is only looking at the nearby digits, which is based on the fixed geometry of the dial pad which never changes. It's either 2 or 3 or 0 every single time. So these two inner loops don't grow at all and this loop only grows at n.

[00:10:00]
So that should tell you more than anything why this is a linear algorithm, cuz the only thing that grows is the outer loop and it only grows by n. There's nothing else complecting it. There's nothing else adding to it. It's not like one of these inner loops is then also bounded by n, so now it's an n squared or something like that.

[00:10:23]
If we go back to the browser, just to kinda get a sense of things, I'm gonna refresh, and I'm gonna go ahead and start us at 25, [LAUGH] and I'm gonna click the 4. And we're gonna see that that was 0.2 milliseconds. And then I'm gonna go up to 250, and that was 1.2 milliseconds.

[00:10:45]
And then I'm gonna go up to 2500, and that was 13.1 milliseconds. Because it's doing almost no work. It's just simply running through. And if we go back to the slides, we'll be able to kind of reinforce what's actually happening here. An O(6) does exactly 120 operations, and if you do an O(60) it does exactly 1200 operations, and if you do an O(600), it does exactly 12000 operations.

[00:11:23]
I literally counted those, I put a countering. No matter how big n is, if you multiply n by 10, you just get a number of operations multiplied by 10, which proves to use that this is a perfect linear solution, exactly linear solution. Like I said, it's rare that we get to those unicorn solutions, but when we do, that's when you turn the computer off and you get a beer, and you're like, hah, did it.

[00:11:52]
I earned my pay for today. I thought about the problem and I figured out the better solution. Any other questions or comments about the Knight's Dialer?
>> Comparing the two, cuz the previous recursion with the memoization was top-down and this is bottom-up, if there was a case in production of a Knight's Dialer, would this actually be what is put it to use?

[00:12:16]
>> If I had to do the Knight's Dialer for production, would I do this?
>> Yeah.
>> I 100% would write that code with a bottom-up tabulation. My process is that my brain does not, for me, my brain does not naturally think about the problem in reverse the way the bottom-up tabulation requires you to think about it.

[00:12:38]
So for me, I almost always have to solve the problem top-down recursively first, knowing that it's likely not to be the performance solution. And then I have to decide, is there a way for me to do it in reverse? In other words, are the number of possible buckets for all those leaves to be in a fixed and small enough number or is it practically infinite?

[00:13:01]
If it's a fixed and small enough number and if the problem is a counting thing or is something that I can make act like counting, right, can I make that work? Then I'll start trying to write the bottom-up tabulation. And if not, I'll apply a memorization and see, I'll look at my problem, but I'll apply memorization to see if that solves my recursive problem.

[00:13:23]
So that would be my general approach to this. I hope maybe someday I can just look at a problem and immediately know, that's a bottom-up tabulation. I'm not there yet, but I've at least generalized enough of this that I can see what parts of this do need to be present for this kind of solution to even be possible.

[00:13:41]
Yeah.
>> Comment on interpreting this problem. One of the features, and this is quite rare, problem you had is you have a stable tree. Your state tree is finite short, and it is a legitimate tree, so no cycles, no. And so as you expand, it expands to an endpoint to a fixed width.

[00:14:09]
That's your cue. When you can say, that fixed width fits nicely in a small box, that's the cue that this could be a good strategy, because the function is self-organizing in those cases. So that's just a comment, but I agree with you very much. It's not something that's gonna jump out to you.

[00:14:29]
>> Right, and you do have to inspect the problem, you have to think about the problem. To put it in slightly different terms than what he just said, if you think about it as the recursive fanning out. If there's a convergence into and I keep using this term of buckets, but as he said, it's kinda a finite set, even if that finite set is large, if it's finite, it can be done with this tabulation.

[00:14:54]
But if as you fan out into all possible solutions, you get to practically infinite, then this probably isn't the algorithmic approach that's gonna prove fruitful for you, so I probably wouldn't even try it. So let's take for example, because this is segue for the next exercise that we're gonna dive into.

[00:15:16]
If you were trying to think about all the possible words that you might be generating and fanning out recursively and trying to generate a bunch of different English words. Well, the English dictionary's 80,000 words, that is a fixed finite size. So if you were trying to count that, you could have, practically speaking, 100,000 buckets and do the counting of that.

[00:15:43]
But if it was all possible combinations of characters that aren't constrained by they need to be valid words in the dictionary, that's practically an infinite set. And if you have a practically infinite set, that's not where this algorithm is gonna work. So that's, I think, what he's saying, is you have to be able to see that it's gonna converge to something finite, not infinite.

[00:16:05]
Yes, there's another question.
>> What are the cons of tabulation?
>> I mean, the big con to tabulation is the unfamiliarity. It's not what most people see other people writing. It's not what people pull out readily. And at least for me, it's not the way my brain first thinks about the problem.

[00:16:29]
Because, if I look at the function 4, 6, my brain starts with, okay, if I'm gonna recurse, I'm gonna break down the problem into the hopCount of 5 and the hopCount of 4. It's the divide and conquer way of thinking. So if you've been trained to think that way, it's very hard to think in reverse.

[00:16:48]
And once you get better at being able to think in reverse, that gets easier, but I'm not sure it ever gets to the point where that's the natural way that you think is to solve a problem in reverse. That's just one of those techniques that you pick up.

[00:17:01]
So I'd say that's the big downside to it. The sort of secondary effect of that is whatever code you write to do that, somebody else can read that code, but they can't understand why that code solves the problem. I mean, most people are not gonna have any trouble reading your three-nested for loops.

[00:17:22]
It's pretty straightforward code, it's not terribly declarative, but it's pretty straightforward code. Most people are not gonna really struggle with understanding, I see some for loops here. But they are likely to strongly struggle with seeing that code and understanding how that code solves the problem. So there's an additional burden for you to document, perhaps even creating the slides like I did, document why that solution solves the problem.

[00:17:48]
You have to remember that the code that we write is our communication to other humans, including our future selves. And the code in this particular solution is not doing a great job of explaining the why. It's doing a pretty good job of explaining the how. So there's an additional documentation burden to explain the why.