Check Function: Recursion

[00:00:00]
>> Okay, so we're gonna switch back to our code editor. And we're gonna take out this hard coding of return yucky. And I'm gonna make it go back to the empty array, because it is in fact part of the specification. That in the case that we do not find it, we wanna return an empty array.

[00:00:20]
That's how we indicate if it failed to spell it, is that we return an empty array. Okay, so the first thing that we definitely want to check is to make sure, this might not seem like it's super useful but you'll see why, in a minute, why we're gonna want this.

[00:00:34]
We need to check that we actually have been given something. The app is gonna make sure that we do that but you'll see why in a moment, cuz we're gonna invoke some recursion here. We need to check to make sure that we actually have some input word to look at.

[00:00:48]
So, first thing, we definitely need that if statement kinda bounding what it is that we're doing. Now, we want to go through all of the elements and figure out, how do I start spelling this? So, if you were to pull out a pen and a piece of paper and you had the periodic table in the job, which I've linked to in the project, you could just sort of hand do that, right?

[00:01:09]
You could say, all right, I'm gonna start with the first letter, and I'll see if I find an element that matches the first letter. And then you might go back and say, well, actually, what I wanna first do is check to see if I find the first two letters as a, symbol because I want to prefer fewer symbols.

[00:01:25]
That's the interpretation we'll take. I wanna prefer fewer symbols, so maybe I'll first go through the periodic list and see if I find any two letter matches. But even if we find a two letter match, it may end up being that the next letter you don't have, and so, actually have a one letter match.

[00:01:41]
So, you're gonna have to do some backtracking. As soon as you start to write this out on a piece of paper, you're gonna immediately notice some examples where the greedy approach of, let me take the two symbol every time ends up not being optimal or it ends up putting you in a corner where the solution doesn't work.

[00:01:59]
So, sometimes you wanna start with the two symbol but be able to backtrack and try a single symbol. That'll end up happening a lot if you try that out on paper, so I'm short-circuiting a little bit of that work for you, but try it yourself. Take a couple of words and try it.

[00:02:14]
And by the way, I should have mentioned this before. Let me switch back to the app.js. I gave you some test cases here. These are all words that can actually be spelled with just the periodic symbols, and I wanna highlight even words like the word irresponsibilities. Some really interesting words that you might not have expected, dynasties, all of these are words that can be spelled with our speller, and there are, I'm sure, many more, ostentatious, viscosities.

[00:02:42]
I told you about yucky, I like that one. So, there's some fun options in here. Anyway, you can pick any of those as you're kind of testing on your paper. Try spelling those out and see that you'll end up needing to do some backtracking from the two back to the one, that sort of thing.

[00:03:00]
So, we're gonna need to handle that. And as soon as you start realizing that your problem is gonna need to backtrack, that's the first mental bookmark that tells you, I'm gonna need to manage a stack of states. I'm gonna need to go down in a problem solution path, and then I might get to the end and everything's great, or it might realize, I need to back myself back up, so, I need to remember those states and back up.

[00:03:24]
And as soon as you're managing a stack of states, the first thing that should come to your mind is, maybe I wanna solve this with recursion. I could do it with a loop and managing my own states, but this is probably gonna be a case where I want some recursion to make things a little easier.

[00:03:40]
So, we do need to go through all of the elements. There's no short-circuiting this. So, I'm gonna of elements. We need to go through the whole list of our elements to see, to inspect each one. And the thing that we want to guard on is if the input word has enough characters in it for whatever symbol we're looking at.

[00:04:12]
The input word at this moment could have only one character in it, and we might be looking at a symbol that has two characters in it, in which case we don't need to pay any attention to that symbol. You follow me? So, we're gonna do an if statement here that says, if the symbol length, Sorry, let me do this.

[00:04:33]
Let's save ourselves a little bit of typing by assigning this to a variable. We're gonna say, element.symbol, and we're gonna need it to be lowercase for our comparison, so I'm just gonna go ahead and lowercase it. So, we're just saving off that property. There's a question? Yes.
>> Should we divide input by two and recursively cover both cases and do that for each possibility?

[00:05:00]
>> That's a great question. So, you remember that we talked earlier in the workshop in the primer about that notion of divide and conquer that recursive search. Remember the eight golden spheres, if we did four and four and then two and two and then one and one. The nature of that problem allowed us to eliminate half of the possible things that we needed to look at.

[00:05:22]
Does the nature of this problem allow us that same strategy? Imagine if we took the first half of whatever the word is and the second half of the word. We are gonna have to do both. So, that's not really removing part of our problem, but it does make the problem easier.

[00:05:40]
So, it does still fit generally under the concept of divide and conquer. If I can find out the symbols for the first half and the symbols for the second half, that seems on the surface to be a plausible approach. And then for each one of those, you can divide and divide.

[00:05:54]
So, it does seem, on the surface, that it works, but there is a wrinkle here that will make this probably not the right strategy for us. I wonder if anybody can spot the wrinkle, why might that not be what we wanna do?
>> If you do it, it's in the middle.

[00:06:13]
The combination of letters that you used to split could have been needed for you to spell the word.
>> Yeah, exactly, if you chose to split, first of all, we have the question of, what if my word is not an even number of letters? So then, I'm gonna have a four and a three, for example, not that big a deal cuz we can still handle those independently.

[00:06:33]
But if I chose to divide it at four and three, and figure out symbols for the four and then symbols for the three, what if the symbol that actually works to make this a match needs to span that gap? So, I'm actually gonna need to potentially pick multiple pivot points for that splitting and do the work multiple times.

[00:06:52]
Do the work in one way, and if it doesn't work, then try splitting it in a different way and see if I can make it work there. So, we're gonna end up potentially doing more work that way. So, that's the wrinkle that we wanna worry about. Yes,
>> I would say that you also have to duplicate your reference dataset somehow.

[00:07:09]
If you are running two checks, you can't assume that the lookup table can be halved. So, if you have if you split one array into two, you either need to have two references to the same lookup or you need to ship that lookup table to both points, because you can't make the assumption that you know how to split up your data.

[00:07:30]
>> Yeah, so, another way of stating that is that we have a state management problem, which we have anyway when we're doing this recursive and backtracking thing, but we have a reference problem, which is just passing the array to the next level or keeping track of the array at the next level.

[00:07:46]
Might not work because of the references that the array might survive across those function calls. So, you're right, we'd have to be more careful with our state management in that scenario, absolutely. So, we're gonna go a different approach here, which is what our strategy that we're going to take, and you may have arrived at this already.

[00:08:05]
But this is, again, we're gonna do an implementation is the naive way, and then we'll come back and try to rethink if there's a better way. So, when you look at this solution that I'm gonna try, you may think, this is awful. That's the point, we want something that works.

[00:08:19]
And this was the most naive that I came up with. Others may come up with different ones, this is the most naive that I came up with. What we're going to do is, we're going to take off a symbol off of our element list if it matches the first one or two characters in the input word that we're considering, we're gonna take one of those and attempt it.

[00:08:42]
Basically we'll think about it kind of like a candidate. We're gonna have a partial match. So, we'll take that one, and then we'll split the word into what we matched versus what we have not yet matched. So, it's kinda like divide and conquer, but it's not a binary thing where we're doing halves, we're gonna split it into what I've already matched versus what I have not yet matched.

[00:09:02]
And we're gonna recurse into matching what I have not yet matched as the new word, it's a partial word that gets smaller and smaller. So, it's an implementation of divide and conquer, but it's not your strictly half and half kind of thing the way, we typically think of in a binary search, okay?

[00:09:20]
We're gonna try that and go all the way down. So, we're gonna sort of depth-first recurse all the way down to try to find that answer. And if we succeed, great, but if we fail, then we have to kinda back our way up and try a different symbol at each one of those steps.

[00:09:36]
We have to keep trying to go down and back up and down and back up until we either have exhausted all possible options, or we found a match. That'll be our basic strategy here. Makes sense? Hopefully, at least roughly. I'm getting a couple of nods, so, we'll hope that that makes at least rough sense.

[00:09:56]
Let's try this with some code. So, let's say that we need to double check. As I was saying a bit before I got ahead of myself, we wanna double check that we actually have enough characters left in the input word to match the symbol that we're looking at.

[00:10:11]
So, we wanna say that the symbol.length is less than or equal to the inputWord.length. Remember, as I recurse down, this parameter is gonna get a smaller and smaller string. We're gonna be slicing off more and more off the front of it and leaving only the remaining characters in the string.

[00:10:31]
So, we're going from the front. We could go from the back, but it turns out it's better to go from the front. It's less work to go from the front. So, what we're checking here is, for this given symbol, do I have at least enough input word characters to make a match?

[00:10:48]
And then we're gonna ask, did I actually make a match? So, if the input word.slice, and we're gonna take the number of characters that we need off of the input word, I could do this with a regular expression, but since people don't like regular expressions, we're gonna avoid those.

[00:11:06]
So, we need to get the slice of that, and the way I know how many characters I want is to do inputWord,slice, starting at position 0, going forward, the number of characters in the symbol, could be one or two. But I need to get that many characters off of the input word string.

[00:11:24]
So, take the first one or two characters off the string and see if it's equal to symbol. In other words, did I make a match? Put a code comment here so we're not losing track, did the symbol match the first one or two characters in inputWord? Some people hate code comments, they think that it is a smell that your code is not written.

[00:11:54]
Those people are wrong. Code comments are extremely important, and they are 1000 times more important when you're trying to figure out how to write an algorithm. So, absolutely write code comments, leave breadcrumbs for yourself. Yes, it does require you to maintain those code comments. That's just part of the job.

[00:12:14]
Okay, so we do have a match, but now we have another decision point, which is have we finished or not? Did the match that we just make fully sufficiently match the whole word? In our base case, if we passed in a two-character word like the word be, B-E, and we found the symbol beryllium, B-E, I think that's beryllium, B-E and B-E, well, we've made a match.

[00:12:44]
We've found enough symbols to cover the word. So, we need to ask, have we made that full word match? Are there any characters left? So, that's how we're gonna ask it is if the inputWord, remember, this slice is just pulled a substring off. It didn't actually mutate the string.

[00:13:03]
So, we still have the full word here and inputWord and we need to say, if the inputWord length is greater than the symbol.length, then we still have characters left. I'll make another code comment for that, still have characters left. If inputWord length is greater than symbol length, that means they're still characters to look at.

[00:13:30]
And this is where we eventually now have arrived at our need to recurse, okay? We cannot do a return of the recursive call. Many, many times you see recursive examples, they'll do return and then a function call. But here we can't return because we have to conditionally decide whether what we got from the return worked, in which case we can return it, or did it fail, in which case we need to let the loop at this layer of the stack just keep going.

[00:14:03]
So, we're gonna save this off into a variable, I'll call it res, for a result. And we're gonna recursively call our same function. And here's where this becomes recursive, because we're going to say, inputWord, but less than the inputWord that we received at this level. This is where we shrink our problem.

[00:14:21]
This is our divide and conquer approach, we're shrinking the word. So, the shrinking of that word is to take inputWord.slice starting at this position, starting at symbol.length and going to the end. And I don't need to put a second argument to slice because it will automatically go to the end if I provide only one argument.

[00:14:48]
So, this expression here says get all the rest of the characters, I could assign that to a variable called rest of characters. And I'm calling check on the rest of the characters. There's our recursive call. We matched off two characters and we've got seven left. So, check, go figure out how to spell these seven characters with the periodic table of elements, and then I'll combine your answer with my symbol for passing back up to the next level.