Coding With O(0) Time Complexity: Fun With Advanced TypeScript

Hello everyone, I'm hoping you're having an amazing conference and I'm happy to be able to talk to you today. My name is Dante, you can find me on dantedruwe.com and I'm going to talk a little bit about the fun side of advanced TypeScript. And this is going to be an interactive coding session. And that means I will never even leave my VS Code. This is also inside VS Code and we'll jump right into the code.

All right. So let's get started. I have a little demo, uh, for you guys. This is a game of Wordle. And so what you can see is that this is a type called game and it evaluates to five blank dots in here. And so that I don't have to keep hovering over this type, uh, to show you what the type actually is. I'm going to use a little VS Code extension that can show you this type in line. If I just point to it, then it will show this type and this will update in real time. So that will be easy.

Now, what is Wordle? I hope you all know it. You can guess a word and then, uh, yeah, you get score based on how close you are to the secret word. And if it's green, then it means your letter is correct. If it's yellow, that means your letter is correct, but it's not in the correct spot. And white in this case means that none of the characters, that this character on that spot is not correct. So we can make our first guess and I'm going to guess water and you can immediately see this type updating to a green dot, a yellow dot, and some three white dots. So that means our W is correct. Our R is also correct, but it's in the wrong spot and yeah, the other letters don't appear in this word. So let's guess for words cause the R is there. Okay. Now the R is in the correct spot. The O as well. So we guessed that correctly. The D is in the word you can see by the yellow dots, but it's in the wrong place. So it has to be like this. And then of course I think this is world.

So now we guess this game of word correctly and make no mistake. This is wordle at compile time. This is not running anywhere. This is all purely within TypeScript types. And if I hover over the secret word, you can see that it was indeed world.

Okay. How would we now implement this wordle type? This seems like a lot of magic is going on and it is kind of magical, but yeah, I can explain to you what is happening. I'm not going to show the code quite yet. You can already see we're online 29. So that means in 28 or less lines, this wordle type is defined. It's not in a different file. It's just all here. So that's quite impressive.

Now, how would we implement this in simple TypeScript? This is pseudo. Yeah, it compiles. I mean it runs, but this is how you can kind of do this. So we have a guess and a secret. You keep a result array here. We loop over the other secrets and we check if the letters match by doing index off.

You keep a result array here. We loop over the other secrets and we check if the letters match by doing index off. So if a, uh, the first letter of the guest is index off in the word is if it's minus one, the index off function, it means it's not in the word. So for example, this a here we do index off a in the secret and we see the a is not in there. It's minus one. So then we get a white dot if the index off is equal to the eye. So this means that for example, this one will look up the w in the next word and it comes back as zero w is an index zero here and it is an index zero there. That means it's in the same spot. So that means a green dot. For example, the R here would not be at index I, because we would look here at this at index four and here it is at index two. So that would not be a match. So then we would get a yellow dot. And so this is how we would do this in TypeScript. You could also push to this array, but I chose to wrote it, write it like this because in Typescript types, we cannot push to arrays. We can only use the spread operator.

So if you're wondering how I, this code is structured like this, it's because it has a resemblance to the final Typescript code that we're going to write. What do we have to do to make this work? Yeah. We have to find a way to loop over a string. Like we do here. We have to keep counting the loop. We have to have this index here so we can compare the different positions. We have to have a sort of an index of functionality in our TypeScript final product. We need to do if checks, we need to do a conditional check and we need to keep a result array and add to it. And that's what I told you before with the, with the spread operator here. So this is all everything that we will have to do in TypeScript types to make this work with TypeScript types.

This index off function is also looping over string, keeping count and checking if their letters match. By doing these simple steps, my learning, how we do this in TypeScript, we can do the entire thing. So that's quite exciting. Let's start with the first thing, the conditional check.

Okay, let's, let's start with the first thing, the conditional check. What are we going? I'm going to put this back so we can keep track of it. Um, what are we going to do in TypeScript types for a conditional check? So for example, we can make a type, not empty and it's going to take in, yeah, I'll call it normally everything in generic types is called T, but I'll call it S for string. Uh, for now you can also say here that it should extend string, uh, to make sure you can only pass a string into it. And, um, we're going to check if this string is empty. Well, we can just, we cannot do it like this, right? We cannot say true or false. We have to say that the string extends something. So in TypeScript types you can only do conditional checks by using extends. And that means that this string should extend this string or it should be assignable to that string. So if F is, if S is empty, well, that's not good. We'll make that never and never just means kind of, it's more nuanced than that, but this kind of means, yeah, this is a type of error. If, if, if something evaluates to an ever, you can only assign never to that. So that will in practice, all, all always be a type error. And if it is not extending the empty string, well then we have not empty. So then we just return S again. How do we use this then not empty off? Hello, for example, well, not empty of hello. That will just return. Hello, because this will not extend the empty string. So we will just return. What is the input if not empty off empty string that will be never. And then we know in our code, for example, Oh, uh, if, uh, yeah, that, that, that is an empty string. So this is the way we do conditional checks, uh, in TypeScript. We just use the ternary operator and the extends, uh, yeah, clause there.

Let's build another type to, to hammer this down. So we do a contains, for example, this is something we'll, we'll need to check if letters are contained in, in a string. So we have a string and a letter, and we want to check if this string extends, something that contains this letter somewhere. And if that's, I will just write it like this for now, if that is correct, then, okay. It does contain it. We'll return one, for example, and otherwise we'll return zero just if that's, we can also return true or false. Those are also types in TypeScript, so you can have a true type.

Um, yeah. Okay. We just need to figure out how do we see if this S extends something that has an L in it? Well, then TypeScript, you have what's called, uh, type template literals. Yeah. String template literals. And you can check if something has, for example, of the, of the shape string number, for example, you can check if something is versus string and then the number in, in, in a string, which is quite, uh, advanced, which is quite cool, but we can, for example, just do then this also check if something is a string followed by the letter that we put in, followed by another string. And these strings can also be the empty string. So that means this L, this letter can be contained anywhere in the string, but TypeScript complains L is not assignable to type string number. So we have to constrain it here, uh, to make sure TypeScript knows that we will definitely pass in a string and if you see results, for example, if you see how we use this, you can see contains, um, yeah. React. If that contains an A we'll check. Yeah. That contains an A. Does that contain an X? No, that is not. So what it's really doing is checking if react extends this pattern. Well, does it with the X in the middle? No, it doesn't cause it's nowhere to be found. Okay. So we can use template literals to check the shape of a string. Interesting.

Um, what if we want to take the first element of a string? What if we want to find that? Well, we can use the template literals again. We can see check if S extends the template literal of some first character and then a string. Hmm. Yeah. Well, if that's true, then return the first character and otherwise return never. There's an issue here. They cannot find the name F. We don't have this type. If you remember the previously, then we passed in the type and then TypeScript knows, oh, okay. You meant to pass in the type in here, but now we don't have it.

You meant to pass in the type in here, but now we don't have it. We need to infer what TypeScript sees here. We need to infer the first character and that's exactly what the infer keyword is for. So TypeScript can infer what this first character is here. And if it follows this shape, then it also knows what this first character is. So if I do the results first off react, for example, then you will see that the result is R because TypeScript saw that this string extends this pattern. Namely the F would be the R and then the rest of the string is this part and then we return the first letter. So it would find the R. Cool.

A good use of the infer keyword. Let's see what happens if we use this now to implement this index off function. So we can keep count and loop. This is not really, this is not really what we have seen yet. We can do conditional checks with strings and stuff. That's all easy. We need to also find a way to loop over a string. So for that, let's build a repeat function that takes a type, any type, and it repeats it n times.

Okay. So that will make, for example, if we do repeat react for three times, it will say a tuple and type tuple of react, react, react. This is what we want to achieve. How are we going to build this? We are going to have to see if the result, we have going to have to build a result. We are going to have to build this tuple. We start with an empty tuple and we'll build, we'll add react to it until we get three instances. So for that, I'm going to keep a results tuple and it's going to extend a tuple of T because we're going to add the type that we passed in into it, extends, excuse me. And it's going to start out empty. And when do we stop? Keep adding to this because we don't, yeah, we have to know how many iterations the loop is going to take. When do we stop adding? When the result tuple is as long as the count is. So in this case, three, so three elements count. Luckily we can take the length of tuples.

Luckily we can take the length of tuples. We can take length of this result tuple and check if it extends N. So that means if the tuple has three elements in this case, then we stop. And what does it mean that we stop? We return the result, of course. So we have built up this results, not yet, but we will. And then when it extends the right length, then we return it. If it doesn't extend the right length, that means we're not finished yet. And that means we're going into recursion.

So we had the base case when it's done, return, and now we're going to do repeat again with the same type, the same N, but we'll add to the result one extra type. So we do the exact same operation with the exact parameters, except for we keep an extra T in this result. So we spread, just like we do in here, we spread the result with an extra value and we spread here as well. And now if you hover over resolve, you can see react, react, react, which is very nice. You can also do five and then it will do it five times. I think you can go up to 999 and it will do it. But if you go to 1000, TypeScript will complain because yeah, it is possibly infinite. No, it is not, but they hard cap it because of recursion limits in the type system. Pretty insane.

So now we have a loop. We can kind of keep count in the loop because we keep building this result array and we can always get the length of it. So the index is just the length of the array at that point, or we can keep counting this loop. We have conditional checks, we keep a result array, we add to it. I think we're ready to show you how the wordle example is actually working. Yeah. Looping over a string, by the way, is really what we also did in the, in the, in the case with the infer key words, because if you just always take the first character and with infer, so if you do something like this, uh, type X is, yeah, X of S for example, is you check if this S is extends first and then the rest of the string. And then if you're done, you just return the results.

But if you're not done and do you do something recursively with the rest of the string? And so you'd keep chopping off the first part of the string and you keep recursing with the rest and eventually you will be done and you will have looped over a string. And that's exactly what happens in the wordle example here.

I scroll up. This is, so this is the part that you didn't see in the beginning. We have an index of type and it takes a string, a character to look into the string. And it keeps also a result array. And for now I just kept a result, yeah, not array, tuple actually. I just used zeros because it's one character and it's, it's easy to count and you check if this S extends first and rest.

So that means you just chop off the first part. And then you check if these two are equal to each other. Uh, you could just do, uh, first extends rest to check if the strings are kind of equal, but for extra protection and against input of, of, of the user, you can also, yeah, both uppercase them first to make it, uh, to make it case insensitive. This uppercase type is by the way, in the base library of TypeScript. So you can use it just whenever you want and every project you'll have to write it yourself.

If these two characters are equal to each other, we take the length of the result array because that's where we keep our index. So this means we have found a character in the words. So you return the index, where you found it. If you didn't find it yet, then you keep searching through the rest that you have here.

So you keep chopping off the first thing. The first one doesn't match the letter. Okay. We'll chop off the next part. Okay. That doesn't match the letter. You keep looking through the rest. If everything else fails and this doesn't evaluate anymore, you've reached the end of the string. There's no first to chop off anymore. Then you return negative one because that means you haven't found anything. And that means you return negative one. That's what the index off function does.

So if you want to see here, index off, then if you do index off react a, then you will find that it is two because a is at the second spot of this string type. It will just do this. It will take the R it will check if the R and the A are equal. They are not. So they will continue with the rest, which will be E-act. And also we add an extra element to the result array. That says that we are now at index one.

So it will check the E and so on. And then eventually it will check the A. We will have added three things to the result array already. And so that means we will find the, uh, sorry, two things. We will find the A at the next two. So that's, that's kind of how it works. And this is the most complicated thing that you need to know to build this word type because now it's just checking what the index off is. Is the index off equal to the length of the, of the result array? So that means, is it in the correct spot? Yeah. Well then it's green. Just like we did here. This is just, this part is the last piece of the puzzle.

So in here we check if we didn't find the letter in the word, then it means that it's a white dot and then everything else is the yellow dot. So this way we can make a extremely complicated, uh, TypeScript type just by using very strange, logical thinking and just by knowing the limits of the TypeScript system and using them. And if you think, well, why are we doing this? Yeah. Uh, just because it's freaking awesome. You know, it's just cool. Um, these types, you will rarely write yourself, but if you're writing any library code that other people have to use, you can write for sure. These, these, these types, this repeat type to make tuples, and these kinds of types will be really helpful for, for your developers that you're writing this library for.

So I hope you learned something new. I didn't have enough time to show you everything I wanted, but I hope you enjoyed it. I hope you enjoy the rest of the conference. And if there's any questions, feel free to ask them to me, uh, in the chat later, or, uh, send me an email. You'll find every contact detail of mine, on my website. Thank you very much. And see you later.