On: Python code to solve xkcd 1313 by Peter Norvig

[gwern]

It's too bad he didn't try to tackle the optimal regexp problem and settled for approximations - it may be a NP-hard problem, but all the example solutions are short enough that the instances might be still tractable. Would've been nice to know for sure.

[abecedarius → gwern]

I coded a brute-force one before: https://github.com/darius/sketchbook/blob/master/regex/find_...

Though it cares about the size of the AST rather than the concrete syntax. I can't try running it now, I'm on an iPad.

[jules → gwern]

Another xkcd applies here: http://xkcd.com/356/

[chao_xu → gwern]

I asked the problem for regular expression(the theoretical kind) for a finite set on cstheory a while ago.

http://cstheory.stackexchange.com/questions/16860/minimizing...

Apparently this problem is still open.