Thursday, January 14, 2010

Super RegEx Smash

I think there should exist games that teach computer science concepts:
- regular expressions
- A* search
- pointers
- Dijkstra's algorithm
- B+ trees
- ...

I remember in college, it was difficult to form an intuitive understanding of these concepts by reading a textbook or listening to a lecture. But I bet if you played a graphical game where you have to construct regular expressions to save the princess, you'd learn them real quick.

For example, in one possible incarnation of the game, the princess would be imprisoned in a traveling buggy. You are riding a horse, attempting to catch up to the buggy. The evil guard driving the buggy throws regular expressions at you. You have to construct a string which matches the regex before it reaches your horse. If you get it wrong, the part that doesn't match will flash green, and you can try again in the remaining time.

The game with B+ trees could consist of building a tree out of numbered jigsaw pieces sent by the princess from her prison tower. Dijkstra's algorithm is used to find the shortest path to the prison tower.

I've expressed this dream to friends, in the past. They laughed at me. Indeed no one will amass wealth or fame from making these games. But they should exist! It is a travesty that they do not exist in this world. The creator of these games would get adoration, at least from me.

This is like Dan's idea that technical articles should be written with dramatic plot and character development. I was skeptical at the time. But now it has been three years, and I still vividly remember that silhouette detection and rendering paper!


Andrew said...

It might be more fun if you had a predefined set of strings, so you had to pick the right one. Some would match more than one, but you could only use each one once, so you might have to play through each level a few times.

Or, a two-player game where each player takes turns hurling regular expressions at a big block of text, attempting to tactically match certain parts of it somehow.

Niniane said...

I considered the "hand of cards" where each card is a regular expression. I didn't go with it, because it would require a lot of deliberation at each turn, instead of the fast-paced timed sequence I envisioned.

pawliger said...

Cool idea! Could be like those learn to type games... For early learning levels, could highlight the parts of the regex that matched so far. That would work if you limited the earlier rounds to more deterministic expressions.

gregbo said...

Hmmm ... WRT regexes, I suppose it depends upon the way the course is taught. When I took computability, it was more important when given a description of a language, and some candidate strings, to give the regex, or finite automaton. Other things covered were the the equivalence of deterministic and nondeterministic finite automata, the equivalence of regular languages to regular grammars, and when a finite automaton cannot recognize a language. I'm not sure that your game idea will produce that type of intuition. Why not run your idea by some theorists and see what they say?

FWIW, I'd like to know how you eventually developed intuition for those subjects. I write about that sort of thing in my journal occasionally.

Gavin Doughtie said...

Oh my gosh -- Niniane, I'd *pay* to play some of these games. Not, you know, a LOT... but...

WebGL + WebSockets == Massively Multiplayer Online Computer Science Education Games (MMOCSEGs)!

vijay said...

Strangely enough in my data structures class, this postdoc had created such a game and experimented on me and a friend with it. It was somewhat elucidating, but maybe a more refined version would work better. Here's a link, I'm ready for all the embarrassment that might follow:

Niniane said...

Vijay, your link does not work! Please post a new link. I would like to see the game.

vijay said...

Strange, I just downloaded it from that url, and now it doesn't work for me either. I have put it up here. It's more of an interactive visualization than a game per se, but it's close enough that a modification isn't a giant leap.