¿Podrías dejar de barajar la baraja y jugar ya?

31

Reto:

Entrada: Una lista de enteros positivos distintos dentro del rango .[1,tamaño de lista]

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 )[1,tamaño de lista][0 0,tamaño de lista-1]
  • 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 5en este caso.

Reglas generales:

  • Este es el , 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
Kevin Cruijssen
fuente
Sería bueno uno o dos casos de prueba con una longitud impar y una salida mayor que 0. Es fácil desordenar el riffle en tales casos si tiene que escribir el código del riff usted mismo en lugar de confiar en los builtins.
Olivier Grégoire
@ OlivierGrégoire El [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.
Kevin Cruijssen
Lo malo: estaba seguro de que el caso de prueba que mencionaste era del tamaño 8. Pero gracias por los casos de prueba adicionales.
Olivier Grégoire
1
La pregunta tal como está formulada actualmente parece "incorrecta" ... ¡un solo riffle shuffle debería resultar en el cambio de la primera y la última carta, a menos que esté haciendo algún tipo de truco de estafa! es decir, [6,1,7,2,8,3,9,4,10,5] después de una sola baraja de 10 cartas.
Steve
2
@ Steve Creo que tienes razón. Riffle-shuffling en general simplemente intercala dos mitades, por lo que ambas [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.
Kevin Cruijssen

Respuestas:

6

Jalea , 8 bytes

ŒœẎ$ƬiṢ’

Pruébalo en línea!

¿Cómo?

ŒœẎ$ƬiṢ’ - Link: list of integers A
    Ƭ    - collect up until results are no longer unique...
   $     -   last two links as a monad:
Œœ       -     odds & evens i.e. [a,b,c,d,...] -> [[a,c,...],[b,d,...]]
  Ẏ      -     tighten                         -> [a,c,...,b,d,...]
     Ṣ   - sort A
    i    - first (1-indexed) index of sorted A in collected shuffles
      ’  - decrement
Jonathan Allan
fuente
25

JavaScript (ES6), 44 bytes

Versión más corta sugerida por @nwellnhof

Espera un mazo con cartas indexadas como entrada.

f=(a,x=1)=>a[x]-2&&1+f(a,x*2%(a.length-1|1))

Pruébalo en línea!

Dado un mazo [c0,,cL1] de longitudL , definimos:

xn={2nmodLif L is odd2nmod(L1)if L is even

Y buscamos n tal quecxn=2 .


JavaScript (ES6),  57 52  50 bytes

Espera un mazo con cartas indexadas 0 como entrada.

f=(a,x=1,k=a.length-1|1)=>a[1]-x%k&&1+f(a,x*-~k/2)

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 longitud L , este código buscan tal que:

c2(k+12)n(modk)

donde do2 es la segunda cartak se define como:

k={LSi L es imparL-1Si L incluso

Arnauld
fuente
12

Python 2 , 39 bytes

f=lambda x:x[1]-2and-~f(x[::2]+x[1::2])

Pruébalo en línea!

-4 gracias a Jonathan Allan .

Erik el Outgolfer
fuente
Ahorre cuatro bytes conf=lambda x:2!=x[1]and-~f(x[::2]+x[1::2])
Jonathan Allan
@JonathanAllan ¡Oh, por supuesto! Bueno ... !=puede ser -. ;-)
Erik the Outgolfer
Ah, sí, advertencia: emptor: D (o simplemente x[1]>2supongo)
Jonathan Allan
5

R , 58 55 45 bytes

a=scan();while(a[2]>2)a=matrix(a,,2,F<-F+1);F

Pruébalo en línea!

Simula el proceso de clasificación. La entrada está indexada en 1, devuelve FALSE0.

Kirill L.
fuente
¡Muy agradable! Estaba trabajando en un enfoque similar pero usando una función recursiva, que no funcionó como golf.
user2390246
5

Perl 6 , 34 32 bytes

-2 bytes gracias a Jo King

{(.[(2 X**^$_)X%$_-1+|1]...2)-1}

Pruébalo en línea!

Similar al enfoque de Arnauld . El índice de la segunda carta después de n barajas es 2**n % kcon k definido como en la respuesta de Arnauld.

nwellnhof
fuente
5

APL (Dyalog Unicode) , SBCS 35 26 23 22 bytes

{⍵≡⍳≢⍵:01+∇⍵[⍒2|⍳⍴⍵]}

Prué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:

{⍵≡⍳≢⍵:01+∇⍵[⍒2|⍳⍴⍵]}
{⍵≡⍳≢⍵:01+∇⍵[⍒2|⍳⍴⍵]}  function takes one argument: ⍵, the array
 ⍵≡⍳≢⍵                  if the array is sorted:
 ⍵≡⍳≢⍵                  array = 1..length(array)
      :0                then return 0
                       otherwise
         1+             increment
                       the value of the recursive call with this argument:
            ⍵[      ]   index into the argument with these indexes:
                 ⍳⍴⍵    - generate a range from 1 up to the size of 
               2|       - %2: generate a binary mask like [1 0 1 0 1 0]
                       - grade (sorts but returns indexes instead of values), so we have the indexes of all the 1s first, then the 0s.

¹

Ven
fuente
1
Cuente la profundidad de recursión para -3.
Erik el Outgolfer
@EriktheOutgolfer Mucho mejor, gracias!
Ven
1
∧/2≤/⍵->⍵≡⍳≢⍵
ngn
@ngn no se dio cuenta de que la matriz no tenía agujeros. ¡Gracias!
Ven
4

Perl 6 , 36 34 32 bytes

-2 bytes gracias a nwellnhof

$!={.[1]-2&&$!(.sort:{$++%2})+1}

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:

$!={.[1]-2&&$!(.sort:{$++%2})+1}
$!={                           }   # Assign the anonymous code block to $!
    .[1]-2&&                       # While the list is not sorted
            $!(             )      # Recursively call the function on
               .sort:{$++%2}       # It sorted by the parity of each index
                             +1    # And return the number of shuffles
Jo King
fuente
3

05AB1E (heredado) , 9 bytes

[DāQ#ι˜]N

Pruébalo en línea!

Explicación

[   #  ]     # loop until
  ā          # the 1-indexed enumeration of the current list
 D Q         # equals a copy of the current list
     ι˜      # while false, uninterleave the current list and flatten
        N    # push the iteration index N as output
Emigna
fuente
Ni siquiera sabía que era posible generar el índice fuera del ciclo en el legado. Pensé que sería 0 nuevamente en ese punto, al igual que en la nueva versión 05AB1E. ¡Buena respuesta! Más corto que mi 10-byter usando el desarmado incorporado Å≠que inspiró este desafío. :)
Kevin Cruijssen
@KevinCruijssen: Interesante. No sabía que había una confusión. En este caso, es lo mismo que mi versión, pero unshuffle mantiene las dimensiones en matrices 2D.
Emigna
3

Java (JDK) , 59 bytes

a->{int c=0;for(;a[(1<<c)%(a.length-1|1)]>2;)c++;return c;}

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:

a->{int i=1,c=0;for(;a[i]>2;c++)i=i*2%(a.length-1|1);return c;}

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

Olivier Grégoire
fuente
163 bytes usando dos veces en x.clone()lugar de A.copyOf(x,l).
Kevin Cruijssen
2
64 bytes
Arnauld
@Arnauld ¡Gracias! Me costó mucho imaginar cómo simplificar esa "longitud si es extraño, longitud - 1"
Olivier Grégoire
@Arnauld ¡Oh! Mi nuevo algoritmo es en realidad el mismo que el tuyo ... Y pasé media hora descifrándolo por mí mismo ...
Olivier Grégoire
Más precisamente, es equivalente a una mejora sobre mi algoritmo original encontrado por @nwellnhof.
Arnauld
3

J , 28 26 bytes

-2 bytes gracias a Jonah!

 1#@}.(\:2|#\)^:(2<1{])^:a:

Pruébalo en línea!

Inspirado en la solución APL de Ven.

Explicación:

               ^:       ^:a:   while 
                 (2<1{])       the 1-st (zero-indexed) element is greater than 2   
     (        )                do the following and keep the intermediate results
          i.@#                 make a list form 0 to len-1
        2|                     find modulo 2 of each element
      /:                       sort the argument according the list of 0's and 1's
1  }.                          drop the first row of the result
 #@                            and take the length (how many rows -> steps)     

K (ngn / k) , 25 bytes

¡Gracias a ngn por el consejo y por su intérprete K!

{#1_{~2=x@1}{x@<2!!#x}\x}

Pruébalo en línea!

Galen Ivanov
fuente
Converge reiterar , a continuación, colocar uno, y cuenta - esto lleva a código más corto
NGN
@ngn. Entonces, similar a mi solución J: lo intentaré más tarde, ¡gracias!
Galen Ivanov
1
1#@}.(\:2|#\)^:(2<1{])^:a:por 26 bytes
Jonás
@ Jonás ¡Gracias!
Galen Ivanov
2

APL (NARS), caracteres 49, bytes 98

{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}

¿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)]:

  f←{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}
  f ,1
0
  f 1 2 3
0
  f 1,9,8,7,6,5,4,3,2,10
3
  f 1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20
17
RosLuP
fuente
Es la primera vez que veo a alguien diferenciar entre caracteres y bytes 👍. Siempre me molesta cuando veo caracteres Unicode y afirman que es un byte por carácter. ¡Este 😠 no es un byte!
Kerndog73
@ Kerndog73 Todo es número, pero en APL los personajes no son números ... (parecen elementos en la matriz AV)
RosLuP
2

Ruby , 42 bytes

f=->d,r=1{d[r]<3?0:1+f[d,r*2%(1|~-d.max)]}

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.

GB
fuente
2

R , 70 72 bytes

x=scan();i=0;while(any(x>sort(x))){x=c(x[y<-seq(x)%%2>0],x[!y]);i=i+1};i

Pruébalo en línea!

Ahora maneja el caso de reproducción aleatoria cero.

Nick Kennedy
fuente
1
@ user2390246 punto justo. Ajustado en consecuencia
Nick Kennedy
2

C (CCG) 64 63 bytes

-1 byte de nwellnhof

i,r;f(c,v)int*v;{for(i=r=1;v[i]>2;++r)i=i*2%(c-1|1);return~-r;}

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

a[999],b[999],i,r,o;f(c,v)int*v;{for(r=0;o=1;++r){for(i=c;i--;(i&1?b:a)[i/2]=v[i])o=(v[i]>v[i-1]|!i)&o;if(o)return r;for(i+=o=c+1;i--;)v[i]=i<o/2?a[i]:b[i-o/2];}}

Pruébalo en línea

a[999],b[999],i,r,o; //pre-declare variables
f(c,v)int*v;{ //argument list
    for(r=0;o=1;++r){ //major loop, reset o (ordered) to true at beginning, increment number of shuffles at end
        for(i=c;i--;(i&1?b:a)[i/2]=v[i]) //loop through v, split into halves a/b as we go
            o=(v[i]>v[i-1]|!i)&o; //if out of order set o (ordered) to false
        if(o) //if ordered
            return r; //return number of shuffles
        //note that i==-1 at this point
        for(i+=o=c+1;i--;)//set i=c and o=c+1, loop through v
            v[i]=i<o/2?a[i]:b[i-o/2];//set first half of v to a, second half to b
    }
}
rtpax
fuente
2

R, 85 bytes

s=scan();u=sort(s);k=0;while(any(u[seq(s)]!=s)){k=k+1;u=as.vector(t(matrix(u,,2)))};k

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 ordenado uque 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 orden byrow=TRUEes por eso que Taparece en matrix().

R , 84 bytes

s=scan();u=sort(s);k=0;while(any(s[seq(u)]!=u)){k=k+1;s=as.vector(matrix(s,,2,T))};k

Pruébalo en línea!

Volare
fuente
Me tomé la libertad de arreglar su título y agregar un enlace TIO para los casos de prueba (basado en la otra respuesta R ), y también verifiqué que su respuesta funciona según lo previsto, ¡así que haga un +1 y bienvenido a PPCG! :)
Kevin Cruijssen
1

Pyth , 18 bytes

L?SIb0hys%L2>Bb1
y

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 llama ycon el Qargumento implícito (stdin evaluado).

L?SIb0hys%L2>Bb1
L                function y(b)
 ?               if...
  SIb            the Invariant b == sort(b) holds
     0           return 0
      h          otherwise increment...
       y         ...the return of a recursive call with:
             B   the current argument "bifurcated", an array of:
              b   - the original argument
            >  1  - same with the head popped off
          L      map...
         % 2     ...take only every 2nd value in each array
        s         and concat them back together

¹

Ven
fuente
1

PowerShell , 62 71 70 66 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, $ja un nuevo ámbito.

for($a=$args;$a[1]-2;$a=&{($a|?{++$j%2})+($a|?{$i++%2})}){$n++}+$n

Pruébalo en línea!

mazzy
fuente
1

Japt , 13 11 10 bytes

Tomando mi brillante, nueva , muy -El trabajo en progreso intérprete para una prueba de conducción.

ÅÎÍ©ÒßUñÏu

Pruébalo o ejecuta todos los casos de prueba

ÅÎÍ©ÒßUñÏu     :Implicit input of integer array U
Å              :Slice the first element off U
 Î             :Get the first element
  Í            :Subtract from 2
   ©           :Logical AND with
    Ò          :  Negation of bitwise NOT of
     ß         :  A recursive call to the programme with input
      Uñ       :    U sorted
        Ï      :    By 0-based indices
         u     :    Modulo 2
Lanudo
fuente
1
Este intérprete se ve súper genial.
recursivo
0

Python 3, 40 bytes

f=lambda x:x[1]-2and 1+f(x[::2]+x[1::2])  # 1-based
f=lambda x:x[1]-1and 1+f(x[::2]+x[1::2])  # 0-based

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

Alex
fuente