image

Эстафета из 100 языков программирования


Квайн — компьютерная программа, которая выдаёт на выходе точную копию своего исходного текста. Цепной квайн отличается от обычного тем, что на каждой последующей итерации выводится код на другом языке программирования, до тех пор, пока не выведется код оригинального квайна. В середине 2013 года японский программист Юсукэ Эндо (?? ??) разработал цепной квайн, содержащий 50 языков программирования. В конце 2014 кода он опубликовал новую версию, включающую уже 100 языков!

Исходники и информация о компиляции всех этих квайнов есть на гитхабе: quine-relay. Любопытно, что исходный код в виде картинки был написан не в ручную (что невозможно в принципе), а сгенерирован. Автор отмечает, что в течении года он опубликует книгу про обфусцированное программирование, которая будет включать в себя подробное объяснение о том, как писать квайны, ascii-art квайны, цепные квайны (подобные этой эстафете).

Радиационно-устойчивый квайн


Интересный вид квайнов, в которых при удалении символа из любого места в коде, он все равно компилируется и выводит сам себя. Исходники, автором которых является вышеупомянутый японец вместе с Darren Smith aka. flagitious, находятся здесь: radiation-hardened-quine.

eval=eval=eval='eval$s=%q(eval(%w(puts((%q(eval=ev
al=eval=^Z^##^_/#{eval@eval@if@eval)+?@*10+%(.size
>#{(s=%(eval$s=%q(#$s)#)).size-1}}}#LMNOPQRS_##thx
.flagitious!##    )+?@*12+%(TUVW    XY/.i@rescue##
/_3141592653       589793+)+?@*       16+%(+271828
182845904;          _987654321          0;;eval)+?
@*18+%("x            =((#{s.s            um}-eval.
_sum)%256             ).chr;             ;eval)+?@
*12+%(.s             can(//){             a=$`+x+$
^_a.unpa            ck      (^            H*^)[0].
hex%999989==#{s.unpac        k("H*")[0].hex%999989
}&&eval(a)}#"##"_eval        @eval####@(C)@Copyrig
ht@2014@Yusuke@Endoh@#      ###)).tr("@_^",32.chr<
<10<<39).sub(?Z,s));e xit#AB CDEFGHIJK)*%()))#'##'
/#{eval eval if eval          .size>692}}#LMNOPQRS
##thx.flagitious!##            TUVWXY/.i rescue##/
3141592653589793+                +271828182845904;
9876543210;;eval                  "x=((42737-eval.
sum)%256).chr;;eval            .scan(//){a=$`+x+$'
a.unpack('H*')[0].hex%999989==68042&&eval(a)}#"##"
eval eval#### (C) Copyright 2014 Yusuke Endoh ####

Проверить, то, что автор нас не обманывает можно следующим образом:

Создаем скрипт для удаления случайного символа из файла (mutate.rb):
$ cat mutate.rb
src = ARGF.read
src[rand(src.size), 1] = ""
print src

Применяем его к оригинальному файлу (rquine.rb), а затем компилируем получившийся и записываем результат в новый файл broken.rb
$ ruby mutate.rb rquine.rb > broken.rb

Запускаем «сломанную» программу:
$ ruby broken.rb > rquine2.rb

Вычисляем разницу между получившимся (rquine2.rb) и исходным (rquine.rb) файлами:
$ diff rquine.rb rquine2.rb

Вуаля! Файлы совпадают!
Стоит отметить, что первая версия имела больше избыточного кода (по сути дублирование кода). Последняя версия же работает более интеллектуально, заменяя ошибки в самой себе.


Квайновые часы


Мои квайны, конечно, менее впечатляющие, но, по крайней мере, выводят красивую ASCII картинку на выходе =)
В 2014 году меня заинтересовало то, что квайн может быть связан со своими предыдущими итерациями по данным (когда каждая следующая итерация использует какие-то данные из предыдущей, что повсеместно используется, например, в вышеупомянутых квайнах) или по времени (в этом случае необходимо использовать функции ОС для создания задержки или функции получения времени). Одним из проектов воплощающих идею со временем стали квайновые часы.

Мной были выделены две вариации квайновых часов:
  • Ожидающие перед выводом кода время.
  • Записывающие время ожидания в выходной код.

Первый тип по сути можно реализовать и без использования техники квайнов (компилируя одну и ту же программу, ожидая время до следующего секундного тика), однако это не спортивно. Второй же тип является более интересным, поскольку время ожидания нужно записывать в выходную программу, чтобы при следующем запуске его учитывать (также можно еще учитывать время компиляции для минимизации погрешности). Однако к этой статье я успел подготовить только первый вариант, файлы которого (исходники .cs и файлы .bat, .ps1, .sh) хранятся здесь: QuineClock.

Стоит отметить, что код генерируется на основе принципов, описанных в моей статье: Звездные войны в исходном коде.

Скрипты для запуска квайновых часов на разных операционных системах (проверял на Windows 7 и Linux Mint) выглядят следующим образом:

Запуск в Windows


Batch

echo off

:LOOP
    "C:\Windows\Microsoft.NET\Framework\v4.0.30319\csc.exe" "QuineClock.cs"
    "QuineClock.exe" > "QuineClock.cs"
    type "QuineClock.cs"
goto LOOP

:END

Powershell

while ($true) {
    &"C:\Windows\Microsoft.NET\Framework\v4.0.30319\csc.exe" "QuineClock.cs"
    ./"QuineClock.exe" > "QuineClock.cs"
    type "QuineClock.cs"
}

Запуск в Linux (Mono)

while :
do
    mcs "QuineClock.cs"
    mono "QuineClock.exe" > "QuineClock.cs"
    cat "QuineClock.cs"
done


Пример одного кадра:


Более интересной и сложнее в реализации оказалась игра «Змейка».

Квайновая змейка


Не так давно я познакомился с реализацией тетриса в C++ во время компиляции: Stupid Template Tricks: Super Template Tetris, а еще узнал о конкурсе GoStash и вспомнил о своих квайнах. Тетрис было бы сложнее реализовать, поэтому в голову пришла идея реализовать игру с более простой логикой, а именно Змейку. Может, конечно, в конкурсе я ничего не выиграю, но, по крайней мере, он заставил меня вытащить данную статью из черновиков и дополнить ее. :)

«Игра» была реализован поэтапно, с постепенной минификацией кода. Сначала была реализована полная версия, которая просто запускалась в консоли. В ней содержались дотнетовские перечисления, словари, разбиение на методы и другие избыточные вещи. Затем весь код был переписан в говнокод изменен до неузнаваемости: пересечения были заменены на константы, все методы были объединены в один, вместо условных операторов (if else) были использованы тернарные операторы. Везде, где только возможно, были использованы переменные, объявленные ранее (глобальные) и проведены прочие магические вещи. Также на финальном этапе весь код пропускался через разработанный мной минификатор для укорочения имен переменных и удаления пробельных символов везде, где это только возможно (ручная минификация для остальных вещей оказалась все же более эффективной, но и более трудоемкой). Несмотря на все эти манипуляции, потенциал для минификации длины кода, как мне кажется, еще остался.

Определенные проблемы также были с реализацией пользовательского ввода, которые, однако, удалось решить только для Windows версии. Дело в том, что bat или powershell инструкция «QuineSnake.exe» > «QuineSnake.cs» ожидает пользовательского ввода (Console.ReadKey) и только потом записывает результат вывода программы в файл (тем самым, можно «запомнить», какую клавишу нажал пользователь). Однако аналогичная shell команда не перехватывает пользовательский ввод. Как по-другому это сделать, я не разобрался. Единственно, что пользовательский ввод можно эмулировать с помощью аргументов командной строки (передавать w,a,s,d), но тогда играть станет менее удобно.

Исходный код квайновой змейки
using System;class E{static int A=4,B=10,M=1,D=5,Z=3,F=0;static int[]L={3,3};
static string a2(){int a=A,b=B,c=0,e=3,g=0,h,i,j,k,l,m,p,q=L.Length;var r=false;
var t=new int[10,20];t[M,D]=8;if(F!=1)goto X;for(int u=0;u<q;u++){c=L[u];int d=u
==0?Z:L[u-1];if(d==0||d==2){k=0;l=2;m=1;p=3;j=2;h=0;i=1;}else{k=1;l=3;m=0;p=2;j=
1;h=1;i=0;}if(u==0){if((Z!=k||c!=l)&&(Z!=l||c!=k))e=Z;else e=c;g=e==k?-1:1;A=A+g
*h;B=B+g*i;if(A<0||A>=10||B<0||B>=20){F=2;goto X;}if(t[A,B]==8)r=true;t[A,B]=5;}
if(u!=q-1||r)t[a,b]=c==m||c==p?c==m^d!=k?3:4:j;else t[a,b]=d==0||d==2?7:6;if(c==
0)b++;if(c==2)b--;if(c==1)a++;if(c==3)a--;}if(t[A,B]!=5){F=2;goto X;}if(r){t[a,b
]=c==0||c==2?7:6;F=3;for(h=0;h<10;h++)for(i=0;i<20;i++)if(t[h,i]==0)F=1;if(F==3)
goto X;var v=new Random();for(;;){M=v.Next(10);D=v.Next(20);if(t[M,D]==0){t[M,D]
=8;break;}}var w=new int[q+1];for(g=0;g<q;g++)w[g+1]=L[g];w[0]=e;L=w;}else{for(g
=q-2;g>=0;g--)L[g+1]=L[g];L[0]=e;}X:var R="";var x="\r\n";var s=new string('/',
20+4);R+=x+s+x;var y=" |-\\/O\"=*";for(h=0;h<10;h++){R+="//";if(F==1)for(i=0;i<
20;i++)R+=y[t[h,i]].ToString();else{var z=F==2?"Game Over!":"  Win!!!  ";int C=
20/2;R+=new string(' ',C-5)+z+new string(' ',20-C-5);}R+="//";R+=x;}R+=s+
"   QuineSnake by KvanTTT for GoStash"+x;return R;}static void Main(){if(F!=0){
int a=(int)Console.ReadKey(true).Key;Z=a<37||a>40?L[0]:a-37;}if(F==0)F=1;var R=a2();var s=
"using System;class E{{static int {10}={8},{11}={9},{12}={6},{13}={7},{14}={4},{17}={16};static int[]{15}={5};static string a2(){{int a={10},b={11},c=0,e=3,g=0,h,i,j,k,l,m,p,q={15}.Length;var r=false;var t=new int[10,20];t[{12},{13}]=8;if({17}!=1)goto X;for(int u=0;u<q;u++){{c={15}[u];int d=u==0?{14}:{15}[u-1];if(d==0||d==2){{k=0;l=2;m=1;p=3;j=2;h=0;i=1;}}else{{k=1;l=3;m=0;p=2;j=1;h=1;i=0;}}if(u==0){{if(({14}!=k||c!=l)&&({14}!=l||c!=k))e={14};else e=c;g=e==k?-1:1;{10}={10}+g*h;{11}={11}+g*i;if({10}<0||{10}>=10||{11}<0||{11}>=20){{{17}=2;goto X;}}if(t[{10},{11}]==8)r=true;t[{10},{11}]=5;}}if(u!=q-1||r)t[a,b]=c==m||c==p?c==m^d!=k?3:4:j;else t[a,b]=d==0||d==2?7:6;if(c==0)b++;if(c==2)b--;if(c==1)a++;if(c==3)a--;}}if(t[{10},{11}]!=5){{{17}=2;goto X;}}if(r){{t[a,b]=c==0||c==2?7:6;{17}=3;for(h=0;h<10;h++)for(i=0;i<20;i++)if(t[h,i]==0){17}=1;if({17}==3)goto X;var v=new Random();for(;;){{{12}=v.Next(10);{13}=v.Next(20);if(t[{12},{13}]==0){{t[{12},{13}]=8;break;}}}}var w=new int[q+1];for(g=0;g<q;g++)w[g+1]={15}[g];w[0]=e;{15}=w;}}else{{for(g=q-2;g>=0;g--){15}[g+1]={15}[g];{15}[0]=e;}}X:var R={1}{1};var x={1}{2}r{2}n{1};var s=new string('/',20+4);R+=x+s+x;var y={1} |-{2}{2}/O{2}{1}=*{1};for(h=0;h<10;h++){{R+={1}//{1};if({17}==1)for(i=0;i<20;i++)R+=y[t[h,i]].ToString();else{{var z={17}==2?{1}Game Over!{1}:{1}  Win!!!  {1};int C=20/2;R+=new string(' ',C-5)+z+new string(' ',20-C-5);}}R+={1}//{1};R+=x;}}R+=s+{1}   QuineSnake by KvanTTT for GoStash{1}+x;return R;}}static void Main(){{if({17}!=0){{int a=(int)Console.ReadKey(true).Key;{14}=a<37||a>40?{15}[0]:a-37;}}if({17}==0){17}=1;var R=a2();var s={1}{0}{1};Console.Write(s,s,'{1}','{2}{2}',R,{14},{1}{{{1}+string.Join({1},{1},{15})+{1}}}{1},{12},{13},{10},{11},{1}A{1},{1}B{1},{1}M{1},{1}D{1},{1}Z{1},{1}L{1},{17},{1}F{1});}}}}{3}";Console.Write(s,s,'"','\\',R,Z,"{"+string.Join(",",L)+"}",M,D,A,B,"A","B","M","D","Z","L",F,"F");}}




Исходники и скрипты квайновой змейки можно также можно взять из гиста: QuineSnake

Управление осуществляется с помощью стрелок.
Что ж, всем приятной игры и хороших квайнов. =)

P.S. Прощу прощения за возможные ошибки и недоработки в статье, писал ее на скорую руку, хотел успеть до окончания конкурса gostash challenge.

И если вам понравилась статья или описанные в ней материалы, то проголосуйте пожалуйста за мой код на проекте gostash: QuineSnake.

Комментарии (9)


  1. bubuq
    13.07.2015 00:58
    +12

    японский программист Юсукэ Эндо (Yusuke Endoh)
    японский программист Юсукэ Эндо (?? ??)


  1. nitro80
    13.07.2015 05:14

    А есть в природе подобные заставки???


    1. mapron
      13.07.2015 08:05
      +2

      Ну квайнов в природе нет, но вон если от морской звезды луч отрезать, говорят, она себя восстанавливает.


      1. GarryC
        13.07.2015 10:41
        +1

        Как это нет а люди? Разве мы себя не воспроизводим?


        1. WST
          13.07.2015 10:51
          +4

          Люди были бы квайнами, если бы рожали собак, которые рожают кошек, которые рожают людей, умеющих делать то же самое :)


          1. WST
            13.07.2015 11:28
            -3

            Впрочем, так как программа, печатающая свой исходный текст, сама по себе является квайном, то люди тоже квайны.


            1. Dobrii
              13.07.2015 11:38
              +6

              Люди не выдают точную копию самих себя


            1. Alexeyco
              13.07.2015 11:43
              +5

              Люди — это обфусцированные бинарники, которые изучают себя декомпиляцией, надеясь научиться себя патчить. И не имеют к исходникам своих производных, также, никакого отношения.


  1. gromozeka1980
    13.07.2015 10:16
    +3

    Надеюсь, книгу Юсукэ переведут хотя бы на английский :)

    Два года назад писал тут о технологии создании квайнов-уроборосов — habrahabr.ru/post/188378