typedef

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