Regex (smak PCRE), 66 (65🐌) bajtów
Zainspirowany widząc, że zarówno Martin Ender, jak i jaytea , dwaj geniusze wyrażeń regularnych, napisali regexowe rozwiązania dla tego kodu golfa, napisałem własne od zera. Słynny regex sprawdzania liczby pierwszych nie pojawia się nigdzie w moim rozwiązaniu.
Nie czytaj tego, jeśli nie chcesz, aby zepsuta dla ciebie jakaś magia wyrażenia regularnego. Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie zalecamy rozpoczęcie od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript:
- Dopasuj liczby pierwsze (jeśli jeszcze nie wiesz, jak to zrobić w wyrażeniach regularnych)
- Dopasuj moce 2 (jeśli jeszcze tego nie zrobiłeś). Lub po prostu przebij się przez Regex Golf , który obejmuje Prime i Powers. Pamiętaj, aby wykonać zarówno zestawy problemów Classic, jak i Teukon.
Znajdź najkrótszy sposób dopasowania mocy N, gdzie N jest pewną stałą (tzn. Określoną w wyrażeniu regularnym, a nie wejściowym), która może być złożona (ale nie jest wymagana). Na przykład dopasuj moc 6.
Znajdź sposób dopasowania N-tych mocy, gdzie N jest pewną stałą> = 2. Na przykład dopasuj idealne kwadraty. (W celu rozgrzewki dopasuj główne moce .)
Dopasuj prawidłowe instrukcje mnożenia. Dopasuj liczby trójkątne.
Dopasuj liczby Fibonacciego (jeśli jesteś tak szalony jak ja), lub jeśli chcesz trzymać się czegoś krótszego, dopasuj poprawne stwierdzenia potęgowania (dla rozgrzewki, wróć jako logarytm do podstawy 2 potęgi 2 - bonus, zrób to samo dla dowolnej liczby, zaokrąglając ją, jak chcesz) lub liczb silni (dla rozgrzewki, dopasuj liczby pierwotne ).
Dopasuj obfite liczby (jeśli jesteś tak szalony jak ja)
Oblicz liczbę niewymierną do żądanej precyzji (np. Podziel dane wejściowe przez pierwiastek kwadratowy z 2, zwracając zaokrąglony wynik jako dopasowanie)
(Silnik wyrażeń regularnych, który napisałem, może być pomocny, ponieważ jest bardzo szybki przy jednoargumentowych wyrażeniach matematycznych i zawiera jednoargumentowy tryb liczbowy, który może testować zakresy liczb naturalnych (ale także ma tryb ciągów znaków, który może oceniać wyrażenia jednoargumentowe lub jednoargumentowy z ogranicznikami). Domyślnie jest kompatybilny z ECMAScript, ale ma opcjonalne rozszerzenia (które mogą selektywnie dodawać podzbiory PCRE, a nawet molekularne spojrzenie w przód, coś, czego nie ma żaden inny silnik wyrażenia regularnego).
W przeciwnym razie czytaj dalej, a także czytaj GistHub Gist (ostrzeżenie, wiele spoilerów), który kronika podróży wypychania wyrażenia regularnego ECMAScript w celu rozwiązania problemów z liczbami naturalnymi o rosnącym stopniu trudności (poczynając od zestawu łamigłówek Teukona, nie wszystkich matematycznych, które wywołały ten problem podróż).
Podobnie jak w przypadku innych regexowych rozwiązań tego problemu, dane wejściowe są podawane jako dwie liczby w jednostajnym bijective, oddzielone przecinkiem, reprezentujące zakres obejmujący. Zwracany jest tylko jeden numer. Wyrażenie regularne można zmodyfikować, aby zwracać wszystkie liczby, które dzielą ten sam najmniejszy największy czynnik główny, jako osobne dopasowania, ale wymagałoby to spojrzenia o zmiennej długości i umieszczenia go \Kw przód lub zwrócenia wyniku jako przechwytywania zamiast dopasowania.
Zastosowana tutaj technika wielokrotnego niejawnego dzielenia przez najmniejszy czynnik pierwszy jest identyczna z tą stosowaną w ciągach Match, których długość jest czwartą odpowiedzią na moc, którą zamieściłem jakiś czas temu.
Bez zbędnych ceregieli:
((.+).*),(?!.*(?=\1)(((?=(..+)(\5+$))\6)*)(?!\2)).*(?=\1)\K(?3)\2$
Możesz to wypróbować tutaj.
I wersja z wolnym odstępem, z komentarzami:
# No ^ anchor needed, because this algorithm always returns a
# match for valid input (in which the first number is less than
# or equal to the second number), and even in /g mode only one
# match can be returned. You can add an anchor to make it reject
# invalid ranges.
((.+).*), # \1 = low end of range; \2 = conjectured number that is the
# smallest number in the set of the largest prime factor of each
# number in the range; note, it is only in subsequent tests that
# this is implicitly confined to being prime.
# We shall do the rest of our work inside the "high end of range"
# number.
(?! # Assert that there is no number in the range whose largest prime
# factor is smaller than \2.
.*(?=\1) # Cycle tail through all numbers in the range, starting with \1.
( # Subroutine (?3):
# Find the largest prime factor of tail, and leave it in tail.
# It will both be evaluated here as-is, and later as an atomic
# subroutine call. As used here, it is not wrapped in an atomic
# group. Thus after the return from group 3, backtracking back
# into it can increase the value of tail – but this won't mess
# with the final result, because only making tail smaller could
# change a non-match into a match.
( # Repeatedly divide tail by its smallest prime factor, leaving
# only the largest prime factor at the end.
(?=(..+)(\5+$)) # \6 = tool to make tail = \5 = largest nontrivial factor of
# current tail, which is implicitly the result of dividing it
# by its smallest prime factor.
\6 # tail = \5
)*
)
(?!\2) # matches iff tail < \ 2
)
# now, pick a number in the range whose largest prime factor is \2
.*(?=\1) # Cycle tail through all numbers in the range, starting with \1.
\K # Set us up to return tail as the match.
(?3) # tail = largest prime factor of tail
\2$ # Match iff tail == \2, then return the number whose largest
# prime factor is \2 as the match.
Algorytm można łatwo przenieść do ECMAScript, zastępując wywołanie podprogramu kopią podprogramu i zwracając dopasowanie jako grupę przechwytywania zamiast używania \ K. Wynik ma długość 80 bajtów:
((x+)x*),(?!.*(?=\1)((?=(xx+)(\4+$))\5)*(?!\2)).*(?=\1)(((?=(xx+)(\8+$))\9)*\2$)
Wypróbuj online!
Zauważ, że ((.+).*)można to zmienić ((.+)+), zmniejszając rozmiar o 1 bajt (z 66 do 65 bajtów ) bez utraty poprawnej funkcjonalności - ale wyrażenie regularne eksploduje wolniej.
Wypróbuj online! (79-bajtowa wersja ECMAScript-spowolnienie wykładnicze)