ECMAScript regex 733+ 690+ 158 119 118 (117🐌) bajtów
Moje zainteresowanie regexem rozbudziło nowe życie po ponad 4,5 roku bezczynności. W związku z tym szukałem bardziej naturalnych zestawów liczb i funkcji, które pasowałyby do jednoargumentowych wyrażeń regularnych ECMAScript, wznowiłem ulepszanie mojego silnika wyrażeń regularnych i zacząłem odświeżyć również na PCRE.
Fascynuje mnie obca konstrukcja funkcji matematycznych w wyrażeniu regularnym ECMAScript. Do problemów należy podchodzić z zupełnie innej perspektywy i aż do nadejścia kluczowej wiedzy nie wiadomo, czy można je w ogóle rozwiązać. Wymusza rzucenie znacznie szerszej siatki w celu znalezienia właściwości matematycznych, które można by wykorzystać do rozwiązania konkretnego problemu.
Dopasowywanie liczb czynnikowych było problemem, o którym nawet nie pomyślałem w 2014 r. - lub gdybym tylko chwilowo odrzucił to jako zbyt mało prawdopodobne, aby było to możliwe. Ale w zeszłym miesiącu zdałem sobie sprawę, że można to zrobić.
Podobnie jak w przypadku innych postów z wyrażeniami regularnymi ECMA, dam ostrzeżenie: zdecydowanie zalecam naukę rozwiązywania pojedynczych problemów matematycznych w wyrażeniach regularnych ECMAScript. To była dla mnie fascynująca podróż i nie chcę zepsuć jej nikomu, kto mógłby potencjalnie chcieć spróbować samemu, szczególnie tym, którzy interesują się teorią liczb. W tym wcześniejszym poście znajduje się lista zalecanych problemów oznaczonych spoilerem do rozwiązania jeden po drugim.
Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuła Ci się jakaś zaawansowana magia wyrażeń regularnych . Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript, jak opisano w linku powyżej.
To był mój pomysł:
Problem z dopasowaniem tego zestawu liczb, jak w większości innych, polega na tym, że w ECMA zwykle nie jest możliwe śledzenie dwóch zmieniających się liczb w pętli. Czasami można je multipleksować (np. Moce tej samej bazy można jednoznacznie sumować), ale zależy to od ich właściwości. Więc nie mogłem po prostu zacząć od liczby wejściowej i podzielić ją przez stopniowo rosnącą dywidendę, aż osiągnę 1 (a przynajmniej tak myślałem).
Potem przeprowadziłem badania na temat mnogości czynników pierwszych w liczbach czynnikowych i dowiedziałem się, że istnieje na to formuła - i prawdopodobnie mógłbym ją zaimplementować w wyrażeniu regularnym ECMA!
Po tym, jak dusiłem go przez chwilę i w międzyczasie skonstruowałem kilka wyrażeń regularnych, podjąłem się zadania napisania wyrażenia regularnego. Zajęło to kilka godzin, ale skończyło się ładnie. Jako dodatkowy bonus algorytm może zwrócić odwrotność silni jako dopasowanie. Nie można było tego uniknąć; z samej natury tego, w jaki sposób należy go wdrożyć w ECMA, konieczne jest odgadnięcie, czym jest odwrotna silnia, zanim zrobi się cokolwiek innego.
Minusem było to, że ten algorytm stworzył bardzo długi regex ... ale byłem zadowolony, że ostatecznie wymagał techniki stosowanej w moim regexie mnożenia 651 bajtów (tej, która okazała się przestarzała, ponieważ inna metoda stworzyła 50 bajt regex). Miałem nadzieję, że pojawi się problem wymagający tej sztuczki: działanie na dwóch liczbach, które są potęgami tej samej bazy, w pętli, poprzez ich jednoznaczne połączenie i rozdzielenie ich przy każdej iteracji.
Ale ze względu na trudność i długość tego algorytmu zastosowałem molekularne wyczekiwanie (formy (?*...)) do jego wdrożenia. Jest to funkcja nie w ECMAScript ani żadnym innym głównym mechanizmie regex, ale ta, którą zaimplementowałem w moim silniku . Bez przechwytywania wewnątrz molekularnego spojrzenia, jest funkcjonalnie równoważny atomowemu spojrzeniu naprzód, ale przy przechwytywaniu może być bardzo potężny. Silnik wróci do poprzedniej wersji i można go użyć do ustalenia wartości, która przechodzi przez wszystkie możliwości (do późniejszego testowania) bez zużywania znaków z danych wejściowych. Korzystanie z nich może zapewnić znacznie czystszą implementację. (Za wyglądem o zmiennej długości ma co najmniej tyle samo mocy, co molekularne spojrzenie w przód, ale ten ostatni sprawia, że bardziej proste i eleganckie wdrożenia).
Tak więc długości 733 i 690 bajtów w rzeczywistości nie reprezentują inkarnacji rozwiązania zgodnych z ECMAScript - stąd „+” po nich; z pewnością możliwe jest przeniesienie tego algorytmu do czystego ECMAScript (co znacznie zwiększyłoby jego długość), ale nie poradziłem sobie z tym ... ponieważ myślałem o znacznie prostszym i bardziej zwartym algorytmie! Taki, który można łatwo wdrożyć bez uprzedzeń molekularnych. Jest także znacznie szybszy.
Ten nowy, podobnie jak poprzedni, musi odgadnąć odwrotną silnię, przechodząc przez wszystkie możliwości i testując je pod kątem dopasowania. Dzieli N przez 2, aby zrobić miejsce na pracę, którą musi wykonać, a następnie tworzy pętlę, w której wielokrotnie dzieli dane wejściowe przez dzielnik, który zaczyna się od 3 i zwiększa za każdym razem. (Jako takie, 1! I 2! Nie mogą być dopasowane przez główny algorytm i muszą być traktowane osobno.) Dzielnik jest śledzony przez dodanie go do bieżącego ilorazu; te dwie liczby można jednoznacznie rozdzielić, ponieważ przy założeniu M! == N, bieżący iloraz będzie nadal podzielny przez M, dopóki nie wyniesie M.
Wyrażenie regularne wykonuje dzielenie według zmiennej w najbardziej wewnętrznej części pętli. Algorytm podziału jest taki sam, jak w moich innych wyrażeniach regularnych (i podobny do algorytmu mnożenia): dla A≤B, A * B = C, jeśli istnieje, tylko jeśli C% A = 0 i B jest największą liczbą, która spełnia B≤C i C% B = 0 i (CB- (A-1))% (B-1) = 0, gdzie C to dywidenda, A to dzielnik, a B to iloraz. (Podobny algorytm można zastosować w przypadku, gdy A ≥B, a jeśli nie wiadomo, jak A porównuje się do B, wystarczy jeden dodatkowy test podzielności.)
Uwielbiam więc to, że problem mógł zostać zredukowany do jeszcze mniejszej złożoności niż mój zoptymalizowany golfowo regex Fibonacciego , ale wzdycham z rozczarowaniem, że moja technika multipleksowania mocy tej samej bazy będzie musiała poczekać na inny problem to faktycznie tego wymaga, ponieważ ten nie. To historia mojego algorytmu mnożenia 651 bajtów, który został zastąpiony przez 50-bajtowy!
Edycja: Udało mi się upuścić 1 bajt (119 → 118), używając sztuczki znalezionej przez Grimy'ego, która może dodatkowo skrócić podział w przypadku, gdy iloraz gwarantowany jest większy lub równy dzielnikowi.
Bez zbędnych ceregieli, oto regex:
Wersja prawda / fałsz (118 bajtów):
^((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\3$|^xx?$
Wypróbuj online!
Zwraca odwrotną silnię lub brak dopasowania (124 bajty):
^(?=((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\3$)\3|^xx?$
Wypróbuj online!
Zwraca odwrotną silnię lub brak dopasowania w ECMAScript +\K (120 bajtów):
^((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\K\3$|^xx?$
I wersja z odstępami z komentarzami:
^
(?= # Remove this lookahead and the \3 following it, while
# preserving its contents unchanged, to get a 119 byte
# regex that only returns match / no-match.
((x*)x*)(?=\1$) # Assert that tail is even; \1 = tail / 2;
# \2 = (conjectured N for which tail == N!)-3; tail = \1
(?=(xxx\2)+$) # \3 = \2+3 == N; Assert that tail is divisible by \3
# The loop is seeded: X = \1; I = 3; tail = X + I-3
(
(?=\2\3*(x(?!\3)xx(x*))) # \5 = I; \6 = I-3; Assert that \5 <= \3
\6 # tail = X
(?=\5+$) # Assert that tail is divisible by \5
(?=
( # \7 = tail / \5
(x*) # \8 = \7-1
(?=\5(\8*$)) # \9 = tool for making tail = \5\8
x
)
\7*$
)
x\9 # Prepare the next iteration of the loop: X = \7; I += 1;
# tail = X + I-3
(?=x\6\3+$) # Assert that \7 is divisible by \3
)*
\2\3$
)
\3 # Return N, the inverse factorial, as a match
|
^xx?$ # Match 1 and 2, which the main algorithm can't handle
Pełna historia moich optymalizacji golfowych tych wyrażeń regularnych znajduje się na github:
regex dla dopasowania liczb silniowych - metoda porównywania wielokrotności, z molekularnym lookahead.txt
regex dla dopasowania silni liczb.txt (ta pokazana powyżej)
((x*)x*)((x*)+)((x+)+)n=3!\23−3=0
Mechanizm wyrażeń regularnych .NET nie emuluje tego zachowania w trybie ECMAScript, a zatem 117 wyrażeń regularnych działa:
Wypróbuj online! (wersja spowolnienia wykładniczego z silnikiem regex .NET + emulacja ECMAScript)
1?