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
a&1|~b&1&f(a/2,b/2)
travailler?b<2
finira 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.b<2
origine, mais je suppose que cela fonctionnera maintenant.f(a/2,b/2)
seuls les retours0
,1
,false
outrue
, je ne même pas besoin&1
.Python 2, 50 octets
Chaque numéro est associé à un triple dont l’ordre trié correspond à l’ordre souhaité.
[-n][n&n-1:]
, qui gère les puissances de 2 à la fin. Le bit et "n&n-1
est " est zéro exactement quandn
est 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.n&-n
extrait le facteur de puissance 2 den
.n
égale à 2 en faveur du plus grand nombre.Les tuples respectifs sont passés à
cmp
pour voir si cette comparaison est<=0
. Python 3 économiserait un octet avec une division float(n&n-1<1)/n
pour la première valeur du triple, mais en manquaitcmp
.la source
cmp(...)<=0
équivalent àcmp(...)<1
?~
place de<1
Python 2,
8771 octetsCela 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 :
la source
JavaScript (ES6),
7064 octetsPourrait probablement être joué un peu plus, mais comme première tentative:
Prend les entrées avec la syntaxe de currying
(x)(y)
. Retours0
/1
.Cas de test
Afficher l'extrait de code
la source
b>a||(b==a&&y>=x)
, cela ne fera aucune différence pour l'exécution.[1, 5]
erronée serait identifiée comme une vérité.Perl 6 ,
8984 octets( 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,
... et observe ensuite que2, 3
il génère:3
apparaît avant2
.Pour l'entrée,
... et observe ensuite que9, 6
il génère:9
apparaît avant6
.Il pourrait être plus intelligent et générer encore moins de séquence, mais cela prendrait plus d'octets de code.
la source
Python 2, 54 octets
Une solution récursive semblable à celle de Neil.
la source
f(158,158)
est faux etf(2,8)
est vrai.f(1,5)
est Faux.f(1,5)
devrait être Faux, mais le code donne Vrai.Mathematica, 65 octets
Fonction non
True
nommée prenant une liste d’entiers positifs et retournant si la liste forme une séquence ascendante dans l’ordre Sharkovskii,False
sinon. (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 formem*2^k
, avecm
impair, en paire ordonnée{2^k,m}
(et ce, pour chaque élément de la liste d'entrée).OrderedQ
dé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.la source
APL (Dyalog Extended) , 27 octets
Essayez-le en ligne!
Fonction dyadique tacite dont l'argument gauche est
a
et la droite estb
.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é
Partie 2: Comparer deux tableaux imbriqués
La syntaxe dfn prend en charge les instructions conditionnelles, par exemple la
{a:x ⋄ b:y ⋄ z}
significationif a then x else if b then y else z
, mais elle est beaucoup trop détaillée à utiliser dans ce cas.la source
Haskell,
143138 octetsFondamentalement, une mise en œuvre relativement simple des critères:
Essayez-le en ligne!
la source
Python,
159158153144142141 octetsEnregistré
un2 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
la source
(a, b)
sur la deuxième ligne où vous pouvez supprimer l'espace entre la virgule etb
.05AB1E , 14 octets
Essayez-le en ligne! ou valider tous les cas de test .
la source