Reachable Keys Function

[00:00:00]
>> Let's switch over to our code editor. And in our dialer module, you'll note that we have the three functions that correspond to the three tasks that I just described you. And our to do comments they're quite helpfully explained to us what we need to be returning. The reachableKeys function is called by the app.

[00:00:22]
You with me? It's called by the app. And when we go to run our app, we're going to need it to be able to respond correctly. Because in our app, when you hover over a key, the app uses the return from reachableKeys to highlight the possible places that we can jump.

[00:00:41]
So it's just a little usability thing. So reachableKeys is not just an internal utility, it's one of our public API methods used by the app. We'll look at the app here in just a moment, okay? We also want to implement the count Paths, that's their counter. And you can probably guess that this is where we're gonna have some pretty deep and moderately complex recursion going on, right?

[00:01:07]
Because there's a lot of paths and a lot of backtracking that immediately evokes the idea that we're probably gonna want to be doing some recursion. And then we have our listing out of our acyclic paths, and again, we're probably gonna end up using some recursion to do that.

[00:01:21]
Lots to tackle, we're gonna do it one by one so don't feel too intimidated. Let's just start with the reachableKeys. The first thing that we want to do is start with some basic data structure that's going to allow us to build off of. It may not be the data structure that we finish with, and in fact, it definitely won't be.

[00:01:43]
But let's just pick a place to start. It's putting a stake in the sand and saying, this is what I can start with. And I want to just describe what I think is the most basic and obvious of possible data structures. Which is that I want to represent my dialpad as a two-dimensional array.

[00:02:15]
I'm gonna leave spaces here for those empty ones and put the zero in its location, just so it's obvious what's going on. Dialpad is my starting data structure. And the purpose of reachableKeys is given any specific input startingDigit, any one of these, return me an array of all the possible places that I could move to.

[00:02:53]
The reachableKeys from that location. So let's dive in. I do want to declare a thing which I'll call nearbyKeys, this is my array that I'm gonna return. And I will fill it in with any keys that I can discover that I'm able to. If you think about our dial pad, I'm gonna go back to the slides for a moment, so we can get some conceptual backing here.

[00:03:32]
If you think about our dial pad, the coordinate system of our dial pad is not that unlike the coordinate system we initially started with on our chessboard. Unlike our chessboard, we don't have any diagonals going on here, which is nice. But we do have this sort of horizontal and vertical movement by coordinates that was very similar to the horizontal and vertical movement that we made on the chessboard initially.

[00:03:59]
And you'll notice that if I start on 1 and I go over to 6, then I increased my row index by 1, from 0 to 1, and I increased my column index by 2. I went from column 0 to column 2. So we went from the coordinate 0, 0 to the coordinate 1, 2.

[00:04:23]
And notice that if I were going from 1 to 8, it would be going from the coordinate 0, 0 to the coordinate 2, 1, that increased the row by 2 and the column by 1. You might start to see a pattern here. Similar to how on the diagonals the coordinates change, both by one the row and the column index by one.

[00:04:42]
Here we have a bit of asymmetry, which is that in any given move, we always change one of the two coordinates by two and we always change the other coordinate by one. That is, we never do a 1, 1 move, and we never do a 2, 2 move.

[00:04:57]
It's always 1, 2, 2, 1, negative 1, 2, negative 1, negative 2, etc. Everybody follow that? We're always changing by one of the coordinates by one and the other coordinate by two. So we can just simply exploit that. Matter of fact, we can just simply brute force this.

[00:05:16]
I can start, if I was given the starting key of one, I can try all combinations of increasing my row and or my column index by 1 or 2 respectively, and check to see if there's a key there. And if there is, put it in the array and if not, don't.

[00:05:34]
So, I can just brute force and answer to this. I don't even need something super clever, we can just simply start with any index and try all the possible coordinate connections, and see if there are keys there. That's what we're gonna do. Just plain old brute force. That makes sense to everyone?

[00:05:53]
Okay. So let's do it. What we're going to do is start with an outer loop, And I'm gonna do something some of you are familiar with, I'm going to do a destructuring here of the dialpad.entries. So this is giving me an iterator that returns me tuples with the key and the value in it, instead of only the value.

[00:06:21]
You've seen for of loops before, but here I'm gonna get the key and the value so it's gonna be row index and row. Entries will return this back, these pairings of the index and the value, the row index and the row. And we're just simply destructuring those into individual variables here so that I don't have to have a temporary variable, okay?

[00:06:45]
Now what I need to do is ask if the startingDigit is in this particular row, whatever iteration we're on, is the startingDigit in this row? So we could say, is the colIdx, Because we know row is gonna be an array of numbers, if you give me 2 on the first row that I look at, we definitely will have 2 there and its index will be 1, zero based index will be 1.

[00:07:20]
Everybody follow that? Did I lose anyone? If startingDigit is 2, the first iteration is gonna look at this row and it's gonna say what is the index of startingDigit 2, and it's gonna find it here and the index will be 1. So here, we'll have rowIdx 0, colIdx 1.

[00:07:41]
So how do I know if I found it in this row? Well, if colIdx is not equal to -1, if it's 0 or above, then we know that we found it. Otherwise, this is not the row that we care about, so move on. So we'll just wrap an if statement here.

[00:07:55]
We'll say, if colIdx is not equal to -1. I prefer the not equal to -1 to the greater than or equal to 0 approach, other people see it differently, however you feel stylistically. Okay, so we know we have found it. We have the rowIdx and the colIdx of the thing that we've been asked for.

[00:08:23]
Everybody follow that? By the way, we could have done that with math, but we were gonna need to loop anyway, so it just made sense to use a loop to get to this point. But we could've done it. Strictly speaking, we could've done it with some modulus math, but, We needed a loop anyway.

[00:08:41]
Okay, so let's look at the column. I'm sorry. Let's look at the possible moves that could happen from the perspective of changing a row index. A row index could increase by 1 or increase by 2. Or a row index could decrease by 1 or it could decrease by 2.

[00:09:09]
Follow that? That doesn't mean that it's on the board, but it's just theoretically that's what could happen to a row index if we were making a move. It could either increase by 1, increase by 2, decrease by 1, or decrease by 2. I'm gonna write that out. I'm gonna say, let's do a for loop for all of those moves, let's do let rowMove of, and I'm gonna list those out, -2, -1, 1, and 2.

[00:09:40]
So rowMove is like my delta, right? Same thing with my columns, my columns can change by plus 1, plus 2, minus 1, or minus 2. Let's write the same kind of for loop there. All right, First of all, we know that a 1, 1, a 1 negative 1, a 2, 2, a 2 negative 2.

[00:10:21]
Those are all invalid moves, right? Those are not night moves. So of the 16 possible moves that are happening here, not all of them are actually even night moves. That make sense? So we're gonna need an if statement to filter out the things that are not even valid night moves.

[00:10:37]
And that can be, we're gonna take the absolute value of the rowMove has to be not equal to the absolute value of the colMove. That is one of them is got to have an absolute value of one and the other one's got to have an absolute value of two.

[00:10:56]
I know we're getting super deeply nested here. Part of the reason why we're doing this by the way, just to give you a little hint. I want this code to feel super ugly because it's gonna motivate what we do in a little bit. Okay, s we definitely have valid night moves, but they may not be on the board.

[00:11:32]
We need to make sure that we're only looking at moves that are actually within the geometry of the board. So we need to have several conditions be true to make it a valid move. We need to say that our current rowIdx plus rowMove has to be greater than or equal to 0.

[00:11:51]
In other words, we have to stay on the board. And rowIdx plus a rowMove has to be, how many rows do we have? We have row index three, we have four rows, right? So that has be less than or equal to 3 on my rowIdx. And my colIdx plus my colMove has to be greater than or equal to 0.

[00:12:16]
And my colIdx plus my colMove has to be less than or equal to, there's only three columns so less than or equal to 2. And one final little wrinkle, is that we don't wanna end up in the bottom left or bottom right which aren't keys, right? So the last little part of this condition is that the dialpad of rowIdx + rowMove and colIdx + colMove cannot be undefined.

[00:12:58]
Because it would be undefined for the two bottom empty corners, otherwise there would be a value there. All the way down, deeply nested in here, if we get all the way down to this point, we know for sure we have found a valid move that we could make from whatever the startingDigit was, because we brute forced our way to that.

[00:13:23]
Does everybody see why that would guarantee us one of our possible valid moves? So now I need to simply stick these into nearbyKeys. Whatever it is at that position is what goes into nearbyKeys. I'm gonna make this slightly more readable. I'm moving on to another line. I don't know if there's a way to make this line slightly more readable but, I'll try.

[00:14:27]
All right, there is our reachableKeys function. Everybody with me on that solution? It's ugly, it's brute force, but it gets the job done. And we wanna test that it gets the job done. And we have our nights dialer here, we haven't done any of the counting stuff yet, but if we hover over the keys, we should see the nearby keys being highlighted in blue.

[00:15:02]
If your implementation of that reachable keys function did not work, don't fret because I'm about to delete it, okay? I'm just like one of those mean teachers back in school that makes you do work and then shows you that it wasn't even for a grade.