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:


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:


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


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!

  • \$\begingroup\$ @mbomb007 all the information is in the question, the link is just extra if you get interested (This is a very basic implementation) \$\endgroup\$
    – Artyer
    Commented Oct 31, 2016 at 21:43
  • 3
    \$\begingroup\$ Why are the ^ and $ in quotes? it might make it more clear to take it out of quotes, or put them in backquotes. \$\endgroup\$ Commented Oct 31, 2016 at 22:37

12 Answers 12


JavaScript, 217 215 bytes


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


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:


Very, very rarely, this outputs syntactically valid JS:


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

  • 3
    \$\begingroup\$ I wonder what the probability of this generating valid JavaScript is. (Nerd snipe warning) \$\endgroup\$
    – DanTheMan
    Commented Nov 1, 2016 at 6:29
  • 2
    \$\begingroup\$ @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 ;) \$\endgroup\$ Commented Nov 1, 2016 at 13:23
  • 1
    \$\begingroup\$ Might want to note this is FF only due to the use of uneval \$\endgroup\$
    – Shaun H
    Commented Nov 1, 2016 at 13:42
  • 1
    \$\begingroup\$ @ShaunH Thanks, I forgot that only FF supports uneval. \$\endgroup\$ Commented Nov 1, 2016 at 13:46
  • 5
    \$\begingroup\$ 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%. \$\endgroup\$
    – Artyer
    Commented Nov 2, 2016 at 15:31

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!


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.

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
    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
    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.
    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:
    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!
    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

    ## Place a copy of the code as data here ##
  • \$\begingroup\$ 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. \$\endgroup\$
    – mbomb007
    Commented Mar 21, 2017 at 16:49
  • \$\begingroup\$ 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. \$\endgroup\$
    – hyper-neutrino
    Commented May 14, 2021 at 3:50

C, 306 328 585 611 615 623 673 707 bytes

Source code:


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  }


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:


  • 1
    \$\begingroup\$ Can you add a version without newlines and whitespace so we can verify the byte count? \$\endgroup\$
    – Steven H.
    Commented Nov 2, 2016 at 20:38
  • 1
    \$\begingroup\$ Yes, I've added the single line version at the top. \$\endgroup\$
    – user61383
    Commented Nov 2, 2016 at 20:44

Perl 5, 81 bytes

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


Try it online!

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

  • 8
    \$\begingroup\$ If you told me the first example was valid Perl I would believe you. \$\endgroup\$ Commented Nov 1, 2016 at 17:33
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ Commented Nov 1, 2016 at 17:46
  • \$\begingroup\$ @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). \$\endgroup\$
    – user62131
    Commented Mar 21, 2017 at 15:30

Ruby, 152 bytes

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


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

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.

  • 4
    \$\begingroup\$ p<<<<<33 The super-super-super-concat operator? ;-) \$\endgroup\$ Commented Nov 1, 2016 at 22:10
  • 3
    \$\begingroup\$ That's the "waaaay less than" operator. \$\endgroup\$
    – mbomb007
    Commented Nov 2, 2016 at 15:22
  • 2
    \$\begingroup\$ I love the words this generates! The fact the first example is so concerns if the object Has(s).ears(2) makes me chuckle! \$\endgroup\$ Commented Nov 2, 2016 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[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();

    // 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:


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, 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);

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

Sample output:



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


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



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);
  • \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard
    Commented Mar 21, 2017 at 15:52
  • \$\begingroup\$ Oh, good, thank you. I was looking for the rules. I'll have to revise this. \$\endgroup\$
    – Umbrella
    Commented Mar 21, 2017 at 16:05

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!


Vyxal D, 18 bytes


Try it Online!

Sample outputs:



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


Try it Online!


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*
while 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.