Un modèle de Markov simple sera utilisé dans cette question. Pour plus d'informations sur les chaînes de Markov, voir http://setosa.io/ev/markov-chains/ .

Prenez une ficelle. Pour cet exemple, nous utiliserons le mot:

reader

Maintenant, pour chaque caractère, prenez les caractères qui apparaissent après chaque occurrence du caractère dans la chaîne. ( ​`^`​représente le début de la chaîne et ​`$`​représente la fin)

`^` -> {'r'}       # After the start of the string, there is an `r`.
'r' -> {'e', `$`}  # After the first `r` (*r*eader), there is an `e`
                   # after the second (reade*r*), there is the end of the string.
'e' -> {'a', 'r'}
'a' -> {'d'}
'd' -> {'e'}

Maintenant, à partir du début de la chaîne, choisissez aléatoirement l'un des caractères du jeu suivant. Ajoutez ce personnage, puis choisissez parmi les personnages de son prochain ensemble, et ainsi de suite jusqu'à la fin. Voici quelques exemples de mots:

r
rereader
rer
readereader

Si un personnage apparaît plusieurs fois après un autre personnage, il est plus susceptible d'être choisi. Par exemple, dans cocoa can, après un c, il y a deux tiers de chance d'obtenir un oet un tiers de chance d'obtenir un a.

'c' -> {'o', 'o', 'a'}

Défi

Créez un programme qui ne prend aucune entrée et génère une chaîne aléatoire générée à l'aide d'une chaîne de Markov, comme ci-dessus, où l'entrée de la chaîne est la source du programme.

1. Le programme doit avoir au moins deux caractères, dont deux doivent être identiques (pour éviter les chaînes "ennuyeuses" qui n'ont qu'une seule sortie)
2. Vous pouvez modifier le modèle pour utiliser des octets au lieu de caractères si vous le souhaitez, mais changer "caractères" en "octets" dans la règle 1
3. Le programme devrait produire des chaînes de façon aléatoire avec la fréquence attendue en théorie

C'est du golf de code , donc le programme le plus court gagne!

Pip , 64 octets

C'était amusant.

t:V Y\"m:"Yt@0T9=A OyY@>RC(t(Xy).'.)"ST["t:V Y"RPy";Vm"C9]\";Vm<tab>

<tab>représente un caractère de tabulation littéral ( 0x09). Essayez-le en ligne!

Comment?

TL; DR: syntaxe de chaîne d'échappement, repr et eval.

Pour les chaînes qui doivent contenir des "caractères littéraux , Pip a échappé les chaînes , en utilisant \"comme délimiteur. Un quine standard utilisant des chaînes d'échappement ressemblerait à ceci:

V Y\""V Y".RPy\"

C'est-à-dire: Yank (stockage en tant que y) une chaîne contenant "V Y".RPyet e Val. RPyprend la repr de y, à laquelle nous ajoutons la chaîne littérale V Y. Enfin, affichez le résultat de l'évaluation.

La structure du quine Markov est similaire, sauf que nous voulons enregistrer le code au lieu de le sortir et ensuite faire quelques trucs avec. t:V Y\"...\"affecte le résultat de l'évaluation à t. À l'intérieur du code évalué, m:"..."assigne une chaîne de code à mlaquelle nous évaluerons à la fin Vm.

ST["t:V Y"RPy";Vm"C9] construit une liste contenant

"t:V Y"  Literal string
RPy      Repr(y)
";Vm"    Literal string
C9       Tab character

et le convertit en une chaîne qui, par défaut, concatène tous les éléments. Cette section est équivalente à celle "V Y".RPydu quine d'origine. Comme il s'agit de la dernière expression de la grande chaîne d'évaluation, sa valeur correspond à ce que l' Vopérateur retourne et donc à ce qui lui est attribué t.

Ainsi, après l'évaluation et l'affectation, test égal au code complet et mcontient

Yt@0T9=A OyY@>RC(t(Xy).'.)

Évalue maintenant Vmcela en tant que code. Décomposons ce qui se passe.

                            We'll use y to hold the current character in the chain
Yt@0                        Yank first character of t into y (chain always starts there)
         Oy                 Output y without newline each time we...
    T9=A                    Loop till ASCII code of y equals 9 (tab)
                            Since there's only one literal tab, at the end of the program,
                              this satisfies the Markov chain ending requirement
                   Xy       Generate a regex that matches y
                  (  ).'.   Concatenate . to regex: now matches y followed by any character
                (t       )  Find all matches in t (returns a list)
              RC            Random choice from that list
           Y@>              Slice off the first character and yank the remaining one into y

Quelques notes:

• Terminer le code avec un onglet littéral était plus court que de faire un test d'expression régulière pour "le caractère suivant ou la fin de la chaîne".
• Le regex que j'ai utilisé ne fonctionne pas correctement s'il y a des caractères doublés dans le code; par exemple, l'appliquer à xxyreviendrait uniquement xxet non xydans les correspondances. Heureusement, cependant, il n'y a pas de caractères doublés dans ce code, donc cela n'a pas d'importance.

JavaScript, 217 215 octets

a="a=q;a=a.replace('q',uneval(a));for(b=c='a';d=a.split(c),c=d[Math.random()*~-d.length+1|0][0];b+=c);alert(b)";a=a.replace('q',uneval(a));for(b=c='a';d=a.split(c),c=d[Math.random()*~-d.length+1|0][0];b+=c);alert(b)

Notez que cela utilise uneval, qui n'est pris en charge que par Firefox. Exemples de cycles:

a=ale(a.lend[Ma=d[Macepla.ler(b+=c)b=q;fom(a=q;a=dort(b+1|0],c);a.lit(a)
at(c=c;d[0],c=q;ath+1|0][0];dorerac=ac=d[Ma),c;)*~-d[Ma=alenepl(b+=ac=c;a=c;d[2];d.re(c;fom()
a="a[0],und=d=a)
angt(b),und=d.l(b=a)
a)
ale(a.rth.revanepleplit(b)
ac);fore(b)*~-d.r(b+1|0];fora';a)*~-d.splalith+=dorth+=c=";ath+=a.length+=';ale(b)
a.r(b=c=a)b+1|0],und[0][0];d.splerath.spleneva)";ath.r(ceneplith+=d=aceple(c;)*~-d=';ala';)b='ac;fom(b=c;a.ler(b=d=d[Ma.rt(c=cendor()*~-d='a=";ac;a.spla)b=ceva=';a=d.rt(angt(alength+1|0],c;angt()
al(ac=dorth+1|0][0][0][0][Ma.split()

Comme vous pouvez le voir, c'est surtout du charabia, mais c'est normal ;) L'OP a créé un JSFiddle qui démontre que la probabilité qu'une sortie soit JS syntaxiquement valide est d'environ 6,3%.

Si les fonctions d'auto-lecture étaient autorisées, cela pourrait être 78 octets d'ES6:

f=(c="f",p=("f="+f).split(c),q=p[Math.random()*~-p.length+1|0][0])=>q?c+f(q):c

Très, très rarement, cela génère un JS syntaxiquement valide:

f=>e?c+f():c
f=>e?c=>engt():c
f=>e?c=(e):c
f=>e?c=>e=>ength.split():c
f=p=>q?c+f():c
f(q).sp=",p[Mat(q?c=(),plith.lith.sp.sp[0]).lendom().lith+f=>q=p.lendom(",p=p=>q?c+f():c
f(q),q?c=(c=(q)*~-p[0]):c
f().random(),q?c=(c=p[0]):c
f=>q?c=(q="+f"+f).rath.split(c):c
f="+1|0])=().lith.rat()*~-p=>q?c=p[Mat(c=",q?c=p.rath.splendom()*~-plength.splith.lendom(c):c

Mon préféré des noms de fonctions qu'il a créés est .splendom()( split+ length+ random)

Perl, 103 octets

Sur la base du quine standard et ma réponse à cette question :

$_=q{$_="\$_=q{$_};eval";@s='$';{push@s,(@n=/(?<=\Q$s[-1]\E)(.|$)/g)[rand@n];$s[-1]&&redo}print@s};eval

Exemple de sortie

$_=q{$_=q{$_=";@sh@s=";eval
$_="\$_=q{$_='$_=q{$_}pus=\$_=";@n=";@ndo};{pus=';edo};@n]\Q$_};{$_};@s=q{$_=';@s[rand@s=/g)(@s,(@s,(@sh@s[-1];@ndo};ed@s[-1]\E)(.|$_}prevan]&ral";evan];{$_}pus='$_};ed@sh@sh@s[-1]\$_='$_};evando};eval
$_=q{$_=";ed@s[-1];evand@s="\Q$_=";@s[-1]\Q$_=q{$_=";@nd@sh@sh@s='$_=q{$_=q{$_='$_="\Q$_='$_};{pus=\$_=q{$_}pral
$_=";evando};@nd@sh@s,(@n]\$_=";@s,(@s[-1];{$_=q{$_}pral
$_=";eval
$_='$_=q{$_="\$_="\Q$_=";ed@sh@s=\E)(.|$_=q{$_=q{$_=q{$_=q{$_}pus=/(?<=q{$_};eval
$_=";ed@sh@s[-1]\Q$_=';edo};{$_=q{$_=";@nt@s,(@n]&&&&&&&ral";@nd@s,(@s[-1]\$_}pus=\E)(.|$_=';@nt@s[ral

De manière similaire à l'autre question, certains résultats génèrent du Perl valide:

$_=q{$_};{$_};eval";@sh@s[-1]\$_='$_};evan]\Q$_}preval";eval
$_=q{$_};{$_=q{$_=';@nd@s=q{$_};@s[-1]\E)(@s[-1]\E)(@n=';edo};{$_}predo};eval
$_=q{$_=q{$_};edo};@n=q{$_=q{$_};@s[rin='$_=q{$_}pus=/g)(.|$_=q{$_};edo};eval
$_=q{$_};eval
$_=q{$_=";@ndo};{$_}preval

mais les chances sont légèrement inférieures, à ~ 2%.

Code machine MS-DOS (fichier .COM), 63 octets - non concurrent

Non concurrent car un quine ne doit pas accéder à son propre code source.

Une variante de 126 octets répondrait à l'exigence "ne pas accéder à son propre code source"!

La variante de 63 octets ressemble à ceci:

FC BE 00 01 AC 50 88 C2 B4 02 CD 21 E8 1A 00 59
4E AC 81 FE 3F 01 7C 03 BE 00 01 38 C1 75 F2 FE
CA 75 EE 81 FE 00 01 75 DB 8A 16 00 80 31 C0 8E
D8 31 C9 AC 00 C2 E2 FB 0E 1F 88 16 00 80 C3

Je ne suis pas sûr non plus de la distribution de probabilité du générateur aléatoire:

Le programme utilise le fait que les compteurs d'horloge et autres informations modifiées par des interruptions sont stockées dans le segment 0 pour générer des nombres aléatoires.

Voici des exemples de sorties générées:

FC BE 00 01 7C 03 BE 00 80 C3

FC BE 00 01 38 C1 75 F2 FE 00 80 31 C9 AC 81 FE 00 80 C3

FC BE 00 01 38 C1 75 EE 81 FE 00 01 38 C1 75 EE 81 FE CA
75 F2 FE 00 01 75 F2 FE 00 80 C3

FC BE 00 C2 B4 02 CD 21 E8 1A 00 01 7C 03 BE 00 59 4E AC
81 FE 3F 01 AC 81 FE 3F 01 7C 03 BE 00 01 7C 03 BE 00 01
AC 81 FE 3F 01 7C 03 BE 00 80 C3

Converti en code assembleur, le programme ressemble à ceci:

    cld                # Ensure SI is being incremented
    mov si, 0x100      # Move SI to the first byte of the program
nextOutput:
    lodsb              # Load one byte of the program ...
    push ax            # ... save it to the stack ...
    mov dl, al         # ... and output it!
    mov ah, 2
    int 0x21
    call pseudoRandom  # Create a random number (in DL)
    pop cx             # Take the stored byte from the stack
    dec si             # Go back to the last byte loaded
nextSearch:
    lodsb              # Load the next byte
    cmp si, programEnd # If we loaded the last byte ...
    jl notEndOfProgram # ... the next byte to be loaded ...
    mov si, 0x100      # ... is the first byte of the program.
notEndOfProgram:
    cmp cl, al         # If the byte loaded is not equal to ...
                       # ... the last byte written then ...
    jne nextSearch     # ... continue at nextSearch!
    dec dl             # Decrement the random number and ...
    jnz nextSearch     # ... continue at nextSearch until the ...
                       # ... originally random number becomes zero.
    cmp si, 0x100      # If the last byte read was not the last byte ...
    jnz nextOutput     # ... of the program then output the next ...
                       # ... byte!

    # Otherwise fall through to the random number generator
    # whose "RET" instruction will cause the program to stop.        

    # The random number generator:
pseudoRandom:
    mov dl, [0x8000]   # Load the last random number generated
                       # (Note that this is uninitialized when
                       # this function is called the first time)
    xor ax, ax         # We use segment 0 which contains the ...
    mov ax, ds         # ... clock information and other data ...
                       # ... modified by interrupts!
    xor cx, cx         # Prepare for 0x10000 loops so ...
                       # ... all bytes in the segment are processed ...
                       # ... once and the value of SI will be ...
                       # ... unchanged in the end!
randomNext:
    lodsb              # Load one byte
    add dl, al         # Add that byte to the next random number
    loop randomNext    # Iterate over all bytes
    push cs            # Restore the segment
    pop ds
    mov [0x8000], dl   # Remember the random number
    ret                # Exit sub-routine

programEnd:

C, 306 328 585 611 615 623 673 707 octets

Code source:

p[256][256]={0};char*X="p[256][256]={0};char*X=%c%s%c,Y[999],c,j,*a;main(){sprintf(Y,X,34,X,34);for(a=Y;*a;a++)p[*a][*(a+1)]++;for(j=*Y;putchar(c=j);)while(p[c][++j]<<16<rand());}",Y[999],c,j,*a;main(){sprintf(Y,X,34,X,34);for(a=Y;*a;a++)p[*a][*(a+1)]++;for(j=*Y;putchar(c=j);)while(p[c][++j]<<16<rand());}

Avec des nouvelles lignes et des espaces ajoutés pour plus de lisibilité / explication:

01  p[256][256]={0};
02  char*X="p[256][256]={0};char*X=%c%s%c,Y[999],c,j,*a;main(){sprintf(Y,X,34,X,34);for(a=Y;*a;a++)p[*a][*(a+1)]++;for(j=*Y;putchar(c=j);)while(p[c][++j]<<16<rand());}",
03  Y[999],c,j,*a;
04  main(){
05      sprintf(Y,X,34,X,34);
06      for(a=Y;*a;a++)p[*a][*(a+1)]++;
07      for(j=*Y;putchar(c=j);)
08          while(p[c][++j]<<16<rand());
09  }

Explication

Line 01: p[][] contient les décomptes d'un personnage après l'autre.

Line 02: Xcontient la source du programme, échappé avec%c%s%c .

Line 03: Ycontiendra la source littérale du programme. c, j,*a Sont des variables de comptage.

Line 05: Ensemble Y pour contenir le quine.

Line 06: Nombre d'occurrences de lettres dans p[][] .

Line 07: Imprimer l'état actuel.

Line 08: Trouver le caractère suivant au hasard, proportionnel aux nombres dans p[][] .

Exemple de sortie:

p[++);p[99]=Y;putfor(aind(a++j,*a+j=j,c][c,*an(arile(pr*Y,Y[256]<<1);)][*Y,Y;)wha+++j=*aintfor*Y;prin(a+j]=j][256<1)pr(a;a;f(p[char(Y;for());};a;ma;ma=%s%chain(Y;ar(j][256<<<1)p[256<<raile(cha][9]<rin(j,34,34,Y[256]+j,Y,34,Y,c=Y,*a;*a;for(){0}

Rubis, 152 octets

0;s="0;s=%p<<33
0until putc($/=Hash[[*(s%%s).chars.each_cons(2)].shuffle][$/])==?"<<33
0until putc($/=Hash[[*(s%s).chars.each_cons(2)].shuffle][$/])==?!

Exemple de sortie:

0;s.c($/=Has(s).ears(2).ch[*(2)=Hacontc(2).ears.eas=Has==Hars%putc($/]).ears%sh_chuffl puns=Hachach[$/==?!

ou

0;s.ch[*($/=%pufl puns($/=%s.shas($/=Harsh_chutilears)])].e]).s)=Hac($/=="<<33\ntile].chufffle][[$/=Hars%sh_c(2)=%p<<<<<33
0;s)].ears)=Hars).c(s).eacon0un0;sh_c($/][*(s.s=Hacons=?!

Quines utilisant le formatage de chaînes via "s%s", et fait le chaînage de Markov en prenant toutes les tranches de deux caractères, en les mélangeant et en les transformant en un dictionnaire de hachage, où pour les clés en double, la dernière apparence définit la valeur. Pour éviter d'ajouter de la logique supplémentaire pour le début, je surveille le dernier caractère de sortie à l'aide de $/, qui est automatiquement initialisé sur une nouvelle ligne, et je m'assure que les nouvelles lignes sont toujours suivies dans le code par 0le même caractère que le code commence par. Pour la fin, je manipule le code source afin qu'il n'y en ait qu'un, !donc nous finissons toujours après le coup, en l' <<33ajoutant sans le littéral. Cela pourrait être approfondi en utilisant un caractère à un chiffre non imprimable au lieu de l'ASCII 33, mais cela semblait trop ennuyeux.

Rouille, 564 octets (non compétitif)

extern crate rand;fn main(){let t=("extern crate rand;fn main(){let t=", ";let mut s=format!(\"{}{:?}{}\",t.0,t,t.1).into_bytes();s.push(0);let mut r=rand::thread_rng();let mut c=s[0];while c!=0{print!(\"{}\",c as char);let u=s.windows(2);c=rand::sample(&mut r,u.filter(|x|x[0]==c),1)[0][1];}}");let mut s=format!("{}{:?}{}",t.0,t,t.1).into_bytes();s.push(0);let mut r=rand::thread_rng();let mut c=s[0];while c!=0{print!("{}",c as char);let u=s.windows(2);c=rand::sample(&mut r,u.filter(|x|x[0]==c),1)[0][1];}}

Comme j'avais déjà écrit un quine Rust assez soigné pour une autre question, j'ai pensé l'adapter pour cela, car cela semblait assez simple. Bien que l'original soit petit, pour cela, j'ai fait très peu d'efforts pour réduire la taille. Voici une version étendue pour expliquer ce qui se passe:

// Random numbers are removed from the standard library in Rust,
// I had to make a cargo project to even compile this...
// Rust is hardly a golfing language.
extern crate rand;

fn main(){

    // The quine is fairly simple, we just make a tuple with 
    // "everything before this tuple" as first element, and
    // "everything after this tuple" with any quotes escaped 
    // as second. That makes it really easy to print.
    let t=("[...before...]", "[...after...]");

    // Instead of printing it, we save it as a byte vector
    // and append 0
    let mut s=format!("{}{:?}{}",t.0,t,t.1).into_bytes();
    s.push(0);

    // Start with the first character
    let mut c=s[0];
    let mut r=rand::thread_rng();

    while c!=0 {
        print!("{}",c as char);

        // We slide a 2 wide window over it to save a vector
        // of all bigrams. 
        let u=s.windows(2);

        // Filter it to only those which have the current character 
        // as first. Take one at random, its second is our next 
        // character.
        c=rand::sample(&mut r, u.filter(|x|x[0]==c), 1)[0][1];

        // Keep at it until the 0 byte is generated.
    }
}

Exemple de sortie 1:

eran(),0{ller=samarin chas c).pr,teteran mut madoletet manthilaplerng().wind_byt.wit();let.u.0][*s=[*s.plleas.wshit, rnd:Vec<_byte mputextet ut t leat=r,t rant!=r().filllet rng();lar("{}{let.ind_byt.what amusarando_ramut!=st ct!(\").0]=colet!(&lec<_ret.plec=s.whrararandormpr=saile ret=r,0]=r);le(\"),t und;fint.prilt!();ler(2).forap(&ler=s(),t ut rat mu:t=ramund:Ve s.putec==[0];wst and_byt sh(\"et c s[1), munwhras[0];c=s=s="etornws(2)[0, ain(|x|x[0,0,0];fowile c ct(&l=",tes().co_byt().wrmat ash(|x|x[*s.lethrant.wrarmu.file(\"et, r==[1);uterile().0,t ando_rinwhas=[0{}"ect.wilant!("{ple mut, mut mamprmant,0];le(&lec=s.1),t co_>=fin mamustec!(\",c=[0];}}",0];leteteat.ust(",ternwhashrarmut ler("erat,0]==file and_reter==s.utet an letet.ut=", ras.1);fin("{:?}"et t letes[*sado_bytet rnd::Verain s[0];whant(){}{}\"echin s(2);lerad;wst reth(\",t u.iletermat c 1];}{}

Exemple de sortie 2:

et!().0][0][0{}

Python 2, 211 octets

Sort le résultat vers stderr.

import random;X='q=[(list(t)+["$$"])[i+1]for i in range(len(t))if t[i]==c];c=random.choice(q)\nif c=="$$":exit(o)\no+=c\nexec X';s='import random;X=%r;s=%r;q=t=s%%(s,X);o=c="i";exec X';q=t=s%(s,X);o=c="i";exec X

Essayez-le en ligne

Exemple de sortie:

i+[(s,X)));exenit(or;q=rt(t(t(t);o='ic\n(q)+1]=c\ndor randort))\ngeno));X)\nge(st))ic]=";oic=%ran(s%%(s%rt(q)\ngexe(s=st(t[(s=[if X=%(ompoiforanom;e(t X="$"$"ic="$"i";X=c rt X

Brève explication:

• Ce programme utilise le s='s=%r;print s%%s';print s%sformat quine. Je crée une chaînes qui contiendra l'ensemble du programme.
• La chaîne X contient la procédure à exécuter récursivement.
• La procédure crée la chaîne de sortie o, qui sera imprimée dansstderr la fin de la chaîne de Markov.
• La fin de la chaîne est représentée par la chaîne $$, en utilisant deux caractères pour que le programme fonctionne pour toutes les chaînes. J'aurais pu utiliser un personnage qui n'était pas dans mon programme commechr(0) , mais je pense que c'est plus long.
• Le personnage choisi à chaque exécution est placé dans clequel (aveco ) est initialisé au premier caractère du programme.
• La liste des caractères qui suivent chaque occurrence de choix cdans la chaîne t(la variable contenant le quine du code source) est q, qui sera choisie pour la prochaine sélection de c.

PHP, 144 135 130 130 120 272 220 212 octets

<?$e='$p=$n="";foreach(str_split($s)as$w)$p=$m[$p][]=$w;do echo$n=$m[$n][array_rand($m[$n])];while("\n"!=$n);
';$s='<?$e=%c%s%1$c;$s=%1$c%s%1$c;$s=sprintf($s,39,$e,$s);eval($e);';$s=sprintf($s,39,$e,$s);eval($e);

Ou, formaté pour la lisibilité:

<?$e='$p = $n = "";
foreach (str_split($s) as $w) {
    $p = $m[$p][] = $w;
}
do {
    echo $n = $m[$n][array_rand($m[$n])];
} while ("\n" != $n);
';$s='<?$e=%c%s%1$c;$s=%1$c%s%1$c;$s=sprintf($s,39,$e,$s);eval($e);';$s=sprintf($s,39,$e,$s);eval($e);

Exemple de sortie:

<?p=')ay_r_gecorr_splililen]=$p=$w;

et:

<?p=$n=$ntststs$m[$n=$m[ay_r_chondo$n=$ph(s$nt(fitstr_r_geantentr_s('m[$n=$n"!=$p etstsp][$w;d(fililile(s$w)$nt(sphor_str_getrarast(''''m[$n='m[$m';

et:

<?p=$who eay_re($n=$n=$nt(')];d(fililileando et($m[]=$pleay_ch(')aray_ren='''))ay_st_r_s($m[$m[asp])ay_co$m[$p $phorentechitr_rean)][$n=$nd("\n"!=$n=$wh(filend('')ay_gen=$ndo$nt_rasp=$n][$p=$whp=$n='m[$n"\n)))))][$w;dorechph(';dorracho$ple_s$w;fil

et:

<?ph($n);

PHP Cheating, 117

Pour les curieux, si nous trichons en lisant notre propre source, nous pouvons faire 117:

<?=$p=$n='';foreach(str_split(file('m')[0])as$w)$p=$m[$p][]=$w;do echo$n=$m[$n][array_rand($m[$n])];while("\n"!=$n);