Creating a Diagonal Data Structure

[00:00:00]
>> If you find yourself banging your head against an algorithm solution, one of the questions that you should somewhat regularly revisit is, did one of my earlier decisions put me into this position? And could I have made a different decision that might unstick me? Ironically, it's somewhat like the back tracking in recursive dissent algorithms that we've already kind of seen that you might go three-fourths of the way down the tree to one particular solution.

[00:00:34]
And then only then discover that wasn't the optimal path and have to some back tracking. And sometimes you have to back track all the way to the beginning. Thus far, we've been trying to convince ourselves that maybe if we just keep plugging away at this, we're gonna get something that looks like a more graceful, or more direct, or more straightforward kind of solution that's optimal.

[00:00:59]
And I think we definitely have improved the performance of the solution insofar as is possible. Maybe there are a few tweaks here and there, but I really think that the mental model that we used is the problem. And that's okay. We learned some valuable things lessons along the way.

[00:01:19]
But sometimes, it does make sense to go back and start from scratch. So, I wanna show you this next slide, you remember I told you about these at the beginning of this exercise. This being the major diagonals, and the minor diagonals. We fundamentally chose a data structure that was oriented horizontally and vertically.

[00:01:49]
And why do we choose that? Well, it was quite convenient to use the data structure of the DOM as our earliest bootstrapping steps. The DOM is oriented in that way, it's kind of very hierarchical nested in that way. In other words, the DOM has no notion of diagonals.

[00:02:09]
So what we have been attempting to do is retrofit on to a data structure that is horizontally and vertically oriented a problem. That is quite literally 45 degrees of skew. You follow me? And it's not a surprise that that only becomes apparent when you draw it out, I said earlier in the workshop, don't be afraid of pulling out a pen and a sheet of paper.

[00:02:42]
And when I was working on this problem and trying to come up with better ways to do things, I pulled out a sheet of paper and I started drawing it out. And I don't know exactly what it was, why it happened, but I'm gonna tell you a story as if it is, I'm telling a story as if this really happened even though it technically didn't.

[00:03:03]
A little tuft of wind blew the paper just so it turned 45 degrees on my desk, and the light bulb moment went off. And what went off for me was, why am I doing arrays have rows and columns instead of doing a matrices of my diagonals? Why don't I construct a data structure that is shaped and oriented to the problem that I have Instead of trying to take the problem and retrofit it to a data structure?

[00:03:45]
You see that? So I want you to notice that I have arbitrarily indexed these major diagonals zero through 14, the 15 major diagonals. I just chose this ordering, you could have picked a different ordering but this was convenient. I ordered these major diagonals zero through 14 as such.

[00:04:11]
And notice that when we look at the minor diagonals, I started there indexing at 15 rather than at zero and ordered them from 15 to 29. So there are a total of 30 diagonals, 15 major and 15 minor, and I chose to put them in one list zero through 29 as opposed to two separate lists.

[00:04:36]
Is that a good or bad choice? Could be debated, but that's just a convention I chose, okay? And we're gonna see what we can do with those numbers. Sometimes it's literally just an arbitrary decision that you make, you put a stick in the ground and you build the fence around the stick, and that's all I did.

[00:04:56]
I looked at these diagonals and said, I'm gonna treat them as a data structure. And rather than doing like a two dimensional set of diagonal data structures or something, I'm just gonna have one dimension of all my diagonals. The first half of my data structure is the majors and the second half is the minors, that's it.

[00:05:13]
That's all I did, it's not very sophisticated but I numbered them as such. And here's what that further got me because going back to the coordinate system, if this is my, we'll call it the Cartesian coordinate or the DOM coordinate, four, two. I need to translate that coordinate into the diagonals coordinate system.

[00:05:39]
In other words, there's an index of the major diagonal that four, two square participates in, and there's an index of the minor diagonal that four, two participates in. Specifically, it participates in the major diagonal at index 5 and the minor diagonal at index 21. So in other words, I need a way to convert the coordinate four, two to the coordinate five, 21.

[00:06:12]
This is not gonna turn out to be very much rocket science, it's pretty straightforward math. It might look slightly arbitrary but if you follow along with this math, you will see that I can take the coordinate four minus two and subtract that from seven and I get five.

[00:06:33]
And you think, well, there's a lot of ways that you could have done it. But notice that if I do that same thing for all of the other coordinates along that diagonal, they all have the exact same pattern. Which is that if I subtract the column index from the row index and then subtract that from seven I get, the major diagonal index of five.

[00:06:56]
I was just messing around with numbers and I was like, yep, that works. And then, I tried it on the other rows, like on row four, I mean diagonal four, and diagonal three, and all of them. And it turns out that math works for all of those diagonals.

[00:07:11]
And I said, okay, well, I've done half the problem, I've converted my row index into my major diagonal index. Now, I need to convert my column index into my minor diagonal index. That being the general formula for converting. And that general formula is only the general formula based upon the arbitrary decisions that I made about how I structured my data structure.

[00:07:38]
So I inferred it from looking at the diagram that I drew out on paper. You'd make different decisions in your data structure, you end up with a different formula. But it can be the exact same concept. You follow me? So then we switch to the minor diagonal. And it turns out that I can compute 21 as taking the row index plus the column index, and then adding 15.

[00:08:04]
And the same is true for all of the tiles along that diagonal and so I have a general formula for converting from the row and column index to the minor diagonal. Like that. That means that if I had a data structure that kept track of all of those diagonals in those indexes, and I click one specific diagonal and I know what it's tile and row, I know what its index is.

[00:08:41]
Then it's a trivial computation mathematically to find out what indexes of the two major and minor diagonals I have. And then I just need to loop over all the elements in each of those two diagonals, I don't need to do any math of like minus ones and plus ones and less than or equal.

[00:08:59]
It's just all the elements in the major diagonal collection and all of the elements in the minor diagonal collection I had highlighted to them, that's it. No math at all. So let's do it. First thing is that our list of tiles in the two dimensional grid which we thought was an improvement on the previous stuff, we're gonna get rid of that.

[00:09:31]
Actually, we're gonna do a lot of deleting, so it's gonna get kind of fun here, I love when I get to delete things. We do need to add something, which is that we need to keep track of our new data structure, which I'm gonna call diagonals, okay? And diagonals is going to be an array, indexed zero through 29, so it's gonna be 30 diagonals in this, okay?

[00:09:53]
So we need to set up those 30 diagonals. There might be more clever ways of doing it, but I wanna be super obvious about it, I'm going to create 30 diagonals by pushing an empty array into it 30 times. This is setting up my diagonals data structure. Everybody following so far?

[00:10:29]
I can get rid of the row tiles and tiles push, and row tiles push, that stuff we can get rid of. And indeed I can get rid of the dataset row and dataset column stuff, and you'll see why in just a moment. I need to compute from the row and column index, which of the diagonals, the 30 that are there, which ones do I need to store a reference to it and which index do I need to put it in?

[00:11:11]
You with me? We have those formulas on the slides and just gonna type them out here. If I were to say the major diagonal index, you recall that it is seven minus the quantity row index which is I minus J. You remember that from the slides? And minor diagonal index is 15 plus, I plus J.

[00:11:56]
So I need to store the tile element reference inside of those diagonals, so I can say diagonals of major Diagindx.push, tileEl, and diagonals of minor Diagindx.push,tileEl, that is the constructing of my new data structure, everybody follow that? Each time I create a new tile elements I make sure to insert it into the appropriate diagonals.

[00:12:35]
Order doesn't matter within these diagonals cuz all we're doing is highlighting all of them are clearing all of them. We don't care what order it is.