4 ms·
Of course from your description, both of us have incorrect algorithms. Because we'd match things like '0777'. Instead you need to match 0 or match 1-9, follow
by btilly 16y ago
Of course from your description, both of us have incorrect algorithms. Because we'd match things like '0777'. Instead you need to match 0 or match 1-9, followed by a sequence that leads to 0, followed by anything. (I still can't download the link, so I can't test whether you actually have this bug.)
If you add to my notation (n.>.m) for a match for any sequence descending from n that finally reaches m, then the answer is something like this:
^(
0 |
(
(
7 |
(1|8) (1.>.0) |
(2|9) (2.>.0) |
3 (3.>.0) |
4 (4.>.0) |
5 (5.>.0) |
6 (6.>.0) |
) (0...0)*
)
)$
And, of course, you can expand something like (4.>0.) out into
(4...4)* (
(4...0) |
(4...1) (1.>.0) |
(4...2) (2.>.0) |
(4...3) (3.>.0)
)
And now we'll get an even bigger heinous mess. But a more correct one.
- eru 16y agoI do match 0777, and consider it the correct thing to do. I don't care here whether some programming languages consider leading zeros to indicate octal. Also I treat the empty string as equal to zero. It would be easy to extend the regex so that it would not match numbers with leading zeroes or the empty string, if one wanted to. If you give me your email address, I can send you the regex and the program that generates it. (My address is in my profile, or you just post yours here.)
- eru 16y agoP.S. Try this link http://pastebin.com/q2AXes8u http://pastebin.com/q2AXes8u
- btilly 16y agoThanks, that link works. It looks like it did something similar to the strategy I described, but it ordered the states differently. It also inserted a lot of unnecessary parentheses. I also dislike the need for \ everywhere. With Perl compatible REs you don't need them, and that gets rid of a lot of line noise. I'm tempted to put together a Python program to generate these, with options to control how much they expand out.
- eru 16y agoI removed most of the unnecessary parenthesis, now. I also put my program on http://github.com/matthiasgoergens/Div7 http://github.com/matthiasgoergens/Div7 I targeted grep, because I know that grep handles regular expressions properly. Perl does a very bad job, according to http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html Perl can take an exponential time to match (or reject). grep always finishes in linear time. Because grep does regular expressions according to theory. While Perl does something strange. To quote: "This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep. The two approaches have wildly different performance characteristics ... The trends shown in the graph continue: the Thompson NFA handles a 100-character string in under 200 microseconds, while Perl would require over 10^15 years." P.S. Good news: I found out that grep -E makes the backslash unnecessary. At http://pastebin.com/Dr7xk8in http://pastebin.com/Dr7xk8in you will find the new and shorter version.
- btilly 16y agoThere are disaster regular expressions where Perl will be slow. But most of the common disasters disappeared a number of years ago. And your regular expression is one that is unlikely to have performance problems due to backtracking. (Though the regular expression engine may hate the size.) That said, Russ Cox is generally well worth listening to.