Optimizing with a Data Structure

[00:00:00]
>> I want you to notice something about reachable keys, it is brute force, it is ugly code. But I want you to notice something about the output of reachable keys. Does it ever change, depending on anything about the user's actions? Is there anything about the user's actions that affects the outcome of the reachable keys function?

[00:00:34]
The answer is no. In fact, what we are doing is brute force computing something which is already pre-known by the geometry of the board. You with me? Why don't we just make a data structure that has the reachableKeys in it, instead of making a data structure that is the dial pad that we then have to go and compute some geometry information from?

[00:01:07]
Why don't we just start with the data structure that is the list of reachableKeys? It's fixed information, it's gonna be very easy to compute. Why recompute it every single time we hover over a key? Everybody follow that? I'm gonna show you how easy it is to precompute. I'm gonna copy that code, and I think only that code, let me make sure.

[00:01:37]
Yeah, only that code I'm gonna copy. Just gonna drag over my little console here, so we have a little bit more space to put some code in. I'm gonna put that code in here. It's a little harder for you to read down there, but maybe I can zoom this in, so it's a little easier for you to type.

[00:02:08]
All I'm going to do is create a for loop that calls this function once for each of the possible keys. And I'm gonna call that nearbykeys for (let i = 0; i <= 9; i ++) {NearbyKeys.push(reachableKeys(i));}. This for loop is simply going to call that function once for each of the possible digits, 0 through 9.

[00:02:52]
Whatever it returns, we're just gonna push it into this nearbyKeys array. And then just for good measure, I'm gonna pretty print out the nearbyKeys, you'll see why here in a moment. So we run this code. I meant to do a JSON string, sorry. Console.log(JSON.stringify), was what I meant to pretty print it.

[00:03:30]
And now, I'm simply going to copy-paste. I'm gonna copy that and I go back to the code editor, and I'm gonna delete all of that. And give me just a moment to manually type all this. I could probably do this with a regular expression, but I'm gonna type this out even quicker than I could write the regular expression.

[00:04:08]
The truth is in about the same amount of time as we wrote the code and then wrote the code to drive it, we could have just manually written this out. You could have just looked at the board and said, I know if I'm on key 0, I can go to key 4 and 6.

[00:04:23]
And if I'm on key 1, I can go to 6 and 8. And if I'm on keys 2, I can go to 7 and 9. You could have just written this out, probably a lot quicker than it took for us to go through writing the code. But I did that because I want to reinforce the point that in many algorithmic problems that we tackle, there is fixed known upfront stuff and you should precompute as much of that as you can.

[00:04:47]
You should not defer until the run time that which can be figured out pre-run time. There is absolutely nothing about that knowledge of those nearby keys that needs to be recomputed, and so we should precompute it. And it turns out that the nearbyKeys is gonna be a much better data structure for us to start from than the data path.

[00:05:18]
We do still need that reachable keys function, because again, it's a, Public API method but look what it now does, instead of all that other junk that it was doing, now it just simply says nearbyKeys of startingDigit. That's a lot better, right? How many people like that solution better?

[00:05:43]
If you liked the previous one, no shame, but I don't understand why, just as a little bit of a heads up, because I like this code better and because it gets rid of a bunch of clutter in here. I jumped ahead a little bit, this optimization that I just made wasn't until one of our later branches.

[00:06:02]
So in the branches when you div, you'll see that I still left in that older version of reachableKeys. I just jumped ahead because I didn't wanna keep seeing all that ugly code.