Practical Problem Solving with Algorithms spellWord Function Q&A
Transcript from the "spellWord Function Q&A" Lesson
>> All right, now, let's go back to my mistake. Everybody likes to talk about mistakes, right? Let's go back to my mistake. You'll notice, if you do a comparison to what I've got typed out here right now and what is actually in the repository, it is slightly different.
[00:00:15] Because what I have typed out in the repository is that I went ahead and did my array concatenation right here. Oops, I did it ahead of time in which case, We do want to compare this to charlesLeft. And we do want to return only result. Those are functionally equivalent pieces of code just doing one operation before doing it after, but functionally equivalent pieces of code.
[00:00:58] When I got tripped up in my copy, paste preparing the repository is that I did that for the one-block but I didn't do it for the two-block. So to make things consistent for what you're gonna see, let's make sure that we do this same approach up here, which is, Type a two in there, spread out the spell word into an array.
[00:01:25] We wanna check this against charsLeft, and then we want to return result. So those blocks should now mirror each other. This block will slightly differ from what you currently see in the repository. Maybe by the time you're watching this video, I'll have already patched the repository. But anyway, those two blocks should look the same because they're doing the same thing.
[00:01:54] It's just that we're doing it with two and then we're doing it with one letter candidates. Yes?
>> Could you use two sets, like one letter candidates and two letter candidates in spellwork function?
>> If you had wanted to pass them as two separate sets, sure. That would have muddied up the function signature to spell word to pass in both candidate lists, but there's no reason why you couldn't have kept them separate.
[00:02:23] All right, so let me restate the question. They're basically saying, should we special case a pre-check for these before we attempt to do the spelling of the whole word? Should we look for all of the single letter candidates and match against any of the single letters in our input word and do a pre-check for those before invoking the recursive spell word function which will then favor two letter versions over one letter versions?
[00:02:50] I do not agree with that, and I actually think that would be functionally incorrect in some circumstances. Because I do believe there are periodic table elements where there is a character that appears only as the second character in a two letter symbol and never appears as its own individual letter.
[00:03:11] That would be, I think, the biggest functional trap. I'd have to validate that, but that's my instinct that that would fail. But even if it was functionally okay to do, I think a further special casing of this, the question was, what do you think about the trade-off? A further special casing where we pre-check for stuff that we're then already gonna check for later, that is a premature optimization, we'll say, or an immature optimization.
[00:03:41] Our algorithm already checks for the one letter candidates being in there by default, and I don't think avoiding a few iterations before we get there on the whole is going to end up. It's definitely not going to change or improve the bigger order of magnitude of this solution.
[00:04:03] It might trim off in some cases and might not trim off in others. There's another question?
>> But to comment on that, I would say that is the wrong way to go, because you want to rule out your large sets first, because we want to return the largest set possible.
[00:04:21] So we want to get all of those out of the set that we're iterating before we match, so we can use implicit negation.
>> Because we know everything that we've already matched, we only look at single characters for what isn't matched, and that is a much lower overhead flow.
>> I agree with you. However, in fairness, what was being asked from the chat room is a valid question-
>> Yes, totally agree.
>> Because it's very similar to when we were talking earlier in the workshop about boundary box overlaps and I said if you check for whether they are overlapped that's more conditions to check than to check for the reverse.
[00:05:01] So they're effectively not checking for one-letter candidates, they're checking for the absence of one-letter candidates as a way to short-circuit not even going into the spell word function. So it's a valid approach in the similar way we're checking a negated case to see if we can short-circuit out early.
[00:05:18] I just think in this particular case, duplicating that logic into a special case, first of all, duplicating logic, then ends up creating either a maintenance overhead or a performance overhead if you then have to call it as a separate function. And secondly, probably my instinct is if you were to work out the math on that, it doesn't actually create any statistical increase in your performance.
[00:05:45] It increased your code overhead and you didn't get anything for it, would be my instinct here. So what has this changed versus the way that I solved it before? Well, first, before we answer that question, let's just double check to make sure I didn't make any mistakes, because I probably did with all my typing and retyping.
[00:06:29] Spell word, this is why you run tests. What does that say? In just a moment here, or it's returned value is not iterable. There is an implied else condition right here. And it should return an empty array in that case, because it wasn't a match. And rather than putting that else condition right there because I don't actually want to return right there, because I want to allow the one candidates to go forward.
[00:07:03] So I'd have to figure it around. So I don't put the else candidate here either. So if both of those fall through, then we get down here and we return the empty array. So I think my only problem is that in my rush to, My rush to remove lines of code, I just should not have removed this one.
[00:07:32] I don't know what I was thinking, so sorry about that. Let's try this again, just double check, make sure that it works. Okay, so what's a takeaway from my mistake here? A takeaway from my mistake is that it is very important that you have that reference implementation to go back to.
[00:08:00] Because if I couldn't have figured out this bug, or if I had been banging my head on this bug, what would I have done? I would have pulled back up my reference implementation and tried it with the exact same example and seen if I got it to succeed or fail.
[00:08:15] It might have been the case that I had some corner case that I had not come across. So I would have gone back and tested against the reference implementation to verify that something about my optimization had caused the problem, as opposed to my algorithm. So in this particular case, the mistake that I made, Was as I was reading off the code that I needed to do, and I deleted code a little too aggressively.