---
title: 'Escaping a Dungeon with Regular Expressions'
source: 'https://youtube.com/watch?v=7oziUFtExlQ'
video_id: '7oziUFtExlQ'
date: 2026-07-31
duration_sec: 527
---

# Escaping a Dungeon with Regular Expressions

> Source: [Escaping a Dungeon with Regular Expressions](https://youtube.com/watch?v=7oziUFtExlQ)

## Summary

This video explains regular expressions through a creative dungeon-crawling metaphor. It introduces core ideas from language theory—alphabets, words, regular languages, and finite state automata—to show how regex patterns can be built, read, and used to search text efficiently.

### Key Points

- **The problem regex solves** [00:02] — Finding formatted information (like addresses or dates) in a document when you don't know the exact text; regular expressions are a technique tools use to locate such patterns.
- **The dungeon RPG setup** [00:30] — A minimalist dungeon with a starting room and a gold room; each room has labeled one-way doors, and you win by navigating through doors to reach the gold.
- **The alphabet of door labels** [01:43] — Door labels can be numbers, letters, or symbols (e.g., cat, dog, T-Rex); the collection of all possible labels is called an alphabet.
- **Winning paths are words** [02:45] — Rooms that can never lead to the goal are 'trap rooms' and can be removed. A winning path is called a word, and the list of all possible winning words forms a language.
- **Regular languages and finite representation** [03:13] — Languages with simple repeating patterns are called regular languages. The key question is how to represent an infinite set of words in a finite, neat form.
- **Building regex from simplest cases** [03:42] — If the entrance is the goal, represent the pattern as an empty string. For a corridor, prepend its arc's letter to the pattern. Generalize by treating each next room as the goal.
- **Alternatives with the pipe** [04:25] — When two arcs lead to the same goal, use a vertical line (|) to represent the alternative. More choices simply add more labels with another |.
- **Loops with the asterisk** [05:21] — A loop from a goal state to itself allows zero or more of that label; this is indicated with an asterisk (*). Brackets help remove ambiguity in complex expressions.
- **Regular expressions and finite state automata** [05:46] — A regex is a finite pattern representing a regular language. The reverse process—turning a regex into a graph—creates a device called a finite state automaton (FSA).
- **Fast FSA implementation** [06:19] — An FSA can be built as a table with a column for each input, a row for each state, and next-state entries. Simple memory lookups make this very fast.
- **Search algorithm using FSA** [06:36] — Define a regex, translate it into an FSA, then scan the document: start at the beginning and step through states. If a trap state is reached, advance the start by one and repeat until a goal state is found or the document ends.
- **Date patterns and shorthand** [07:18] — Use \d to represent digits 0-9. Build an ISO 8601 date pattern like \d{4}-\d{2}-\d{2}. Use \w for word characters to handle formats such as 'December 7th 1928'.
- **FSA hierarchy and further topics** [08:15] — Finite state automata are the simplest type of automata, at the bottom of a hierarchy of increasingly powerful models; many details are left for a future video.

### Conclusion

Regular expressions are a practical, elegant tool: any regex corresponds to a finite state automaton, turning infinite pattern-matching into fast table lookups. By mastering concatenation, alternation, and loops, you can build and read regex for real-world formats like dates.

## Transcript

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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
hope you'll enjoy using regular Expressions half as much as I do