Acyclic Paths

[00:00:00]
>> We're gonna push forward, we wanna get ourselves to the option one solution. The last thing that we need to be able to do is list out all of the acyclic paths. This is going to be a little conceptually easier to look at. It's gonna take a little bit more code, but hopefully, it won't be too confusing of a code.

[00:00:18]
Hopefully, we'll be able to explain it so it won't be too confusing. Okay, so the acyclic paths, we're not counting, we actually want to keep track of the path. So that's slightly more complex. We're not just being able to return numbers and add them together. We're gonna have to be able to build up these partial paths and fill them up further and further and figure out when we need to stop, and also do our backtracking and stuff.

[00:00:37]
So there's a little bit more juggling to do. But this is basically what an acyclic path might look like. Starting from digit 1, you might go over to 6, and then 6 down to 0, the orange arrow, and then 0 up to 4, the green arrow, 4 over to 3, the red arrow, 3 down to 8, the pink arrow.

[00:00:54]
Once we get to 8, can you see that we have to stop? Because we can't go anywhere else that we haven't already been. We can't go to 1 because we've already been there. We can't go to 3 because we've already been there. So that path, how many is that?

[00:01:10]
One, two, three, four, five. That's the longest of that acyclic path. It's only five. Other choices that we might have made along the way might have made a longer or shorter path. All we wanna do is for any given starting digit, list out all of these acyclic paths that we could have possibly taken.

[00:01:31]
Makes sense? We are still going to use recursion to do so, But it's gonna be, as I said, slightly more to juggle. All right, so now we're gonna be implementing the listAcyclicPaths function. All right, so the good news is that this function that we're gonna write, it's gonna look pretty simple, but it's gonna call another function, where more of the complexity will be.

[00:02:05]
What we need to do here is have an array of paths. So that's not a counter again, that's gonna be an array of paths. Paths are simply gonna be an array of numbers, like 8, 3, 4, 2, whatever the number would be, right? So we're just gonna push into the paths, however, many acyclic paths we find for a given starting digit.

[00:02:27]
And it's different, we'll see that there's an asymmetry here. There's some symmetry but not all digits have the same number of paths and the same length of paths. So there's some really interesting geometry going on, and I'm still kind of fascinated by. Okay, for any given starting digit, we know that we can get the next hops that we can take, I'll call it.

[00:02:49]
We can get that from the nearby keys of that starting digit. Same thing we did before, right? Could call the function, I think that's the way it is in the Git repo. I'm just gonna go ahead and access the array cuz why call the function. For each of those, we're gonna say, for let nextHop of nextHops.

[00:03:18]
For each of those hops that we're going to take, we need to basically create kind of a sub path. Are you with me? So we're gonna say, this path has the startingDigit at the beginning of the path, and it has the nextHop in that next position. So if that iterates three times, we're gonna create three separate sub-paths.

[00:03:41]
All three of them rooted with the startingDigit, but each of them having a different nextHop in the next position. Does that makes sense? Here's where we hand wave and pretend as if this is as easy as it is, which it isn't. We're gonna call this function that magically doesn't yet exist, but we're gonna write that.

[00:04:09]
Just magically follows all of those paths and fills in our path's array. And then we just simply return paths. So it's kind of like if you're watching one of those TV shows and the chef, it's one of those cooking TV shows, and the chef just kind of says, hey, we stick it in the oven, and then two seconds later, they pull it out, and it's a fully baked cake or whatever.

[00:04:33]
I'm just hand waving here, there's a followPath function that does all this work. It's not as bad as I'm making it seem, but in the past, when I've taught this workshop, more of the questions come from followPath. So I'm just preparing you, it's slightly more to juggle. So what does followPath take?

[00:04:52]
It takes a path and the list of paths that we wanna follow, that we want to mutate. Now, I'm deliberately making a choice here, which is that I'm gonna pass in a reference to an array that I don't own, and I'm gonna mutate that thing as I recurse down.

[00:05:09]
And there are pros and cons to that. It is more efficient, it is also more likely to be the source of bugs when you start mutating stuff at a distance. Generally, you don't wanna pass in an array and have some other function mutated. You wanna return back a new array, but there would be a lot of sub arrays that I'd be returning here.

[00:05:29]
Creates a lot more memory and garbage collection waste. So I'm just gonna take the more efficient route and mutate the paths. But be aware of it, probably in production code, I'd be putting a be aware comment here saying, beware of the side effects, I am mutating at a distance.

[00:05:44]
Cuz this is more likely where bugs are gonna come from. All right, so followPath is gonna do something very similar to the first step that listAcylicPaths did. It needs to get the nextHops. And the nextHops that it needs are from, Get this, we have that path that's passed in.

[00:06:06]
Whatever the last element in the path is, in other words, wherever we currently are in the path, that's where we need to find out the next hops from there. So we're gonna say, path[path.length- 1]. So I know that's kind of double nested. References in here, array references or whatever.

[00:06:27]
What we're saying, path[path.length- 1], that's where we currently are. And we need to get the next hops from there. I'm gonna keep track in a Boolean. There's other ways of doing this, but I like the Boolean approach. ForwardFound, I'm gonna start this out = false, okay? This is a Boolean that's gonna let me know if any of the subpaths that I considered actually worked.

[00:06:58]
If I never found any other subpaths, then there's nothing else for me to do. If I did find any other subpaths, then I need to keep going. Make sense? So I'm just gonna keep track of that Boolean. And actually, let's go ahead and write the if statement for that.

[00:07:12]
If I did not, Find any further paths, what does that tell me? It tells me that that path is complete, and therefore, I can push it into the paths array. I am mutating that paths array with this path. I know that this path has nowhere else that it can go, and therefore, it is complete, and I'll push it into the array.

[00:07:42]
Does that part make sense? Give me thumbs up, thumbs down. How does that part feel, okay? All right, Hopefully, it's not as painful as I warned you that it might be. Hopefully, this isn't feeling too bad. We're almost there. We need to look at all those next hops, so let's do the let nextHop of nextHops.

[00:08:06]
There could be 02 or 3 of those for us to consult. We're just gonna go through however many of them there are. And here's the key thing that this function needs. It's an if statement that says, if the path that we've been on does not already include this nextHop.

[00:08:29]
That's how we make sure that we're not cycling back. I've got a subpath, a path that I'm building up, and I've got another place that I can jump, but I can't jump there if I've already been there. You follow that? Can't do this with a set. Why can't I do this with a set?

[00:08:47]
>> [INAUDIBLE]
>> Cuz order matters, I got to just check to see if I have not yet gone there in this particular path, okay? If that is not true, then I still have a path forward. So I will say, pathForwardFound = true. That way I don't go ahead and add that partial path to the list.

[00:09:12]
We only wanna add that partial path whenever there's nowhere else to go. You with me? And here's the last thing, let's recursively follow that path on its way down. I'm sorry, we got to define the nextPath. What is that nextPath look like? NextPath is the current path plus nextHop.

[00:09:40]
And now, let's follow that path and see where that gets us. So the strategy here is keep recursing down, keep following all of our different nextHops. Keep recursing down until such a time as none of the places that I can move are valid for me to move to, in which case, I know that we're done recursing.

[00:10:04]
So I set the pathForwardFound, or I leave the pathForwardFound to false. That ends up pushing it into our paths array, mutating our paths array, and not doing any recursion. So that function call stack just stops, it doesn't keep going any further deeper. As a little bit of a side note, listAcyclicPaths probably could have been, we could have figured out a way to make that itself be the recursive function.

[00:10:34]
But one of the things that you very quickly get comfortable with when you're doing recursion is that you often wanna make another function be the recursive one because you might want a different signature for your recursive function. Then what you expose to the outside calling code, what you expose to the rest of the app.

[00:10:53]
So there's a little technique here, which is followPath is not exposed to the outside world. I don't wanna give a function to the outside world, where somebody's passing in an array and I'm mutating it. That's total chaos. I only expose the listAcyclicPaths as a nice, clean encapsulation of that side effecting behavior.

[00:11:14]
Meaning that from the beginning of listAcylicPaths to the end of it, all of those side effects that are happening, those are all completely self-contained and they don't leak out to cause problems for the rest of the code. So it is very common that you will end up creating these side helper functions that are the recursive ones so that you have control over their signatures, so that you have control over containing their side effects, etc.

[00:11:49]
The last thing that we should do is test it. See if I've made a mistake or if it works. Okay, let's come back over to our knights dialer, and remember that this one is not concerned with however many hops I add in. If I add in 6 or 12, this one is only concerned with the starting digit, right?

[00:12:13]
So if I click 4, here are the distinct acyclic paths that you can get to starting from 4. You've got 4, 3, 8, 1, 6, 7, 2, 9. You've got 4, 3, 8, 1, 6, but instead of going to 7, you went to 0, and then that was it cuz you couldn't go any further.

[00:12:31]
4, 9, 2, 7, 6, 1, 8, 3, that was it, no further to go. And these ones stopped kept a little early. So you can see here that we've got two of them that are visiting eight of the numbers. So they didn't quite get all of the numbers.

[00:12:46]
But then we've got 4 of them that visited only 6 of the numbers, so they stopped kind of short. That's what happens when you click 4. Would you expect a similar symmetry if I clicked 6? Just by the geometry of the board, if I click 6, we kind of expect, and indeed we get two 8s and four 6s in terms of path length, right?

[00:13:09]
What about if I click 1? We're expecting something different, probably, right? Let's see what we get when we click 1. We've got two paths that are able to visit all nine of the numbers. We've got one path that it can only visit eight of the numbers, two of them at 7 and one of them at 6.

[00:13:29]
So if that's the outcome from 1, what do I expect from 3? Do I expect something somewhat similar? And in fact, we see the same shape there. Now, what about 7 and 9? Do we expect the same outcome from 7 and 9 that we got from 1 and 3, the same shape, I mean?

[00:13:50]
Not the exact same paths, obviously, but the same shape. Let's try it, let's see what 7 gives us. Well, we still got two 9s and 8, two 7s and a 6. We ended up enumerating them in different orders. But I think you might say that we still visited the same kind of number, we still had the same magnitude of paths that we had available to us from 7.

[00:14:18]
Same thing with 9. Oops, we had 4 and 6 gave us the same, what about 2 and 8? Those are giving us different ones. Let's look at 2, we had quite a few more paths from 2. All of them or most all of them were of length 8.

[00:14:39]
We had none of length 9, but we had quite a few different paths of length 8, couple of length 6. Let's see what 8 does. Does it give us something similar now? I guess it basically gives us the same shape, but in slightly different orders here. There's one last key on the board, which is the 0 key.

[00:15:00]
Does anybody have a prediction based upon the geometry that we see? Do you think that we will see more and/or longer paths when we start from 0? Or do you think we will see shorter paths if we start from 0? Some of you have already clicked the 0, so you already know the answer.

[00:15:17]
But if you start from 0, are you expecting fewer paths or more paths? And are you expecting shorter paths or longer paths? I'll tell you how I thought about it before I ever ran this the first time. I thought, well, the 0 is kinda isolated all down by itself, so I bet it's gonna have shorter and fewer paths.

[00:15:42]
That was my intuition. Fewer paths but all of them are of length 9, that totally blew me away. I totally did not expect that starting from 0 no matter what path you take, you can visit all of the digits other than 5, of course. That blew me away when I ran that the first time.

[00:16:07]
Thats totally not what my intution gave me. Its starts out in the most what we were kind of geometricly saying that the most constrained position and it ends up getting the most freedom around the board, which is kind of fasinating to me.