L'étrange commande de Sharkovskii

35

introduction

Dans ce défi, nous aurons affaire à un certain ordre des entiers positifs. La commande se passe comme ceci:

   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

Nous listons d’abord tous les entiers impairs supérieurs à 1 par ordre croissant. Ensuite, nous listons deux fois les entiers impairs supérieurs à 1, puis 4 fois, puis 8 fois, et ainsi de suite: pour tout k , nous listons 2 k fois les entiers impairs supérieurs à 1 par ordre croissant. Enfin, nous listons les puissances de deux dans l' ordre décroissant , se terminant à 1. Chaque entier positif apparaît dans cette "liste" exactement une fois.

Plus explicitement, considérons deux entiers positifs distincts A = n · 2 p et B = m · 2 q , où n, m ≥ 1 sont impairs et p, q ≥ 0 . Ensuite, A vient avant B dans l'ordre, si l'une des conditions suivantes est remplie:

  • n> 1 , m> 1 et p <q
  • 1 <n <m et p = q
  • n> m = 1
  • n = m = 1 et p> q

Cet ordre apparaît dans le résultat mathématique surprenant connu sous le nom de théorème de Sharkovskii , qui concerne les points périodiques des systèmes dynamiques. Je ne vais pas entrer dans les détails ici.

La tâche

Votre tâche dans ce défi est de calculer la commande ci-dessus. Vos entrées sont deux entiers positifs A et B , qui peuvent être égaux. Votre sortie est une valeur de vérité si A vient avant B dans la commande, et une valeur de fausseté sinon. Si A = B , votre sortie devrait être la vérité. Vous pouvez prendre A et B dans l'un ou l'autre ordre, tant que vous êtes cohérent.

Vous n'avez pas à vous soucier du dépassement d'entier, mais votre algorithme devrait théoriquement fonctionner pour des entrées arbitrairement grandes.

Cas de test

Instances de vérité

3 11
9 6
48 112
49 112
158 158
36 24
14 28
144 32
32 32
32 8
3 1
1 1

Instances de fausseté

1 2
1 5
11 5
20 25
2 8
256 255
256 257
72 52
2176 1216
2176 2496
Zgarb
la source

Réponses:

6

JavaScript (ES6), 53 49 octets

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

Explication:

  • Si b est 1, alors a précède (ou est égal à) b
  • Sinon, si a est 1, alors a ne précède pas b
  • Sinon, si a et b sont tous les deux impairs, utilisez le contrôle régulier des inégalités
  • Sinon, si a est impair, alors il précède b
  • Sinon, si b est impair, alors a ne précède pas b
  • Sinon, divisez a et b par 2 et réessayez.

Edit: 2 octets enregistrés grâce à @Arnauld.

Neil
la source
Agréable. Je n'ai pas pensé à utiliser la récursivité ici. Serait a&1|~b&1&f(a/2,b/2)travailler?
Arnauld
@Arnauld Je ne suis pas sûr, je craignais que cela tourne en boucle indéfiniment.
Neil
Ça ne peut pas parce que ça b<2finira par être vrai. Maintenant, un autre problème est que vous allez traiter plus d'itérations que nécessaire et obtenir des valeurs en virgule flottante. Mais je ne trouve aucun contre-exemple qui ne fonctionnerait pas comme prévu.
Arnauld
@Arnauld Ah, d'accord, je n'utilisais pas à l' b<2origine, mais je suppose que cela fonctionnera maintenant.
Neil
@Arnauld Mieux encore, puisque f(a/2,b/2)seuls les retours 0, 1, falseou true, je ne même pas besoin &1.
Neil
6

Python 2, 50 octets

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

Chaque numéro est associé à un triple dont l’ordre trié correspond à l’ordre souhaité.

  • La valeur primaire est [-n][n&n-1:], qui gère les puissances de 2 à la fin. Le bit et " n&n-1est " est zéro exactement quand nest une puissance de2 . Si c'est le cas, nous obtenons la liste [-n]et sinon la liste vide []. Cela met toutes les puissances de 2 à la fin de l’ordre, par ordre décroissant.
  • La valeur secondaire n&-n extrait le facteur de puissance 2 de n.
  • La valeur finale est négale à 2 en faveur du plus grand nombre.

Les tuples respectifs sont passés à cmppour voir si cette comparaison est <=0. Python 3 économiserait un octet avec une division float (n&n-1<1)/npour la première valeur du triple, mais en manquait cmp.

Xnor
la source
N'est pas cmp(...)<=0équivalent à cmp(...)<1?
mathmandan
@mathmandan Oui :)
xnor
Je pense qu'il est permis de prendre les nombres entiers dans l'ordre inverse et de les utiliser à la ~place de<1
Mitch Schwartz
5

Python 2, 87 71 octets

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

Cela ne remportera probablement aucun prix de taille, mais cette réponse fonctionne en construisant un tuple à l'aide de 3 expressions à partir d'un entier qui, une fois ordonné lexicographiquement, donnera le bon ordre.

En termes lisibles, le tuple est pour A = n · 2 p :

[n == 0, p * (1 - 2*(n == 0)), n]
orlp
la source
4

JavaScript (ES6), 70 64 octets

Pourrait probablement être joué un peu plus, mais comme première tentative:

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))

Prend les entrées avec la syntaxe de currying (x)(y). Retours 0/ 1.

Cas de test

Arnauld
la source
Vous pouvez enlever les crochets autour et à l'intérieur b>a||(b==a&&y>=x), cela ne fera aucune différence pour l'exécution.
XavCo7
@ XavCo7 Vous pouvez supprimer les crochets à l'intérieur, mais pas autour. Tous les cas de test existants réussiraient quand même, mais une entrée telle que [1, 5]erronée serait identifiée comme une vérité.
Arnauld
1
@Arnauld J'ajouterai cela comme un nouveau cas de test pour l'avenir.
Zgarb
3

Perl 6 , 89 84 octets

->\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}}

( Essayez-le en ligne. )

Pas tout à fait court, mais j’ai pensé qu’il serait intéressant d’écrire une solution qui génère la séquence de classement (jusqu’à une limite supérieure sûre pour chaque sous-séquence), puis de vérifier quelle entrée y figure en premier.

Par exemple:

  • Pour l'entrée, 2, 3il génère:

    3 5
    6
    12
    4 2 1
    ... et observe ensuite que 3apparaît avant 2.

  • Pour l'entrée, 9, 6il génère:

    3 5 7 9 11
    6 10
    12
    24
    48
    16 8 4 2 1
    ... et observe ensuite que 9apparaît avant 6.

Il pourrait être plus intelligent et générer encore moins de séquence, mais cela prendrait plus d'octets de code.

smls
la source
2

Python 2, 54 octets

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

Une solution récursive semblable à celle de Neil.

orlp
la source
Cela semble gâcher certains cas de test. Il dit f(158,158)est faux et f(2,8)est vrai.
xnor
@xnor Oops, devrait être corrigé maintenant.
Orlp
Ceci dit f(1,5)est Faux.
xnor
Mon mauvais, je voulais dire que cela f(1,5)devrait être Faux, mais le code donne Vrai.
xnor
@xnor Ah, j'ai repéré le bogue corrigé maintenant (pour de bon j'espère). J'ai trop suivi la description de Neil.
Orlp
1

Mathematica, 65 octets

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

Fonction non Truenommée prenant une liste d’entiers positifs et retournant si la liste forme une séquence ascendante dans l’ordre Sharkovskii, Falsesinon. (En particulier, la liste de saisie ne doit pas nécessairement comporter deux éléments: nous bénéficions gratuitement de la fonctionnalité ajoutée.)

Le cœur de l'algorithme est la fonction {1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}, qui déplace de manière répétée les facteurs de 2 pour convertir un entier de la forme m*2^k, avec mimpair, en paire ordonnée {2^k,m}(et ce, pour chaque élément de la liste d'entrée). OrderedQdécide ensuite si la liste résultante des paires ordonnées est déjà triée; par défaut, cela signifie en ordre croissant pour le premier élément, puis en ordre croissant pour le deuxième élément.

C'est exactement ce que nous voulons, sauf que les nombres qui sont des puissances de 2 suivent des règles différentes. Donc, avant de vérifier avec OrderingQ, nous appliquons une dernière règle /.{a_,1}->{∞,-a}, qui convertit (par exemple) {64,1}en {∞,-64}; cela met des puissances de 2 au bon endroit dans la commande.

Greg Martin
la source
1

APL (Dyalog Extended) , 27 octets

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

Essayez-le en ligne!

Fonction dyadique tacite dont l'argument gauche est aet la droite est b.

L’approche est presque identique à la solution Python 2 de xnor , en ce sens que nous convertissons chaque nombre en un tableau imbriqué et que nous effectuons une comparaison lexicographique entre eux.

Partie 1: Convertir un nombre en tableau imbriqué

{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]

Partie 2: Comparer deux tableaux imbriqués

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)

La syntaxe dfn prend en charge les instructions conditionnelles, par exemple la {a:x ⋄ b:y ⋄ z}signification if a then x else if b then y else z, mais elle est beaucoup trop détaillée à utiliser dans ce cas.

Barboteur
la source
0

Haskell, 143 138 octets

Fondamentalement, une mise en œuvre relativement simple des critères:

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  

Essayez-le en ligne!

flawr
la source
0

Python, 159 158 153 144 142 141 octets

Enregistré un 2 octets grâce à Kritixi Lithos!

Ceci est principalement juste pour pratiquer le golf mon Python!
Utilisé la formule donnée par le PO plutôt que les réponses les plus intelligentes

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))
Noodle9
la source
Vous pouvez jouer au golf en supprimant les espaces inutiles: par exemple, (a, b)sur la deuxième ligne où vous pouvez supprimer l'espace entre la virgule et b.
Kritixi Lithos