Dziwne uporządkowanie Sharkovskiego

33

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
Zgarb
źródło

Odpowiedzi:

6

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.

Neil
źródło
Miły. Nie myślałem o użyciu rekurencji tutaj. Czy a&1|~b&1&f(a/2,b/2)zadziała?
Arnauld,
@Arnauld Nie jestem pewien, martwiłem się, że zapętli się w nieskończoność.
Neil,
Nie może, bo w b<2koń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.
Arnauld,
@Arnauld Ah, prawda, nie używałem b<2pierwotnie, ale myślę, że teraz będzie działać.
Neil,
@Arnauld Jeszcze lepiej, ponieważ f(a/2,b/2)zwraca tylko 0, 1, falselub true, nawet nie potrzebne &1.
Neil,
5

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]
orlp
źródło
5

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.

xnor
źródło
Nie jest cmp(...)<=0równoważne z cmp(...)<1?
matmandan
@mathmandan Tak :)
xnor
Myślę, że dozwolone jest przyjmowanie liczb całkowitych w odwrotnej kolejności i używanie ~zamiast<1
Mitch Schwartz
4

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

Arnauld
źródło
Możesz wyjąć wsporniki dookoła i wewnątrz b>a||(b==a&&y>=x), nie będzie miało to wpływu na wykonanie.
XavCo7,
@ XavCo7 Usunięcie nawiasów wewnątrz, ale nie dookoła jest w porządku. Wszystkie istniejące przypadki testowe nadal przejdą [1, 5]pomyślnie , ale dane wejściowe, które zostałyby błędnie zidentyfikowane jako prawdziwe.
Arnauld,
1
@Arnauld Dodam to jako nowy przypadek testowy na przyszłość.
Zgarb,
3

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.

smls
źródło
2

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.

orlp
źródło
Wydaje się, że to psuje niektóre przypadki testowe. Mówi, że f(158,158)jest fałszywy i f(2,8)jest prawdziwy.
xnor
@xnor Ups, należy teraz naprawić.
lub
To mówi, że f(1,5)to fałsz.
xnor
Moi źli, miałem na myśli, że to f(1,5)powinno być False, ale kod podaje True.
xnor
@ xnor Ah, zauważyłem błąd, naprawiony teraz (na szczęście mam nadzieję). Trochę za luźno podążałem za opisem Neila.
lub
1

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.

Greg Martin
źródło
0

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!

wada
źródło
0

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))
Kluski 9
źródło
Możesz zagrać w golfa, usuwając niepotrzebne spacje: na przykład w (a, b)drugiej linii, w której możesz usunąć spację między przecinkiem a b.
Kritixi Lithos
0

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.

Bubbler
źródło