Sobre a série

Primeiro, você pode tratar isso como qualquer outro desafio de código de golfe e respondê-lo sem se preocupar com a série. No entanto, existe uma tabela de classificação em todos os desafios. Você pode encontrar a tabela de classificação junto com mais informações sobre a série no primeiro post .

Buraco 8: embaralhar uma lista infinita

Você deve escrever uma função ou programa que use uma lista infinita como entrada e retorne uma versão aleatória dessa lista.

Sobre E / S infinita

Existem várias maneiras pelas quais você pode receber e produzir resultados para este desafio:

• Você pode fazer uma lista de números inteiros positivos ou uma representação de sequência, ou uma sequência ou lista de caracteres ASCII imprimíveis (0x20 a 0x7E, inclusive). O formato de saída deve corresponder ao formato de entrada. Vou me referir aos dados como "a lista" a partir de agora, independentemente da opção que você escolher.
• Você pode ler a lista de um fluxo de entrada padrão infinito e gravar a saída continuamente em um fluxo de saída padrão infinito. A solução não deve depender de nenhum valor específico ou sequência de valores para garantir que o fluxo de saída seja gravado e liberado regularmente (por exemplo, você não pode simplesmente gravar a saída sempre que houver uma 5na lista de entrada). Obviamente, se você ler uma representação de string de uma lista, não há problema em esperar até encontrar o separador de listas.
• Nos idiomas que os suportam, você pode escrever uma função que pega e retorna uma lista ou sequência lenta e infinita.
• Nas linguagens que os suportam, você pode implementar um gerador infinito que aceita outro gerador como entrada.
• Como alternativa, você pode escrever uma função que não aceita argumentos e retorna um valor de saída cada vez que é chamado. Nesse caso, você pode assumir que uma função foi definida que não aceita argumentos e retorna o próximo valor de entrada cada vez que é chamada. Você pode escolher livremente o nome dessa função.

Você pode supor que seu programa seja executado para sempre e que haja memória infinita disponível. (É possível resolver isso com uma quantidade finita de memória, mas o que isso significa é que você pode vazar memória.)

Sobre a aleatoriedade

Para qualquer valor v que seja lido na posição i da entrada infinita, deve haver uma probabilidade positiva para que ele termine em qualquer uma das posições i-9 a i + 9 da saída infinita (a menos que essa posição seja negativa ) Essas probabilidades não precisam ser as mesmas para diferentes posições de saída ou mesmo para diferentes posições de entrada. Tudo bem se sua solução também puder embaralhar os valores para outras posições mais distantes.

Portanto, não é necessário que sua solução possa embaralhar o primeiro valor muito abaixo da lista ou embaralhar um valor muito tardio até a primeira posição, embora seja bom se o fizer, desde que todas as posições a 9 passos da entrada é possível.

Por exemplo, se você pegou a seguinte string como entrada, ___indica todas as posições que Xdevem ser capazes de terminar na saída:

                  ___________________
 abcdefghijklmnopqrstuvwxyzXabcdefghijklmnopqrstuvwxyz...

Se seu idioma não possui um gerador de números aleatórios embutido ou você não deseja usá-lo, você pode usar um valor adicional de semente como entrada e implementar seu próprio RNG adequado usando a semente. Esta página pode ser útil para isso.

Independentemente da distribuição real que sua solução usa, ela quase certamente deve produzir o próximo valor após um tempo finito (mas arbitrário).

Inclua uma breve explicação sobre como sua implementação atende a esses requisitos.

Pontuação

Isso é código-golfe , então a resposta mais curta e válida - medida em bytes - vence.

Entre os melhores

O primeiro post da série gera uma tabela de classificação.

Para garantir que suas respostas sejam exibidas, inicie todas as respostas com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

(O idioma não é mostrado no momento, mas o snippet exige e o analisa, e eu posso adicionar um cabeçalho por idioma no futuro.)

Python 3 , 78 bytes

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

Experimente online!

Pega a entrada de STDIN (uma por linha), imprime em STDOUT.

Mantém um buffer lde até 10 elementos. O buffer é embaralhado a cada etapa. Quando seu comprimento é 10, o último elemento é impresso e removido.

Se um elemento for impresso assim que foi inserido, ele saltou à frente de outros 9 elementos aguardando no buffer e, portanto, aparece 9 pontos restantes. Um elemento pode esperar arbitrariamente no buffer por muito tempo, para que sua posição possa mover qualquer valor certo.

Não parece haver uma boa maneira de produzir e remover um elemento aleatório de uma lista. Baralhar parece exagero. É 2 bytes mais longo para usar l.pop(randint(0,9))(que usa que a lista possui 10 elementos).

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

Ele não é melhor é fazer x=choice(l);l.remove(x)a linguagem .A com poprandomcomo

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

poderia muito bem fazer

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

Befunge ( sabor quirkster ), 4 bytes

?,?~

,lê um caractere do fluxo e o coloca na pilha. ~aparece o caractere superior da pilha (se houver) e o imprime. ?randomiza qual comando será executado a seguir. Portanto, o algoritmo aqui é "Em um loop infinito, com probabilidade igual de pressionar um caractere ou exibir um caractere". Acho que isso satisfaz os requisitos: um personagem pode ver arbitrariamente muitos caracteres adicionados acima dele na pilha, para que possa se mover arbitrariamente para a direita e pode ser impresso quando a pilha é arbitrariamente grande, para que possa se mover arbitrariamente para longe. a esquerda.

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

Experimente online!

Ok, um link TIO não faz muito sentido. Para facilitar o teste, criei o seguinte programa C que produzirá caracteres aleatórios ascii ou repetirá uma sequência 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 será referido como iro.

Correção do programa

O que faço aqui é ler 9valores em um buffer. Depois disso, os índices aleatórios são escolhidos nessa matriz e são gerados e substituídos pelo próximo caractere no fluxo.

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

Experimente online!

Essencialmente, ele continua recebendo informações (no intérprete on-line por meio de argumentos, mas no intérprete oficial off-line, ele permite que você digite no console (infinitamente)) em blocos de 15 por vez (30 no primeiro bloco).

Ele carrega a entrada em uma fila temporária e escolhe 15 sortudos (aleatoriamente, mas não igualmente distribuídos em termos de probabilidade ou distribuição).

O restante permanece enquanto novas entradas preenchem a fila, a primeira entrada pode ser embaralhada até o fim (basicamente acho que os caracteres seguem uma distribuição normal). É interessante notar que este programa é apenas duas vezes mais detalhado que o python e talvez "mais golfista" que o Java.

Para ver melhor os resultados, eu tenho uma versão não compatível que recebe a entrada como uma string (no entanto, pode conter apenas 8.000 caracteres).

Experimente online!

Apenas por diversão, aqui está este post alimentado através da versão string.

 [.L.Ooy "9beS.IS]", 14 st b1
 apenas

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

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

htpsgthyx]: iub.om/jhujh .. tcraa.IOo /TytonieSu:wl/.L lnn!: tt / iS
[Em hsto.un / nuslprxRUCoDsio /]: e#NzZn6j4c/2xNQFnF7y0aLzkrosd9Dov2yxJNx774HBrgPUdi9CySI09sCLw5TJwB7jlB1XVeQFE7m1VMsIQvDOjBmdtME3umNzYXs9unFbqRamVDfUDw@RT3NHoL7/i04bz16DCoP4eulOU7jPD8OmYjATpynkuMDuBPYmtnIJzseyyhaNkMyQgXG2R782vqMDIiUm6Kq4Q3mJkxlUsR1rrldPw./l28Z SL.XS - IONuscOT "
senallyxMz.stiitkp ingN "
 O objetivo deste artigo é apresentar uma revisão bibliográfica sobre o tema, com o objetivo de apresentar uma revisão bibliográfica sobre o tema, bem como abordar os principais temas abordados no livro.
hs 0É 
 lodshipo alauttt.mpra quuet i reanicks a lck eaoy d randomyn p 15 (uo equl, unbtty drbutedaynistinems oftrly ordisrprob abition h ibttmin.Tet ri)
 nwit u ree nusfil th queusen 
pte ftip, e a última atualização ocorre em todo o mundo, em parte por um ramo (sc ho noreiItrolwaaldibtio lmiru.t 'mais à frente), que mostra apenas os prasnon hogIms.
 tte s / "gt 
obter tsvea non-omhTrehs uma plntvesion hcahihk ine teuts sriprics e rwvritcaw aa g (hoee n onl kein n00 orscat, 0 cter).

[Você está online! Hrhrys :.ru] p // o / lsslo # jVd (tinnexi3E @ KDpit / LrhtwXwVEUuscxPmJjFFCaNimMzlHiQEcMmdVIT7vqs8mNgxU3mD / J1AwXq / @ ivbao1j nb4I6 / m93655bThmb4cy5TUX3xvI018cZzrXItuO5B @ NX5JD / HzyE @ L @ @ D5eqrGem3l0HPGRutZfpi2PzVA d3CVRTm4zJxnZdcFSTEO0JOT9KhDI6byjnLhS0cNmGz7hJrTdAgORT8Ndvv7DgZSbJdkp9v5al8qMyNCb9tXe0ChrShXRTOt @ 7fFgV3zTkbVbsD @ JpKina2oKgNVakjsjLCpD29u7l0XVRWalVTyArF1FqypQAxXb / BedqUqpJGOPVyxOjLj0jXup8cE277L2I6 @ lSowK5pA7nGldRBiJwyKxF6z2c3kW / sJ4EYBbbpSuBxs55nyI9sdnu @ nJJeGqtKprGEUbc6NDGMjjO2tN / KuKTWh2WWbbRRLVaq / P6KqkoMNWGRgTQZLlbXfQI050bY0rz0xmzCVZ4vowjpV0dCmkDFq0VNa5GSDzVn5Qw7idwPTxu5xTAtLQCDN / YIApfAn4dsDmYksCqUU27sRggpzRK4SmdjmPUPQO4j5FmgHMFRWS2eI1CfA2YIcf7JlylFjdZypVTH0IJu4ZJHiUviyBFKqhrkCjgXAAB8d710NhHgDwcJksuvPPprcfzHPTaJGFX8OIExW / cBZjaPiY7a4WD6rTYmOouBVucROlwvuBJiHWdJQjjbobNGTd7M1P6z8dw / Um @ 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. "ddd

Aceto , 24 bytes, não concorrente

Não concorrente porque tive que corrigir um erro no intérprete.

^




OYpO
r^`!
?d0=   >

Pega um fluxo infinito de linhas e as produz em uma ordem aleatória. Todo elemento tem uma chance de ocorrer em qualquer ponto aleatório.

Começamos com um ?no canto inferior esquerdo, o que nos move em uma direção aleatória. Se isso é baixo ou esquerdo, somos empurrados para trás.

Se formos movidos para cima, rcalculamos um valor, embaralhamos a pilha ( Y) e voltamos ao Origin.

Se formos movidos para a direita, dduplicamos o valor da pilha superior, pressionamos a 0e testamos a igualdade (já que estamos lendo strings, nunca podemos ter o número inteiro 0). Se os valores forem iguais, isso significa que alcançamos a parte inferior da pilha (da qual não queremos imprimir). Nós negar a comparação ( !), e pRint somente se ( `) as coisas não eram iguais. Depois, também voltamos ao Origin.

Ruby, 43 bytes

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

Minha resposta original usou uma lista infinita avaliada preguiçosamente, mas é mais curta. Ah bem.

MATL , 11 bytes

`rEkN*?D}iT

Experimente online!

Porto da resposta Befunge do histocrata .

Explicação: (Agradecimentos 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.

Isso produz quase certamente em tempo finito e quase certamente requer apenas memória finita .

Para completar, eis uma versão de 15 bytes que mantém um buffer de 10 elementos e gera um elemento aleatório a partir disso:

`htnt9>?Yr&)wDT

Eu gosto desta versão pelo muito idiomático (na medida em que os idiomas do golfe podem ser idiomáticos) tn...Yr&), que exibe um elemento aleatório da lista e retorna a lista sem esse elemento. No entanto, a logística específica desse desafio adiciona muitos bytes (o necessário wpara a exibição, t9>?para verificar se a lista está cheia o suficiente ...).

Alice , 7 bytes

a&IdU,O

Experimente online!

Isso deve funcionar em uma entrada infinita com tempo e memória infinitos, mas não é tão fácil de testar na prática :)

Explicação

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.

A cada iteração, 10 caracteres são lidos na entrada e apenas um vai para a saída; portanto, o uso da memória aumenta linearmente durante a execução. Com uma entrada finita, isso atinge rapidamente o EOF, do qual dez -1 serão enviados para a pilha a cada iteração. Tentar produzir -1 como um caractere não tem efeito, mas é improvável que todos os caracteres da entrada sejam impressos em um período de tempo razoável.

A posição i da saída pode ser tomada por qualquer caractere na entrada até a posição 10i , isso está de acordo com o desafio que requer pelo menos um intervalo 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;}}

Como funciona

Experimente on-line (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ć,

Experimente online! (modificado para receber 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

Experimente online!

xargs pega continuamente 9 letras de STDIN e as envia para embaralhar

uma lista infinita pode ser gerada por:

yes {a..z}

que imprime abcde .. z infinitas vezes.

O teste pode ser realizado 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]}}

Inicia com um vetor vazio x. Em um loop infinito, ele pega um novo valor de STDIN e embaralha o vetor. Em seguida, verifica se o comprimento da lista criada é 10 ou superior. Se for, pode começar a imprimir. Dessa forma, o vetor possui um buffer de 10 entradas, cada uma sendo embaralhada a cada iteração. Portanto, é possível que a entrada seja impressa 10 lugares antes e infinitamente muitos lugares depois (seguindo uma distribuição geométrica com p=1/10). Quando o buffer é longo o suficiente, o primeiro elemento é impresso e removido do vetor.

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

Usa o mesmo método da resposta do xnor.

Perl 5 , 39 bytes

38 bytes de código + -nsinalizador.

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

Experimente online!

Adicione cada elemento à @Fmatriz (com push@F,$_). Quando @Fcontém 10 elementos ( pushretorna o número de elementos na matriz, portanto 9<push...), um elemento aleatório é removido e impresso ( splice@F,rand 10,1para remover o elemento, printimprimi-lo).
A saída começa a acontecer após o 10º elemento ter sido lido. Portanto, cada elemento pode começar a aparecer pelo menos 9 posições antes do original e pode ser deslocado para a direita infinitamente.

SmileBASIC, 61 58 bytes

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

Cada caractere da lista infinita é adicionado ao final do buffer. Quando o tamanho do buffer é 11, um caractere aleatório é impresso e removido.

Função Rgera o próximo caractere.

Prolog, 70 bytes

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