Sobre la serie

En primer lugar, puede tratar esto como cualquier otro desafío de golf de código y responderlo sin preocuparse por la serie. Sin embargo, hay una tabla de clasificación en todos los desafíos. Puede encontrar la tabla de clasificación junto con más información sobre la serie en la primera publicación .

Hoyo 8: baraja una lista infinita

Debe escribir una función o programa que tome una lista infinita como entrada y devuelva una versión aleatoria de esa lista.

Acerca de E / S infinitas

Hay varias formas en que puede tomar datos y producir resultados para este desafío:

• Puede tomar una lista de enteros positivos, o una representación de cadena de los mismos, o una cadena o lista de caracteres ASCII imprimibles (0x20 a 0x7E, inclusive). El formato de salida debe coincidir con el formato de entrada. Me referiré a los datos como "la lista" de ahora en adelante, independientemente de la opción que elija.
• Puede leer la lista desde una secuencia de entrada estándar infinita y escribir la salida continuamente en una secuencia de salida estándar infinita. La solución no debe depender de ningún valor o secuencia de valores en particular para garantizar que la secuencia de salida se escriba y se vacíe regularmente (por ejemplo, no puede escribir la salida siempre que haya una 5en la lista de entrada). Por supuesto, si lee una representación de cadena de una lista, está bien esperar hasta encontrar el separador de lista.
• En los idiomas que los admiten, puede escribir una función que tome y devuelva una lista o cadena infinita perezosa.
• En los idiomas que los admiten, puede implementar un generador infinito que tome otro generador como entrada.
• Alternativamente, puede escribir una función que no tome argumentos y devuelva un valor de salida cada vez que se llame. En este caso, puede suponer que se ha definido una función que no toma argumentos y devuelve el siguiente valor de entrada cada vez que se llama. Puedes elegir libremente el nombre de esa función.

Puede suponer que su programa se ejecuta para siempre y que hay memoria infinita disponible. (Es posible resolver esto con una cantidad finita de memoria, pero lo que esto significa es que se le permite perder memoria).

Sobre la aleatoriedad

Para cualquier valor v que se lea en una posición i de la entrada infinita, debe haber una probabilidad positiva de que termine en cualquiera de las posiciones i-9 a i + 9 de la salida infinita (a menos que esa posición sea negativa ) Estas probabilidades no tienen que ser las mismas para diferentes posiciones de salida o incluso para diferentes posiciones de entrada. Está bien si su solución también puede barajar los valores a otra posición que esté más lejos.

Por lo tanto, no es necesario que su solución pueda barajar el primer valor muy abajo en la lista, o que pueda barajar un valor muy tardío hasta la primera posición, aunque está bien si lo hace, siempre que todas las posiciones estén a 9 pasos del La entrada es posible.

Por ejemplo, si tomó la siguiente cadena como entrada, ___indica todas las posiciones que Xdeben poder terminar en la salida:

                  ___________________
 abcdefghijklmnopqrstuvwxyzXabcdefghijklmnopqrstuvwxyz...

Si su idioma carece de un generador de números aleatorios incorporado o no desea usarlo, puede tomar un valor semilla adicional como entrada e implementar su propio RNG adecuado utilizando la semilla. Esta página puede ser útil para eso.

Independientemente de la distribución real que utilice su solución, es casi seguro que debe producir el siguiente valor después de un tiempo finito (pero arbitrario).

Incluya una breve explicación sobre cómo su implementación satisface estos requisitos.

Tanteo

Este es el código de golf , por lo que gana la respuesta válida más corta, medida en bytes .

Tabla de clasificación

La primera publicación de la serie genera una tabla de clasificación.

Para asegurarse de que sus respuestas aparezcan, comience cada respuesta con un título, utilizando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(El idioma no se muestra actualmente, pero el fragmento sí lo requiere y analiza, y puedo agregar una tabla de clasificación por idioma en el futuro).

Python 3 , 78 bytes

from random import*
l=[]
while[shuffle(l)]:l[9:]and print(l.pop());l+=input(),

Pruébalo en línea!

Toma datos de STDIN (uno por línea), imprime en STDOUT.

Mantiene un búfer lde hasta 10 elementos. El búfer se baraja con cada paso. Cuando su longitud es 10, el último elemento se imprime y se elimina.

Si un elemento se imprime tan pronto como se insertó, se saltará por delante de otros 9 elementos que esperan en el búfer, por lo que parece que quedan 9 puntos. Un elemento puede esperar en el búfer arbitrariamente largo, por lo que su posición puede mover cualquier cantidad a la derecha.

No parece haber una buena manera de producir y eliminar un elemento aleatorio de una lista. Barajar parece una exageración. Son 2 bytes más largos de uso l.pop(randint(0,9))(que usa que la lista tiene 10 elementos).

from random import*
l=[]
while 1:l+=input(),;l[9:]and print(l.pop(randint(0,9)))

No es mejor hacerlo x=choice(l);l.remove(x). Un lenguaje con me poprandomgusta

poprandom = lambda l:l.pop(randrange(len(l)))

podría hacer muy limpiamente

from random import*
l=[]
while 1:l+=input(),;l[9:]and print(poprandom(l))

Befunge ( sabor peculiar ), 4 bytes

?,?~

,lee un personaje de la secuencia y lo empuja a la pila. ~saca el carácter superior de la pila (si está presente) y lo imprime. ?aleatoriza qué comando se ejecuta a continuación. Entonces, el algoritmo aquí es "En un bucle infinito, con la misma probabilidad de empujar un personaje o reventar un personaje". Creo que esto satisface los requisitos: un personaje puede ver arbitrariamente muchos caracteres agregados encima de él en la pila, por lo que puede moverse arbitrariamente hacia la derecha, y puede imprimirse cuando la pila es arbitrariamente grande, por lo que puede moverse arbitrariamente lejos hacia la izquierda.

C (gcc) , 94 bytes

L;i;f(s){srand(s);int B[9]={0};for(L=0;;)L>9&&putchar(B[i=rand()%10]),B[L>9?i:L++]=getchar();}

Pruébalo en línea!

Ok, un enlace TIO no tiene mucho sentido. Para facilitar la prueba, creé el siguiente programa en C que generará caracteres ascii aleatorios o repetirá una cadena infinitamente.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main(int argc, char** argv){
    srand(time(NULL));
    if(argc < 1) {
        for(;;){
            printf("%c", rand() % 95 + 32);
        }
    } else {
        char* s = argv[1];
        int i = 0;
        for(;;){
            if(s[i] == 0)
                i = 0;
            printf("%c", s[i++]);
        }
    }
}

Este programa se denominará iro.

Corrección del programa

Lo que hago aquí es leer 9valores en un búfer. Después de esto, los índices aleatorios se eligen de esta matriz y se emiten, luego se reemplazan por el siguiente carácter en la secuencia.

SILOS , 149 bytes

b=1
lbla
x=15+b*15
b=1
lblb
readIO
queue 0 i
x-1
if x b
a=0
lblx
x=rand*2
queuePop 0
if x X
printInt m
a+1
b=15-a
if b x
GOTO a
lblX
queue 0 m
GOTO x

Pruébalo en línea!

Esencialmente, sigue recibiendo información (en el intérprete en línea a través de argumentos, pero en el intérprete oficial fuera de línea le permitirá escribir en la consola (infinitamente) en bloques de 15 a la vez (30 el primer bloque).

Carga la entrada en una cola temporal y elige un 15 afortunado (al azar, pero no distribuido equitativamente en términos de probabilidad o distribución).

El resto permanece mientras las nuevas entradas llenan la cola, la primera entrada podría barajarse hasta el final (básicamente, creo que los caracteres siguen una distribución normal). Es interesante notar que este programa es solo dos veces más detallado que Python y quizás "más golfista" que Java.

Para ver mejor los resultados, tengo una versión no compatible que toma la entrada como una cadena (sin embargo, solo puede tener aproximadamente 8,000 caracteres).

Pruébalo en línea!

Solo por diversión, aquí está esta publicación alimentada a través de la versión de cadena.

 [.L.Ooy "9beS.IS]," 14 ts b1
 solo

  = ll
   x = 1b 15 1
5b a * b = lb rd # + lb eaI O e 
 X
 ifquu   
1 0x b
   =

    mi
0 0
   i lblxa -d * 2
    quu x = rn 
   x Xea p0
   pnInt ora
   mf = iePit
  ba 1
   GTO 1 fb x + Oa


 qe -lblX u0 m GOOue  
[rlT 

 tnn5! I.STii] [S.LO es decir

htpsgthyx]: iub.om/jhujh .. tcraa.IOo /TytonieSu:wl/.L lnn!: tt / iS
[En hsto.un / nuslprxRUCoDsio /]: e#NzZn6j4c/2xNQFnF7y0aLzkrosd9Dov2yxJNx774HBrgPUdi9CySI09sCLw5TJwB7jlB1XVeQFE7m1VMsIQvDOjBmdtME3umNzYXs9unFbqRamVDfUDw@RT3NHoL7/i04bz16DCoP4eulOU7jPD8OmYjATpynkuMDuBPYmtnIJzseyyhaNkMyQgXG2R782vqMDIiUm6Kq4Q3mJkxlUsR1rrldPw./l28Z SL.XS - IONuscOT "
senallyxMz.stiitkp ingN "
 eestaint on heeInliinrprt (oe e toghr tetgpnmntuon eruEuut rh ofi off, bhenecil inretea.atr ialoks tirilw upeitfleptly ty honso (e oote cenfine iwllbc 15 atly) nitloo aim (te) nikfte3 firs bk
hs 0 It te 
 lodshipo alauttt.mpra quuet i reanicks a lck eooy d randomyn p 15 (uo equl, unbtty drbutedaynistinems oftrly ordisrprob ill abition h ibttmin.Tet ri)
 a nwit u ree nusfil th queusen 
pte ftip, ae uldsfuesis ob hl rlelth weual t tc hdyoend, f tbaaly thi an elnkhecarcthe (sc ho noreiItrolwaaldibtio lmiru.t 'iereaf) tsng tetntiottssht prasnon hogIms only twieatisi s vroscpythonp.
 tte s / "gt 
Obviamente, tsvea no omhTrehs una plivevesion hcahihk ine teuts sriprics at rwvritcaw aa g (hoee n onl kein n00 orscat, 0 cter).

[Tyauoas onine! Hrhrys :.ru] p // o / lsslo # jVd (tinnexi3E @ KDpit / LrhtwXwVEUuscxPmJjFFCaNimMzlHiQEcMmdVIT7vqs8mNgxU3mD / J1AwXq / ivbao1j @ nb4I6 / m93655bThmb4cy5TUX3xvI018cZzrXItuO5B @ NX5JD / HzyE @ G @ D5eqrGem3l0HPGRutZfpi2PzVA @ d3CVRTm4zJxnZdcFSTEO0JOT9KhDI6byjnLhS0cNmGz7hJrTdAgORT8Ndvv7DgZSbJdkp9v5al8qMyNCb9tXe0ChrShXRTOt @ 7fFgV3zTkbVbsD @ JpKina2oKgNVakjsjLCpD29u7l0XVRWalVTyArF1FqypQAxXb / BedqUqpJGOPVyxOjLj0jXup8cE277L2I6 @ lSowK5pA7nGldRBiJwyKxF6z2c3kW / sJ4EYBbbpSuBxs55nyI9sdnu @ nJJeGqtKprGEUbc6NDGMjjO2tN / KuKTWh2WWbbRRLVaq / P6KqkoMNWGRgTQZLlbXfQI050bY0rz0xmzCVZ4vowjpV0dCmkDFq0VNa5GSDzVn5Qw7idwPTxu5xTAtLQCDN / YIApfAn4dsDmYksCqUU27sRggpzRK4SmdjmPUPQO4j5FmgHMFRWS2eI1CfA2YIcf7JlylFjdZypVTH0IJu4ZJHiUviyBFKqhrkCjgXAAB8d710NhHgDwcJksuvPPprcfzHPTaJGFX8OIExW / cBZjaPiY7a4WD6rTYmOouBVucROlwvuBJiHWdJQjjbobNGTd7M1P6z8dw / A @ GU02hgjCcrjjQHkAdS6r7UjQ6wAPqB @ sIgxkKcbZDixeWS6mn160CKQpn7aUwGLK22u9I0oX6YIwPMhFVaX5uYon0AyoNTCZvnmtilVhV3 / pgTGc7r39lIS5PmqM / NGnUSLnTw9eTJ7qqrNQKsJHz @ Tt8mDZVWKCKTkBro1PuQAksDdN1yaVGiVXElRW9i5M11cINmxNGYAg9TD7sxtEDI2OkKMaBXgvO5dOplUQQIdpb2w66NePBScMmEnAX8ydGSiiHlss @ hOLZzInnIoTevRtEm / TGHWOkly5ljMK4FkgDDSWCWBW3YwmEVYCIBV @ GMIg3TZtGwMFWXVxQwBb5iD6PfS7h7Sric1ib5ZYIvW6n3tlaK7 / 6 @ 3OAHy4LjOuW @ tzaBP3 @ mFbJpHsVsQKPfeui / o1 @ aBcbZ4TK96T8tp3QjeA1vDXMKBIqdK @ HZs2vsMlQE36YmrBEnVRUvAGNuCt44e0RB0sL0MkNu1Q5wOwliTT2JQzVrOnHAmSXIU // sqjdG6jdT2r1v @@ lGjouzkGWoD4zhnzJBxo0OT6OTbBDgeDFRnY8TMXZbMPdxsCtbXeUxIBqST4VRwkpbgwChBcJxMx6hLIVZhfuylDvF1l26Nbl3xRLgQnatSCMigx @ PCT6lcG1ebdk / 86UBUFp9UkxjoCGSJnlxMtUdHf6IjkMnil5aua9L @ xXsdHEKW @ 8JpVqlgKsr12bAKG2Typfv @ Yy4CkUydETWphcdmdpWq7egtxqP8pYI2rSaSuYBwW0tNTdXn4qcjnZ9JKhuVwaWRycwCWt247LSflsCHsB3u0KoLTQJzL1uMl0duij / IF7LCc5FSpIPW7gcjOYj @ jQdpQHv0WUz / IbMhS0XmFiWm1i0cTbxXjsjLxt6nGmQNQoKfREklc8pTFyHub7jUg8TR4QrZ2w3YjaLWNi @ FFerCnNgY0LqgrA6qkWg8H / 7Pv6YhtqeZzvoB0yD5Wm1eLL1Vf / SouI0Q / fox7eQlXieZB1F1v2 / in / btqyVPtubWhDIKH8WaTlry43N6HgOEzX5HOjv1 @ lamBeZlJpqJnG3B2LZe8sXUafdAcVvVjBBlqxbEThCdjpelc7YVuYXOqM8MyVV3iPxbqYu @ nmbHnoKpK1Eww11sA9aiwN8kMe0ioVO7qnucL1A8wHJ4wTsdltrm3CC4bpCd5hMhyDGXSdGgdKvnCKUpNB9nH @ wXLgu5iUEcfJbDKZFjx6gI9i8fCcUFiQXxeSbKnwhT6 @ v / I6yS / Ew9k @ tgI68 / LO @ 4jjx0PZBpSo5vWLCDi4zb @ TJejQQPtvlgde98MDGJ4vUW3T @ iJTA89gGhUJIgy @ MDBpaz3s7PT2ZIwStVANsxpCmhghh68huncD0VdumQt0lT / Su6HW3kMLFfo / FphQ0QhtoZ5iRN / @ Hz / DmHq8UZEgiblprekkw1I366fMhePmDclSxirOlYH2Hwe3fom3aoe1 @ yaQYwi5ZPd2FcITXO7cu9 @ 6tiHZJc7lKSB8e3 / mXx34xYH / 8F @ TUxx / 5vs5yHsYBL4ekscycqT1BnuV19 / "SFE / iRAIL.O NqUXAm. T3zDreu) .S –IOxs ". drere

Aceto , 24 bytes, no competidor

No competir porque tuve que corregir un error en el intérprete.

^




OYpO
r^`!
?d0=   >

Toma una secuencia infinita de líneas y las produce en un orden aleatorio. Cada elemento tiene la posibilidad de ocurrir en cualquier punto aleatorio.

Comenzamos con un ?en la esquina inferior izquierda, que nos mueve en una dirección aleatoria. Si eso es hacia abajo o hacia la izquierda, nos empujan hacia atrás.

Si nos mueven hacia arriba, rañadimos un valor, barajamos la pila ( Y) y volvemos al Origin.

Si nos dmovemos hacia la derecha, duplicamos el valor de la pila superior, presionamos ay probamos la 0igualdad (dado que estamos leyendo cadenas, nunca podremos tener el entero 0). Si los valores son iguales, eso significa que hemos llegado al final de la pila (desde la que no queremos imprimir). Nos negamos la comparación ( !), y print sólo si ( `) las cosas no eran iguales. Luego también volvemos a saltar al Origin.

Ruby, 43 bytes

l=[];loop{l<<gets;l[9]&&$><<l.shuffle!.pop}

Mi respuesta original usaba una lista infinita de evaluación diferida, pero esta es más corta. Oh bien.

MATL , 11 bytes

`rEkN*?D}iT

Pruébalo en línea!

La respuesta Befunge del puerto de histocrat .

Explicación: (Gracias a Luis Mendo por -1 byte)

`         T % Start do-while (`) .... true (T)
 rEk        % 50-50 chance of outputting or inputting:
            %   Random number between 0...1, multiplied by 2 and converted to logical. 
    N       % Check if there is anything on the stack to output
     *?     % If there is anything on the stack and (*) we want to output:
       D    % Output. Sadly, D errors when the stack is empty, requiring the N*
        }i  % Else, input.

Esto produce casi seguramente en tiempo finito, y casi seguramente solo requiere memoria finita .

Para completar, aquí hay una versión de 15 bytes que mantiene un búfer de 10 elementos y genera un elemento aleatorio a partir de eso:

`htnt9>?Yr&)wDT

Me gusta esta versión para los muy idiomáticos (en la medida en que los idiomas de golf pueden ser idiomáticos) tn...Yr&), que extrae un elemento aleatorio de la lista y devuelve la lista sin ese elemento. Sin embargo, la logística particular de este desafío agrega muchos bytes (los requeridos wpara la visualización, t9>?para verificar si la lista está lo suficientemente llena ...).

Alice , 7 bytes

a&IdU,O

Pruébalo en línea!

Esto debería funcionar en una entrada infinita con tiempo y memoria infinitos, pero no es tan fácil de probar en la práctica :)

Explicación

a&I         Push 10 characters from the input to the stack.
     d        Push the depth of the stack.
      U       Pop a number (d), push a random number in [0,d)
        ,       Pop a number (n), move the element which is n elements below the top to the top of the stack.
         O    Output the character on top of the stack.

                Execution loops back to the beginning of the line.

En cada iteración, se leen 10 caracteres de la entrada y solo uno va a la salida, por lo que el uso de la memoria aumenta linealmente durante la ejecución. Con una entrada finita, esto llega rápidamente a EOF, desde el cual diez -1 serán empujados a la pila en cada iteración. Intentar generar -1 como un carácter no tiene ningún efecto, pero es poco probable que todos los caracteres de la entrada se impriman en un tiempo razonable.

La posición i de la salida puede ser tomada por cualquier carácter en la entrada hasta la posición 10i , esto cumple con el desafío que requiere al menos un rango de i-9 a i + 9 .

C, 214 bytes

c;i;char B[19]={0};char*I;
S(p,q){if(B[p]-B[q])B[p]^=(B[q]^=(B[p]^=B[q]));}
R(n){while(n--)putchar(B[c]),B[c]=*I,c=++i%19,I++;}
main(c,v)char**v;{srand(time(0));I=v[1];R(19);i=9;for(;;){S(i,rand()%19);R(1);i=++i%19;}}

Cómo funciona

Probar en línea (UNIX)

#include <stdio.h>
#include <unistd.h>

// animation speed
#define ANIMATION_SLOW 600000
#define ANIMATION_NORMAL 400000
#define ANIMATION_FAST 200000

c;i;char Buffer[19]={0};char*input;
Swap(p,q){if(Buffer[p]!=Buffer[q])Buffer[p]^=(Buffer[q]^=(Buffer[p]^=Buffer[q]));}
Read(n){while(n-->0)putchar(Buffer[c]),Buffer[c]=*input,c=++i%19,input++;}

main(int argc, char**argv)
{
    // initialization
    srand(time(0));
    input=argv[1];
    Read(19);i=9;

    // shuffle machine
    while(1)
    {
        usleep(ANIMATION_NORMAL);
        Swap(i,rand()%19);
        Read(1);
        i=++i%19;
    }
}

05AB1E , 13 bytes

[I)˜¼¾T›i.rć,

Pruébalo en línea! (modificado para tomar 20 elementos)

[             # Infinite loop
 I)˜          # Add the next element from input to the array
    ¼         # Increment the counter variable
     ¾T›i     # If the counter variable is greater than 10...
         .r   #   Get a random permutation of the array
           ć, #   Print and remove the first element 

Bash , 17 bytes

xargs -n9 shuf -e

Pruébalo en línea!

xargs toma continuamente 9 letras de STDIN y las envía a barajar

Una lista infinita puede ser generada por:

yes {a..z}

que imprime abcde .. z infinitas veces.

La prueba puede hacerse por:

yes {a..z} | xargs -n9 shuf -e 

R, 70 bytes

x=NULL;repeat{x=sample(c(x,scan()));if(sum(x|1)>9){cat(x[1]);x=x[-1]}}

Comienza con un vector vacío x. En un bucle infinito, toma un nuevo valor de STDIN, luego baraja el vector. Luego comprueba si la longitud de la lista acumulada es 10 o superior. Si es así, puede comenzar a imprimir. De esta forma, el vector tiene un búfer de 10 entradas, cada una barajada en cada iteración. Por lo tanto, es posible que la entrada se imprima 10 lugares antes e infinitamente muchos lugares después (siguiendo una distribución geométrica con p=1/10). Cuando el búfer es lo suficientemente largo, el primer elemento se imprime y se elimina del vector.

Javascript, 78 bytes

for(l=[];;){l.push(prompt());l.length==10&&alert(l.splice(Math.random()*9,1))};x.sort(()=>Math.random()<0.5);alert(x)}

Utiliza el mismo método que la respuesta de xnor.

Perl 5 , 39 bytes

38 bytes de código + -nbandera.

print splice@F,rand 10,1if 9<push@F,$_

Pruébalo en línea!

Agregue cada elemento a la @Fmatriz (con push@F,$_). Cuando @Fcontiene 10 elementos (por lo tanto, pushdevuelve el número de elementos en la matriz 9<push...), se elimina e imprime un elemento aleatorio ( splice@F,rand 10,1para eliminar el elemento, printimprimirlo).
La salida comienza a suceder después de que se haya leído el décimo elemento. Por lo tanto, cada elemento puede comenzar a aparecer al menos 9 posiciones antes de su original, y puede desplazarse a la derecha infinitamente.

SmileBASIC, 61 58 bytes

@L
B$=B$+R()IF I>8THEN R=RND(9)?B$[R];:B$[R]="
I=I+1GOTO@L

Cada carácter de la lista infinita se agrega al final del búfer. Cuando la longitud del búfer es 11, se imprime y elimina un carácter aleatorio.

La función Rgenera el siguiente carácter.

Prólogo, 70 bytes

s(L):-get0(C),(length(L,9)->random_select(H,L,R),put(H);L=R),s([C|R]).