spellWord Function with Character Sets

[00:00:00]
>> Okay, so find candidates. Hopefully we feel pretty good about that. Let's look at the check function, which was full of our previous implementation. And I'm gonna do one of my favorite things to do in all of programming. Which is to delete it all. [LAUGH] I don't know about you, but I just love that visceral feeling.

[00:00:24]
We're gonna write more code in its place, but I love that visceral feeling of getting to get rid of code. So, the check function, this is the public API method that's called on our module, and in the check function, we need to get those candidates. So this is gonna be where we call, we're gonna say candidates = findCandidates for that input word.

[00:00:45]
And then we want to call another function which is going to be our recursive function which I will call spellWord. And we need to pass in the candidate for it to use for this word, and the word itself. You might wonder why we're passing in candidates, as opposed to simply referencing it as an outer variable.

[00:01:11]
It's simply to be a little bit more appropriate. We're not gonna modify candidates ever so we don't have any mutation of that value. But it is better to pass that along than it is to reference an outer variable, just again in terms of trying to reduce the surface area of places where bugs can occur.

[00:01:28]
So, what's left for us to do then is to write the spellWord function. We know that it takes the candidates. And the inputWord and you remember that its job is to return, the worst case scenario if it didn't find anything its job is to return the empty array to indicate that we were not able to find something.

[00:02:01]
So, how do we know that we definitely can't find something? This is called the base condition when you do recursive programming you may have heard that term base conditions before. Turns out in this case it's pretty straightforward to know what our base condition is. So rather than just having kind of like a fall through return we can actually put this in an affirmative if statement and make the base condition a bit more obvious.

[00:02:27]
Characters left, we're gonna do a different thing rather than passing in the inputWord, we're just gonna have a counter down for how many characters that we need to get. So we'll explain that here in just a minute. Sorry, charsleft is the string, the length of it is the count I keep getting myself confused right there.

[00:02:51]
So, charsleft is what I wanna call it and not length, sorry I got confused between left and length. Okay, so if the count of the characters left or the inputWord, whatever parameter name you wanted to give that. If the count of those is down to 0, then we're definitely sure that we've got nothing else to do for this iteration, and so we can simply return that empty array.

[00:03:24]
If there's more characters left, then there's more work to do. Now we said that we want to prefer or prioritize to letter matches over one letter matches. Which is part of the reason why we returned them at the beginning of that candidates list, we want to prefer those.

[00:03:40]
And so what we're going to do is check for those first, so we're gonna say check for two letters symbols first. That can only happen if the charsleft.length that is how many characters we have left is at least 2. So let's get the two left most of those characters so we'll say charsletf.slice (0,2).

[00:04:17]
That gets our next two characters off of our string. And let's just for convenience, put the rest of them into another variable called rest, are we slice starting at position 2? I got a typo here, charsleft. [COUGH] So, if. The candidates includes the two that we just pulled off, in other words, is that one of our candidates?

[00:05:01]
If we had made it into a combined set, then it would just be a.has call. But here we, again, just to imply the ordering, we kept it as arrays here. And then we can say if this is similar to our previous condition, we need to know whether or not we have any more work to do after this match.

[00:05:20]
This was a match, so we could put a little comment here we could say, found a match. All right, so if we did find the match now we need to know, do we need to do more work or are we done? Remember how we asked that same question before and the way we asked it was, is there anything left in the rest?

[00:05:43]
So we could say, if rest.length > 0 that means there's more work to do. So far making sense? Give me some thumbs up, thumbs down, how are we feeling? Or at least thumbs sideways. Give me thumbs sideways. Okay, I'll take it, I'II take the thumbs sideways. I gotta stop and go back if I get a thumbs down, but thumbs sideways we'll keep trudging along [LAUGH].

[00:06:19]
Okay, so if the length > 0, I think in the checked in version of the repo I think I have not equal to the empty string. Either one of those checks is equivalent, we're are saying is it, not the empty string so I'll just leave it as the length.

[00:06:36]
I think this one communicates a little bit better. If the length > 0, and then we'll say, let's go ahead and make our recursive calls similar to what we did before, we're gonna say, let result = spellWord. And we'll give it the candidates as is whenever changing the candidates will give you the candidates as is and will give it whatever is left.

[00:06:58]
But what's left is rest instead of charsleft. If, what comes back from this call. Is equal to what we were trying to match then we can simply return the result. So, there's join here is joining an empty string. Is joining whatever we passed in. Careful, I think this should have been.

[00:08:12]
We'll check this in just a moment. I might have a little bit of mistake here, we'll check. What comes back if there's no more work to do? That is this check fails there's no more work to do, then we know that we simply need to return an array with only the element that.

[00:08:48]
Okay, so that takes care of looking for our two character symbols and you'll notice that we are recursing in here and we're recursing into the two symbol options first. So we'll be looking at all of our two symbol options all the way down first. As I'm thinking about this, I'm pretty sure that I do have a slight mistake.

[00:09:08]
Although, the end result is still working, but I'll go ahead and call it out because I'm sure somebody will eventually get this. I am checking to see if what comes back from spellWord is equal to my current word. Which means that spellWord has to go then do that work a second time at each level.

[00:09:31]
So what I should have been doing is checking to see if what comes back from spellWord is rest, and returning. Returning to the ....result, like we did in our first version of the solution, either of those is going to end up producing correct answers. This one is gonna produce a few less iterations.

[00:10:00]
In our case, it's not gonna be that big of a problem. So the other one is not necessarily super wrong, but it is doing unnecessary work so I just make this little change. So that's slightly different from the code that you'll see in the repo. Okay, so now we wanna check for the one that are symbols.

[00:10:26]
And it's a very similar process. We only wanna do this if charsleft is. >=1. It always should be because if it was 0 we would have not even come into this branch. But this is just doubly making sure to communicate. This is the one character symbols length. Technically that if statements not necessary.

[00:10:53]
Just trying to make code that makes a little more sense here. So we're gonna do the same thing with the one as we did with the two. Which is we'll let 1 = and we'll get the characters charsleft at position 0 the leftmost character. We'll get the rest is = charsleft.slice.

[00:11:19]
Quick poll, do you say chars, cars, characters? What's the correct pronunciation? I guess chars sounds best to me, but I think I always like to say chars as in characters, but I think chars maybe is better. I don't know, anyway, if, let me scroll this down. Candidates.includes (one).

[00:11:43]
So is the thing that we've just sliced off the single character one of our one letter candidates is it found in the candidates list? We can do the not equals to this or I again above I kinda like the > 0. Either way you wanna do that check.

[00:12:14]
I know how I got off track on the two letter one, we'll go back and fix this in a moment. So, in the above one the way that we did this was we said let result = spellWord and we did candidates. Now I know how I got, it was a copy paste here that got us off.

[00:12:36]
Okay, so we can do let result and then we can say if result.join = chars, we wanted to say rest, return in this case, we want to return one and whatever came back in result. And if we didn't have any work left to do, one second I'll get to the question.

[00:13:03]
If we didn't have any work left to do, then we would simply return one. So those two if blocks, if you compare them, they should look exactly the same except one is doing it with the two character candidates and one's doing it with the one character candidates. But algorithmically they're doing the same work.

[00:13:19]
Basically the question was, did candidates really need to be in an array? I mentioned earlier, remember we had this discussion? What if we'd done these with sets instead of with arrays? And I suggested to you that the choice for the array, there were multiple factors that I put into that choice, right?

[00:13:37]
One of the reasons I put that into that choice is that we want order, and a set implies no order. You with me? So if I were to have done this with sets. I would end up with two sets here, and I could concatenate the two sets together, which requires iterating over the two sets and then creating a new set from their iteration.

[00:14:02]
There's no set append operator in JavaScript. You basically have to drop down into arrays, combine the two arrays together and then produce it back into a set. The way I'm using it is indeed as a set, I am not actually going through the candidates list in order. So we don't technically need the ordering to be preserved.

[00:14:26]
But what I was trying to suggest here was that, one of the factors for me choosing an array over a set here was that I wanted to communicate ordering matters. It is not the case that strictly speaking the ordering in this array matters. But overall order does matter and in that case, it is in fact the order of if statements.

[00:14:51]
The way that we go through it it's kind of if you're thinking about traversing a tree you go down the left branch versus the right branch you are gonna get a different traversal. We're going down the two branch versus the one branch that's gonna give us the ordering that we want in our recursion.

[00:15:06]
If I had made these as sets, I think it communicates when somebody's reading fine candidates that ordering doesn't matter to the candidates. And it would be harder to spot that the if statements are what's applying the ordering. So that was one of the reasons why I chose the array.

[00:15:23]
The other reason I chose the array is because I know that JavaScript cannot concatenate two sets together without dropping it back into an array. Which is slightly more expensive, not a big deal, but slightly more expensive. Whereas with these arrays, the ...array concatenation is very highly optimized. So to be honest with you, it's kind of 50, 50.

[00:15:46]
It is not the case that have we chosen sets that would have been wrong and if you had preferred sets here probably would have gotten a perfectly fine answer. The final impact of all of this or the final kind of swaying point for me, was the candidates is never more than a half dozen, maybe a dozen entries total.

[00:16:08]
For any word that you type in, which means that the array includes is going to be just as fast as a set house. So we're not really losing any performance by making this choice, and I felt it was a slightly better one but it's entirely reasonable that you might have chosen to do it with sets.

[00:16:25]
Hopefully that answers the question more fully than I had answered before.