8
\$\begingroup\$

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:

  1. The regular expression should have a reasonable size.

  2. 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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – ugoren
    Mar 21, 2013 at 7:46
  • \$\begingroup\$ "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. \$\endgroup\$ Mar 21, 2013 at 13:00
  • \$\begingroup\$ Would've been more fun with negative numbers :-D \$\endgroup\$
    – J B
    Mar 21, 2013 at 14:45
  • \$\begingroup\$ if(min == 123456 && max == 7654321){print_hardcoded_regex}else{enumerate_range_and_join} \$\endgroup\$ Jun 10, 2013 at 12:06

4 Answers 4

7
\$\begingroup\$

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('|',<>..<>),'$'
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 25, 2013 at 13:35
  • 2
    \$\begingroup\$ @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 :) \$\endgroup\$
    – user7486
    Mar 25, 2013 at 14:40
3
\$\begingroup\$

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.' :-)

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

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\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\$ 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
    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\$ Mar 22, 2013 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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