Markov Chain Quine

Question

A simple Markov Model will be used in this question. For more information about Markov Chains, see http://setosa.io/ev/markov-chains/.

Take a string. For this example, we will use the word:

reader

Now, for each character, take the characters that appear after each occurence of the character in the string. (​`^`​ represents the start of the string and ​`$`​ represents the end)

`^` -> {'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'}

Now, starting from the start of the string, pick randomly from one of the characters in the next set. Append this character and then pick from the characters in its next set, and so on until you get to the end. Here are some example words:

r
rereader
rer
readereader

If a character appears after another character multiple times, it is more likely to be chosen. For example, in cocoa can, after a c, there is a two thirds of a chance of getting an o and a one thirds chance of getting an a.

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

Challenge

Create a program that takes no input and outputs a random string generated using a Markov Chain, like above, where the input to the chain is the program's source.

1. The program must have at least two characters, two of which must be the same (To prevent "boring" chains that only have one output)
2. You can modify the model to use bytes instead of characters if you wish, but change "characters" to "bytes" in rule 1
3. The program should output strings randomly with the expected frequency in theory

This is code-golf, so the shortest program wins!

Answer 1

JavaScript, 217 215 bytes

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)

Note that this uses uneval, which is only supported by Firefox. Sample runs:

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

As you can see, it's mostly gibberish, but that is to be expected ;) The OP has created a JSFiddle which demonstrates that the chance of an output being syntactically valid JS is about 6.3%.

---

If self-reading functions were allowed, this could be 78 bytes of ES6:

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

Very, very rarely, this outputs syntactically valid JS:

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

My favorite of the function names it's created is .splendom() (split + length + random)

Answer 2

Pip, 64 bytes

This was fun.

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

<tab> represents a literal tab character (0x09). Try it online!

How?

TL;DR: escaped-string syntax, repr, and eval.

For strings that need to contain literal " characters, Pip has escaped strings, using \" as the delimiter. A standard quine using escaped strings would look like this:

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

That is: Yank (storing as y) a string containing "V Y".RPy and eVal it. RPy takes the repr of y, to which we prepend the literal string V Y. Finally, output the result of the eval.

The structure of the Markov quine is similar, except that we want to save the code instead of outputting it and then do some stuff with it afterwards. t:V Y\"...\" assigns the eval result to t. Inside the eval'd code, m:"..." assigns a string of code to m, which we will evaluate at the end with Vm.

ST["t:V Y"RPy";Vm"C9] builds a list containing

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

and converts it to a string, which by default concatenates all the items. This section is equivalent to "V Y".RPy in the original quine. Since it is the last expression in the big eval string, its value is what the V operator returns, and thus what gets assigned to t.

Thus, after the eval and assignment, t is equal to the full code, and m contains

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

Now Vm evaluates that as code. Let's break down what happens.

                            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

A couple notes:

• Ending the code with a literal tab was shorter than doing a regex test for "next character or end of string."
• The regex I used does not work properly if there are doubled characters in the code; for instance, applying it to xxy would return only xx and not xy in the matches. Fortunately, however, there are no doubled characters in this code, so it doesn't matter.

Answer 3

MS-DOS machine code (.COM file), 126 bytes

(A 63-byte variant would be possible if the program was allowed to read its own code.)

The first half (63 bytes) of the program are code and look like this:

FC BE<3F>01 AC 50 88 C2 B4 02 CD 21 E8 1A 00 59
4E AC 81 FE<7E>01 7C 03 BE<3F>01 38 C1 75 F2 FE
CA 75 EE 81 FE<3F>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

The second half (63 bytes) are data and are a 1:1 copy of the code.

(In the 63-byte variant reading its own code, the bytes marked with "<>" have different values and the second half of the program is not present.)

I'm also not sure about the random generator's probability distribution:

The program uses the fact that the clock counters and other information modified by interrupts are stored in segment 0 to generate random numbers.

Converted to assembly code the program looks like this:

# 0x100:
    cld                # Ensure SI is being incremented
    mov si, programEnd # Move SI to the first byte of the copy 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
                       # If we loaded the last byte ...
    cmp si, 2*programEnd-0x100
    jl notEndOfProgram # ... the next byte to be loaded ...
    mov si, programEnd # ... 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, programEnd # 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:
    ## Place a copy of the code as data here ##

Answer 4

C, 306 328 585 611 615 623 673 707 bytes

Source code:

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

With newlines and whitespace added for legibility/explanation:

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  }

Explanation

Line 01: p[][] holds the counts of one character following another.

Line 02: X contains the program's source, escaped with %c%s%c.

Line 03: Y will contain the program's literal source. c, j, *a are counting variables.

Line 05: Set Y to contain the quine.

Line 06: Count letter occurrences in p[][].

Line 07: Print the current state.

Line 08: Find the next character randomly, proportional to the counts in p[][].

Sample output:

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}

Answer 5

Perl 5, 81 bytes

Based on the standard quine and my answer to this question:

$_=q{@$=a^E;@$="\$_=q{$_};eval"=~/(?<=\Q$@\E).?/g,print$@while$@=$$[rand@$]};eval

Try it online!

As with the faux source code answer, this sometimes produces valid Perl, but very infrequently (<2%):

$$$_=al
$_=a^E;eval
$_=al
$$=q{$$]};eval
$@=a^E;@whil
$_=q{@\E;e$]};evaleva^E;eval
$$=q{@\$_=a^E;evant$@$="=$$]};evaleval
$_=q{@whind@$_=$]};eval
$_=q{@\$@=~/(?<=\$[rilevale$=ant$[rint$_};evaleval
$_=aleval
$_=q{@$_};@whil
$$=q{@$=q{@$=\E;evand@whint$_};eva^E).?<=$=~/g,prand@$_=al"\E;e$@\E).?/g,prant$_};evaleval
$_=\$_=~/g,prind@=q{$]};@$@\Q$$$_};e$@$_=q{@$_=~/g,pril
$_=q{$=aleval"\E;evaleva^E;eva^E).?/g,pra^E;eva^E).?/(?/g,print$@$_};eval
$@=q{$_=~/(?<="\$_};eval

Answer 6

Ruby, 152 bytes

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][$/])==?!

Sample output:

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

or

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 using string formatting via "s%s", and does the Markov chaining by taking all two-character slices, shuffling them, and turning them into a Hash dictionary, where for duplicate keys the last appearance defines the value. To avoid adding extra logic for the beginning, I track the most recently output character using $/, which is automatically initialized to a newline, and ensure that newlines are always followed in the code by 0, the same character the code starts with. For the end, I manipulate the source code so that there's only one ! so we always end after the bang, using <<33 to add it without the literal. This could be golfed further using an unprintable single-digit character instead of ASCII 33, but that seemed too annoying.

Answer 7

Rust, 564 bytes (not competitive)

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

Since I already had written a pretty neat Rust quine for another question, I thought I'd adapt it for this, since it seemed simple enough. While the original was small, though, for this I have made very little attempt to minimize size. Here's an expanded version to explain what's going on:

// 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.
    }
}

Sample output 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];}{}

Sample output 2:

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

Answer 8

Python 2, 211 bytes

Outputs the result to 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

Try it online

Sample output:

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

Brief Explanation:

• This program uses the s='s=%r;print s%%s';print s%s quine format. I create a string s, which will contain the entire program.
• The string X contains the procedure to execute recursively.
• The procedure builds the output string o, which will be printed to stderr upon reaching the end of the Markov chain.
• The end of the chain is represented by the string $$, using two characters so that the program will work for all strings. I could have used a character not in my program like chr(0), but I think that's longer.
• The character chosen each execution is placed in c, which (along with o) is initialized to the first character of the program.
• The list of characters that follow each occurrence of choice c in the string t (the variable holding the quine of the source code) is q, which will be chosen from for the next selection of c.

Answer 9

PHP, 144 135 130 120 272 220 212 bytes

<?$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);

Or, formatted for readability:

<?$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);

Sample output:

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

and:

<?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';

and:

<?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

and:

<?ph($n);

PHP Cheating, 117

For the curious, if we cheat by reading our own source, we can do 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);

Answer 10

Julia 1.7, 103 bytes

(c='(';a=:((c = (q = "(c='(';a=:($(a)))|>eval")[(print(c) != 1) + rand(findall(c, q))]):eval(a)))|>eval

Try it online!

All those spaces are painful but necessary because the code is stored in an Expr (AST), which will add spaces when interpolated. Replace print(c) with println(q) to check the validity of the quine.

based on this quine:
(a=:(print("(a=:($(a)))|>eval")))|>eval Try it online!

Answer 11

Vyxal D, 18 bytes

`{Ȯq‛DĖ+$/Ḣ℅h:₴`DĖ

Try it Online!

Sample outputs:

`{Ȯq‛DĖ
`DĖ
`{Ȯq‛DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ
`DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ+$/Ḣ℅h:₴`DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ+$/Ḣ℅h:₴`DĖ
`DĖ+$/Ḣ℅h:₴`{Ȯq‛DĖ

Explanation:

`              `D  # push this string to the stack and triplicate => [ <code> , <code> , <code> ]
                 Ė # Execute the top => [ <code>, <code> ]
 {                 # While true
  Ȯ                # push the second to last item on the stack => [ <code> , <code> , <code> ]
   q‛DĖ+           # quote and add ‛DĖ => [ <code> , <code> , `<code>`DĖ ]
        $          # swap => [ <code> , `<code>`DĖ , <code> ]
         /Ḣ        # split and discard the first element => [ <code> , [`DĖ] ]
           ℅h      # choose at random an element and get it's first element => [ <code> , ` ]
             :₴    # duplicate and print without a newline => [ <code> , ` ]
## on loop ##
 {                 # While true
  Ȯ                # push the second to last item on the stack => [ <code> , ` , <code> ]
   q‛DĖ+           # quote and add ‛DĖ => [ <code> , ` , `<code>`DĖ ]
        $          # swap => [ <code> , `<code>`DĖ , ` ]
         /Ḣ        # split and discard the first element => [ <code> , [<code>, DĖ] ]
           ℅h      # choose at random an element and get it's first element (or error and stop the program) => [ <code> , <char> ]
             :₴    # duplicate and print without a newline => [ <code> , <char> ]

Also 18 bytes

`q‛:Ė+:{h~/$₴Ḣ℅`:Ė

Try it Online!

Answer 12

Python 3.8 (pre-release), 103 102 bytes

exec(s:="from random import*;c='e'\nwhile c:print(end=c);c=choice(f'exec(s:={s!r})'.split(c)[1:])[0]")

Try it online!

the program stops by crashing due to an IndexError. To avoid crashing, [0] must be replaced by [:1] for the cost of 1 byte

How it works?

• I started from the quine exec(s:="print('exec(s:=%r)'%s)")

then the core program is the following :

from random import*
c='e'
while c:
  print(end=c)
  c=choice('<the quine string>'.split(c)[1:])[0]

• I assign c to the first letter of our quine (e).

while c is not the empty string :

• I print c
• I randomly choose a successor of c beween all possible successor

to choose a successor :

• let say our string is "abacbdeb" and I want a successor of 'b':
• I split the string using 'b' as separator : ['a','ac','de','']
• I remove the first substing which corresponds to the char before the first occurence of b : ['ac','de','']
• I take up to 1 char of these substring : ['a','d','']

If the char is at the end of a string, it will have the empty string as potential successor and will crash the program when atempting to get its first character. It only works beacuse no char is repeated twice.