2 ms·
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
by gwern 13y ago
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.
- jules 13y agoAnother xkcd applies here: http://xkcd.com/356/ http://xkcd.com/356/
- abecedarius 13y agoI coded a brute-force one before: https://github.com/darius/sketchbook/blob/master/regex/find_min_re.py 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.
- chao_xu 13y agoI 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-size-of-regular-expression-for-finite-sets http://cstheory.stackexchange.com/questions/16860/minimizing... Apparently this problem is still open.