Regex (smak ECMAScript), 392 358 328 224 206 165 bajtów
Techniki, które muszą wejść w grę, aby dopasować liczby Fibonacciego do wyrażenia regularnego ECMAScript (jednostronnie), są dalekie od tego, jak najlepiej to zrobić w większości innych smaków wyrażeń regularnych. Brak odwołań do przodu / zagnieżdżonych wstecz lub rekurencji oznacza, że nie można bezpośrednio policzyć ani zachować bieżącej sumy czegokolwiek. Brak wyglądu sprawia, że często jest to wyzwanie, nawet mając wystarczająco dużo miejsca do pracy.
Do wielu problemów należy podchodzić z zupełnie innej perspektywy i wydają się nierozwiązywalne aż do pojawienia się jakiegoś kluczowego wglądu. Zmusza cię to do rzucenia znacznie szerszej sieci w celu znalezienia, które matematyczne właściwości liczb, z którymi pracujesz, mogą być wykorzystane do rozwiązania konkretnego problemu.
W marcu 2014 r. Stało się tak w przypadku liczb Fibonacciego. Patrząc na stronę Wikipedii, początkowo nie mogłem znaleźć sposobu, chociaż jedna konkretna właściwość wydawała się kusząco blisko. Następnie matematyk teukon nakreślił metodę, która wyraźnie dała do zrozumienia, że można to zrobić, używając tej właściwości razem z inną. Nie chciał skonstruować wyrażenia regularnego. Jego reakcja, kiedy poszedłem naprzód i to zrobiłem:
Jesteś szalony! ... Myślałem, że możesz to zrobić.
Podobnie jak w przypadku moich innych jednoargumentowych wyrażeń regularnych ECMAScript, ostrzeżę : Gorąco 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. Zobacz ten post, aby uzyskać listę 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ę 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.
Wyzwanie, z którym początkowo się zmierzyłem: dodatnia liczba całkowita x jest liczbą Fibonacciego tylko wtedy, gdy 5x 2 + 4 i / lub 5x 2 - 4 to idealny kwadrat. Ale nie ma miejsca na obliczenie tego w wyrażeniu regularnym. Jedyne miejsce, w którym musimy pracować, to sam numer. Nie mamy nawet dość miejsca, aby pomnożyć przez 5 lub wziąć kwadrat, nie mówiąc już o obu.
pomysł teukona na to, jak go rozwiązać ( pierwotnie opublikowany tutaj ):
Wyrażenie regularne jest prezentowane z ciągiem postaci ^x*$, niech z będzie jego długością. Sprawdź, czy z jest jedną z pierwszych kilku liczb Fibonacciego ręcznie (do 21 powinno wystarczyć). Jeżeli nie jest:
- Przeczytaj kilka liczb, a <b, tak aby b nie było większe niż 2a.
- Wykorzystaj prognozy na przyszłość, aby zbudować 2 , ab i b 2 .
- Upewnij się, że 5a 2 + 4 lub 5a 2 - 4 to idealny kwadrat (więc dla niektórych n musi być F n-1 ).
- Upewnij się, że albo 5b 2 + 4, albo 5b 2 + 4 to idealny kwadrat (więc b musi być F n ).
- Sprawdź, czy z = F 2n + 3 lub z = F 2n + 4 , używając wcześniej zbudowanego 2 , ab i b 2 oraz tożsamości:
- F 2n-1 = F n 2 + F n-1 2
- F 2n = (2F n-1 + Fn ) F n
W skrócie: te tożsamości pozwalają nam zmniejszyć problem sprawdzania, czy dana liczba to Fibonacciego, do sprawdzania, czy para znacznie mniejszych liczb to Fibonacciego. Mała algebra pokaże, że dla wystarczająco dużej n (n = 3 powinno wystarczyć), F 2n + 3 > F n + 5F n 2 + 4, więc zawsze powinno być wystarczająco dużo miejsca.
A oto makieta algorytmu w C, który napisałem jako test przed zaimplementowaniem go w regexie.
Więc bez zbędnych ceregieli, oto regex:
^((?=(x*).*(?=x{4}(x{5}(\2{5}))(?=\3*$)\4+$)(|x{4})(?=xx(x*)(\6x?))\5(x(x*))(?=(\8*)\9+$)(?=\8*$\10)\8*(?=(x\2\9+$))(x*)\12)\7\11(\6\11|\12)|x{0,3}|x{5}|x{8}|x{21})$
Wypróbuj online!
I ładnie wydrukowana, skomentowana wersja:
^(
(?=
(x*) # \2+1 = potential number for which 5*(\2+1)^2 ± 4
# is a perfect square; this is true iff \2+1 is a Fibonacci
# number. Outside the surrounding lookahead block, \2+1 is
# guaranteed to be the largest number for which this is true
# such that \2 + 5*(\2+1)^2 + 4 fits into the main number.
.*
(?= # tail = (\2+1) * (\2+1) * 5 + 4
x{4}
( # \3 = (\2+1) * 5
x{5}
(\2{5}) # \4 = \2 * 5
)
(?=\3*$)
\4+$
)
(|x{4}) # \5 = parity - determined by whether the index of Fibonacci
# number \2+1 is odd or even
(?=xx (x*)(\6 x?)) # \6 = arithmetic mean of (\2+1) * (\2+1) * 5 and \8 * \8,
# divided by 2
# \7 = the other half, including remainder
\5
# require that the current tail is a perfect square
(x(x*)) # \8 = potential square root, which will be the square root
# outside the surrounding lookahead; \9 = \8-1
(?=(\8*)\9+$) # \10 = must be zero for \8 to be a valid square root
(?=\8*$\10)
\8*
(?=(x\2\9+$)) # \11 = result of multiplying \8 * (\2+1), where \8 is larger
(x*)\12 # \12 = \11 / 2; the remainder will always be the same as it
# is in \7, because \8 is odd iff \2+1 is odd
)
\7\11
(
\6\11
|
\12
)
|
x{0,3}|x{5}|x{8}|x{21} # The Fibonacci numbers 0, 1, 2, 3, 5, 8, 21 cannot be handled
# by our main algorithm, so match them here; note, as it so
# happens the main algorithm does match 13, so that doesn't
# need to be handled here.
)$
Algorytm mnożenia nie jest wyjaśniony w tych komentarzach, ale jest krótko wyjaśniony w akapicie mojego obfitego numeru wyrażenia regularnego .
Utrzymywałem sześć różnych wersji wyrażenia Fibonacciego: cztery, które zapadają od najkrótszej do największej prędkości i używają algorytmu wyjaśnionego powyżej, oraz dwie inne, które używają innego, znacznie szybszego, ale o wiele dłuższego algorytmu, który, jak się przekonałem, może faktycznie powrócić indeks Fibonacciego jako dopasowanie (objaśnienie tego algorytmu jest poza zakresem tego postu, ale wyjaśniono to w oryginalnej dyskusji Gist ). Nie sądzę, bym zachował tak wiele bardzo podobnych wersji wyrażenia regularnego, ponieważ w tym czasie przeprowadzałem wszystkie testy w PCRE i Perlu, ale mój silnik wyrażeń regularnych jest wystarczająco szybki, aby obawy o szybkość nie były już tak ważne (a jeśli konkretny konstrukt powoduje wąskie gardło, mogę dodać dla niego optymalizację) - choć prawdopodobnie ponownie utrzymałbym jedną najszybszą wersję i jedną najkrótszą wersję, jeśli różnica w prędkości były wystarczająco duże.
Wersja „zwraca indeks Fibonacciego minus 1 jako dopasowanie” (niezbyt mocno golfa):
Wypróbuj online!
Wszystkie wersje są na github z pełną historią zatwierdzeń optymalizacji golfa:
regex do dopasowania liczb Fibonacciego - krótkie, prędkość 0.txt (najkrótszą ale najwolniejszy jeden, jak w tym poście)
regex do dopasowania liczb Fibonacciego - krótkie, prędkość 1.txt
regex do dopasowania liczb Fibonacciego - krótki, prędkość 2.txt
regex dopasowania liczby Fibonacciego - krótki, prędkość 3.txt
regex do dopasowania liczb Fibonacciego - fastest.txt
regex do dopasowania liczb Fibonacciego - powrót index.txt
