O tipo de expressão regular é PCRE.

Escreva um programa que produza um PCRE válido, de forma que ele corresponda a todos os números naturais entre me ne não corresponda a mais nada. Não são permitidos zeros à esquerda.

Por exemplo, let me nbe 123e 4321, então o programa pode sair 1(2[3-9]|[3-9]\d)|[2-9]\d\d|[123]\d\d\d|4([012]\d\d|3([01]\d|2[01])).

Isto corresponde a seqüência exata, por isso ^e $âncoras estão implícitas.

Deve-se tentar equilibrar os dois:

1. A expressão regular deve ter um tamanho razoável.

2. O código deve ser curto.

Vamos otimizar para

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

Nota: Pode ser interessante se pudermos provar que a expressão regular PCRE mais curta é do tamanho O (log n log log n) ou algo assim.

Perl, pontuação 455

191 caracteres, 132 comprimento de regex

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.'}$'

Entrada: 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}$

Atualização: Pude simplificar ainda mais isso quando percebi que a maioria dos padrões terminava com coisas do tipo \d{3}. Eles nada mais faziam do que impor um comprimento de string - e repetidamente, uma vez que ocorriam em todos os termos. Eu eliminei isso usando outra cabeça de impressão para impor a condição "menor que", apenas verificando se: 1) a primeira parte do número não excede a entrada ou 2) o número tem menos dígitos que a entrada. Em seguida, o regex principal apenas verifica se não há muitos dígitos.

Também incorporei a ideia de Peter Taylor de olhar para frente negativo para verificar a condição "maior que".

A chave para simplificar esse problema (pelo menos para mim) foi dividir o regex em dois: um olhar em frente garante que o número não seja menor que o mínimo e, em seguida, a parte principal do regex verifica se ele não é maior que o máximo. É um pouco tolo para entradas pequenas, mas não é tão ruim para entradas grandes.

Nota: 0|no início é excluir qualquer coisa que comece com um zero da correspondência. Isso é necessário devido à natureza recursiva da função regex: partes internas da correspondência podem começar com zero, mas o número inteiro não. A função regex não pode dizer a diferença, então excluí qualquer número começando com zero como um caso especial.

Entrada: 1, 4

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

Versão Regex irracionalmente longa, 29 caracteres:

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

Javascript, pontuação 118740839

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

Suponho que você goste ou não disso depende de como você define "um tamanho razoável". :-)

Haskell 2063 + 2 * 151 = 2365

É garantido que o regex gerado tenha comprimento 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

O código abaixo é uma versão simples que ajuda a entender o algoritmo, mas não faz nenhuma otimização para melhorar o tamanho do regex.

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)))))

A expressão regular possui 680 caracteres. Aqui está o código

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

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}*}%_')'*]}%'(?!'\~'$)'\

Para os valores dados, ele fornece

(?!(\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])))))))

Dissecção a seguir, mas a idéia básica é definir um bloco de código que mapeie um único número natural para uma regex que corresponda a qualquer número natural menor e, em seguida, transforme as entradas lbe ubem uma aparência negativa para (número natural menor que lb) combinado com o regex para (número natural menor que ub+1).

A lógica é bastante complicada, portanto, mesmo para os padrões GolfScript, é enigmático. Até eu começar a escrever uma dissecção detalhada, aqui está uma lista de variáveis:

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