Escaping a Dungeon with Regular Expressions

[00:02] something in a computer document where you don't know the exact text but you know kind of what it looks like for example an address or a date there is a technique called regular Expressions that are used byments which is very

[00:15] effective at trying to find this formatted information from Tech in this video I'm going to explain the technique and on the way I'll introduce some of the fundamental ideas from a field of mathematics called language Theory to do

[00:30] this I'm going to introduce a highly contrived minimalist dungeon crawling role-playing game before that I'm going to pause and say that the field of language Theory and regular expressions in particular is something that I have a

[00:46] great passion for not just because they are a highly versatile tool but because are a highly versatile tool but because they have a type of abstract Beauty they have a type of abstract Beauty hidden underneath what is admittedly an

[00:58] ugly exterior in many ways space they have a gap in my way that keeps drawing me back to them so let's introduce my RPG it is set in a dungeon made of various rooms there is a starting room and a gold room in each room there are

[01:15] labeled one-way doors that allow you to exit the room travel down the corridor exit the room travel down the corridor and enter another room in order to win you have to navigate through the doors and end up in the Gold Room as

[01:29] role-playing games go this is very Bare Bones all the rooms have the same number of doors and a consistent labeling scheme these labels could be anything scheme these labels could be anything numbers letters symbols this collection

[01:43] of door labels will be called our alphabet so we could have an alphabet alphabet so we could have an alphabet consisting of cat dog T-Rex and taito the kanji meaning looking like dragons flying in this

[01:58] looking like dragons flying in this dungeon each room will have four exits a winning play in this particular game would be dog dog and another effective Hearth would be T-Rex dog sitting out the rooms like this is complex and hard

[02:13] to follow so let's turn this into a map this is a diagram of all the paths we can take in this dungeon each circle represents a room the double circle represents the goal room and the arcing arrows between each room are the

[02:28] corridors and this solid arrow with start on it represents the start this is still a bit complex since we only care about the goal any rooms that can never lead to the goal are not important to us these are basically traps we can

[02:45] simplify our dungeon by removing all the Trap rooms a winning path through this dungeon is called word we can create a list of all these words you can notice by making use of Loops within the dungeon there are an infinite number of

[03:01] possible words we call this list of all possible words a language because language is created this way are rather simple and have regular patterns we call

[03:13] these languages regular languages is there a way of conveniently representing infinite words in a regular language in a neat finite form it might also give us

[03:26] an easier way to interpret a complex graph and gain understanding of graphs like this and from this perhaps find texts that matches patterns which is the main task we set up whenever there is a complex problem it is Handy to start

[03:42] with the simplest solution and slowly work up the complexity now in the simplest case the entrance is the same as our goal that is pretty trivial and we can rep present this pattern with an empty string now the next most complex

[03:56] would be two rooms with a corridor joining them we could depict them in a joining them we could depict them in a map like this so in order to get to the room we'd have to pass along the latter Arc we should prepend this arcs letter

[04:11] Arc we should prepend this arcs letter to the empty string this sounds like a roundabout way of saying we should write down the letter but by putting it this way we can generalize it to any number of change rooms just treat the next room

[04:25] of change rooms just treat the next room as a goal follow the rule of prepending the appropriate letter let's consider a slightly more complex situation where slightly more complex situation where there are two arcs going to the goal

[04:39] state in this situation there are two possible letters that can reach the goal we can write this down by using a vertical line to represent the vertical line to represent the alternative so this map accepts dog or

[04:52] look at more than two is simple as well just another line and another appropriate label we can use the same trick that we used before of thinking of each state as a goal State for the state before it in order to string together

[05:06] States sometimes we might need to add brackets to remove ambiguity the last brackets to remove ambiguity the last bit of complexity is Loops again let's start with the simplest Loop one that goes from the goal state to the goal

[05:21] State this means you can have zero or more of that label let's indicate this more of that label let's indicate this using an asterisk with the same logic we using an asterisk with the same logic we can treat each part as having goal and

[05:34] start States so we can reduce any complex map into a simple finite pattern since this is an expression that is used to represent a regular language we call

[05:46] this a regular expression or regex for sure process of turning a graph into a regex can be reversed allowing us to create a graph that will match a regular expression for a particular regex the mathematical term for devices that can

[06:02] operate automatically are called automata and since these automata only have a finite number of of possible States they are called finite state automata it is quite easy to build finite state automata in a computer we

[06:19] can construct a table with a column for each input a row for each state and populate it with the next state to step into doing Simple memory lookups like this on a computer is very fast so what we can do is Define a regex that looks

[06:36] like the thing we want to see then we translate it into a finite State automata we can then search the text by starting at the start of the document and stepping through the finite State machine until it reaches a trap State or

[06:51] the goal state if it reaches a trap State the starting point is moved forward by one and the scan is repeated until a match is found or we run out of document like with everything else there are alternatives and optimizations that

[07:05] can be made implementing this so to find dates in a document all we need to do is create our regex to match the date to make things more compact we can write 0

[07:18] make things more compact we can write 0 1 2 3 4 5 6 7 8 9 AS Slash D then we can 1 2 3 4 5 6 7 8 9 AS Slash D then we can do an ISO 8601 date like this four dates for the year followed by a dash two dates for the month another Dash then

[07:33] the final two digits in a just and perfect world The only date format would perfect world The only date format would be the iso 8601 date format however we don't live in such a world some people make use of Twisted formats like

[07:50] make use of Twisted formats like December 7th 1920 eight we can build on our previous regex for example if we use slash W to represent the word characters slash W to represent the word characters A to Z we can go something like this and

[08:03] A to Z we can go something like this and indeed we can keep adding to this the various representations of date the advantages of Rec access is that you can learn to read them and you can build up

[08:15] complex regular expression from many simple patterns finite State autonomous simple patterns finite State autonomous are the simplest type of autonomous sit at the bottom of a hierarchy of increasingly powerful automata which

[08:28] increasingly powerful automata which I've glossed over much of the details of I would love to go deeper into these details but that would be something for another video but for the time being thank you very much for watching and I

[08:42] hope you'll enjoy using regular Expressions half as much as I do