Pull to refresh
  • by relevance
  • by date
  • by rating

Цепной квайн произвольного порядка на Python

Abnormal programming *
   Впечатленный цепным полиглотным квайном японца, приведенным в этом хабратопике, я, ранее уже встречавшийся с программами-квайнами, решил познакомиться с ними плотнее. После беглого гугления и непродолжительного чтения вики/блогов/сайтов по теме, у меня зачесались руки и захотелось написать свой квайн. Квайн был написан, даже в нескольких вариантах, но этого мне показалось мало. Позже я даже написал двойной квайн (код на python генерирует код на prolog а код на prolog в свою очередь первоначальный python-код).

   Однако, тут возник вопрос. А можно ли написать квайн любого порядка (т.е. тот, который будет переходить сам в себя после N запусков)? Как оказалось, это вполне возможно. Результатом изысканий явился следующий код:

# xonix
L=19;B,Q,N,q,n=map(chr,(36,81,78,39,10))
X='import sys;sys.stdout.write(%s%s%s.replace(chr(36)+chr(81)+chr(36),chr(39)).replace(chr(36)+chr(81),chr(36)).replace(chr(36)+chr(78)+chr(36),chr(10)).replace(chr(36)+chr(78),chr(36)))'
Y='# xonix%sL=%s;B,Q,N,q,n=map(chr,(36,81,78,39,10))%sX=%s%s%s%sY=%s%s%s%sE="""%s""";exec E%simport sys;sys.stdout.write(b())'
E="""def b(l=L):
  if l==L: Ql=q
  else: Ql=B+Q*(L-l)+B;Nl=B+N*(L-l)+B
  if l>0: return X%(Ql,b(l-1),Ql)
  else: return Y%(Nl,str(L),Nl,Ql,X,Ql,Nl,Ql,Y,Ql,Nl,E.replace(n,Nl),Nl)"
"";exec E
import sys;sys.stdout.write(b())


Читать дальше →
Total votes 39: ↑32 and ↓7 +25
Views 1.4K
Comments 9

Кросс-языковое программирование

Abnormal programming *
Читая статью в вики про Квайны вспомнил, что давно, очень много кликов тому назад — не помню уже ссылки, читал как один умелец описывал процесс создания исходного текста программы(скрипта) работающего в двух разных языках. Если мне не изменяет память, это был некий bat-ник, который успешно компилировался в turbo pascale-е.

Предлагаю в качестве разминки для ума скинуть в комментарии примеры (если таковые возможны).
Читать дальше →
Total votes 19: ↑10 and ↓9 +1
Views 1.4K
Comments 19

Рекурсивный zip-архив

Abnormal programming *
Translation
Многие хабрапользователи наверняка знакомы с квайнами — программами, выводящими собственный исходный код. Сегодня я хочу показать как сделать интересный вариант квайна — ZIP-архив, который распаковывается сам в себя.

Читать дальше →
Total votes 171: ↑168 and ↓3 +165
Views 37K
Comments 55

Как писать квайны

Abnormal programming *
Введение

Многие программисты считают написание квайнов (программ, выводящих свой исходный код) непосильной задачей. И действительно — все эти цепные квайны и квайны различного порядка, при взгляде на которые можно потеряться в, казалось бы, бессмысленном наборе символов…

Однако, на самом деле, написать квайн на каком-либо языке не так сложно, как кажется. Сейчас я расскажу, как сделать это на различных языках программирования. Более того, мы не будем использовать «хаки» интерпретеруемых языков вроде операции вывода исходного кода и функций типа eval и напишем квайны на интерпретируемых и компилируемых языках.
Читать дальше →
Total votes 84: ↑80 and ↓4 +76
Views 31K
Comments 56

Эстафета из 50-ти квайнов

Abnormal programming *Ruby *


Квайн — компьютерная программа, которая выдаёт на выходе точную копию своего исходного текста. Японский рубист Юсукэ Эндо (Yusuke Endoh) создал нечто невероятное. Quine Relay — программа на Ruby, которая генерирует код программы на Scala, которая генерирует код программы на Scheme, которая генерирует… и так далее на 50-ти языках программирования, пока программа на REXX снова не генерирует изначальный код на Ruby.
Читать дальше →
Total votes 245: ↑237 and ↓8 +229
Views 104K
Comments 120

Мультиязыковые квайны

Abnormal programming *Python *Brainfuck *
Sandbox
Прочитал статью «Эстафета из 50-ти квайнов». Действительно, человек написал потрясающую штуку, колоссальный труд, настоящее произведение искусства. Но по комментам судя, многие не понимают, как подобные вещи делаются и полагают их чем-то на грани, если не за гранью, человеческих возможностей, особенно много эмоций было по поводу эзотерических языков (Brainfuck, Unlambda, Whitespace) в списке.
В этой статье я попытаюсь объяснить, как подобные квайны пишутся.

Читать дальше →
Total votes 65: ↑57 and ↓8 +49
Views 19K
Comments 17

Автограммы

Abnormal programming *Entertaining tasks
В связи с тем, что моя первая статья, Мультиязыковые квайны, похоже, понравилась коллегам-программистам, хочу продолжить и написать ещё несколько статей про всякие автореферентные штуки. Меня всегда поражала автореферентность — рекурсия, фракталы, квайны, человеческое самосознание… Сейчас я начну разглагольствовать и мне совершенно справедливо накидают чего-нибудь нехорошего в карму. Я лучше посоветую прочитать «Гёдель Эшер Бах» Хофштадтера тем, кто ещё не читал. Это гениальная книга и гимн автореферентности. А теперь к делу.

Автограммы.

Пока программисты пишут квайны на разных языках, те, кто программирование ещё по каким-либо причинам не освоил, могут заняться не менее интересным и довольно таки похожим делом — сочинением автограмм.
Автограммы — это предложения на естественном языке, описывающие собственную внутреннюю структуру.
Читать дальше →
Total votes 26: ↑25 and ↓1 +24
Views 4.2K
Comments 15

С днем программиста !! атсиммаргорп менд С (Квайн-палиндром)

Abnormal programming *C# *
Я тоже присоединяюсь к поздравлениям в честь дня программиста! И делаю это с помощью квайна-палиндрома.

Читая пост о мультиквайногенераторах и другие посты о квайнах в последнее время, мне захотелось сделать тоже что-нибудь интересное и нестандартное в области квайнов. Думать долго не пришлось, поскольку идея квайнов-палиндромов лежит на поверхности.
Читать дальше →
Total votes 74: ↑54 and ↓20 +34
Views 13K
Comments 24

Теорема Клини о неподвижной точке: квайны

Programming *Algorithms *
Здравствуйте, хабралюди. В последнее время было много разговоров о квайнах, и даже некоторый теоретический спин-офф.
Повторю за автором только что упомянутого топика: если вы знакомы с CS, то далее читать нет смысла — все это
вы и так хорошо знаете. А статья будет ответом на вопрос — всегда ли можно написать квайн? Точнее, на любом ли языке?
Физики скажут, что на всех: раз можно написать и на компилируемом C, и на брейнфаке, а кто-то и на SQL пишет — опыт говорит, что ответ на вопрос да. Математика тоже говорит, что да.

Теорема 2
На любом алгоритмически полном языке программирования можно написать программу, печатающую свой код.
Читать дальше →
Total votes 59: ↑55 and ↓4 +51
Views 21K
Comments 22

А квайн ли это?

Abnormal programming *Programming *Algorithms *

Пользуясь тем, что на Хабре проходит очередной месячник квайнов (см., например, Теорема Клини о неподвижной точке: квайны или Мультиязыковые квайны), рискну рассказать и одну свою историю. В ней не будет таких сложностей и заумствований, как в упомянутых топиках, поэтому данный текст можно воспринимать как пятничное развлечение.

Дело происходило почти четверть века назад, в эпоху отсутствия всеобщей компьютеризации и интернета. Возник у меня как-то вопрос — а можно ли написать программу, выводящую свой собственный текст. Слова «квайн» в те времена никто из моих знакомых не знал, а посмотреть в википедии я не мог «за отсутствием таковой» (с).
Промучался я над этой задачкой неделю, но таки победил её. Программа получилась корявенькая, длинная, но требованию удовлетворяла. Ужасно гордый собой, я начал предлагать эту задачу всем своим друзьям. По ходу дела пришлось уточнять условия — нельзя читать из файла, программа должна быть не пустой. Обычно после этого товарищи надолго задумывались.
Однако, один из друзей мне моментально ответил, что это, дескать, элементарно, и тут же предоставил мне требуемую программу, удовлетворяющую поставленным условиям.
Оказалось, что я всё-таки упустил одно важное и, казалось-бы, очевидное условие. Однако без его явного упоминания задачка действительно становится тривиальной. Тем не менее даже в современной статье о квайнах в википедии это условие почему-то отсутствует. Хотите знать, что это за условие?

Я и так знаю, просто хочу себя проверить...
Total votes 54: ↑33 and ↓21 +12
Views 15K
Comments 37

Звездные войны в исходном коде

Abnormal programming *C# *

У меня давно была идея реализовать что-нибудь интересное, связанное с квайнами. И наконец-то получилось довести это дело до конца. Когда-то увидел реализацию игры «Жизнь» в исходном коде: Self Printing Game of Life и мне захотелось сделать нечто похожее. Некоторое время поразмыслив, я вспомнил, что существует ASCII-графика. Но еще интересней и сложнее было бы сделать анимацию в ASCII-графике. Пример долго искать не пришлось, почти сразу же были найдена анимация «Звездных войн», а точнее 4 эпизода «Новая Надежда» под названием Asciimation. Работа японского программиста Yusuke Endoh «квайновая эстафета» также подстегнула меня к реализации этой идеи. В процесс реализации такого «фильма» пришлось решить множество других проблем, о чем, впрочем, жалеть не пришлось.

Получившийся исходник вот: gist. Для облегчения «просмотра» там также содержится скрипт, который и будет крутить всю анимацию. Исходники же всего проекта для его генерации, интерфейса и других утилит выложены на гитхабе: Freaky-Sources (Туда же включены квайны-палиндромы, о которых я уже писал). Понятное дело, что подобная вещь не несет в себе никакой практической пользы, это просто just for fun.
Желающие ознакомиться с деталями реализации, добро пожаловать под кат!
Total votes 62: ↑55 and ↓7 +48
Views 34K
Comments 9

Создаём Zoomquilt

Abnormal programming *Python *
Захотелось продолжить серию постов о всяких интересных автореферентных штуковинах и решил я написать о жанре Zoomquilt. Сделал поиск, увидел, что один пост на Хабре уже есть. Подумал, подумал и решил, что пост я всё равно напишу, но он будет технический, о технологии создания Zoomquilt.

Для начала собственно о жанре. Тут проще показать чем рассказывать.

zoomquilt.org

zoomquilt2.madmindworx.com/zoomquilt2.swf

www.syfy.com/tinman/oz

www.deviantart.com/art/kopfsalat-digital-edition-30069104

Приближаемся к картинке и вместо того, чтобы в какой-то момент увидеть пиксели величиной с кулак, видим следующую картинку, повторяем процедуру многократно (на самом деле, выглядит это как один вполне себе плавный процесс и если художники хорошо поработали, то «стыков» мы вообще не увидим) и в итоге приходим к первоначальной картинке. В общем мультиквайны, только для художников.
А как такая штука делается? Конечно можно нарисовать это всё покадрово, более того, некоторые талантливые аниматоры вполне бы с этим справились. Но практически во всех существующих произведениях этого жанра указано, что это плоды коллективного творчества. Обычно есть коллектив художников, координатор проекта и программист, который собственно собирает это всё вместе и пишет интерфейс.

Дальше о технологии создания. Под катом много картинок.
Читать дальше →
Total votes 44: ↑43 and ↓1 +42
Views 9.5K
Comments 14

Квайн на Brainfuck, тьюториал

Abnormal programming *Brainfuck *
На Хабре уже есть множество статей о квайнах и технологиях их написания. Любителям квайнов может стать скучно — есть шаблон, следуешь ему, получаешь квайн. Мультиязыковой квайн, даже с участием эзотерических языков тоже написать несложно и об этом тоже есть по меньшей мере три статьи. Вот тут то и приходят на помощь квайны целиком написанные на эзотерических языках, возвращая заскучавшему программисту интерес.

Попробую рассказать о процессе написания квайнов на Brainfuck.

Читать дальше →
Total votes 38: ↑31 and ↓7 +24
Views 14K
Comments 9

Квайн на Ассемблере? Это просто

Assembler *
Sandbox
Известно, что квайн (куайн) — программа, результатом работы которой является вывод текста самой программы. При этом предполагается, что обращения к файлу, содержащему программу, не происходит.

Квайны могут быть составлены практически на всех языках программирования за исключением, быть может, некоторых экзотических. Рассмотрим задачу составления квайна на ассемблере, предполагая, что программа должна быть Win32 приложением и должна выводить свой текст в окно.

Читать дальше →
Total votes 43: ↑18 and ↓25 -7
Views 5.2K
Comments 8

Интересности из мира квайнов (100 языков, радиационно-устойчивый, часы, змейка)

Abnormal programming *C# *
image

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


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

Исходники и информация о компиляции всех этих квайнов есть на гитхабе: quine-relay. Любопытно, что исходный код в виде картинки был написан не в ручную (что невозможно в принципе), а сгенерирован. Автор отмечает, что в течении года он опубликует книгу про обфусцированное программирование, которая будет включать в себя подробное объяснение о том, как писать квайны, ascii-art квайны, цепные квайны (подобные этой эстафете).
Далее
Total votes 48: ↑46 and ↓2 +44
Views 22K
Comments 9

Пишем квайн-полиглот-палиндромы в честь дня 2^2^3

Positive Technologies corporate blog Abnormal programming *Java *C# *

PalidromePolyglotQuine


Поздравляю всех трансляторов человеческого языка в машинный с их профессиональным днем, желаю вам меньше багов и больше-либо-равно классных идей! А в качестве идейного подарка со своей стороны предлагаю решение одной красивой задачи — написание кода, который на выходе выдаёт свой собственный текст, является валидным для интерпретаторов и компиляторов разных языков, и при этом правильно исполняется при реверсе исходников.


Не так давно я узнал о коде, который может одновременно интерпретироваться в PHP и компилироваться в Java: PhpJava.java. Как оказалось, эта идея не нова: код, валидный сразу для нескольких компиляторов или интерпретаторов, называется полиглотом (polyglot). Такой код возможно писать из-за особенностей обработки строк и комментариев в различных интерпретаторах или компиляторах.

Читать дальше →
Total votes 38: ↑37 and ↓1 +36
Views 7.2K
Comments 11

Пятничный JS: единственно верный способ вычисления факториала

Abnormal programming *JavaScript *

Введение


Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа N обозначается как N! и равняется произведению всех натуральных чисел от единицы до N включительно. Например, $6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720$. Казалось бы, что тут сложного? Однако есть свои нюансы.

Например, сравним два самых распространённых способа вычисления факториала.

Через цикл
function factorial(n){
    var result = 1;
    while(n){
        result *= n--;
    }
    return result;
}


Через рекурсию
function factorial(n, result){
    result = result || 1;
    if(!n){
        return result;
    }else{
        return factorial(n-1, result*n);
    }
}


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

В любом случае, оба эти способа слишком примитивны, чтобы по ним судить о знаниях кандидата. А вот опытный разработчик на React.js уже может написать что-то в этом роде:
Узнать, что же напишет опытный разработчик на React.js
Total votes 21: ↑12 and ↓9 +3
Views 30K
Comments 47

Реализация минимизации логических функций методом Квайна\Мак-Класки

Data Mining *Algorithms *C# *Machine learning *
Sandbox
К рассмотрению предлагается одна из возможных реализаций алгоритма минимизации логических (булевых) функций (ЛФ) заданных в виде совершенной дизъюнктивной нормальной формы (СДНФ) методом Квайна\Мак-Класки (далее просто Мак-Класки) и проблемы, выявленные при её тестировании. В исследуемом варианте алгоритм Мак-Класки реализован на языке C# с использованием Generic-коллекций библиотеки .NET.

Хотелось бы отметить, что задача минимизации ЛФ, по моему мнению, незаслуженно обходится стороной в тематике алгоритмов машинного обучения, т. к. по своему смыслу она реализует процедуру обучения с учителем для определённого набора входных терм (простых конъюнкций), на которых оптимизируемая функция принимает истинное (true) значение. Следовательно, этот набор входных терм, из общего их возможного числа $2^N$, где N – количество двух классовых категориальных (двоичных) переменных в термах, является обучающей выборкой для задачи обучения с учителем с известным (данном случае истинным) выходным значением целевой функции. Для всех остальных возможных терм, не входящих в обучающую выборку, минимизированная ЛФ должна принимать ложное (false) значение.

Одним из легко реализуемых для любого количества входных переменных алгоритмов минимизации ЛФ является метод Мак-Класки. Согласно теории метод Мак-Класки состоит из двух основных этапов:
Читать дальше →
Total votes 17: ↑16 and ↓1 +15
Views 18K
Comments 8

Реализация минимизации логических функций методом Квайна\Мак-Класки при неполном входном наборе

.NET *Data Mining *Algorithms *C# *Machine learning *
Данная статья является, в некоторой степени, продолжением моей статьи по минимизации логических функций методом Квайна-Мак’Класки (https://habr.com/post/328506). В ней рассматривался случай с полностью определёнными логическими функциями (хотя этого в ней прямо не упоминалось, а только подразумевалось). В реальности такой случай встречается достаточно редко, когда количество входных переменных мало. Частично или не полностью определенными называются логические функции, значения которых заданы лишь для части Q из полного множества P=$2^N$ возможных наборов (термов) их аргументов (переменных) количеством N, т. е. Q < P. Такая ситуация встречается на практике в большинстве случаев применений алгоритмов оптимизации логических функций. Действительно, например, если число входных переменных N=30, что является заурядным случаем, например на финансовых рынках, то объём входной обучающей выборки должен составлять порядка $2^{30}$>$10^9$ элементарных уникальных термов. Такой массив данных встречается не в каждой даже очень крупной организации, не говоря уже о частных лицах, т. е. это уже сфера BigData, использования ЦОД-ов и т. д.

Поэтому на практике чаще всего минимизируемые логические функции будут определены не полностью просто в силу отсутствия необходимого количества накопленных данных или в силу разных других объективных причин (например, не хватает места для их хранения). Возникает вопрос о возможности «обхода» этой неприятности при использовании алгоритма, работающего с полностью определённым набором терм логической функции, таким как, например, из предыдущей моей статьи.
Читать дальше →
Total votes 20: ↑19 and ↓1 +18
Views 4.7K
Comments 0
1