Introducción
En este desafío, trataremos con un cierto orden de los enteros positivos. El pedido es así:
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
Primero enumeramos todos los enteros impares mayores que 1 en orden ascendente. Luego enumeramos dos veces enteros impares mayores que 1, luego 4 veces, luego 8 veces, y así sucesivamente: para todos los k , enumeramos 2 k veces los enteros impares mayores que 1 en orden ascendente. Finalmente, enumeramos las potencias de dos en orden descendente , terminando en 1. Cada entero positivo ocurre en esta "lista" exactamente una vez.
Más explícitamente, considere dos enteros positivos distintos A = n · 2 p y B = m · 2 q , donde n, m ≥ 1 son impares, y p, q ≥ 0 . Entonces A viene antes que B en el orden, si se cumple una de las siguientes condiciones:
- n> 1 , m> 1 y p <q
- 1 <n <m y p = q
- n> m = 1
- n = m = 1 y p> q
Este orden aparece en el sorprendente resultado matemático conocido como el teorema de Sharkovskii , que se refiere a los puntos periódicos de los sistemas dinámicos. No entraré en detalles aquí.
La tarea
Su tarea en este desafío es calcular el orden anterior. Sus entradas son dos enteros positivos A y B , que pueden ser iguales. Su salida es un valor verdadero si A viene antes que B en el orden, y un valor falso de lo contrario. Si A = B , su salida debería ser veraz. Puede tomar A y B en cualquier orden, siempre que sea consistente.
No tiene que preocuparse por el desbordamiento de enteros, pero su algoritmo debería funcionar teóricamente para entradas arbitrariamente grandes.
Casos de prueba
Instancias de verdad
3 11
9 6
48 112
49 112
158 158
36 24
14 28
144 32
32 32
32 8
3 1
1 1
Instancias falsas
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)
?b<2
eventualmente será cierto. Ahora, otro problema es que procesará más iteraciones de las necesarias y obtendrá valores de coma flotante. Pero no puedo encontrar ningún contraejemplo que no funcione como se esperaba.b<2
originalmente, pero supongo que funcionará ahora.f(a/2,b/2)
sólo devuelve0
,1
,false
otrue
, no necesita ni siquiera el&1
.Python 2, 50 bytes
Cada número se asigna a un triple cuyo orden ordenado es el orden deseado.
[-n][n&n-1:]
, que maneja las potencias de 2 al final. El bit "y"n&n-1
es cero exactamente cuandon
es una potencia de2
. Si es así, obtenemos la lista[-n]
y, de lo contrario, la lista vacía[]
. Esto pone todas las potencias de 2 al final del orden, en orden decreciente.n&-n
extrae el factor de potencia de 2 den
.n
desempata iguala las potencias de 2 a favor del mayor número.Las tuplas respectivas se pasan a
cmp
para ver si esa comparación es<=0
. Python 3 ahorraría un byte con división flotante(n&n-1<1)/n
para el primer valor en el triple, pero faltacmp
.fuente
cmp(...)<=0
equivalente acmp(...)<1
?~
lugar de<1
Python 2,
8771 bytesEsto probablemente no gane premios de ningún tamaño, pero esta respuesta funciona construyendo una tupla de 3 usando 3 expresiones de un número entero que cuando se ordena lexicográficamente dará como resultado el orden correcto.
En términos legibles, la tupla es para A = n · 2 p :
fuente
JavaScript (ES6),
7064 bytesProbablemente podría jugar un poco más, pero como primer intento:
Toma entrada con la sintaxis de curry
(x)(y)
. Devoluciones0
/1
.Casos de prueba
Mostrar fragmento de código
fuente
b>a||(b==a&&y>=x)
, no hará una diferencia en la ejecución.[1, 5]
que se identifica incorrectamente como verdadera.Perl 6 ,
8984 bytes( Pruébelo en línea )
No es exactamente breve, pero pensé que sería interesante escribir una solución que realmente genere la secuencia de pedido (hasta un límite superior seguro para cada subsecuencia), y luego verifica qué entrada aparece primero.
Por ejemplo:
Para la entrada
... y luego observa que2, 3
genera:3
aparece antes2
.Para la entrada
... y luego observa que9, 6
genera:9
aparece antes6
.Podría ser más inteligente y generar aún menos secuencia, pero eso requeriría más bytes de código.
fuente
Python 2, 54 bytes
Una solución recursiva similar a la de Neil.
fuente
f(158,158)
es falso yf(2,8)
es verdadero.f(1,5)
es falso.f(1,5)
debería ser Falso, pero el código da Verdadero.Mathematica, 65 bytes
Función sin nombre que toma una lista de enteros positivos y regresa
True
si la lista forma una secuencia ascendente en el orden Sharkovskii, de loFalse
contrario. (En particular, la lista de entrada no tiene que tener solo dos elementos: obtenemos la funcionalidad adicional de forma gratuita).El corazón del algoritmo es la función
{1,#}&/@#//.{a_,b_/;EvenQ@b}->{2a,b/2}
, que mueve repetidamente factores de 2 para convertir un entero de la formam*2^k
, conm
impar, en el par ordenado{2^k,m}
(y lo hace para cada elemento de la lista de entrada).OrderedQ
luego decide si la lista resultante de pares ordenados ya está ordenada; por defecto, eso significa en orden creciente por el primer elemento, luego en orden creciente por el segundo elemento.Eso es exactamente lo que queremos, excepto que los números que son potencias de 2 siguen reglas diferentes. Entonces, antes de registrarnos
OrderingQ
, aplicamos una última regla/.{a_,1}->{∞,-a}
, que convierte (por ejemplo){64,1}
a{∞,-64}
; eso pone potencias de 2 en el lugar correcto en el orden.fuente
APL (Dyalog Extended) , 27 bytes
Pruébalo en línea!
Una función diádica tácita cuyo argumento izquierdo es
a
y el derecho esb
.El enfoque es casi idéntico a la solución Python 2 de xnor , ya que convertimos cada número en una matriz anidada y hacemos una comparación lexicográfica entre ellos.
Parte 1: Convertir número a matriz anidada
Parte 2: compara dos matrices anidadas
La sintaxis dfn admite declaraciones condicionales, por ejemplo ,
{a:x ⋄ b:y ⋄ z}
significadoif a then x else if b then y else z
, pero es demasiado detallada para usar en este caso.fuente
Haskell,
143138 bytesBásicamente, una implementación relativamente sencilla de los criterios:
Pruébalo en línea!
fuente
Python,
159158153144142141 bytesGuardado
de un2 bytes gracias a Kritixi Lithos!¡Esto es principalmente para practicar golf en mi Python!
Usó la fórmula dada por el OP en lugar de las formas de todas las respuestas más inteligentes
fuente
(a, b)
la segunda línea, donde puede eliminar el espacio entre la coma yb
.05AB1E , 14 bytes
Pruébalo en línea! o validar todos los casos de prueba .
fuente