3 ms·
Yup, I didn't anchor it. Can I suggest adding that to the generated regex, as it really is part of it? And I fully approve of non-special-casing it, it's just
by Groxx 16y ago
Yup, I didn't anchor it. Can I suggest adding that to the generated regex, as it really is part of it? And I fully approve of non-special-casing it, it's just amazing how big it is for such a "simple" case :)
It's too bad this didn't get up higher, it's quite interesting. Good job, in any case!
- robinhouston 16y agoThanks. I’ve already added the anchors in fact, when I guessed this might be the problem you were having. I'm also wondering whether it would be possible to generate shorter regular expressions by using a different algorithm for converting the DFA into a regex. I'm using state elimination, which was straightforward to implement, but perhaps the results would be shorter using Brzozowski's algorithm? I'll have a play with that, when I get a spare hour. I'm a little disappointed more people didn't find this interesting, because I would have enjoyed discussing it, but it was a fun hack in any case!
- Groxx 16y agoSubmission time seems to play a pretty big role. Looks like this went up around 7pm (here. US Central) - for future reference, try ~4pm for your target, when people get off work ;) I'm almost certain I saw an article here very-roughly a couple months ago that had an example of how to "shrink" regexes to their functional equivalent. Can't find it now, though :\
- robinhouston 16y agoInteresting. If you can dig that out, I'd love to see it. The problem of reducing a regular expression to a minimal equivalent is PSPACE-complete, so there's not much hope for a practical exact algorithm, but I don't know what the state of the art is on approximation algorithms for minimisation.