Dennis Ritchie
Thanks for C and UNIX.
RIP.
Тег «C»
Thanks for C and UNIX.
RIP.
Для тех, кто не знает: quine (квайн) — это программа, которая при запуске выводит свой исходный текст.
Что интересно, мой вариант более чем вдвое короче, чем представленный в Википедии.
main(){char*p="main(){char*p=%c%s%c,c='%c',s[256];sprintf(s,p,c,p,c,c);puts(s);}",c='"',s[256];sprintf(s,p,c,p,c,c);puts(s);}
Изобрел я его совершенно случайно как побочный эффект своих рабочих дел. Опечатавшись, указал в printf() форматную строку как один из подставляемых аргументов, подставив тем самым форматную строку саму в себя. Сразу появились ассоциации с квайнами, повозился минут 15 — и готово. Заодно запостил в соответствующий раздел Codegolf@Stackexchange.
Добавлено
Оказывается, этот подход уже сто лет назад как придумали, и программа намного короче:
char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}
В общем, я изобрел велосипед, ура.
Такая вот классическая задача, которая которую я когда-то увидел в книжке «C Traps and Pitfalls». Для современных компиляторов ответ однозначен: вложенные комментарии вида /*…/*…*/…*/ не поддерживаются, см. п. 6.4.9-1 стандарта C99. Но во времена динозавров, говорят, некоторые компиляторы все-таки поддерживали. Собственно, задача формулируется так:
Написать программу на C, компилирующуюся без ошибок (warning-и не в счет), которая при запуске выводит «YES», если вложенные комментарии поддерживаются, и «NO», если это не так.
Механизм, вокруг которого должна строиться такая программа, очевиден — вложенные комментарии:
/* всегда в комментарии /* всегда в комментарии */ какой-то-код */
Если вложенность поддерживается, какой-то-код — всего лишь часть комментария. Но если вложенности нет, то комментарий кончается на первом же «*/», а какой-то-код будет выполнен. Проблема только в одном: что делать с остающимися в хвосте «*/»? Наверное, нужно где-то раньше поместить парные «/*», но тогда код станет некорректным в случае, если вложенность поддерживается. Нетрудно видеть, что написание комментариев с еще большей глубиной вложенности лишь усугубляет проблему.
(Здесь самое время прекратить читать и попытаться придумать решение самостоятельно.)
Ключ к решению — различная лексическая трактовка символов в зависимости от контекста. Я придумал три способа:
Код выглядит немного странно, но разобраться несложно:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | // file: nestcomm.c? #include <stdio.h> void method1(){ printf("Method 1: "); printf("%s\n", /*/**/" NO\0*/"/*YES\0"/**/"*/"+2); } void method2(){ int a = 1; printf("Method 2: "); printf("%s\n", /*/**/2*/*(&a)+/**/2==4?"NO":"YES"); } void method3(){ printf("Method 3: "); /*/**/#define A */ printf("%s\n", #ifdef A "NO" #else "YES" #endif ); } int main(){ method1(); method2(); method3(); return 0; } |
Компилятор с поддержкой вложенных комментариев уже не найдешь, но можно его сымитировать, написав на flex небольшой препроцессор:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | // file: snc.lex
%option noyywrap
%{
int comm = 0;
%}
%x STRING COMMENT
%%
<INITIAL>{
\" { BEGIN(STRING); ECHO; }
"/*" { comm++; BEGIN(COMMENT); }
. { ECHO; }
}
<COMMENT>{
"/*" { comm++; }
. { }
"*/" { comm--; if (!comm) BEGIN(INITIAL); }
}
<STRING>{
\" { BEGIN(INITIAL); ECHO; }
. { ECHO; }
}
%%
int main()
{
yylex();
return 0;
} |
Ну, и чтобы два раза не вставать, Makefile для автоматического прогона:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | .PHONY: all all: nest_yes nest_no @echo "With nested comments support:" ./nest_yes @echo "Without nested comments support:" ./nest_no nest_yes: nestcomm.c snc ./snc < $< > tmp.c cc -o $@ tmp.c rm -f tmp.c snc: snc.lex flex -o $(subst .lex,.c,$<) $< cc -o $@ $(subst .lex,.c,$<) nest_no: nestcomm.c cc -o $@ $< .PHONY: clean clean: rm -f snc.c snc nest_yes nest_no |
Многие считают подобные упражнения напрасной тратой времени, но на самом деле таким образом можно узнать удивительно много нового о тонкостях языка.
Напомню требования к программе.
Как это часто бывает, есть два очевидных способа решения этой задачи: один быстрый, другой простой.
Суть быстрого алгоритма: возьмем все первые и последние допустимые буквы всех слов и сделаем их вершинами в графе. Сами слова будут представлены дугами. Теперь достаточно в этом графе найти эйлерову цепь или эйлеров цикл. Если кто не помнит, эйлерова цепь/цикл проходит через каждую дугу графа ровно один раз. В честь Эйлера, который желал странного, бродя по кенигсбергским мостам.
Быстрый алгоритм хорош тем, что он быстрый. И плох тем, что трудно его реализовать компактно. Такое случается с быстрыми алгоритмами, ничего не поделаешь… Из-за этого многие им предпочитают медленные и простые, но ради справедливости код все равно пишут длинный и сложный. И комментарии к нему не пишут. А потом увольняются, а новый разработчик все переписывает заново. Используя тот же алгоритм. Да… О чем я говорил?
К счастью, в требованиях к программе ничего не сказано про время работы, что совершенно развязывает нам руки и позволяет использовать Его Величество Полный Перебор. К слову, полный перебор часто недооценивают, и он играет роль этакого алгоритмического goto — подходит не везде, но во многих случаях сильно упрощает жизнь, хотя и сильно нелюбим большинством.
Идея простого алгоритма в том, чтобы рассмотреть все перестановки входной последовательности и проверить каждую на допустимость. Одна из них, согласно условию, обязательно подойдет.
От алгоритма перебора всех перестановок требуется только одно: как можно более короткая реализация. Концептуально наиболее просто способ — перемешивать последовательность случайным образом, как карты в колоде. При идеальном генераторе случайных чисел случайный перебор потребует столько же времени, сколько и «честный». К сожалению, в стандартной библиотеке C нет функций вроде shuffle, поэтому напишем честный перебор руками. Я взял кнутовское «Искусство программирования», том 4, выпуск 2, главу 7.2.1.2 и нашел там на странице 71 (в русскоязычном издании) алгоритм генерации перестановок с помощью циклических сдвигов. Автор уверял, что алгоритм отличается чертовски простой реализацией. Итак, имея исходную последовательность $x_1\ldots x_n$:
Проверка перестановки на допустимость выполняется элементарно. Построим множество первых букв всех слов. Для каждой пары соседних слов в перестановке:
Поскольку первые буквы — прописные, их надо преобразовать в строчные. Проще всего это делается для букв в кодировке ASCII или CP1251: нужно просто прибавить к коду буквы 32.
Итак, первый вариант программы:
#include <stdio.h> #include <string.h> int main(int argc, char** argv){ int k, i, match, first[256]; char *r, *permut[256]; int maxidx; // обнуляем множество первых букв for (i = 0; i < 256; i++) first[i] = 0; // входная последовательность задана в командной строке, поэтому // пропускаем находящееся в начале массива argv имя программы argv++; // проходим по входным словам (argv завершается нулевым указателем) for (i = 0; argv[i]; i++) { permut[i] = argv[i]; // начальная перестановка равна исходной first[permut[i][0] + 32] = 1; // добавляем первую букву слова в множество } maxidx = i - 1; // максимальный индекс слова в последовательности k = maxidx; // когда match станет 1, допустимая последовательность найдена for (match = 0; !match;) { // циклический сдвиг элементов массива permut с 0 по k-1 r = permut[k]; memmove(permut + 1, permut, k*sizeof(char*)); permut[0] = r; // см. алгоритм сдвига if (permut[k] == argv[k]) k--; else k = maxidx; // проверка перестановки на допустимость for (i = 0, match = 1; i < maxidx - 1 && match; i++) { // получим указатель на последнюю букву первого слова r = permut[i] + strlen(permut[i]) - 1; // сдвигаем указатель, пока не найдем букву из множества первых букв while (!first[*r]) r--; // проверяем совпадение match = (*r == *permut[i + 1] + 32); } } for (i = 0; i <= maxidx; ++i) printf("%s\n", permut[i]); return 0; }
А дальше дело техники — надо сжимать программу:
Получим:
k, i, b, f[256]; char *r, *q[256]; main(int l, char** x){ x++; for (i = 0; x[i]; i++) { q[i] = x[i]; f[*q[i] + 32] = 1; } l = i - 1; k = l; for (; !b;) { r = q[k]; memmove(q + 1, q, k*4); q[0] = r; if (q[k] == x[k]) k--; else k = l; for (i = 0, b = 1; i < l - 1 && b; i++) { r = q[i] + strlen(q[i]) - 1; while (!f[*r]) r--; b = (*r == *q[i + 1] + 32); } } for (i = 0; i <= l; ++i) printf("%s\n", q[i]); }
Ну, и остается только
Получим итоговый вариант (разбиение на строки оставлено для читабельности):
k,i,b,f[256]; char*r,*q[256]; main(int l,char**x){ for(x++;q[k]=x[k];f[*q[k++]+32]++); for (l=--k;!b;){ r=q[k]; memmove(q+1,q,k*4); *q=r; k=q[k]==x[k]?k-1:l; for (i=0,b=1;i<l&&b;){ for(r=q[i++];*r++;); while(!f[*--r]); b=*r==*q[i]+32); } } for (i = 0; i <= l; ++i) printf("%s\n", q[i]); }
Вот и все. Должен только заметить, что даже если все допустимые буквы — последние, все равно время работы алгоритма будет что-то вроде $O(n\cdot n!)$, где $n$ — количество строк во входной последовательности. Время работы сильно зависит от порядка слов во входной последовательности и от порядка перебора. На моем компьютере на 14 словах алгоритм работал более 10 минут! Добавить 15-е слово я не решился. Так что с общечеловеческой точки зрения это очень плохой алгоритм.
Кстати, в предыдущем посте у меня в код закралась неиспользуемая переменная, что позволяет сократить решение еще на 2 символа.
Вчера наткнулся на давно закончившийся конкурс на написание самой короткой программы для игры «в города». Вкратце: программе подается на вход набор строк, а она их должна выстроить так, чтобы последняя буква i-ой строки совпадала с первой буквой i+1-ой строки. Если строка оканчивается на букву, с которой не начинается ни одна другая строка, разрешается «удалять» последнюю букву до тех пор, пока это условие не нарушится. Решение всегда есть. Самое главное: основная часть программы должна состоять из минимально возможного количества символов, ввод-вывод-подготовка не считаются.
Победило в конкурсе решение, кто бы сомневался, на Перле в 62 символа (и фиг с ним). Меня поразило решение на C, в котором вся программа состоит из 229 символов. На такое я спокойно смотреть не мог. Несколько часов работы — и получилось то же самое выразить в 225 символах! Давненько я не получал такого удовольствия от возни с кодом!
k,i,t,b,f[256];char*r,*q[256];main(int l,char**s){ for(s++;q[k]=s[k];f[*q[k++]+32]++);for(l=--k;!b;){r=q[k];memmove(q+1,q,k*8);*q=r;k=q[k]==s[k]?k-1:l; for(i=0,b=1;i<l&&b;){for(r=q[i++];*r++;);while(!f[*--r]);b=*r==*q[i]+32;}}}
А если оставить только код, решающий задачу, то получится 174 символа:
for(s++;q[k]=s[k];f[*q[k++]+32]++);for(l=--k;!b;){ r=q[k];memmove(q+1,q,k*8);*q=r;k=q[k]==s[k]?k-1:l;for(i=0,b=1;i<l&&b;){ for(r=q[i++];*r++;);while(!f[*--r]);b=*r==*q[i]+32;}}
Переводы строк, как наверное многие догадались, перед подсчетом надо убрать.
Имена городов передаются в командной строке через пробел. Первая буква каждого имени должна быть прописная. Кодировка cp1251 (если русскими буквами) или ASCII. Компилировать gcc на 64-битной системе. Например:
$ ./cities Kaliningrad Vologda Dalmatovo Dmitrov Arkhangelsk Vladivistok Krakov
Dalmatovo
Vladivostok
Kaliningrad
Dmitrov
Vologda
Arkhangelsk
KrakovЧтобы программа выводила результат, нужно вставить в main код вывода:
for (i = 0; i <= l; ++i) printf("%s\n", q[i]);
Если интересно, как это работает, напишу отдельным постом.
Если кто будет спрашивать, cond — это из мира Лиспа.
Подобную же конструкцию можно сделать и в C:
var = (cond1 ? expression1 : cond2 ? expression2 : /* ... */ else-expression);
Переменной var присваивается значение выражения expression1, если истинно значение выражения cond1, присваивается значение expression2, если истинно значение cond2, и т.д. Если ни один condX не истинен, присваивается значение else-expression.
По-моему, красиво. Для пущего сходства с Лиспом можно добавить скобочек.