typedef

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

В общем, я изобрел велосипед, ура.

(1 голосов, средний: 3,00 из 5)

 Loading ...

Такая вот классическая задача, которая которую я когда-то увидел в книжке «C Traps and Pitfalls». Для современных компиляторов ответ однозначен: вложенные комментарии вида /*…/*…*/…*/ не поддерживаются, см. п. 6.4.9-1 стандарта C99. Но во времена динозавров, говорят, некоторые компиляторы все-таки поддерживали. Собственно, задача формулируется так:

Написать программу на C, компилирующуюся без ошибок (warning-и не в счет), которая при запуске выводит «YES», если вложенные комментарии поддерживаются, и «NO», если это не так.

Механизм, вокруг которого должна строиться такая программа, очевиден — вложенные комментарии:

/* всегда в комментарии /* всегда в комментарии */ какой-то-код */

Если вложенность поддерживается, какой-то-код — всего лишь часть комментария. Но если вложенности нет, то комментарий кончается на первом же «*/», а какой-то-код будет выполнен. Проблема только в одном: что делать с остающимися в хвосте «*/»? Наверное, нужно где-то раньше поместить парные «/*», но тогда код станет некорректным в случае, если вложенность поддерживается. Нетрудно видеть, что написание комментариев с еще большей глубиной вложенности лишь усугубляет проблему.

(Здесь самое время прекратить читать и попытаться придумать решение самостоятельно.)

Ключ к решению — различная лексическая трактовка символов в зависимости от контекста. Я придумал три способа:

1. Использовать двойные кавычки. Символы между парными кавычками становятся частью строкового литерала. Конечно, придется использовать два набора вложенных комментариев.
2. Использовать символ «*», в зависимости от ситуации, как оператор разыменования или оператор умножения. Опять нужно два набора комментариев.
3. Поглотить «*/», сделав эту строку содержимым символа препроцессора. Здесь нужно также вспомнить, что комментарии обрабатываются препроцессором до обработки макродиректив.

Код выглядит немного странно, но разобраться несложно:

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

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

(2 голосов, средний: 4,50 из 5)

 Loading ...

Напомню требования к программе.

1. Входные данные — последовательность строк; каждая строка начинается с прописной буквы, остальные буквы строчные.
2. Входную последовательность всегда можно переупорядочить в допустимую последовательность, в которой у каждой пары смежных строк первая буква второй строки, переведенная в нижний регистр, совпадает с последней допустимой буквой первой строки. Допустимая буква — это буква, с которой начинается хотя бы одно слово последовательности.
3. Требуется написать кратчайшую программу, находящую любую допустимую перестановку входной последовательности.

Как это часто бывает, есть два очевидных способа решения этой задачи: один быстрый, другой простой.

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

Быстрый алгоритм хорош тем, что он быстрый. И плох тем, что трудно его реализовать компактно. Такое случается с быстрыми алгоритмами, ничего не поделаешь… Из-за этого многие им предпочитают медленные и простые, но ради справедливости код все равно пишут длинный и сложный.  И комментарии к нему не пишут. А потом увольняются, а новый разработчик все переписывает заново. Используя тот же алгоритм. Да… О чем я говорил?

К счастью, в требованиях к программе ничего не сказано про время работы, что совершенно развязывает нам руки и позволяет использовать Его Величество Полный Перебор. К слову, полный перебор часто недооценивают, и он играет роль этакого алгоритмического goto — подходит не везде, но во многих случаях сильно упрощает жизнь, хотя и сильно нелюбим большинством.

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

От алгоритма перебора всех перестановок требуется только одно: как можно более короткая реализация. Концептуально наиболее просто способ — перемешивать последовательность случайным образом, как карты в колоде. При идеальном генераторе случайных чисел случайный перебор потребует столько же времени, сколько и «честный». К сожалению, в стандартной библиотеке C нет функций вроде shuffle, поэтому напишем честный перебор руками. Я взял кнутовское «Искусство программирования», том 4, выпуск 2, главу 7.2.1.2 и нашел там на странице 71 (в русскоязычном издании) алгоритм генерации перестановок с помощью циклических сдвигов. Автор уверял, что алгоритм отличается чертовски простой реализацией. Итак, имея исходную последовательность $x_1\ldots x_n$:

1. Установить $a_i = x_i$, $1 \leq i \leq n$.
2. Посетить перестановку $a_1 \ldots a_n$ и установить $k = n$.
3. Заменить $a_1a_2\ldots a_k$ на $a_2\ldots a_ka_1$ (циклический сдвиг). Если $a_k \neq x_k$, перейти к п. 2.
4. Уменьшить $k$ на 1. Если $k > 1$, вернуться к п. 3 (мы будем возвращаться на п.3 без выполнения этой проверки, т.к. знаем, что одна из перестановок нам точно подойдет).

Проверка перестановки на допустимость выполняется элементарно. Построим множество первых букв всех слов. Для каждой пары соседних слов в перестановке:

1. Отбрасываем с конца первого слова буквы до тех пор, пока последняя буква не будет присутствовать в множестве первых букв. Такая буква всегда существует: в худшем случае это будет первая буква слова.
2. Сравниваем последнюю оставшуюся букву первого слова с первой буквой второго слова.

Поскольку первые буквы — прописные, их надо преобразовать в строчные. Проще всего это делается для букв в кодировке 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;
}

А дальше дело техники — надо сжимать программу:

1. Всем переменным — кратчайшие имена.
2. Убираем включения заголовочных файлов, оператор return (компилятор сам вставит), все упоминания типа int (это тип по умолчанию, его можно не указывать).
3. Вспоминаем, что глобальные переменные инициализируются нулями.
4. Заменим sizeof(char*) на 4 или 8, если компилируем, соответственно, на 32- или 64-разрядной системе.
5. Используем argc в качестве одной из нужных нам переменных, например, maxidx.

Получим:

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

Ну, и остается только

1. Избавиться от strlen — указатель на последнюю букву можно найти и короче.
2. Выполнить кое-какие перестановки присваиваний и инкрементов, использовать разыменование вместо индексации.
3. Убрать пробелы и переводы строк.

Получим итоговый вариант (разбиение на строки оставлено для читабельности):

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 символа.

(Еще не оценили)

 Loading ...

Вчера наткнулся на давно закончившийся конкурс на написание самой короткой программы для игры «в города». Вкратце: программе подается на вход набор строк, а она их должна выстроить так, чтобы последняя буква 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]);

Если интересно, как это работает, напишу отдельным постом.

(4 голосов, средний: 4,00 из 5)

 Loading ...

Если кто будет спрашивать, cond — это из мира Лиспа.

Подобную же конструкцию можно сделать и в C:

var = (cond1 ? expression1 :
       cond2 ? expression2 :
       /* ... */
       else-expression);

Переменной var присваивается значение выражения expression1, если истинно значение выражения cond1, присваивается значение expression2, если истинно значение cond2, и т.д. Если ни один condX не истинен, присваивается значение else-expression.

По-моему, красиво. Для пущего сходства с Лиспом можно добавить скобочек.

(1 голосов, средний: 3,00 из 5)

 Loading ...