Die Art des regulären Ausdrucks ist PCRE.

Schreiben Sie ein Programm, das eine gültige PCRE so ausgibt, dass alle natürlichen Zahlen zwischen mund nmit nichts anderem übereinstimmen. Führende Nullen sind nicht zulässig.

Zum Beispiel let mand nbe 123and 4321, dann könnte das Programm ausgegeben werden 1(2[3-9]|[3-9]\d)|[2-9]\d\d|[123]\d\d\d|4([012]\d\d|3([01]\d|2[01])).

Dies entspricht exakt die gleiche Zeichenkette, so ^und $Anker ist implizit.

Man sollte versuchen, die beiden zu balancieren:

1. Der reguläre Ausdruck sollte eine angemessene Größe haben.

2. Der Code sollte kurz sein.

Optimieren wir für

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

Randnotiz: Es ist interessant, wenn wir nachweisen können, dass der kürzeste reguläre PCRE-Ausdruck die Größe O (log n log log n) oder etwas anderes hat.

Perl, Punktzahl 455

191 Zeichen, 132 Regex-Länge

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

Eingang: 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: Ich konnte dies weiter vereinfachen, als mir klar wurde, dass die meisten Muster mit Dingen wie endeten \d{3}. Diese machten nichts weiter als das Erzwingen einer Zeichenfolgenlänge - und dies sehr wiederholt, da sie bei jedem Begriff auftraten. Ich habe dies beseitigt, indem ich einen anderen Lookahead verwendet habe, um die Bedingung "kleiner als" zu erzwingen, und nur überprüft, ob entweder: 1) der erste Teil der Nummer die Eingabe nicht überschreitet oder 2) die Nummer weniger Stellen als die Eingabe hat. Dann überprüft die Haupt-Regex nur, ob es sich nicht um zu viele Ziffern handelt.

Ich habe auch Peter Taylors Idee einer negativen Vorausschau aufgenommen, um die Bedingung "größer als" zu überprüfen.

Der Schlüssel zur Vereinfachung dieses Problems (zumindest für mich) bestand darin, den regulären Ausdruck in zwei Teile zu teilen: Ein Ausblick stellt sicher, dass die Anzahl nicht kleiner als das Minimum ist, und der Hauptteil des regulären Ausdrucks überprüft, ob er nicht größer als der ist maximal. Es ist ein bisschen albern für kleine Eingaben, aber es ist nicht so schlecht für große Eingaben.

Hinweis: 0|Am Anfang wird alles, was mit einer Null beginnt, vom Abgleich ausgeschlossen. Dies ist aufgrund der rekursiven Natur der Regex-Funktion erforderlich: Innenteile der Übereinstimmung können mit Null beginnen, die gesamte Zahl jedoch nicht. Die Regex-Funktion kann den Unterschied nicht erkennen, daher habe ich eine Zahl, die mit Null beginnt, als Sonderfall ausgeschlossen.

Eingang: 1, 4

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

Unangemessen lange Regex-Version, 29 Zeichen:

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

Javascript, Punktzahl 118740839

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

Ich nehme an, ob Ihnen das gefällt oder nicht, hängt davon ab, wie Sie "eine angemessene Größe" definieren. :-)

Haskell 2063 + 2 * 151 = 2365

Es ist garantiert, dass der generierte reguläre Ausdruck die Länge O hat (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

Der folgende Code ist eine einfache Version, die zum Verständnis des Algorithmus beiträgt, jedoch keine Optimierung zur Verbesserung der Regex-Größe vornimmt.

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

Der reguläre Ausdruck hat 680 Zeichen. Hier ist der 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

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

Für die angegebenen Werte gibt es

(?!(\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 zu folgen, aber die Grundidee ist , einen Codeblock zu definieren , die Karten eine einzelne natürliche Zahl mit einem regulären Ausdruck jede kleinere natürliche Zahl übereinstimmt, und dann die Eingänge drehen lbund ubin einen negativen Vorgriff - für (natürliche Zahl kleiner als lb) in Kombination mit der Regex für (natürliche Zahl kleiner als ub+1).

Die Logik ist ziemlich kompliziert, daher ist sie selbst für GolfScript-Standards kryptisch. Bis ich eine detaillierte Präparation schreibe, ist hier eine Liste von Variablen:

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