# Markov Chain Quine

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 , so the shortest program wins!

• @mbomb007 all the information is in the question, the link is just extra if you get interested (This is a very basic implementation) – Artyer Oct 31 '16 at 21:43
• Why are the ^ and $ in quotes? it might make it more clear to take it out of quotes, or put them in backquotes. – Destructible Lemon Oct 31 '16 at 22:37 ## 9 Answers ## 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. # 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];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];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,c=q;ath+1|0];dorerac=ac=d[Ma),c;)*~-d[Ma=alenepl(b+=ac=c;a=c;d;d.re(c;fom() a="a,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;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][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])=>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).lendom().lith+f=>q=p.lendom(",p=p=>q?c+f():c f(q),q?c=(c=(q)*~-p):c f().random(),q?c=(c=p):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) • I wonder what the probability of this generating valid JavaScript is. (Nerd snipe warning) – DanTheMan Nov 1 '16 at 6:29 • @DanTheMan Certainly very, very low. Just the probability of all parentheses and brackets being balanced is incredibly low. Although one time I got a.splerength.r(), which could be valid ;) – ETHproductions Nov 1 '16 at 13:23 • Might want to note this is FF only due to the use of uneval – Shaun H Nov 1 '16 at 13:42 • @ShaunH Thanks, I forgot that only FF supports uneval. – ETHproductions Nov 1 '16 at 13:46 • The second self-reading function isn't valid (meta.codegolf.stackexchange.com/a/4878/48878 "a quine must not access its own source, directly or indirectly."), and @DanTheMan, according to jsfiddle.net/kabkfLak/1, the chance should be around 6.3%. – Artyer Nov 2 '16 at 15:31 ## Perl, 103 bytes Based on the standard quine and my answer to this question: $_=q{$_="$_=q{_};eval";@s='';{push@s,(@n=/(?<=\Qs[-1]\E)(.|)/g)[rand@n];s[-1]&&redo}print@s};eval  ### Example Output _=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  Similarly to the other question, some results generate valid Perl: $_=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  but the chances are slightly lower, at ~2%. • If you told me the first example was valid Perl I would believe you. – ankh-morpork Nov 1 '16 at 17:33 • @dohaqatar7 I misunderstood your comment at first and thought you wouldn't believe me if I said the main code was valid Perl... :D zoitz.com/comics/perl_small.png – Dom Hastings Nov 1 '16 at 17:46 • @ankh-morpork: it's clearly invalid, q{ is the start of a string literal and there's no } to close it. Perl's actually fairly bad at running random sequences of bytes (and when it does, it's normally due to an early string literal or comment). – user62131 Mar 21 '17 at 15:30 # C, 306 328585611615623673707 bytes Source code: p={0};char*X="p={0};char*X=%c%s%c,Y,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,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={0}; 02 char*X="p={0};char*X=%c%s%c,Y,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,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=Y;putfor(aind(a++j,*a+j=j,c][c,*an(arile(pr*Y,Y<<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]<rin(j,34,34,Y+j,Y,34,Y,c=Y,*a;*a;for(){0} • Can you add a version without newlines and whitespace so we can verify the byte count? – Steven H. Nov 2 '16 at 20:38 • Yes, I've added the single line version at the top. – user61383 Nov 2 '16 at 20:44 ## 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 ##  • Non-competing is reserved for answers that meet the challenge criteria but are using a language or feature newer than the challenge. Either post the variant that doesn't read its own source, or delete the answer. – mbomb007 Mar 21 '17 at 16:49 • Non-competing is a (now obsolete) note relating to submissions being in languages that postdate the challenge; we do require all submissions to be valid, and non-competing doesn't bypass that. As such, I am removing this answer as per our policy for handling invalid submissions. Feel free to edit to a valid solution and flag for undeletion. – hyper-neutrino May 14 at 3:50 # 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. • p<<<<<33 The super-super-super-concat operator? ;-) – ETHproductions Nov 1 '16 at 22:10 • That's the "waaaay less than" operator. – mbomb007 Nov 2 '16 at 15:22 • I love the words this generates! The fact the first example is so concerns if the object Has(s).ears(2) makes me chuckle! – Dom Hastings Nov 2 '16 at 19:53 # 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;while c!=0{print!(\"{}\",c as char);let u=s.windows(2);c=rand::sample(&mut r,u.filter(|x|x==c),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;while c!=0{print!("{}",c as char);let u=s.windows(2);c=rand::sample(&mut r,u.filter(|x|x==c),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; 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==c), 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==;wst and_byt sh(\"et c s[1), munwhras;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];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;whant(){}{}\"echin s(2);lerad;wst reth(\",t u.iletermat c 1];}{}  Sample output 2: et!().0][0{}  # 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.

## PHP, 144135130120272220 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'))as$w)$p=$m[$p][]=$w;do echo$n=$m[$n][array_rand($m[$n])];while("\n"!=\$n);

• Welcome to the site! Unfortunately we have some rules about what counts as a proper Quine for challenges like this and unfortunately reading from your own source is forbidden. – Wheat Wizard Mar 21 '17 at 15:52
• Oh, good, thank you. I was looking for the rules. I'll have to revise this. – Umbrella Mar 21 '17 at 16:05