Wprowadzenie
W tym wyzwaniu będziemy mieli do czynienia z pewną kolejnością liczb całkowitych dodatnich. Kolejność wygląda następująco:
3, 5, 7, 9, 11, ...
2*3, 2*5, 2*7, 2*9, 2*11, ...
4*3, 4*5, 4*7, 4*9, 4*11, ...
8*3, 8*5, 8*7, 8*9, 8*11, ...
16*3, 16*5, 16*7, 16*9, 16*11, ...
...
... 64, 32, 16, 8, 4, 2, 1
Najpierw podajemy wszystkie nieparzyste liczby całkowite większe niż 1 w porządku rosnącym. Następnie podajemy dwa razy nieparzyste liczby całkowite większe niż 1, następnie 4 razy, następnie 8 razy i tak dalej: dla wszystkich k podajemy 2 k nieparzyste liczby całkowite większe niż 1 w porządku rosnącym. Na koniec podajemy potęgę dwóch w porządku malejącym , kończąc na 1. Każda dodatnia liczba całkowita występuje na tej „liście” dokładnie raz.
Mówiąc dokładniej, rozważ dwie różne dodatnie liczby całkowite A = n · 2 p i B = m · 2 q , gdzie n, m ≥ 1 są nieparzyste, a p, q ≥ 0 . Następnie A pojawia się przed B w porządku, jeśli zachodzi jeden z następujących warunków:
- n> 1 , m> 1 i p <q
- 1 <n <m i p = q
- n> m = 1
- n = m = 1, a s> Q
To uporządkowanie pojawia się w zaskakującym wyniku matematycznym znanym jako twierdzenie Sharkovskiego , które dotyczy okresowych punktów układów dynamicznych. Nie będę tu wchodził w szczegóły.
Zadanie
Twoim zadaniem w tym wyzwaniu jest obliczenie powyższej kolejności. Twoje dane wejściowe to dwie dodatnie liczby całkowite A i B , które mogą być równe. Twój wynik jest prawdziwą wartością, jeśli A pojawia się przed B w kolejności, a fałszem w przeciwnym razie. Jeśli A = B , twój wynik powinien być prawdziwy. Możesz wziąć A i B w dowolnej kolejności, o ile jesteś konsekwentny.
Nie musisz się martwić przepełnieniem liczb całkowitych, ale Twój algorytm powinien teoretycznie działać dla dowolnie dużych danych wejściowych.
Przypadki testowe
Prawdziwe przypadki
3 11
9 6
48 112
49 112
158 158
36 24
14 28
144 32
32 32
32 8
3 1
1 1
Instancje Falsy
1 2
1 5
11 5
20 25
2 8
256 255
256 257
72 52
2176 1216
2176 2496
a&1|~b&1&f(a/2,b/2)
zadziała?b<2
końcu będzie prawdą. Kolejnym problemem jest to, że przetworzysz więcej iteracji niż potrzeba i uzyskasz wartości zmiennoprzecinkowe. Ale nie mogę znaleźć żadnego kontrprzykładu, który nie działałby zgodnie z oczekiwaniami.b<2
pierwotnie, ale myślę, że teraz będzie działać.f(a/2,b/2)
zwraca tylko0
,1
,false
lubtrue
, nawet nie potrzebne&1
.Python 2,
8771 bajtówPrawdopodobnie nie zdobędzie to żadnych nagród, ale ta odpowiedź działa przez skonstruowanie 3-krotek przy użyciu 3 wyrażeń z liczby całkowitej, która przy uporządkowaniu leksykograficznym spowoduje prawidłowe uporządkowanie.
W sensie czytelnym krotka jest dla A = n · 2 p :
źródło
Python 2, 50 bajtów
Każda liczba jest odwzorowana na potrójną, której posortowana kolejność jest pożądaną kolejnością.
[-n][n&n-1:]
, która obsługuje moce 2 na końcu. Bitowe „i”n&n-1
wynosi zero dokładnie wtedy, gdyn
jest potęgą2
. Jeśli tak, otrzymujemy listę[-n]
, a w przeciwnym razie pustą listę[]
. To stawia wszystkie potęgi 2 na końcu kolejności, w malejącej kolejności.n&-n
wyodrębnia współczynnik mocy 2 wynoszącyn
.n
rozstrzygnięć równa potęgi 2 na korzyść większej liczby.Odpowiednie krotki są przekazywane,
cmp
aby sprawdzić, czy to porównanie jest<=0
. Python 3 zapisałby bajt z dzieleniem zmiennoprzecinkowym(n&n-1<1)/n
dla pierwszej wartości w potrójnym, ale brakujecmp
.źródło
cmp(...)<=0
równoważne zcmp(...)<1
?~
zamiast<1
JavaScript (ES6),
7064 bajtówPrawdopodobnie można by jeszcze zagrać w golfa, ale jako pierwsza próba:
Pobiera dane wejściowe ze składnią curry
(x)(y)
. Zwraca0
/1
.Przypadki testowe
Pokaż fragment kodu
źródło
b>a||(b==a&&y>=x)
, nie będzie miało to wpływu na wykonanie.[1, 5]
pomyślnie , ale dane wejściowe, które zostałyby błędnie zidentyfikowane jako prawdziwe.Perl 6 ,
8984 bajtów( Wypróbuj online. )
Nie do końca krótkie, ale pomyślałem, że byłoby interesujące napisać rozwiązanie, które faktycznie generuje sekwencję porządkowania (do bezpiecznej górnej granicy dla każdej podsekwencji), a następnie sprawdza, które wejście pojawia się w niej jako pierwsze.
Na przykład:
Dla danych wejściowych
... a potem zauważa, że2, 3
generuje:3
pojawia się wcześniej2
.Dla danych wejściowych
... a potem zauważa, że9, 6
generuje:9
pojawia się wcześniej6
.Może być mądrzejszy i generować jeszcze mniej sekwencji, ale wymagałoby to więcej bajtów kodu.
źródło
Python 2, 54 bajty
Rozwiązanie rekurencyjne podobne do rozwiązania Neila.
źródło
f(158,158)
jest fałszywy if(2,8)
jest prawdziwy.f(1,5)
to fałsz.f(1,5)
powinno być False, ale kod podaje True.Mathematica, 65 bajtów
Bezimienna funkcja pobierająca listę dodatnich liczb całkowitych i zwracająca,
True
jeśli lista tworzy rosnącą sekwencję w kolejności Sharkovskiego, wFalse
przeciwnym razie. (W szczególności lista wejściowa nie musi zawierać tylko dwóch elementów - dodatkowe funkcje otrzymujemy za darmo).Sercem algorytmu jest funkcja
{1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}
, która wielokrotnie przesuwa współczynniki 2 dookoła, aby przekształcić liczbę całkowitąm*2^k
zm
nieparzystą w uporządkowaną parę{2^k,m}
(i robi to z każdym elementem listy wejściowej).OrderedQ
następnie decyduje, czy wynikowa lista uporządkowanych par jest już posortowana; domyślnie oznacza to rosnącą kolejność według pierwszego elementu, a następnie rosnącą kolejność według drugiego elementu.Właśnie tego chcemy, z wyjątkiem liczb, które są potęgami 2, podlegają innym zasadom. Dlatego przed zalogowaniem się
OrderingQ
stosujemy ostatnią regułę/.{a_,1}->{∞,-a}
, która konwertuje (na przykład){64,1}
na{∞,-64}
; co stawia moce 2 we właściwym miejscu w porządku.źródło
Haskell,
143138 bajtówZasadniczo stosunkowo proste wdrożenie kryteriów:
Wypróbuj online!
źródło
Python,
159158153144142141 bajtówZapisane 2 bajty dzięki Kritixi Lithos!
Dotyczy to głównie gry w golfa w moim Pythonie!
Zastosowano formułę podaną przez PO, a nie sposoby wszystkich sprytniejszych odpowiedzi
źródło
(a, b)
drugiej linii, w której możesz usunąć spację między przecinkiem ab
.APL (Dyalog Extended) , 27 bajtów
Wypróbuj online!
Milcząca funkcja dyadyczna, której lewy argument jest
a
prawyb
.Podejście to jest prawie identyczne z rozwiązaniem xnor w Pythonie 2 , ponieważ konwertujemy każdą liczbę na zagnieżdżoną tablicę i dokonujemy porównania leksykograficznego między nimi.
Część 1: Konwertuj liczbę na tablicę zagnieżdżoną
Część 2: Porównaj dwie tablice zagnieżdżone
Składnia dfn obsługuje instrukcje warunkowe, np.
{a:x ⋄ b:y ⋄ z}
Znaczenieif a then x else if b then y else z
, ale w tym przypadku jest zbyt szczegółowa.źródło
05AB1E , 14 bajtów
Wypróbuj online! lub sprawdź poprawność wszystkich przypadków testowych .
źródło