À propos de la série

Tout d'abord, vous pouvez traiter cela comme n'importe quel autre défi de golf de code et y répondre sans vous soucier de la série. Cependant, il existe un classement pour tous les défis. Vous pouvez trouver le classement avec plus d'informations sur la série dans le premier post .

Trou 8: Mélangez une liste infinie

Vous devez écrire une fonction ou un programme qui prend une liste infinie en entrée et renvoie une version mélangée de cette liste.

À propos des E / S infinies

Il existe plusieurs façons de prendre des entrées et de produire des sorties pour ce défi:

• Vous pouvez soit prendre une liste d'entiers positifs, soit une représentation sous forme de chaîne de ceux-ci, soit une chaîne ou une liste de caractères ASCII imprimables (0x20 à 0x7E, inclus). Le format de sortie doit correspondre au format d'entrée. Je vais simplement désigner les données comme "la liste" à partir de maintenant, quelle que soit l'option que vous choisissez.
• Vous pouvez lire la liste à partir d'un flux d'entrée standard infini et écrire la sortie en continu sur un flux de sortie standard infini. La solution ne doit pas dépendre d'une valeur particulière ou d'une séquence de valeurs pour garantir que le flux de sortie est régulièrement écrit et vidé (par exemple, vous ne pouvez pas simplement écrire la sortie chaque fois qu'il y a un 5dans la liste d'entrée). Bien sûr, si vous lisez une représentation sous forme de chaîne d'une liste, il est normal d'attendre de rencontrer le séparateur de liste.
• Dans les langues qui les prennent en charge, vous pouvez écrire une fonction qui prend et renvoie une liste ou une chaîne infinie paresseuse.
• Dans les langues qui les prennent en charge, vous pouvez implémenter un générateur infini qui prend un autre générateur en entrée.
• Alternativement, vous pouvez écrire une fonction qui ne prend aucun argument et renvoie une valeur de sortie à chaque appel. Dans ce cas, vous pouvez supposer qu'une fonction a été définie qui ne prend aucun argument et renvoie la valeur d'entrée suivante à chaque appel. Vous pouvez librement choisir le nom de cette fonction.

Vous pouvez supposer que votre programme s'exécute pour toujours et qu'une mémoire infinie est disponible. (Il est possible de résoudre ce problème avec une quantité de mémoire limitée, mais cela signifie que vous êtes autorisé à perdre de la mémoire.)

À propos du caractère aléatoire

Pour toute valeur v lue à une position i de l'entrée infinie, il doit y avoir une probabilité positive qu'elle se retrouve dans l'une des positions i-9 à i + 9 de la sortie infinie (à moins que cette position ne soit négative ). Ces probabilités ne doivent pas nécessairement être les mêmes pour différentes positions de sortie ou même pour différentes positions d'entrée. C'est bien si votre solution peut également mélanger les valeurs à une autre position plus éloignée.

Par conséquent, il n'est pas nécessaire que votre solution puisse mélanger la première valeur très loin dans la liste, ou qu'elle puisse mélanger une valeur très tardive jusqu'à la première position, bien que ce soit correct si c'est le cas, tant que toutes les positions se trouvent à 9 étapes de la entrée sont possibles.

Par exemple, si vous avez pris la chaîne suivante en entrée, le ___indique toutes les positions que le Xdoit pouvoir finir dans la sortie:

                  ___________________
 abcdefghijklmnopqrstuvwxyzXabcdefghijklmnopqrstuvwxyz...

Si votre langue ne dispose pas d'un générateur de nombres aléatoires intégré ou si vous ne souhaitez pas l'utiliser, vous pouvez prendre une valeur de départ supplémentaire en entrée et implémenter votre propre RNG approprié à l'aide de la valeur de départ. Cette page peut être utile pour cela.

Quelle que soit la distribution réelle utilisée par votre solution, elle doit presque sûrement produire la valeur suivante après un temps fini (mais arbitraire).

Veuillez inclure une brève explication sur la manière dont votre implémentation satisfait à ces exigences.

Notation

Ceci est un code-golf , donc la plus courte réponse valable - mesurée en octets - victoires.

Classement

Le premier post de la série génère un classement.

Pour vous assurer que vos réponses s'affichent, veuillez commencer chaque réponse par un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les rayant. Par exemple:

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

(La langue n'est pas actuellement affichée, mais l'extrait de code l'exige et l'analyse, et je pourrai ajouter un classement par langue à l'avenir.)

Python 3 , 78 octets

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

Essayez-le en ligne!

Prend l'entrée de STDIN (une par ligne), imprime vers STDOUT.

Conserve un tampon lde jusqu'à 10 éléments. Le tampon est mélangé à chaque étape. Lorsque sa longueur est de 10, le dernier élément est imprimé et supprimé.

Si un élément est imprimé dès qu'il a été inséré, il a sauté devant 9 autres éléments en attente dans la mémoire tampon, il apparaît donc 9 taches. Un élément peut attendre arbitrairement dans la mémoire tampon, donc sa position peut déplacer n'importe quel montant vers la droite.

Il ne semble pas y avoir une bonne façon de produire et de supprimer un élément aléatoire d'une liste. Le brassage semble exagéré. C'est 2 octets de plus à utiliser l.pop(randint(0,9))(qui utilise que la liste a 10 éléments).

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

Ce n'est pas mieux de faire x=choice(l);l.remove(x). Une langue avec poprandomcomme

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

pourrait très proprement faire

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

Befunge ( saveur excentrique ), 4 octets

?,?~

,lit un personnage du flux et le pousse sur la pile. ~sort le premier caractère de la pile (si présent) et l'imprime. ?randomise quelle commande est exécutée ensuite. Donc, l'algorithme est ici "dans une boucle infinie, avec une probabilité égale, soit pousser un caractère ou pop un caractère." Je pense que cela satisfait les exigences: un personnage peut voir arbitrairement de nombreux caractères ajoutés au-dessus de lui dans la pile, donc il peut se déplacer arbitrairement loin vers la droite, et il peut être imprimé lorsque la pile est arbitrairement grande, donc il peut se déplacer arbitrairement loin vers la gauche.

C (gcc) , 94 octets

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();}

Essayez-le en ligne!

Ok, un lien TIO n'a pas beaucoup de sens. Pour faciliter les tests, j'ai créé le programme C suivant qui produira des caractères ascii aléatoires ou répétera une chaîne à l'infini.

#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++]);
        }
    }
}

Ce programme sera appelé iro.

Exactitude du programme

Ce que je fais ici, c'est lire les 9valeurs dans un tampon. Après cela, des indices aléatoires sont choisis dans ce tableau et sont sortis, puis remplacés par le caractère suivant dans le flux.

SILOS , 149 octets

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

Essayez-le en ligne!

Essentiellement, il continue de prendre des informations (sur l'interpréteur en ligne via des arguments, mais sur l'interpréteur officiel hors ligne, il vous permettra de taper dans la console (à l'infini)) par blocs de 15 à la fois (30 le premier bloc).

Il charge l'entrée dans une file d'attente temporaire et sélectionne un 15 chanceux (au hasard, mais pas également distribué en termes de probabilité ou de distribution).

Le reste reste là où de nouvelles entrées remplissent la file d'attente, la première entrée pourrait être mélangée jusqu'à la fin (en gros, je pense que les personnages suivent une distribution normale). Il est intéressant de noter que ce programme n'est que deux fois plus verbeux que python et peut-être "golfeur" que Java.

Pour mieux voir les résultats, j'ai une version non conforme qui prend l'entrée sous forme de chaîne (mais elle ne peut contenir que 8 000 caractères environ).

Essayez-le en ligne!

Juste pour le plaisir, voici ce post alimenté par la version chaîne.

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

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

    e
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 ie

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 firsck
hs 0It te 
 lodshipo alauttt.mpra quuet i reanicks a lck eooy d randomyn p 15 (uo equl, unbtty drbutedaynistinems oflyly 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 vroscpernebavs aposcperneonavs ef "
 tte s / "gt 
obterelIe tsvea non-omhTrehs a plntvesion hcahihk ine teuts sriprics at rwvritcaw aa g (hoee n onl kein n00 orscat, 0 cter).

[Tyauoas on on! 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. "dréré

Aceto , 24 octets, non concurrent

Non concurrent car j'ai dû corriger un bug dans l'interpréteur.

^




OYpO
r^`!
?d0=   >

Prend un flux infini de lignes et les produit dans un ordre aléatoire. Chaque élément a une chance de se produire à tout moment aléatoire.

Nous commençons par un ?dans le coin inférieur gauche, qui nous déplace dans une direction aléatoire. Si c'est vers le bas ou vers la gauche, nous sommes repoussés tout de suite.

Si nous sommes déplacés vers le haut, nous rlisons une valeur, mélangeons la pile ( Y) et revenons au Origin.

Si nous sommes déplacés vers la droite, nous drépliquons la valeur de pile supérieure, poussons a 0et testons l'égalité (puisque nous lisons des chaînes, nous ne pouvons jamais avoir l'entier 0). Si les valeurs sont égales, cela signifie que nous avons atteint le bas de la pile (à partir de laquelle nous ne voulons pas imprimer). Nous nions la comparaison ( !) et pn'imprimons que si ( `) les choses n'étaient pas égales. Ensuite, nous revenons également au Origin.

Rubis, 43 octets

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

Ma réponse originale utilisait une liste infinie évaluée paresseusement, mais elle est plus courte. Tant pis.

MATL , 11 octets

`rEkN*?D}iT

Essayez-le en ligne!

Réponse de Befunge du port d' histocrate .

Explication: (Merci à Luis Mendo pour -1 octet)

`         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.

Cela produit presque sûrement en temps fini, et ne nécessite presque sûrement qu'une mémoire finie .

Pour être complet, voici une version à 15 octets qui conserve un tampon à 10 éléments et génère un élément aléatoire à partir de cela:

`htnt9>?Yr&)wDT

J'aime cette version pour le très idiomatique (dans la mesure où les langues de golf peuvent être idiomatiques) tn...Yr&), qui fait apparaître un élément aléatoire dans la liste et renvoie la liste sans cet élément. Cependant, la logistique particulière de ce challenge ajoute beaucoup d'octets (le nécessaire wà l'affichage, le t9>?pour vérifier si la liste est assez pleine ...).

Alice , 7 octets

a&IdU,O

Essayez-le en ligne!

Cela devrait fonctionner sur une entrée infinie avec un temps et une mémoire infinis, mais ce n'est pas si facile à tester dans la pratique :)

Explication

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.

À chaque itération, 10 caractères sont lus à partir de l'entrée et un seul va à la sortie, donc l'utilisation de la mémoire augmente linéairement pendant l'exécution. Avec une entrée finie, cela atteint rapidement EOF, à partir duquel dix -1 seront poussés vers la pile à chaque itération. Essayer de sortir -1 en tant que caractère n'a aucun effet, mais il est peu probable que tous les caractères de l'entrée soient imprimés dans un délai raisonnable.

La position i de la sortie peut être prise par n'importe quel caractère dans l'entrée jusqu'à la position 10i , ce qui répond au défi nécessitant au moins une plage de i-9 à i + 9 .

C, 214 octets

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;}}

Comment ça marche

Essayez en ligne (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 octets

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

Essayez-le en ligne!(modifié pour prendre 20 éléments)

[             # 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 

Frapper , 17 octets

xargs -n9 shuf -e

Essayez-le en ligne!

xargs prend continuellement 9 lettres de STDIN et les envoie au shuffle

une liste infinie peut être générée par:

yes {a..z}

qui imprime abcde .. z des temps infinis.

Le test pourrait être effectué par:

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

R, 70 octets

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

Commence par un vecteur vide x. Dans une boucle infinie, il prend une nouvelle valeur de STDIN, puis mélange le vecteur. Ensuite, il vérifie si la longueur de la liste accumulée est de 10 ou plus. Si c'est le cas, l'impression peut commencer. De cette façon, le vecteur a un tampon de 10 entrées, chacune étant mélangée à chaque itération. Il est donc possible d'imprimer 10 entrées plus tôt et infiniment plus tard (en suivant une distribution géométrique avec p=1/10). Lorsque le tampon est suffisamment long, le premier élément est imprimé et supprimé du vecteur.

Javascript, 78 octets

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

Utilise la même méthode que la réponse de xnor.

Perl 5 , 39 octets

38 octets de code + -nindicateur.

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

Essayez-le en ligne!

Ajoutez chaque élément au @Ftableau (avec push@F,$_). Lorsqu'il @Fcontient 10 éléments ( pushrenvoie le nombre d'éléments dans le tableau, donc 9<push...), un élément aléatoire est supprimé et imprimé ( splice@F,rand 10,1pour supprimer l'élément, printpour l'imprimer).
La sortie commence à se produire après la lecture du 10e élément. Par conséquent, chaque élément peut commencer à apparaître au moins 9 positions avant sa position d'origine et peut être déplacé vers la droite à l'infini.

SmileBASIC, 61 58 octets

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

Chaque caractère de la liste infinie est ajouté à la fin du tampon. Lorsque la longueur de la mémoire tampon est de 11, un caractère aléatoire est imprimé et supprimé.

La fonction Rgénère le caractère suivant.

Prolog, 70 octets

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