Reto:
Entrada: Una lista de enteros positivos distintos dentro del rango .
Salida: Un número entero: la cantidad de veces que la lista se baraja rápidamente . Para una lista, esto significa que la lista está dividida en dos mitades, y estas mitades están intercaladas (es decir, la combinación aleatoria de la lista [1,2,3,4,5,6,7,8,9,10]
una vez daría como resultado [1,6,2,7,3,8,4,9,5,10]
, por lo que para este desafío la entrada [1,6,2,7,3,8,4,9,5,10]
daría como resultado 1
).
Reglas de desafío:
- Puede suponer que la lista solo contendrá enteros positivos en el rango (o si elige tener listas de entrada indexadas a 0 )
- Puede suponer que todas las listas de entrada serán una lista aleatoria válida o una lista ordenada que no se baraja (en cuyo caso la salida sí lo es
0
). - Puede suponer que la lista de entrada contendrá al menos tres valores.
Ejemplo paso a paso:
Entrada: [1,3,5,7,9,2,4,6,8]
Descomponerlo una vez se convierte en: [1,5,9,4,8,3,7,2,6]
porque cada elemento indexado en 0 par primero es el primero [1, ,5, ,9, ,4, ,8]
, y luego todos los elementos indexados en 0 impares después de eso [ ,3, ,7, ,2, ,6, ]
.
La lista aún no está ordenada, así que continuamos:
Desorganizar la lista nuevamente se convierte en: [1,9,8,7,6,5,4,3,2]
Nuevamente se convierte en: [1,8,6,4,2,9,7,5,3]
Entonces: [1,6,2,7,3,8,4,9,5]
Y finalmente:, [1,2,3,4,5,6,7,8,9]
que es una lista ordenada, por lo que hemos terminado de barajar.
Des barajamos el original [1,3,5,7,9,2,4,6,8]
cinco veces para llegar [1,2,3,4,5,6,7,8,9]
, por lo que la salida es 5
en este caso.
Reglas generales:
- Este es el código de golf , por lo que la respuesta más corta en bytes gana.
No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolf. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación. - Las reglas estándar se aplican a su respuesta con las reglas de E / S predeterminadas , por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
- Las lagunas predeterminadas están prohibidas.
- Si es posible, agregue un enlace con una prueba para su código (es decir, TIO ).
- Además, se recomienda agregar una explicación para su respuesta.
Casos de prueba:
Input Output
[1,2,3] 0
[1,2,3,4,5] 0
[1,3,2] 1
[1,6,2,7,3,8,4,9,5,10] 1
[1,3,5,7,2,4,6] 2
[1,8,6,4,2,9,7,5,3,10] 2
[1,9,8,7,6,5,4,3,2,10] 3
[1,5,9,4,8,3,7,2,6,10] 4
[1,3,5,7,9,2,4,6,8] 5
[1,6,11,5,10,4,9,3,8,2,7] 6
[1,10,19,9,18,8,17,7,16,6,15,5,14,4,13,3,12,2,11,20] 10
[1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20] 17
[1,141,32,172,63,203,94,234,125,16,156,47,187,78,218,109,249,140,31,171,62,202,93,233,124,15,155,46,186,77,217,108,248,139,30,170,61,201,92,232,123,14,154,45,185,76,216,107,247,138,29,169,60,200,91,231,122,13,153,44,184,75,215,106,246,137,28,168,59,199,90,230,121,12,152,43,183,74,214,105,245,136,27,167,58,198,89,229,120,11,151,42,182,73,213,104,244,135,26,166,57,197,88,228,119,10,150,41,181,72,212,103,243,134,25,165,56,196,87,227,118,9,149,40,180,71,211,102,242,133,24,164,55,195,86,226,117,8,148,39,179,70,210,101,241,132,23,163,54,194,85,225,116,7,147,38,178,69,209,100,240,131,22,162,53,193,84,224,115,6,146,37,177,68,208,99,239,130,21,161,52,192,83,223,114,5,145,36,176,67,207,98,238,129,20,160,51,191,82,222,113,4,144,35,175,66,206,97,237,128,19,159,50,190,81,221,112,3,143,34,174,65,205,96,236,127,18,158,49,189,80,220,111,2,142,33,173,64,204,95,235,126,17,157,48,188,79,219,110,250]
45
fuente
[1,3,5,7,9,2,4,6,8]
es de longitud 9, pero agregaré algunos más para las longitudes 7 y 11 tal vez. EDITAR: Se agregaron los casos de prueba[1,3,5,7,2,4,6] = 2
(longitud 7) y[1,6,11,5,10,4,9,3,8,2,7] = 6
(longitud 11). Espero que ayude.[1,6,2,7,3,8,4,9,5,10]
o[6,1,7,2,8,3,9,4,10,5]
son posibles. En mi desafío, significa que la carta superior siempre seguirá siendo la carta superior, así que de hecho es un poco un truco. Sin embargo, nunca he visto a alguien usar solo barajas para mezclar un mazo de cartas. Por lo general, también usan otro tipo de barajaduras intermedias. De todos modos, es demasiado tarde para cambiar el desafío ahora, por lo que, por el bien de este desafío, la carta superior siempre seguirá siendo la carta superior después de un riffle-shuffle.Respuestas:
Jalea , 8 bytes
Pruébalo en línea!
¿Cómo?
fuente
JavaScript (ES6), 44 bytes
Versión más corta sugerida por @nwellnhof
Espera un mazo con cartas indexadas como entrada.
Pruébalo en línea!
Dado un mazo[ c0 0,…,cL−1] de longitudL , definimos:
Y buscamosn tal quecxn=2 .
JavaScript (ES6),
57 5250 bytesEspera un mazo con cartas indexadas 0 como entrada.
Pruébalo en línea!
¿Cómo?
Dado que JS carece de soporte nativo para extraer segmentos de matriz con un paso personalizado, simular todo el riffle-shuffle probablemente sería bastante costoso (pero para ser sincero, ni siquiera lo intenté). Sin embargo, la solución también se puede encontrar simplemente mirando la segunda carta y el número total de cartas en el mazo.
Dado un mazo de longitudL , este código buscan tal que:
dondedo2 es la segunda cartak se define como:
fuente
Python 2 , 39 bytes
Pruébalo en línea!
-4 gracias a Jonathan Allan .
fuente
f=lambda x:2!=x[1]and-~f(x[::2]+x[1::2])
!=
puede ser-
. ;-)x[1]>2
supongo)R ,
585545 bytesPruébalo en línea!
Simula el proceso de clasificación. La entrada está indexada en 1, devuelve
FALSE
0.fuente
Perl 6 ,
3432 bytes-2 bytes gracias a Jo King
Pruébalo en línea!
Similar al enfoque de Arnauld . El índice de la segunda carta después de n barajas es
2**n % k
con k definido como en la respuesta de Arnauld.fuente
APL (Dyalog Unicode) , SBCS
35262322 bytesPruébalo en línea!
Gracias a Adám por la ayuda, Erik the Outgolfer por -3 y ngn por -1.
El enlace TIO contiene dos casos de prueba.
Explicación:
¹
fuente
∧/2≤/⍵
->⍵≡⍳≢⍵
Perl 6 ,
36 3432 bytes-2 bytes gracias a nwellnhof
Pruébalo en línea!
El riffle inverso se baraja clasificándolo por el módulo de índice 2 hasta que se ordena la lista, luego devuelve la longitud de la secuencia.
Es curioso, generalmente no intento el enfoque recursivo para Perl 6, pero esta vez terminó más corto que el original.
Explicación:
fuente
05AB1E (heredado) , 9 bytes
Pruébalo en línea!
Explicación
fuente
Å≠
que inspiró este desafío. :)Java (JDK) , 59 bytes
Pruébalo en línea!
Funciona de manera confiable solo para matrices con un tamaño inferior a 31 o soluciones con menos de 31 iteraciones. Para una solución más general, vea la siguiente solución con 63 bytes:
Pruébalo en línea!
Explicación
En un riffle, la siguiente posición es la anterior una vez dos módulos, ya sea longitud si es impar o longitud - 1 si es par.
Así que estoy iterando sobre todos los índices usando esta fórmula hasta que encuentre el valor 2 en la matriz.
Créditos
fuente
x.clone()
lugar deA.copyOf(x,l)
.J ,
2826 bytes-2 bytes gracias a Jonah!
Pruébalo en línea!
Inspirado en la solución APL de Ven.
Explicación:
K (ngn / k) , 25 bytes
¡Gracias a ngn por el consejo y por su intérprete K!
Pruébalo en línea!
fuente
1#@}.(\:2|#\)^:(2<1{])^:a:
por 26 bytesAPL (NARS), caracteres 49, bytes 98
¿Por qué usar en el bucle más profundo, un algo que debería ser nlog (n), cuando podemos usar un n lineal? solo por unos pocos bytes más? [⍵≡⍵ [⍋⍵] O (nlog n) y la confrontación de cada elemento para ver están en orden usando la prueba ∧ / ¯1 ↓ ⍵≤1⌽⍵ O (n)]:
fuente
Ruby , 42 bytes
Pruébalo en línea!
Cómo:
Busque el número 2 dentro de la matriz: si está en la segunda posición, el mazo no se ha barajado, de lo contrario verifique las posiciones donde lo colocarían los barajamientos sucesivos.
fuente
R ,
7072 bytesPruébalo en línea!
Ahora maneja el caso de reproducción aleatoria cero.
fuente
C (CCG)
6463 bytes-1 byte de nwellnhof
Esta es una respuesta drásticamente más corta basada en las respuestas de Arnauld y Olivier Grégoire. Dejaré mi solución anterior a continuación, ya que resuelve el problema un poco más general de los mazos con cartas que no son contiguas.
Pruébalo en línea
C (GCC) 162 bytes
Pruébalo en línea
fuente
R, 85 bytes
Pruébalo en línea.
Explicación
Método estúpido (fuerza bruta), mucho menos elegante que seguir la carta n. ° 2.
En lugar de mezclar la entrada
s
, comenzamos con un vector ordenadou
que barajamos progresivamente hasta que sea idéntico as
. Esto proporciona advertencias (pero los recuentos aleatorios siguen siendo correctos) para longitudes impares de entrada debido al plegado de un vector de longitud impar en una matriz de 2 columnas; en ese caso, en R, el punto de datos que falta se llena reciclando el primer elemento de entrada.El ciclo nunca terminará si proporcionamos un vector que no se puede mezclar.
Anexo: guarda un byte si no se baraja en su lugar. A diferencia de la respuesta anterior, no hay necesidad de transponer
t()
, sin embargo, el ordenbyrow=TRUE
es por eso queT
aparece enmatrix()
.R , 84 bytes
Pruébalo en línea!
fuente
PowerShell ,
116 114 108 8478 bytes-24 bytes gracias a Erik el Outgolfer 's solución .
-6 bytes gracias a mazzy .
Pruébalo en línea!
fuente
Wolfram Language (Mathematica) , 62 bytes
Pruébalo en línea!
Explicación
La lista de entrada es
a
. No está dividido y se compara con la lista ordenada hasta que coinciden.fuente
Rojo ,
877978 bytesPruébalo en línea!
fuente
Perl 5
-pa
, 77 bytesPruébalo en línea!
fuente
Pyth , 18 bytes
Pruébalo en línea!
-2 gracias a @Erik the Outgolfer.
El script tiene dos líneas: la primera define una función
y
, la segunda línea llamay
con elQ
argumento implícito (stdin evaluado).¹
fuente
PowerShell ,
62717066 bytes+9 bytes cuando Casos de prueba con un número par de elementos agregados.
-1 byte con salpicaduras.
-4 Bytes: envolver la expresión con
$i
,$j
a un nuevo ámbito.Pruébalo en línea!
fuente
Japt ,
131110 bytesTomando mi brillante, nueva
, muy -El trabajo en progresointérprete para una prueba de conducción.Pruébalo o ejecuta todos los casos de prueba
fuente
Python 3, 40 bytes
Pruébalo en línea!
Necesito actualizar la página con más frecuencia: me perdí la edición de Erik the Outgolfer haciendo un truco similar =)
fuente