В этом вопросе будет использована простая модель Маркова. Для получения дополнительной информации о цепях Маркова см. Http://setosa.io/ev/markov-chains/ .

Возьми строку. Для этого примера мы будем использовать слово:

reader

Теперь для каждого символа возьмите символы, которые появляются после каждого вхождения символа в строке. ( ​`^`​представляет начало строки и ​`$`​представляет конец)

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

Теперь, начиная с начала строки, выберите случайным образом один из символов в следующем наборе. Добавьте этот символ, а затем выберите его из следующего набора и так далее, пока не дойдете до конца. Вот несколько примеров слов:

r
rereader
rer
readereader

Если персонаж появляется после другого символа несколько раз, он более вероятен. Например, cocoa canпосле a cесть две трети шансов получить oи одна треть шансов получить a.

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

Вызов

Создайте программу, которая не требует ввода и выводит случайную строку, сгенерированную с использованием цепочки Маркова, как описано выше, где вход в цепочку является источником программы.

1. В программе должно быть как минимум два символа, два из которых должны быть одинаковыми (чтобы предотвратить «скучные» цепочки, которые имеют только один вывод)
2. Вы можете изменить модель, чтобы использовать байты вместо символов, если хотите, но измените «символы» на «байты» в правиле 1
3. Программа должна выводить строки случайным образом с ожидаемой частотой в теории

Это код-гольф , поэтому выигрывает самая короткая программа!

Пип , 64 байта

Это было весело

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

<tab>представляет буквенный символ табуляции ( 0x09). Попробуйте онлайн!

Как?

TL; DR: синтаксис экранированной строки, repr и eval.

Для строк, которые должны содержать буквенные "символы, Pip экранировал строки , используя \"в качестве разделителя. Стандартный quine, использующий экранированные строки, будет выглядеть так:

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

То есть: Yank (сохраняя как y) строку, содержащую "V Y".RPyи все Vэто. RPyпринимает ответ y, к которому мы добавляем литеральную строку V Y. Наконец, выведите результат eval.

Структура марковской квайны аналогична, за исключением того, что мы хотим сохранить код, а не выводить его, а затем сделать с ним что-то еще. t:V Y\"...\"присваивает eval результат t. Внутри eval'd-кода m:"..."присваивает строку кода m, которую мы будем оценивать в конце Vm.

ST["t:V Y"RPy";Vm"C9] создает список, содержащий

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

и преобразует его в строку, которая по умолчанию объединяет все элементы. Этот раздел эквивалентен "V Y".RPyоригинальному Quine. Поскольку это последнее выражение в большой строке eval, его значение - это то, что Vвозвращает оператор, и, следовательно, то, что ему присваивается t.

Таким образом, после eval и присваивания, tон равен полному коду и mсодержит

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

Теперь Vmоценивает это как код. Давайте разберемся, что происходит.

                            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

Пара замечаний:

• Завершение кода с помощью буквенной табуляции было короче, чем выполнение теста регулярного выражения для «следующего символа или конца строки».
• Регулярное выражение, которое я использовал, не работает должным образом, если в коде есть двойные символы; например, применение его к xxyбудет возвращать только, xxа не xyв матчах. К счастью, в этом коде нет двойных символов, так что это не имеет значения.

JavaScript, 217 215 байт

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)

Обратите внимание, что это использует uneval, который поддерживается только Firefox. Образцы прогонов:

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

Как вы можете видеть, это в основном бред, но этого и следовало ожидать;) OP создал JSFiddle, который демонстрирует, что вероятность того, что вывод будет синтаксически верным JS, составляет около 6,3%.

Если бы были разрешены функции самостоятельного чтения, это могло бы быть 78 байтов ES6:

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

Очень, очень редко, это выводит синтаксически допустимый 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

Мой любимый из названий функций, которые он создал, .splendom()( split+ length+ random)

Perl, 103 байта

Основываясь на стандартной квине и моем ответе на этот вопрос :

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

Пример вывода

$_=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

Как и в случае с другим вопросом, некоторые результаты генерируют допустимый 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

но шансы немного ниже, на ~ 2%.

Машинный код MS-DOS (файл .COM), 63 байта - не конкурирующий

Не конкурирует, потому что квин не должен иметь доступ к своему исходному коду.

126-байтовый вариант будет соответствовать требованию «не иметь доступа к своему исходному коду»!

63-байтовый вариант выглядит так:

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

Я также не уверен насчет распределения вероятностей случайного генератора:

Программа использует тот факт, что счетчики часов и другая информация, измененная прерываниями, хранятся в сегменте 0 для генерации случайных чисел.

Примеры полученных результатов:

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

Преобразованная в ассемблерный код программа выглядит так:

    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:

С, 306 328 585 611 615 623 +673 707 байтов

Исходный код:

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

С символами новой строки и пробелами добавлены для удобочитаемости / объяснения:

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[][]содержит количество символов, следующих за другим.

Line 02: Xсодержит исходный код программы, экранированный с %c%s%c.

Line 03: Yбудет содержать буквальный источник программы. c, j, *aРассчитывают переменные.

Line 05: YСодержит квинну.

Line 06: Считать буквы в p[][].

Line 07: Печать текущего состояния.

Line 08: Случайно найти следующий символ, пропорциональный количеству в p[][].

Образец вывода:

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}

Рубин, 152 байта

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

Образец вывода:

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
0;s)].ears)=Hars).c(s).eacon0un0;sh_c($/][*(s.s=Hacons=?!

В Quines используется форматирование строк с помощью "s%s"и выполняется цепочка Маркова путем взятия всех двухсимвольных срезов, их перетасовки и превращения в хэш-словарь, где для дублированных ключей последнее появление определяет значение. Чтобы избежать добавления дополнительной логики для начала, я отслеживаю использование самого последнего выходного символа $/, который автоматически инициализируется новой строкой, и гарантирую, что в коде всегда следуют символы новой строки 0, с того же символа, с которого начинается код. В конце я манипулирую исходным кодом, чтобы он был только один, !поэтому мы всегда заканчиваем после взрыва, используя его <<33для добавления без литерала. Это можно было бы использовать в дальнейшем, используя непечатный символ из одной цифры вместо ASCII 33, но это казалось слишком раздражающим.

Ржавчина, 564 байта (неконкурентоспособна)

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

Так как я уже написал довольно аккуратный вопрос Rust для другого вопроса, я решил приспособить его для этого, поскольку он казался достаточно простым. Хотя оригинал был небольшим, для этого я сделал очень небольшую попытку минимизировать размер. Вот расширенная версия, чтобы объяснить, что происходит:

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

Пример вывода 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];}{}

Пример вывода 2:

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

Python 2, 211 байт

Выводит результат в 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

Попробуйте онлайн

Образец вывода:

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

Краткое объяснение:

• Эта программа использует s='s=%r;print s%%s';print s%sформат Quine. Я создаю строку s, которая будет содержать всю программу.
• Струна X содержит процедуру, выполняемую рекурсивно.
• Процедура создает строку вывода o, которая будет напечатана вstderr по достижении конца цепочки Маркова.
• Конец цепочки представлен строкой $$, состоящей из двух символов, чтобы программа работала для всех строк. Я мог бы использовать персонаж не в моей программе, какchr(0) , но я думаю, что это дольше.
• Персонаж, выбранный в каждом исполнении, помещается в cкоторый (вместе сo ) инициализируется первым символом программы.
• Список символов, которые следуют за каждым вхождением выбора cв строке t(переменная, содержащая квинус исходного кода) q, будет выбран для следующего выбора c.

PHP, 144 135 130 120 272 220 212 байт

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

Или отформатирован для удобства чтения:

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

Образец вывода:

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

и:

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

и:

<?ph($n);

Обман PHP, 117

Для любопытных, если мы обманываем, читая наш собственный источник, мы можем сделать 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);