3 ms·
The link is not loading for me. So I can only guess how it was done. But here is how I would do it. First as you proceed through the digits of a number, you
by btilly 16y ago
The link is not loading for me. So I can only guess how it was done. But here is how I would do it.
First as you proceed through the digits of a number, you know that after each digit you will have some remainder mod 7. And each digit changes that remainder. Now let's invent a piece of notation. Let's say that (n...m) is a regular expression that matches any string of digits that carries you from a remainder of n to a remainder of m without in the middle having a remainder that is m or lower, or n or lower.
So, for instance, (3...1) would match strings like '6' or '23' or '200', but not '242' because after adding the digits '24' your remainder is 2, which is too low for the middle.
Now with this piece of notation, the desired regular expression is simply:
(0...0)+
And (0...0) is not to hard to figure out. It is
(
0 |
7 |
(0...1)(1...1)*(1...0) |
(0...2)(2...2)*(2...0) |
(0...3)(3...3)*(3...0) |
(0...4)(4...4)*(4...0) |
(0...5)(5...5)*(5...0) |
(0...6)(6...6)*(6...0)
)
Taking just one of those pieces, what is (0...3)? It is just
(
3 |
(0...4)(4...4)*(4...3) |
(0...5)(5...5)*(5...3) |
(0...6)(6...6)*(6...3)
)
And so on. If you expand all of the pieces out eventually you'll come up with a horrible regexp without my invented notation that will test for divisibility by 7. (And nothing stops you from repeating that for divisibility by anything else.)
- eru 16y agoMy approach was more mechanistic, but may boil down to the same idea. I build up the finite automaton for testing for divisibility by 7; one state for each possible remainder from 0 to 6. Then I compiled this description of an automaton to a regular expression using the textbook algorithm.
- btilly 16y agoOf 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.