El tipo de expresión regular es PCRE.

Escriba un programa que genere un PCRE válido de modo que coincida con todos los números naturales entre my ny no coincida con nada más. No se permiten ceros a la izquierda.

Por ejemplo, let mand nbe 123y 4321, entonces el programa podría salir 1(2[3-9]|[3-9]\d)|[2-9]\d\d|[123]\d\d\d|4([012]\d\d|3([01]\d|2[01])).

Esto coincide con la cadena exacta, por lo que ^y $anclajes están implícitos.

Uno debe tratar de equilibrar los dos:

1. La expresión regular debe tener un tamaño razonable.

2. El código debe ser corto.

Optimicemos para

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

Nota al margen: sería interesante si podemos demostrar que la expresión regular PCRE más corta es del tamaño O (log n log log n) o algo así.

Perl, puntaje 455

191 caracteres, 132 de longitud de expresión regular

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

Actualización: pude simplificar aún más esto cuando me di cuenta de que la mayoría de los patrones terminaban con cosas como \d{3}. Estos no hacían más que imponer una longitud de cadena, y lo hacían de manera muy repetitiva, ya que ocurrían en cada término. Eliminé esto usando otra búsqueda anticipada para imponer la condición "menor que", solo comprobando que: 1) la primera parte del número no excede la entrada o 2) el número tiene menos dígitos que la entrada. Luego, la expresión regular principal solo verifica que no tenga demasiados dígitos.

También incorporé la idea de Peter Taylor de anticipación negativa para verificar la condición "mayor que".

La clave para simplificar este problema (al menos para mí) fue dividir la expresión regular en dos: una observación anticipada asegura que el número no sea menor que el mínimo, luego la parte principal de la expresión regular verifica que no sea mayor que el máximo. Es un poco tonto para entradas pequeñas, pero no es tan malo para entradas grandes.

Nota: 0|al principio es excluir cualquier cosa que comience con un cero de la coincidencia. Esto es necesario debido a la naturaleza recursiva de la función regex: las partes internas de la coincidencia pueden comenzar con cero, pero el número entero no. La función regex no puede notar la diferencia, por lo que excluí cualquier número que comience con cero como un caso especial.

Entrada: 1, 4

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

Versión Regex irrazonablemente larga, 29 caracteres:

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

Javascript, puntaje 118740839

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

Supongo que si te gusta o no depende de cómo definas "un tamaño razonable". :-)

Haskell 2063 + 2 * 151 = 2365

Se garantiza que la expresión regular generada tiene una longitud 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

El siguiente código es una versión simple que ayuda a comprender el algoritmo, pero no hace ninguna optimización para mejorar el tamaño de la expresión regular.

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

La expresión regular tiene 680 caracteres. Aqui esta el codigo

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 los valores dados da

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

Disección a seguir, pero la idea básica es definir un bloque de código que mapee un solo número natural a una expresión regular que coincida con cualquier número natural más pequeño, y luego convierta las entradas lby uben una búsqueda negativa (número natural menor que lb) combinado con el regex para (número natural menor que ub+1).

La lógica es bastante complicada, por lo que incluso para los estándares de GolfScript es críptico. Hasta que empiece a escribir una disección detallada, aquí hay una lista de variables:

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