Как стать автором
Обновить

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

Время на прочтение3 мин
Количество просмотров1.7K
   Впечатленный цепным полиглотным квайном японца, приведенным в этом хабратопике, я, ранее уже встречавшийся с программами-квайнами, решил познакомиться с ними плотнее. После беглого гугления и непродолжительного чтения вики/блогов/сайтов по теме, у меня зачесались руки и захотелось написать свой квайн. Квайн был написан, даже в нескольких вариантах, но этого мне показалось мало. Позже я даже написал двойной квайн (код на 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())


Читать дальше →
Всего голосов 39: ↑32 и ↓7+25
Комментарии9

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

Время на прочтение4 мин
Количество просмотров38K
Введение

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

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

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

Время на прочтение9 мин
Количество просмотров7.6K

PalidromePolyglotQuine


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


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

Читать дальше →
Всего голосов 38: ↑37 и ↓1+36
Комментарии11

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

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

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

Полиморфный квайн

Время на прочтение2 мин
Количество просмотров5.4K

Данный квайн печатает себя в зашифрованном виде. Каждый раз с новым ключом для декодирования. Шифр простой — берём код символа и прибавляем к нему ключ. Далее ключ увеличивается на единицу. И так бесконечно. Пока не кончатся числа. :)


спектрограмма тела
Читать дальше →
Всего голосов 21: ↑21 и ↓0+21
Комментарии2

Пятничный JS: квайн, который играет в крестики-нолики

Время на прочтение6 мин
Количество просмотров7K
Приветствую всех в своей традиционной рубрике, полной лавкрафтианского безумия.

В процессе написания одной из прошлых статей (не ищите, она была не особенно хороша) я задумался над тем, что квайн… Да, на всякий случай напомню: квайн — это программа, которая выводит свой собственный текст, причём делает это «честно» (не подсмотрев, допустим, этот текст в файле на жёстком диске). В общем, традиционная бессмысленная пузомерка программистов.

Так вот, я задумался над тем, что квайн, в принципе, может нести произвольную полезную нагрузку. То есть — делать ещё что угодно помимо своей основной функции. И в качестве proof-of-concept я решил написать квайн, который играет в крестики-нолики. И написал. Грязные подробности под катом.

image
Но как он может делать что-то ещё, кроме вывода своего текста?
Всего голосов 38: ↑37 и ↓1+36
Комментарии7

Пришествие бинарных нейронных сетей на основе случайных нейронов и логических функций

Время на прочтение27 мин
Количество просмотров6.5K

На сегодня среди множества алгоритмов машинного обучения широкое применение получили нейронные сети (НС). Основное преимущество НС перед другими методами машинного обучения состоит в том, что они могут выявить достаточно глубокие, часто неочевидные закономерности в данных. Классической парадигмой среди НС являются полносвязные сети с обратным распространением ошибки.


У полносвязных НС с обратным распространением ошибки имеется много преимуществ, главным среди которых является достаточно высокая точность классификации исходных данных, основанная на «сильном» математическом аппарате, лежащем в основе их функционирования. Но, с другой стороны, есть и недостатки, самым значительным среди которых является склонность к переобучению, когда НС подстраивается под локальные особенности обучающей выборки и утрачивает обобщающую способность. Это снижает эффективность и целесообразность их использования в качестве средства классификации или прогнозирования вне обучающей выборки на произвольных данных.


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

Читать дальше →
Всего голосов 8: ↑8 и ↓0+8
Комментарии41

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

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

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

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

Время на прочтение5 мин
Количество просмотров40K
Многие хабрапользователи наверняка знакомы с квайнами — программами, выводящими собственный исходный код. Сегодня я хочу показать как сделать интересный вариант квайна — ZIP-архив, который распаковывается сам в себя.

Читать дальше →
Всего голосов 171: ↑168 и ↓3+165
Комментарии55

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

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

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

Читать дальше →
Всего голосов 43: ↑18 и ↓25-7
Комментарии8

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

Время на прочтение4 мин
Количество просмотров50K

Введение


Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа 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
Всего голосов 21: ↑12 и ↓9+3
Комментарии47

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

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

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

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

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

Время на прочтение6 мин
Количество просмотров13K
Я тоже присоединяюсь к поздравлениям в честь дня программиста! И делаю это с помощью квайна-палиндрома.

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

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

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

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

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

Время на прочтение2 мин
Количество просмотров15K

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

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

Я и так знаю, просто хочу себя проверить...
Всего голосов 54: ↑33 и ↓21+12
Комментарии37

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

Время на прочтение12 мин
Количество просмотров35K

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

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

Создаём Zoomquilt

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

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

zoomquilt.org

zoomquilt2.madmindworx.com/zoomquilt2.swf

www.syfy.com/tinman/oz

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

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

Дальше о технологии создания. Под катом много картинок.
Читать дальше →
Всего голосов 44: ↑43 и ↓1+42
Комментарии14

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

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

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

Читать дальше →
Всего голосов 38: ↑31 и ↓7+24
Комментарии9

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

Время на прочтение2 мин
Количество просмотров106K


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

Цепной квайн С# (n=2)

Время на прочтение1 мин
Количество просмотров14K
Приветствую!

Вдохновленный статьёй Эстафета из 50-ти квайнов попробовал повторить действо, но только на C# и n=2, получилась неплохая задачка!
Читать дальше →
Всего голосов 36: ↑28 и ↓8+20
Комментарии8
1