Dopasuj ciągi, których długość stanowi czwartą potęgę

W ramach tego pytania rozważmy tylko ciągi znaków, które składają się ze znaku xpowtarzanego dowolną liczbę razy.

Na przykład:

<empty>
x
xx
xxxxxxxxxxxxxxxx

^{(Cóż, tak naprawdę nie musi tak być x- każdy znak jest w porządku, o ile cały łańcuch ma tylko 1 typ znaku)}

Napisz regex w dowolnym smaku regex, aby dopasować wszystkie ciągi, których długość wynosi n ⁴ dla niektórych nieujemnych liczb całkowitych n (n> = 0). Na przykład ciągi o długości 0, 1, 16, 81 itd. Są poprawne; reszta jest nieprawidłowa.

^{Ze względu na ograniczenia techniczne trudno jest przetestować wartości n większe niż 128. Jednak wyrażenie regularne powinno logicznie działać poprawnie niezależnie od tego.}

Zauważ, że nie możesz wykonywać dowolnego kodu w wyrażeniu regularnym (dla użytkowników Perla). Każda inna składnia (rozglądanie się, odwołanie do tyłu itp.) Jest dozwolona.

Dołącz także krótkie wyjaśnienie swojego podejścia do problemu.

^{(Proszę nie wklejać automatycznie generowanego wyjaśnienia składni wyrażenia regularnego, ponieważ są one bezużyteczne)}

To (ir) wyrażenie regularne wydaje się działać.

^((?(1)((?(2)\2((?(3)\3((?(4)\4x{24}|x{60}))|x{50}))|x{15}))|x))*$

Ten wyrażenie regularne jest kompatybilne ze smakami PCRE, Perl, .NET.

Zasadniczo wynika to z „drzewa różnic” (nie jestem pewien, czy jest dla niego odpowiednia nazwa), który mówi regexowi, ile więcej xów ma pasować do następnej czwartej potęgi:

1     16    81    256   625   1296  2401 ...
   15    65    175   369   671   1105 ...
      50    110   194   302   434 ...
         60    84    108   132 ...
            24    24    24 ...  # the differences level out to 24 on the 4th iteration

\2, \3, \4Przechowuje i aktualizuje różnica jak pokazano na 2., 3. i 4. rzędach, odpowiednio.

Konstrukcję tę można łatwo rozbudować o większe moce.

Z pewnością nie jest to eleganckie rozwiązanie, ale działa.

Inne rozwiązanie

To, moim zdaniem, jeden z najciekawszych problemów na stronie. Muszę podziękować deadcode za podbicie go z powrotem na samą górę.

^((^|xx)(^|\3\4\4)(^|\4x{12})(^x|\1))*$

39 bajtów , bez żadnych warunków i zapewnień ... w pewnym sensie. Alternacje, w miarę ich wykorzystywania ( ^|), są rodzajem warunkowego sposobu wyboru między „pierwszą iteracją” a „nie pierwszą iteracją”.

Ten regex można zobaczyć tutaj: http://regex101.com/r/qA5pK3/1

Zarówno PCRE, jak i Python poprawnie interpretują wyrażenie regularne, a także zostało przetestowane w Perlu do n = 128 , w tym n ⁴ -1 i n ⁴ +1 .

Definicje

Ogólna technika jest taka sama jak w przypadku innych rozwiązań już umieszczone: określenia ekspresji odniesienie lokalne, które przy każdej kolejnej iteracji odpowiada długości równej następnego okresu przedniej funkcji różnicy D _f , z nieograniczonym kwantyfikator ( *). Formalna definicja funkcji różnicy w przód:

Dodatkowo można również zdefiniować funkcje różnic wyższych rzędów:

Lub bardziej ogólnie:

Funkcja różnicy w przód ma wiele interesujących właściwości; chodzi o sekwencjonowanie pochodnej funkcji ciągłych. Na przykład, D _C O mocy n p Wielomian stopnia zawsze będzie N-1 p Wielomian stopnia, a dla każdej I , jeśli D _f ^I = D, _F ^{i + 1} , wtedy funkcja f jest wykładniczy, w taki sam sposób, że pochodna e ^x jest sobie równa. Najprostsza funkcja dyskretna, dla której f = D _f wynosi 2 ⁿ .

f (n) = n ²

Zanim przeanalizujemy powyższe rozwiązanie, zacznijmy od czegoś nieco łatwiejszego: wyrażenia regularnego, które pasuje do ciągów, których długości są idealnym kwadratem. Analiza funkcji różnicy naprzód:

Oznacza to, że pierwsza iteracja powinna pasować do ciągu o długości 1 , drugi ciąg o długości 3 , trzeci ciąg o długości 5 itd. I ogólnie każda iteracja powinna pasować do ciągu o dwa dłuższe niż poprzednie. Odpowiednie wyrażenie regularne wynika prawie bezpośrednio z tego oświadczenia:

^(^x|\1xx)*$

Można zauważyć, że pierwsza iteracja będzie pasować tylko do jednej x, a każda kolejna iteracja będzie pasowała do ciągu dwóch dłuższych niż poprzednie, dokładnie tak, jak określono. Oznacza to również niezwykle krótki idealny test kwadratowy w perlu:

(1x$_)=~/^(^1|11\1)*$/

Wyrażenie regularne może być dalej uogólnione, aby pasowało do dowolnej n -gonal długości:

Liczby trójkątne:
^(^x|\1x{1})*$

Liczby kwadratowe:
^(^x|\1x{2})*$

Liczby pięciokątne:
^(^x|\1x{3})*$

Liczby sześciokątne:
^(^x|\1x{4})*$

itp.

f (n) = n ³

Przechodząc do n ³ , jeszcze raz analizując funkcję różnicy naprzód:

Może nie być od razu widoczne, jak to zaimplementować, dlatego badamy również drugą funkcję różnicy:

Tak więc funkcja różnicy do przodu nie zwiększa się o stałą, ale raczej o wartość liniową. Fajnie, że początkowa („ -1 ”) wartość D _f ² wynosi zero, co oszczędza inicjalizację przy drugiej iteracji. Wynikowe wyrażenie regularne jest następujące:

^((^|\2x{6})(^x|\1))*$

Pierwsza iteracja będzie pasować do 1 , tak jak poprzednio, druga będzie pasować do ciągu 6 dłuższych ( 7 ), trzecia będzie pasowała do ciągu 12 dłuższych ( 19 ) itp.

f (n) = n ⁴

Funkcja różnicy w przód dla n ⁴ :

Druga funkcja różnicy w przód:

Trzecia funkcja różnicy w przód:

To brzydkie. Początkowe wartości D _f ² i D _f ³ są niezerowe, odpowiednio 2 i 12 , co należy uwzględnić. Prawdopodobnie już zorientowałeś się, że wyrażenie regularne będzie zgodne z następującym wzorcem:

^((^|\2\3{b})(^|\3x{a})(^x|\1))*$

Ponieważ D _f ³ podczas drugiej iteracji musi mieć długość 12 , a to koniecznie 12 . Ponieważ jednak zwiększa się o 24 w każdym członie, kolejne głębsze zagnieżdżenie musi dwukrotnie użyć poprzedniej wartości, co oznacza b = 2 . Ostatnią rzeczą do zrobienia jest zainicjowanie D _f ² . Ponieważ D _f ² wpływa bezpośrednio na D _f , co ostatecznie chcemy dopasować, jego wartość można zainicjować, wstawiając odpowiedni atom bezpośrednio do wyrażenia regularnego, w tym przypadku (^|xx). Ostateczne wyrażenie regularne staje się wtedy:

^((^|xx)(^|\3\4{2})(^|\4x{12})(^x|\1))*$

Wyższe zamówienia

Wielomian piątego rzędu można dopasować za pomocą następującego wyrażenia regularnego:
^((^|\2\3{c})(^|\3\4{b})(^|\4x{a})(^x|\1))*$

f (n) = n ⁵ jest dość łatwym ćwiczeniem, ponieważ początkowe wartości zarówno dla drugiej, jak i czwartej funkcji różnicy w przód wynoszą zero:

^((^|\2\3)(^|\3\4{4})(^|\4x{30})(^x|\1))*$

Dla wielomianów sześciu rzędów:
^((^|\2\3{d})(^|\3\4{c})(^|\4\5{b})(^|\5x{a})(^x|\1))*$

W przypadku wielomianów siódmego rzędu:
^((^|\2\3{e})(^|\3\4{d})(^|\4\5{c})(^|\5\6{b})(^|\6x{a})(^x|\1))*$

itp.

Zauważ, że nie wszystkie wielomiany można dopasować dokładnie w ten sposób, jeśli którykolwiek z niezbędnych współczynników nie jest liczbą całkowitą. Na przykład n ⁶ wymaga, aby a = 60 , b = 8 , a c = 3/2 . Można to obejść, w tym przypadku:

^((^|xx)(^|\3\6\7{2})(^|\4\5)(^|\5\6{2})(^|\6\7{6})(^|\7x{60})(^x|\1))*$

Tutaj zmieniłem b na 6 , a c na 2 , które mają ten sam produkt, co wyżej podane wartości. Ważne jest, aby produkt się nie zmieniał, ponieważ · b · c ·… kontroluje funkcję stałej różnicy, która dla wielomianu szóstego rzędu to D _f ⁶ . Obecne są dwa atomy inicjujące: jeden do inicjalizacji D _f do 2 , jak w przypadku n ⁴ , a drugi do inicjalizacji funkcji piątej różnicy do 360 , przy jednoczesnym dodaniu brakujących dwóch z b .

Oto rozwiązanie, które nie wykorzystuje warunkowych, zadeklarowanych do przodu lub zagnieżdżonych odwołań wstecznych, lookbehind, równoważenia grup ani rekursji wyrażeń regularnych. Używa tylko wstecznego i standardowych odwołań wstecznych, które są bardzo szeroko obsługiwane. Zainspirowałem się do działania w tych granicach dzięki Regex Golf , który wykorzystuje silnik regex ECMAScript.

Sposób działania tego 50-bajtowego wyrażenia regularnego jest koncepcyjnie raczej prosty i zupełnie inny niż wszystkie inne przedstawione rozwiązania tej układanki. Zaskakujące było odkrycie, że tego rodzaju logika matematyczna była wyrażona w wyrażeniu regularnym.

      \2                     \4  \5
^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+)$)\5){4})*x?$

(Grupy przechwytywania są oznaczone powyżej wyrażenia regularnego)

Regex może być uogólnione do dowolnej mocy po prostu przez zastąpienie 4in {4}o pożądanej mocy.

Wypróbuj online!

Działa poprzez wielokrotne dzielenie najmniejszej czwartej potęgi liczby pierwszej, przez którą można podzielić bieżącą wartość. W związku z tym iloraz na każdym kroku jest zawsze czwartą potęgą, jeśli pierwotna wartość była czwartą potęgą. Końcowy iloraz 1 wskazuje, że pierwotna wartość była rzeczywiście czwartą potęgą; to kończy dopasowanie. Zero jest również dopasowane.

Najpierw używa leniwej grupy przechwytywania, \2aby uchwycić najmniejszy czynnik liczby większy niż 1. W związku z tym gwarantuje się, że czynnik ten jest liczbą pierwszą. Na przykład przy 1296 (6 ^ 4) początkowo przechwyci \2= 2.

Następnie na początku powtarzanej 4 razy pętli sprawdza, czy bieżąca liczba jest podzielna przez \2, za pomocą (?=\2+$). Test ten po raz pierwszy jest bezużyteczny, ale jego cel stanie się widoczny później.

Następny wewnątrz tej pętli wewnętrznej, używa chciwy grupę przechwytywania \4uchwycić number największy współczynnik mniejszy niż on sam: (?=(x+)(\4+)$). W efekcie dzieli to liczbę przez jej najmniejszy czynnik pierwszy \2; na przykład 1296 zostanie początkowo przechwycone jako \4= 1296/2 = 648. Zauważ, że podział bieżącej liczby przez \2jest niejawny. Chociaż możliwe jest wyraźne podzielenie bieżącej liczby przez liczbę zawartą w grupie przechwytywania (którą odkryłem dopiero cztery dni po opublikowaniu tej odpowiedzi), zrobienie tego spowodowałoby wolniejsze i trudniejsze do zrozumienia wyrażenie regularne, i nie jest to konieczne, ponieważ najmniejszy współczynnik liczby większy niż 1 zawsze będzie pasował do jego największego współczynnika mniejszego niż on sam (tak, że ich iloczyn jest równy samej liczbie).

Ponieważ ten rodzaj wyrażenia regularnego może „pożreć” ciąg (zmniejszając go), pozostawiając wynik na końcu łańcucha, musimy „przenieść” wynik podziału na koniec łańcucha. Odbywa się to poprzez przechwycenie wyniku odejmowania (bieżąca liczba minus \4), do grupy przechwytywania \5, a następnie poza spojrzeniem, dopasowanie części początku bieżącej liczby odpowiadającej \5. Pozostawia to nieprzetworzony ciąg na końcu o dopasowanej \4długości.

Teraz pętla wraca do początku wewnętrznej pętli, gdzie staje się jasne, dlaczego istnieje test podzielności przez czynnik pierwszy. Właśnie podzieliliśmy przez najmniejszą liczbę pierwszą liczby; jeśli liczba jest nadal podzielna przez ten współczynnik, oznacza to, że pierwotna liczba może być podzielna przez czwartą potęgę tego współczynnika. Przy pierwszym wykonaniu tego testu jest on bezużyteczny, ale kolejne 3 razy określa, czy wynik niejawnego dzielenia przez \2jest nadal podzielny przez \2. Jeśli nadal jest podzielna przez \2na początku każdej iteracji pętli, oznacza to, że każda iteracja dzieli liczbę przez \2.

W naszym przykładzie z wejściem 1296 nastąpi pętla w następujący sposób:

\2= 2
\4= 1296/2 = 648
\4= 648/2 = 324
\4= 324/2 = 162
\4= 162/2 = 81

Teraz wyrażenie regularne może powrócić do pierwszego kroku; to właśnie *robi finał . W tym przykładzie 81 stanie się nowym numerem; następna pętla przebiegnie w następujący sposób:

\2= 3
\4= 81/3 = 27
\4= 27/3 = 9
\4= 9/3 = 3
\4= 3/3 = 1

Powróci teraz ponownie do pierwszego kroku, z 1 jako nowym numerem.

Liczby 1 nie można podzielić przez żadną liczbę pierwszą, przez co byłaby niepasująca (?=(xx+?)\2+$), więc wychodzi ona z pętli najwyższego poziomu (tej z *końcem). Teraz osiąga x?$. Może to być tylko zero lub jeden. Obecna liczba w tym punkcie będzie wynosić 0 lub 1 tylko wtedy, gdy pierwotna liczba była doskonałą czwartą potęgą; jeśli w tym momencie jest 0, oznacza to, że pętla najwyższego poziomu nigdy niczego nie pasowała, a jeśli jest 1, oznacza to, że pętla najwyższego poziomu dzieliła idealną czwartą moc w dół, dopóki nie była już przez nic podzielna (lub było 1 w pierwszej kolejności, co oznacza, że ​​pętla najwyższego poziomu nigdy niczego nie pasowała).

Możliwe jest również rozwiązanie tego w 49 bajtach przez powtarzanie jawnego podziału (który jest również uogólniony dla wszystkich mocy - zamień pożądaną moc minus jeden na {3}), ale ta metoda jest znacznie wolniejsza i objaśnia algorytm, którego używa wykracza poza zakres tej odpowiedzi:

^((x+)((\2(x+))(?=(\4*)\2*$)\4*(?=\5$\6)){3})?x?$

Wypróbuj online!

Rozwiązanie

^(?:(?=(^|(?<=^x)x|xx\1))(?=(^|\1\2))(^x|\3\2{12}xx))*$

Ten wyrażenie regularne jest kompatybilne ze smakami Java, Perl, PCRE i .NET. Ten regex wykorzystuje całkiem szeroki zakres funkcji: spojrzenie w przyszłość, spojrzenie w przeszłość i zadeklarowane wstecz referencje. Deklarowane z wyprzedzeniem rodzaje referencji ograniczają kompatybilność tego wyrażenia regularnego z kilkoma silnikami.

Wyjaśnienie

To rozwiązanie wykorzystuje następującą pochodną.

Poprzez pełne rozszerzenie sumowania możemy udowodnić następującą równość:

Połączmy sumę po lewej stronie:

Odejmij 2 równania (równanie górne minus równanie dolne), a następnie połącz sumy po lewej stronie, a następnie uprość:

Różnicę między kolejnymi czwartymi potęgami uzyskujemy jako sumę mocy:

Oznacza to, że różnica między kolejnymi czwartymi potęgami wzrośnie o (12n ² + 2).

Aby ułatwić myślenie, odwołując się do drzewa różnic w odpowiedzi Zmienności :

• Prawa strona końcowego równania jest drugim rzędem w drzewie różnic.
• Przyrost (12n ² + 2) jest trzecim rzędem w drzewie różnic.

Dosyć matematyki. Powrót do powyższego rozwiązania:

• Pierwsza grupa przechwytująca utrzymuje serię liczb nieparzystych, aby obliczyć i ^2, jak widać w równaniu.

  Dokładnie mówiąc, długość 1. grupy przechwytywania będzie wynosić 0 (nieużywane), 1, 3, 5, 7, ... podczas iteracji pętli.

  (?<=^x)xustawia wartość początkową dla serii liczb nieparzystych. ^Jest właśnie tam, aby umożliwić spojrzenie wyprzedzeniem jakie muszą być spełnione w pierwszej iteracji.

  xx\1 dodaje 2 i przechodzi do następnej liczby nieparzystej.

• Druga grupa przechwytująca utrzymuje serię liczb kwadratowych dla i ² .

  Dokładnie mówiąc, długość drugiej grupy przechwytywania będzie wynosić 0, 1, 4, 9, ... podczas iteracji pętli.

  ^in (^|\1\2)ustawia wartość początkową szeregu liczb kwadratowych. I \1\2dodaje nieparzystą liczbę do bieżącego numeru kwadratu, aby przejść do następnego numeru kwadratu.

• Trzecia grupa przechwytywania (poza wszelkim wyprzedzeniem i faktycznie zużywa tekst) pasuje do całej prawej strony równania, które wyprowadziliśmy powyżej.

  ^xin (^x|\3\2{12}xx)ustawia wartość początkową, która jest + 1prawą stroną równania.

  \3\2{12}xxdodaje wzrost różnicy (12n ² + 2) przy użyciu n ² z grupy przechwytywania 2 i dopasowuje różnicę w tym samym czasie.

Takie ustawienie jest możliwe, ponieważ ilość tekstu dopasowanego w każdej iteracji jest większa lub równa ilości tekstu potrzebnego do wykonania przewidywania w celu skonstruowania n ² .