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

JavaScript (ES6), 53 49 bajtów

f=(a,b)=>b<2||a>1&&(a&b&1?a<=b:a&1|~b&f(a/2,b/2))

Wyjaśnienie:

• Jeśli b wynosi 1, to a poprzedza (lub równa się) b
• W przeciwnym razie, jeśli a wynosi 1, to a nie poprzedza b
• W przeciwnym razie, jeśli zarówno aib są nieparzyste, użyj regularnej kontroli nierówności
• W przeciwnym razie, jeśli a jest nieparzyste, poprzedza b
• W przeciwnym razie, jeśli b jest nieparzyste, to a nie poprzedza b
• W przeciwnym razie podziel aib przez 2 i spróbuj ponownie.

Edycja: Zapisano 2 bajty dzięki @Arnauld.

Python 2, 87 71 bajtów

k=lambda n:[n&~-n<1,(n&-n)*cmp(n&~-n,1),n/(n&-n)]
lambda a,b:k(a)<=k(b)

Prawdopodobnie 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 :

[n == 0, p * (1 - 2*(n == 0)), n]

Python 2, 50 bajtów

lambda*l:cmp(*[([-n][n&n-1:],n&-n,n)for n in l])<1

Każda liczba jest odwzorowana na potrójną, której posortowana kolejność jest pożądaną kolejnością.

• Podstawową wartością jest [-n][n&n-1:], która obsługuje moce 2 na końcu. Bitowe „i” n&n-1wynosi zero dokładnie wtedy, gdy njest 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.
• Wartość wtórna n&-nwyodrębnia współczynnik mocy 2 wynoszący n.
• Ostateczna wartość nrozstrzygnięć równa potęgi 2 na korzyść większej liczby.

Odpowiednie krotki są przekazywane, cmpaby sprawdzić, czy to porównanie jest <=0. Python 3 zapisałby bajt z dzieleniem zmiennoprzecinkowym (n&n-1<1)/ndla pierwszej wartości w potrójnym, ale brakuje cmp.

JavaScript (ES6), 70 64 bajtów

Prawdopodobnie można by jeszcze zagrać w golfa, ale jako pierwsza próba:

x=>y=>(a=x&-x,x/=a,b=y&-y,y/=b,y<2?x>1|b<=a:x>1&(b>a|b==a&y>=x))

Pobiera dane wejściowe ze składnią curry (x)(y). Zwraca 0/ 1.

Przypadki testowe

let f =

x=>y=>(a=x&-x,x/=a,b=y&-y,y/=b,y<2?x>1|b<=a:x>1&(b>a|b==a&y>=x))

console.log('Testing truthy instances ...');
console.log(f(3)(11));
console.log(f(9)(6));
console.log(f(48)(112));
console.log(f(49)(112));
console.log(f(158)(158));
console.log(f(36)(24));
console.log(f(14)(28));
console.log(f(144)(32));
console.log(f(32)(32));
console.log(f(32)(8));
console.log(f(3)(1));
console.log(f(1)(1));

console.log('Testing falsy instances ...');
console.log(f(1)(2));
console.log(f(1)(5));
console.log(f(11)(5));
console.log(f(20)(25));
console.log(f(2)(8));
console.log(f(256)(255));
console.log(f(256)(257));
console.log(f(72)(52));
console.log(f(2176)(1216));
console.log(f(2176)(2496));

Perl 6 , 89 84 bajtów

->\a,\b{my \u=*>max a,b;a==first a|b,flat [1,2,4...u].&{(3*$_,5*$_...u for $_),.reverse}}

{my \u=*>@_.max;@_[0]==first @_.any,flat [1,2,4...u].&{.map(*X*(3,5...u)),.reverse}}

( 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 2, 3generuje:

  3 5
  6
  12
  4 2 1

  ... a potem zauważa, że 3pojawia się wcześniej 2.

• Dla danych wejściowych 9, 6generuje:

  3 5 7 9 11
  6 10
  12
  24
  48
  16 8 4 2 1

  ... a potem zauważa, że 9pojawia się wcześniej 6.

Może być mądrzejszy i generować jeszcze mniej sekwencji, ale wymagałoby to więcej bajtów kodu.

Python 2, 54 bajty

f=lambda a,b:b<2or[f(a/2,b/2),a>1,0,1<a<=b][a%2+b%2*2]

Rozwiązanie rekurencyjne podobne do rozwiązania Neila.

Mathematica, 65 bajtów

OrderedQ[{1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}/.{a_,1}->{∞,-a}]&

Bezimienna funkcja pobierająca listę dodatnich liczb całkowitych i zwracająca, Truejeśli lista tworzy rosnącą sekwencję w kolejności Sharkovskiego, w Falseprzeciwnym 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^kz mnieparzystą w uporządkowaną parę {2^k,m}(i robi to z każdym elementem listy wejściowej). OrderedQnastę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ę OrderingQstosujemy 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.

Haskell, 143 138 bajtów

Zasadniczo stosunkowo proste wdrożenie kryteriów:

e n=head[k-1|k<-[0..],n`mod`(2^k)>0]   -- exponent of 2
f n=n`div`2^e n                        -- odd part
a#b|n<-f a,p<-e a,m<-f b,q<-e b=n>1&&(m>1&&p<q||n<m&&p==q||m<2)||n<2&&m<2&&p>q||a==b  

Wypróbuj online!

Python, 159 158 153 144 142 141 bajtów

Zapisane 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

f=lambda a,p=0:(a&1)*(a,p)or f(a>>1,p+1)
t=lambda(n,p),(m,q):(n==1)*(m==1)&(p>=q)or (m>1)&(p<=q)|(n<=m)&(p==q)or m==1
lambda a,b:t(f(a),f(b))

APL (Dyalog Extended) , 27 bajtów

1⊃∘⍋⍮⍥{p⍵⍮⍨-⍵⍴⍨⍵=2*p←⊥⍨~⊤⍵}

Wypróbuj online!

Milcząca funkcja dyadyczna, której lewy argument jest aprawy b.

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ą

{p⍵⍮⍨-⍵⍴⍨⍵=2*p←⊥⍨~⊤⍵}  ⍝ Input: positive integer N
                  ⊤⍵   ⍝ Convert N to binary digits
                 ~     ⍝ Flip all the bits (1 to 0, 0 to 1)
             p←⊥⍨      ⍝ Count trailing ones and assign it to p
                       ⍝ (maximum power of 2 that divides N)
         ⍵=2*          ⍝ Test if N itself is equal to 2^p
     -⍵⍴⍨              ⍝ If true, create 1-element array containing -N;
                       ⍝ otherwise, an empty array
 p⍵⍮⍨                  ⍝ Form a 2-element nested array;
                       ⍝ 1st element is the above, 2nd is [p, N]

Część 2: Porównaj dwie tablice zagnieżdżone

1⊃∘⍋⍮⍥f  ⍝ Input: A (left) and B (right)
     ⍥f  ⍝ Evaluate f A and f B
    ⍮    ⍝ Create a 2-element nested array [f A, f B]
   ⍋     ⍝ Grade up; indexes of array elements to make it sorted
         ⍝ Here, the result is [0 1] if A ≤ B, [1 0] otherwise
1⊃∘      ⍝ Take the element at index 1 (0-based)

Składnia dfn obsługuje instrukcje warunkowe, np. {a:x ⋄ b:y ⋄ z}Znaczenie if a then x else if b then y else z, ale w tym przypadku jest zbyt szczegółowa.

05AB1E , 14 bajtów

ΣxÓs1ǝzDg≠i(]Q

Wypróbuj online! lub sprawdź poprawność wszystkich przypadków testowych .