a thoughtful web.
Good ideas and conversation. No ads, no tracking.   Login or Take a Tour!
comment

This is an old thread but I'm posting anyway.

You guys read XKCD? Its this funny, smart, science/tech thing that is well worth checking out.

A few weeks ago he added this which peeked my interest. He took 2 lists and tried to generate a regular expression that matches all the items in the first list and none of the items in the second, with the goal being the shortest expression is the winner. He used Star Wars movie subtitles vs Star Trek movie subtitles and his shortest regular expression was:

    /M ! [TN]!B/
Note that I used "!" instead of the bar as it messes up the formatting here.

I took a shot at writing my own regular expression builder and tried to implement a clever way to find the shortest regular expression by grabbing the terms that were matched by the fewest expressions and picking the expression that matched the highest number of terms. Iterating over that to produce an expression that matched all the provided terms.

The code is on github; its horrible, slow and in need of a lot of refactoring, but my solution to the SW vs ST was:

    ..p!t..
which is 1 character shorter than Randalls solution.

I'm taking some time to focus on neat little problems like this that are solvable. Following on from Richard Feynmans advice, I find a real joy in solving things like this and I forgot they were so much fun.