Łatwo jest opisać maszynę skończoną, która rozpoznaje wielokrotności 9: śledź sumę cyfr (mod 9) i dodaj dowolną cyfrę, która zostanie zaakceptowana jako następna. Taki FSM ma tylko 9 stanów, bardzo proste! Dzięki równoważności między rozpoznawalnością FSM a językami regularnymi istnieje wyrażenie regularne dla wielokrotności 9. Jednak każde takie wyrażenie regularne jest prawdopodobnie ... bardzo ... długie. Jak w, prawdopodobnie rzędu gigabajtów.

Jest działający przykład na https://www.quaxio.com/triple/ dla wielokrotności 3. Na dole strony autor zapewnia nieco „zoptymalizowane ręcznie” rozwiązanie, które jest nieco krótsze niż naiwna konwersja z FSM do wyrażenia regularnego.

Wyzwanie:

Musisz wykonać regex, aby wykryć wielokrotności 9. Ponieważ taki regex ma być bardzo długi, proszę o podanie programu, który może wydrukować regex. (Jeśli naprawdę chcesz podać cały regex, być może hostuj go gdzie indziej i link tutaj!)

Musisz być w stanie powiedzieć nam dokładną liczbę znaków wyjściowych programu - więc posiadanie programu, który po prostu wypróbuje wszystkie wyrażenia regularne do określonej długości, dopóki nie znajdzie takiego, który działa, jest nie do przyjęcia, chyba że działa wystarczająco szybko, abyś mógł uruchom go do końca i podaj nam wynikową długość wyrażenia regularnego!

Punkty są za najkrótsze wyrażenie regularne, nie oparte oczywiście na długości programu. Ponieważ regex jest „programem”, o który proszę, a jego przesyłanie tutaj jest zbyt długie, wciąż taguję ten kod-golf.

Zasady:

• Dane wejściowe będą zawierać tylko pasujące znaki [0-9]*.
• Wyrażenie regularne powinno pasować do wielokrotności 9, ale nie do niczego innego. Przypadki, które nie są w całości wykonane z cyfr 0–9 i są niepoprawnymi danymi wejściowymi, mogą być zgodne lub niepoprawne.
• Biorąc pod uwagę motywację, którą łatwo rozpoznaje DFA, wynikowe wyrażenie regularne musi być wyrażeniem regularnym w bardziej teoretycznej terminologii, to znaczy tylko operatory, pod którymi zamknięte są zwykłe języki. Mówiąc ściślej, jedyne rzeczy, które są dozwolone:
  • Literówki, zakresy znaków ( [ab], [a-f], [^k]), domknięcie kleene'ego ( *), kotwice ( ^i $), grupowanie poprzez nawiasach (naprzemienne| ), opcjonalnie terminów ( ?), jedno-lub-więcej terminów ( +), lookaheads ( (?=)), negatywne lookaheads ( (?!)) lookbehinds ( (?<=)), negatywny lookbehinds ( (?<!)), warunkowe (jak w https://www.regular-expressions.info/conditional.html - (?(?=test)then|else)) i rereferencje ograniczonej długości (patrz poniżej).
• Przykłady rzeczy, które są nie dozwolone:
  • Referencje wsteczne o dowolnej długości, referencje do przodu, rekurencja, podprogramy, konstrukcje zapętlone, kod wykonywalny, dowolna odmiana „eval” lub wbudowane konstrukcje do rzutowania łańcucha na wartość arytmetyczną.
• Odwołania wsteczne, które mogą wykazywać ciąg wiążący o ograniczonej długości, są dopuszczalne, ponieważ mogą być przechowywane w stanie skończonym i nie zmieniają regularności języka. Na przykład wyrażenie regularne (..2.[3-5])4\1.\1jest dopuszczalne, ponieważ grupa przechwytująca ma określoną długość \1. To jest zwykła konstrukcja. Konstrukt taki jak (2*)0\1jest niedopuszczalny, ponieważ przechwyconej grupy nie można zapisać w stanie skończonym.
• Wyrażenie regularne może dowolnie akceptować lub odrzucać liczby całkowite z dodatkowymi zerami wiodącymi. Jednak ciąg"0" musi zostać zaakceptowany.

Haskell , 207,535 202 073 bajtów

5 462 bajtów zapisanych przy użyciu 0|9zamiast, [09]jeśli to możliwe.

digits n
  | x == 0    = "0|9"
  | otherwise = show x
  where x = mod n 9

regex 0 = "[09]*"
regex n = (regex' n (-1) (-1)) ++ "*"

regex' 0 start end = digits (end - start)
regex' n start end = '(':(regex' 0 start end) ++ (concat ['|':(regex' (n-x) (start-x) (-1)) ++ (regex (n-x))
                                                  ++ (regex' (n-x) (-1) (end-x)) | x <- [1..n]]) ++ ")"

main = do
  putStr ("^" ++ (regex 8) ++ "$")

Wypróbuj online!

Wystarczy szybkie dostosowanie wyrażenia regularnego podanego w przypisach do powiązanego artykułu, aby rozpocząć.

Pastebin wyrażenia regularnego wyniku , dzięki uprzejmości Hermana Lauensteina.

Chociaż nie byłem w stanie przetestować pełnego wyrażenia regularnego, zmodyfikowanie programu w celu sprawdzenia podzielności przez 3 zamiast tego daje coś dokładnie równoważnego wyrażeniu regularnemu, na którym to opierałem. Co więcej, modyfikowanie programu w celu sprawdzenia podzielności sumy cyfr przez 4 lub 5 również wydaje się działać na liczbach, na których testowałem.