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.
Comments
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.
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.
Another xkcd applies here: http://xkcd.com/356/
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.