Generate regular expressions for matching natural numbers between `m` and `n`

Question

The type of regular expression is PCRE.

Write a program that output a valid PCRE such that it matches all natural numbers between m and n and does not match anything else. No leading zeros are allowed.

For example, let m and n be 123 and 4321, then the program might output 1(2[3-9]|[3-9]\d)|[2-9]\d\d|[123]\d\d\d|4([012]\d\d|3([01]\d|2[01])).

This matches the exact string, so ^ and $ anchors are implicit.

One should try to balance the two:

The regular expression should have a reasonable size.
The code should be short.

Let's optimize for

code length in characters + 2*regular expression length for input 123456 and 7654321

Side Note: It be interesting if we can prove the shortest PCRE regular expression is of the size O(log n log log n) or something.

Can you define the winning criteria? Maybe something like re_size*5 + prog_size (smaller = better), where re_size is the maximum for m and n up to 5 digits. There are many other ways to do it - what matters is that we can grade the answers. — ugoren, Commented Mar 21, 2013 at 7:46
"Write a program that output a valid PCRE such that it matches all natural numbers between m and n" Presumably "and fails to match all other inputs", no? Lest some smart arse offers print .* in some language. — dmckee --- ex-moderator kitten, Commented Mar 21, 2013 at 13:00
if(min == 123456 && max == 7654321){print_hardcoded_regex}else{enumerate_range_and_join} — John Dvorak, Commented Jun 10, 2013 at 12:06

score 7 · Accepted Answer · 2013-03-25 08:39:26Z

Perl, score 455

191 chars, 132 regex length

sub b{my$a=shift;$_=(@_>0&&$a.b(@_).($a-->0&&'|')).($a>=0&&($a>1
?"[0-$a]":$a));/\|/?"($_)":$_}sub a{b(@a=split//,<>-1+$x++).(@a>
1&&"|.{1,$#a}")}print'(?!0|('.a.')$)(?=('.a.'$))^\d{1,'.@a.'}$'

Input: 123456, 7654321

(?!0|((1(2(3(4(5[0-5]|[0-4])|[0-3])|[0-2])|1)|0)|.{1,5})$)(?=((7(6(5(4(3(21|1)|[0-2])|[0-3])|[0-4])|[0-5])|[0-6])|.{1,6}$))^\d{1,7}$

Update: I was able to further simplify this when I realized that most of the patterns ended with things like \d{3}. These were doing nothing more than enforcing a string length--and doing so very repetitively, since they occurred on every term. I eliminated this by using another lookahead to enforce the "less than" condition, only checking that either: 1) the first part of the number does not exceed the input or 2) the number is fewer digits than the input. Then the main regex just verifies that it is not too many digits.

I also incorporated Peter Taylor's idea of negative look-ahead for checking the "greater than" condition.

The key to simplifying this problem (at least for me) was to break the regex in two: a look-ahead makes sure the number is not less than the minimum, then the main part of the regex checks that it is not greater than the maximum. It is a little bit silly for small input, but it is not so bad for large input.

Note: the 0| at the beginning is to exclude anything that starts with a zero from matching. This is required because of the recursive nature of the regex function: inner parts of the match can start with zero, but the entire number cannot. The regex function can't tell the difference, so I excluded any number starting with zero as a special case.

Input: 1, 4

(?!0|(0)$)(?=([0-4]$))^\d{1,1}$

Unreasonably Long Regex Version, 29 chars:

print'^',join('|',<>..<>),'$'

Don't forget that there's a special special case, which is that if m is 0 then you need to allow 0 despite it having a leading zero. — Peter Taylor, Commented Mar 25, 2013 at 13:35
@PeterTaylor, I thought "natural numbers" meant positive integers. Checking wikipedia, I see that there is actually no agreement on whether zero is a natural number. At this point, I choose to take refuge in the ambiguity rather than change my solution :) — user7486, Commented Mar 25, 2013 at 14:40

Gareth · Accepted Answer · 2013-03-21 16:05:59Z

3

Javascript, score 118740839

function makere(m,n){r='(';for(i=m;i<n;)r+=i+++'|';return (r+i)+')';}

I suppose whether or not you like this depends on how you define 'a reasonable size.' :-)

edited Mar 21, 2013 at 16:05

answered Mar 21, 2013 at 9:14

Gareth

11.4k1 gold badge36 silver badges85 bronze badges

2

\$\begingroup\$ Not gonna test this. I believe you. \$\endgroup\$
– tomsmeding
Commented Mar 21, 2013 at 21:43

Add a comment |

Chao Xu · Accepted Answer · 2013-03-21 17:32:55Z

Haskell 2063+2*151=2365

It's guaranteed the generated regex has length O(log n log log n).

matchIntRange 12345 7654321

1(2(3(4(5[6-9]|[6-9]\d)|[5-9]\d\d)|[4-9]\d{3})|[3-9]\d{4})|[2-9]\d{5}|[1-6]\d{6}|7([0-5]\d{5}|6([0-4]\d{4}|5([0-3]\d{3}|4([012]\d\d|3([01]\d|2[01])))))

import Data.Digits

data RegEx = Range Int Int | MatchNone | All Int
            | Or RegEx RegEx | Concat [RegEx] 

alphabet = "\\d"

instance Show RegEx where
  show (Range i j)
   | i == j    = show i
   | i+1 == j  = concat ["[",show i,show j,"]"]
   | i+2 == j  = concat ["[",show i,show (i+1), show (i+2),"]"]
   | otherwise = concat ["[",show i,"-",show j,"]"]
  show (Or a b)  = show a ++ "|" ++ show b
  show MatchNone = "^$"
  show (All n) 
   | n < 3     = concat $ replicate n alphabet
   | otherwise = concat [alphabet,"{",show n,"}"] 
  show e@(Concat xs) 
   | atomic e  = concatMap show xs
   | otherwise = concatMap show' xs
   where show' (Or a b) = "("++show (Or a b)++")"
         show' x = show x
         atomic (Concat xs) = all atomic xs
         atomic (Or _ _)    = False
         atomic _           = True

-- Match integers in a certain range
matchIntRange :: Int->Int->RegEx
matchIntRange a b
 | 0 > min a b = error "Negative input"
 | a > b       = MatchNone
 | otherwise = build (d a) (d b)
 where build :: [Int]->[Int]->RegEx
       build [] [] = Concat [] 
       build (a@(x:xs)) (b@(y:ys))
         | sl && x == y       = Concat [Range x x, build xs ys]
         | sl && all9 && all0 = Concat [Range x y, All n]
         | sl && all0         = Or (Concat [Range x (y-1), All n]) upper
         | sl && all9         = Or lower (Concat [Range (x+1) y, All n])
         | sl && x+1 <= y-1   = Or (Or lower middle) upper
         | sl                 = Or lower upper
         | otherwise          = Or (build a (nines la)) (build (1:zeros la) b)
         where (la,lb) = (length a, length b)
               sl      = la == lb
               n       = length xs
               upper   = Concat [Range y y, build (zeros n) ys]
               lower   = Concat [Range x x, build xs (nines n)]
               middle  = Concat [Range (x+1) (y-1), All n]
               all9    = all (==9) ys
               all0    = all (==0) xs
       zeros n   = replicate n 0
       nines n   = replicate n 9
       d 0 = [0]
       d n = digits 10 n

The code below is a simple version that helps with understanding the algorithm, but it doesn't do any optimization to improve the regex size.

matchIntRange 123 4321

(((1((2((3|[4-8])|9)|[3-8]((0|[1-8])|9))|9((0|[1-8])|9))|[2-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|((1((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|[2-3]((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))))|4((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-2]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|3((0((0|[1-8])|9)|1((0|[1-8])|9))|2(0|1)))))

The regular expression has 680 characters. Here is the code

import Data.Digits

data RegEx = Range Int Int | MatchNone | Or RegEx RegEx | Concat [RegEx] 

alphabet = "\\d"

instance Show RegEx where
  show (Range i j)
   | i == j    = show i
   | otherwise = concat ["[",show i,"-",show j,"]"]
  show (Or a b)  = concat ["(",show a,"|",show b,")"]
  show MatchNone = "^$"
  show (Concat xs) = concatMap show xs

matchIntRange :: Int->Int->RegEx
matchIntRange a b
 | 0 > min a b = error "Negative input"
 | a > b       = MatchNone
 | otherwise = build (d a) (d b)
 where build :: [Int]->[Int]->RegEx
       build [] [] = Concat [] 
       build (a@(x:xs)) (b@(y:ys))
         | sl && x == y     = Concat [Range x x, build xs ys]
         | sl && x+1 <= y-1 = Or (Or lower middle) upper
         | sl               = Or lower upper
         | otherwise        = Or (build a (nines la)) (build (1:zeros la) b)
         where (la,lb) = (length a, length b)
               sl      = la == lb
               n       = length xs
               upper   = Concat [Range y y, build (zeros n) ys]
               lower   = Concat [Range x x, build xs (nines n)]
               middle  = Concat [Range (x+1) (y-1), build (zeros n) (nines n)]
       zeros n = replicate n 0
       nines n = replicate n 9
       d 0 = [0]
       d n = digits 10 n

Peter Taylor · Accepted Answer · 2013-03-22 01:07:47Z

2

GolfScript (126 + 2*170 = 466)

~)]{`:&,:_,{:i'('\_(<:/i&=48-:D 2<{D^i!!D*|1,*}{'['\i>2D<'-'*D(']?'3$)<}if/D!!*{'\d{'/i>'1,'*_(i-'}|'D}*}%_')'*]}%'(?!'\~'$)'\

For the given values it gives

(?!(\d{1,5}|1([01]\d{4}|2([0-2]\d{3}|3([0-3]\d{2}|4([0-4]\d{1}|5([0-5]))))))$)([1-6]?\d{1,6}|7([0-5]\d{5}|6([0-4]\d{4}|5([0-3]\d{3}|4([0-2]\d{2}|3([01]\d{1}|2([01])))))))

Dissection to follow, but the basic idea is to define a block of code which maps a single natural number to a regex matching any smaller natural number, and then turn the inputs lb and ub into a negative lookahead for (natural number smaller than lb) combined with the regex for (natural number smaller than ub+1).

The logic is quite complicated, so even by GolfScript standards it's cryptic. Until I get round to writing a detailed dissection, here's a list of variables:

&  the whole number string
i  the current idx
D  the current digit
/  not-the-last-digit
_  total number of digits

edited Mar 22, 2013 at 1:07

answered Mar 21, 2013 at 16:28

Peter Taylor

43.1k4 gold badges70 silver badges169 bronze badges

\$\begingroup\$ @dan1111, I looked at the documentation for PCRE but I didn't see anything forbidding out-of-order character classes, and the tester I used didn't give an error. I'll have to look into that. OTOH if your regex engine doesn't like an expression ending in | then that's a bug in your regex engine, not in my regex. \$\endgroup\$
– Peter Taylor
Commented Mar 21, 2013 at 17:14
\$\begingroup\$ sorry, I didn't realize that (a|) is actually valid. However, [1-0] in your previous regex did not work in Perl or an online tester I tried. \$\endgroup\$
– user7486
Commented Mar 22, 2013 at 6:05
\$\begingroup\$ @dan1111, after you pointed it out I realised that the online tester I was using was swallowing the error. I reproduced it on a machine with Perl, and wrote a test framework using Perl to check the regexes. Thanks for pointing it out. \$\endgroup\$
– Peter Taylor
Commented Mar 22, 2013 at 8:49

Add a comment |

Stack Exchange Network

Generate regular expressions for matching natural numbers between `m` and `n`

4 Answers 4

Perl, score 455

Javascript, score 118740839

GolfScript (126 + 2*170 = 466)

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
regular-expression
or ask your own question.

Hot Network Questions

Generate regular expressions for matching natural numbers between `m` and `n`

4 Answers 4

Perl, score 455

Javascript, score 118740839

GolfScript (126 + 2*170 = 466)

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfregular-expression or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
regular-expression
or ask your own question.