У меня ни школьные, ни институтские курсы математики никогда не вызывали особых проблем. Я даже участвовал в каких-то математических олимпиадах и даже, не поверите, занимал призовые места. Это сейчас я обленился  и все забыл, но когда-то решение задачек и головоломок меня весьма увлекало. Однако у меня была и остается одна черта, раз за разом основательно портящая всю малину, — невнимательность.

Помню, как дважды досрочно (каково, а?) сдавал экзамен по дифурам. Оба раза я был идеально готов, и преподаватель об этом знал. И оба раза я сделал глупейшие, хотя и разные, ошибки и пришел к неправильным результатам. Если бы я сам у себя принимал экзамен, то ошибки эти заметил бы непременно, настолько они бросались в глаза! В результате получил «хорошо», и это было очень обидно, но правильно и справедливо.

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

Приведу на тему самопроверки несколько поучительных примеров.

1. True story. Наверняка все уже слышали эту историю.

Был он [преподаватель математики] человеком крупным и покушать любил. В столовой однажды взял он два супа, два вторых… словом, обед в двух экземплярах. Подходит к кассе. Молоденькая кассирша щелк-щелк-щелк на счетах:«С вас 2-17», он в ответ «Неправильно». Кассирша снова за счеты: «2-05», он в ответ «Неправильно». Кассирша, окончательно смущенная и напуганная, — щелк-щелк-щелк — «1-97», а сей ученый муж ей в ответ: «Снова неправильно!» Отчаявшаяся кассирша: «А сколько должно быть?!» Он в ответ: «Не знаю. Но два одинаковых обеда — четное число!»

2. Взвешивание монет.

У нас есть 9 монет, 8 из которых имеют одинаковый вес, а вес одной (фальшивой) больше весов остальных. Также у нас есть равноплечные весы с чашами. Необходимо найти фальшивую монету за минимальное число взвешиваний.

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

Попробуем подойти с другого бока. Представим номер фальшивой монеты в двоичном виде. Очевидно, 3 бит недостаточно, в них можно закодировать только 8 номеров, а 4 — уже слишком много, в них можно закодировать целых 16. Точное значение количества требуемых битов выражается двоичным логарифмом: log₂9. Теперь заметим, что каждое взвешивание может иметь 3 возможных исхода: левая чаша тяжелее, правая чаша тяжелее, чаши в равновесии. Таким образом, результат взвешивания можно представить log₂3 битами. Теперь чтобы найти минимальное необходимое количество взвешиваний, нужно найти отношение количества неизвестных нам битов к количеству битов, получаемых за одно взвешивание, и округлить вверх: ceil(log₂9 / log₂3) = ceil(log₂(9/3)) = ceil(log₂3) = 2.

Понятно, что для 9 монет все это имеет мало смыла в силу очевидности ответа, но что если монет не 9, а 999? Слабо найти минимальное число взвешиваний? Да легко: ceil(log₂999 / log₂3) = ceil(log₂333) = 9. И теперь, зная ответ, гораздо проще подобрать искомую последовательность взвешиваний.

3. Самые быстрые лошади.

В скачках участвует 25 лошадей. В каждом заезде может участвовать не более 5 лошадей. Результатом заезда является последовательность прохождения участниками финишной черты, времена не фиксируются. Две лошади не могут финишировать одновременно. Скорости лошадей постоянны: в каждом заезде лошадь скачет с одной и той же скоростью. Требуется за минимальное количество заездов определить первую, вторую и третью быстрейшую лошадь.

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

Что ж, попробуем подумать. Из условия следует, что если взять любые две лошади, то или первая будет быстрее второй, или вторая быстрее первой. Сформулируем, что именно нужно найти:

• лошадь, которая быстрее каждой из 24 остальных лошадей;
• лошадь, которая быстрее каждой из оставшихся 23;
• лошадь, которая быстрее каждой из оставшихся 22.

Таким образом, для получения ответа нужно знать по меньшей мере 24 + 23 + 22 = 69 отношений «быстрее».

Теперь заметим, что каждый заезд из 5 лошадей дает нам 4 + 3 + 2 + 1 = 10 отношений. После этого легко найти минимальное количество заездов: просто поделим 69 на 10 и округлим вверх. Выходит, что нужно как минимум 7 заездов. Конкретную расстановку лошадей не буду приводить, можете сами определить, если хотите.

При построении проверки, разумеется, тоже можно провраться. Но здесь уже решение может выступить в роли проверки для проверки. Все-таки случаи взаимной совместимости неправильного решения и неправильной проверки маловероятны.

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

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

dpkg -S pattern
dpkg --search pattern
dpkg-query -S pattern
dpkg-query --search pattern

Понятно, что dpkg здесь — просто фронтенд к dpkg-query.

Шаблон имени файла pattern может включать shell-style wildcards (можно я не буду переводить?).

Если же хотим искать во всех пакетах вообще, даже неустановленных, то:

apt-file search pattern

Если задать опцию --regexp|-x, то pattern становится перловой регуляркой.

Кстати, apt-file использует собственную БД, поэтому перед первым использованием нужно выполнить

apt-file update

чтобы синхронизироваться с репозиториями из /etc/apt/sources.list.

ML Class близок к идеалу. Именно таким должен быть настоящий учебный курс — невероятно простым, невыносимо нудным, но при этом дающим твердое понимание того, что происходит и как это работает. Рижским бальзамом на душу льются слова Andrew Ng: «Если вы это не понимаете, не переживайте, сейчас я расскажу, поймете» или «Если вы это не понимаете, не переживайте, я тоже не понимаю, это вам не нужно«. Ну и прочие подобные высказывания и шутки вроде «Если вы эксперт в линейной алгебре и знаете, что такое собственные вектора, то …» доставляют. Столько студентов сразу почувствовали себя экспертами в линейной алгебре! Отдельная благодарность за возможность ускорить лекции в 1.2 и 1.5 раза.

AI Class имеет гораздо больший охват материала, но при этом он менее проработанный. Куча несогласованной терминологии, много недосказанного, вопросы иногда расплывчаты и имеют слабое отношение к тексту. Постоянно происходят какие-то технические накладки, то сроки отодвигаются, то публикуются уточнения к вопросам, то еще какая напасть. Это не говоря уже об очаровательном немецком акценте Prof. Sebastian Thrun, которого я, в отличие от ускоренного Andrew Ng, понимал только процентов на 95 — некоторые фразы не могли понять даже native speakers. Но, несмотря на все недостатки, получился очень неплохой обзорный курс.

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

В целом нисколько не жалею, но курсы будущего семестра — разве что в пассивном режиме посмотрю.

Черт, да что же это за месяц такой…

Категорически не соглашусь. Лично для меня курс философии науки стал, не побоюсь этого слова, откровением. Можно сказать, поворотным пунктом. Когда в школе и в вузе проходят различные науки, совершенно не затрагивают тему того, насколько мы можем быть уверены в предлагаемом знании. И у каждого слушателя формируется своё весьма наивное представление о сущности истины и человеческого знания. Кто-то, например, освоил какой-то метод в какой-то области, сидит и только его применяет, а всё остальное считает ересью. А кто-то, скажем, любое порождение своего мозга принимает за великое открытие. Кто-то считает математику непогрешимой, а кто-то – что математика вообще ни на что не способна. Немалая доля людей вовсе науку не признаёт, а верит в различное НЛО и т. п.

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

Возможно, автору просто не повезло с преподавателями оного курса.

Я вам тоже могу открыто признаться, что не мог терпеть философию до тех пор, пока не прослушал курс философии науки в аспирантуре. В том числе когда проходил «философию» на четвёртом курсе.

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

> В этой области множество людей столетиями придумывали термины, «законы» и «принципы».

Термины, законы и принципы как таковые (то бишь как руководство к действию) не нужны. История философии – это суть собрание заблуждений. И именно этим она ценна. Ибо с очень большой вероятностью человек может встретить среди них и свои заблуждения. И увидеть не только преимущества, но и недостатки по сравнению с другими заблуждениями, и на основании этого, возможно, изменить свои взгляды. Грубо говоря, философия учит задавать себе неудобные вопросы и излечивает от излишней уверенности в себе.

> до какого-нибудь Витгенштейна

Витгенштейн, равно как и вся философия науки двадцатого века, совершенно напрямую связан с математикой и проблемами построения искусственного интеллекта. Ещё раз повторю, что ни его, ни любого другого философа не следует принимать на веру. Просто полезно на минуту представить себя в его шкуре.

> И думается мне, что те принципы, которые, по идее, должна прививать ученому философия, нормальный ученый прививает себе сам.

А вот для чего, скажем, программисты алгоритмы проходят? Достаточно было бы обучить кодить и компилять, а коли человек достаточно умный, то до всех необходимых алгоритмов сам додумается. Конечно, это грубая аналогия, но смысл именно такой. Мировоззрение, конечно, за самого человека никто не сформирует. Но если он будет выбирать подходящее мировоззрение не только из собственных домыслов, но и на основании предыдущего опыта человечества – то он сможет сделать это более адекватно. Конечно, научное мировоззрение неявно сквозит в большинстве специальных курсов. Но, как известно, явное лучше неявного.

> Нет, я согласен, что при наличии хорошего преподавателя это может быть даже интересно, но нужно ли?

А зачем вообще общеобразовательные предметы проходят? Для того, чтобы человек видел перспективу, а не становился специалистом по правой ноздре. Другое дело, что т. н. гуманитарные предметы действительно в массе своей преподаются совершенно паскудным образом. Видимо, потому, что в гуманитарии идут в основном люди, у которых не сложились отношения с математикой и которые посвящают всю оставшуются жизнь убеждению окружающих, что плохи не они, а математика.

Ежели спрашивать лично меня – то я бы исключил литературу и русский язык из школьной программы за полной бесполезностью. Оставил бы только чтение-запись в начальной школе.

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

Из конкретных философских трактатов могу порекомендовать разве что статью Карла Поппера об эволюционной эпистемологии http://www.keldysh.ru/pages/mrbur-web/philosophy/popper.html . Также не совсем по теме, но всё же – Ричард Докинз «Эгоистичный ген».

Что интересно, мой вариант более чем вдвое короче, чем представленный в Википедии.

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
2
3
4
5
6
7

using namespace std;
int value = 0;
while (not (cin >> value)) {
    cout << "Invalid format" << endl;
    cin.clear();
}
cout << "Your input: " << value << endl;

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

Беглый гуглеж приводит меня к функции istream::sync(), которая, как говорит один источник, делает именно то, что нам нужно:

Synchronizes the buffer associated with the stream to its controlled input sequence. This effectively means that the unread characters in the buffer are discarded.

Что ж, попробуем:

1
2
3
4
5
6
7
8

using namespace std;
int value = 0;
while (not (cin >> value)) {
    cout << "Invalid format" << endl;
    cin.clear();
    cin.sync();
}
cout << "Your input: " << value << endl;

Хм. В моей системе результат не изменился, код работает точно так же, как и первый. Беда в том, что функция istream::sync() в некоторых реализациях стандартной библиотеки таки отбрасывает непрочитанные символы. Но не в моем случае.

А я человек простой — лезу в код своей стандартной библиотеки и смотрю что да как. Выходит, что istream::sync() вызывает stdio_sync_filebuf::pubsync(), которая вызывает stdio_sync_filebuf::sync(), которая, наконец, вызывает fflush(stdin). Понятно, что fflush(stdin) не может оказать никакого влияния на входной буфер cin.

Так что упомянутый выше «один источник» не стоит считать истиной в последней инстанции. Но надо сказать, что попытки найти истину в стандарте — еще более неблагодарное занятие.

В общем, правильное решение заключается в использовании функции istream::ignore() таким вот образом:

1
2
3
4
5
6
7
8

using namespace std;
int value = 0;
while (not (cin >> value)) {
    cout << "Invalid format" << endl;
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
cout << "Your input: " << value << endl;

Надо отметить, что вызов ignore() неплохо бы вставлять даже после успешного ввода, так как при вводе строки «123qwe» первые три символа будут прочитаны и распознаны как число, а «qwe» останутся во входном буфере и будут портить жизнь при следующем чтении. Еще одна тонкость — обработка конца файла. Если пользователь в ответ на приглашение к вводу нажмет Ctrl+D или что там в вашей системе для этого предназначено, то программа вместо того, чтобы завершиться, сообщит о неверном формате и предложит ввести число еще раз. Поэтому по-хорошему код должен быть вроде этого (вся программа):

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
29

#include <iostream>
#include <limits>
using namespace std;
template <typename Type>
bool read_value(const std::string &prompt, Type &value)
{
    bool repeat = true;
    bool eof = cin.eof();
    while (repeat and not eof) {
        cout << prompt << ": ";
        cin >> value;
        eof = cin.eof();
        repeat = cin.fail() and not eof;
        if (repeat) {
            cout << "***Invalid data format!" << endl;
            cin.clear();
        } else if (eof) {
            cout << "(EOF)" << endl;
        }
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }
    return not eof;
}
int main()
{
    int value = 0;
    while (read_value("Input integer", value))
        cout << "Your input: " << value << endl;
}

Но и в этом, казалось бы, безошибочном, коде затаилась пара граблей. Например, что если функцию read_value() использовать для ввода символов или строк? Сумеем мы ввести символ пробела? Сумеем ли ввести строку из нескольких слов, разделенных пробелами? Хрен! С вводом символа пробела еще несложно — надо только использовать манипулятор noskipws, а вот ввод строк с пробелами потребует перегрузки read_value() и использования getline() вместо оператора >>.

В общем, писать на C++ — сплошное счастье.
Note: There is a rating embedded within this post, please visit this post to rate it.

• Объектно-ориентированный bash.
• Bash on Balls — web-framework на bash.

1. На младших курсах все студенты изучают математический анализ. Это очень непростой для неокрепших умов предмет, и самое непростое в нем то, что когда его изучаешь, ты абсолютно не понимаешь, зачем все это нужно. Понять доказательство теоремы Вейерштрасса или разложение в ряд Тейлора в принципе можно, но должно пройти немало времени, прежде чем может быть у кого-то возникнет дежа вю — «Кажется, что-то такое я учил на первом курсе… Но уже нифига не помню». Хуже всего, если эти знания действительно нужны, и приходится открывать учебники и учиться заново. Во второй раз изучать получается быстрее, но все равно время жалко.
2. На младших курсах многие студенты изучают еще и разнообразную физику. Это вообще труба, потому что используемый в лекциях матаппарат студенты еще не проходили. В результате физику никто не знает, а когда приходит время изучать тот матаппарат, то параллели провести тоже не получается — едва ли кто-то воскликнет «Так вот что, оказывается, имел в виду наш физик год назад, когда говорил о линейных операторах!».

Интересно то, что многие считают второй случай вопиющей халатностью при составлении учебного плана, а первый — неизбежным злом. Некоторые даже добавят что-то в духе «учиться надо было лучше». Так вот, я учился хорошо. Местами даже отлично. И получил красный диплом. Но сейчас, в аспирантуре, мне приходится изучать математику заново, иногда даже по тем же самым учебникам.

Мне придумалась образное объяснение, почему так происходит — теория крючков. Она состоит из следующих постулатов:

1. Поглощаемые человеком знания ищут в мозгу крючки, за которые могут зацепиться. Чем больше таких крючков, за которые зацепилось некоторое знание, тем дольше оно останется в мозгу.
2. Крючки типизированные: определенным знаниям нужны определенные крючки. Нельзя зацепить знания о языке Фортран за крючки, относящиеся к плаванию кролем.
3. Хотя некоторые уникумы умудряются нарушать типизацию крючков, проводя смелые аналогии в различных областях знаний.
4. Закрепленные в мозгу новые знания сами начинают создавать крючки. Больше знаний — больше крючков — проще усваиваются новые знания.

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

• Когда знаешь много языков программирования (или иностранных языков), изучить еще один — гораздо более простая задача, чем изучить первый. Новый язык цепляется за множество крючков, выращенных уже изученными языками.
• Система крючков гуманитария кардинально отличается от оной у технаря. Поэтому технические понятия гуманитарии воспринимают с трудом — крючки не подходят!
• Проводить аналогии между программированием и постройкой домов, литературой, живописью, вышиванием крестиком или выращиванием цветов — нарушение типизации крючков. Но кто сказал, что это плохо?
• Теория, пересыпанная примерами, изучается куда проще, чем сначала куча теории, а потом куча примеров. Поглощая знания маленькими кусочками, мы цепляем их друг к другу, не давая им успеть забыться. С большими кусками сложнее. Это все равно как есть очень длинную колбасу — пока доедаешь ее конец, начало уже давно переварилось и путешествует по канализации.
• В этом посте неимоверное, зашкаливающее количество употреблений слова «крючок».

В общем, берегите свои крючки и не цепляйте на них всякую гадость.

Написать программу на 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

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

А первые две задачи во втором дивизионе вот уже второй матч подряд совсем простые. Или дело во мне?..

В сносках были ссылки на научные статьи. Такие дела.

Я аж всплакнул от счастья.

• Ghosts of Unix Past, part 1
• Ghosts of Unix Past, part 2
• Ghosts of Unix Past, part 3
• Ghosts of Unix Past, part 4

Вкратце о содержимом. В ранние годы Unix были приняты некоторые архитектурные решения, которые определили то, что сейчас принято называть «Unix Way». Над этими решениями думали не самые глупые люди, но предусмотреть, что будет через 40 лет, никто не в силах. Поэтому в свете современных требований некоторые ключевые решения и паттерны до сих пор остались красивыми и согласованными, а некоторые породили проблемы разной величины. В статьях как раз про второй тип: какие выявились проблемы, как их можно решать и как они решаются сейчас.

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

Как часто бывает на LWN, комменты не менее ценны, чем сами статьи.

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

Победило в конкурсе решение, кто бы сомневался, на Перле в 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]);

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

1. Составляем структурную матрицу $A$ графа $G$. Элемент $a_{ij}$ матрицы содержит:
   • $0$, если в графе нет ребра $(i, j)$.
   • $1$, если $i = j$.
   • Имя булевской переменной, идентифицирующей ребро $(i, j)$. Если $i < j$, указывается сама переменная, а если $i > j$, то ее отрицание, например, $a_{ij}=x$ и $a_{ji}=\bar x$. Если между вершинами $i$ и $j$ несколько ребер, указывается их конъюнкция, например, $a_{ij}=x \wedge y$ и $a_{ji}=\bar x \vee \bar y$.
2. Для нахождения всех простых путей между вершинами $i$ и $j$ необходимо найти дополнительный минор $\bar{M}^j_i$ (вычеркнуть $j$-ую строку и $i$-ый столбец и найти определитель оставшейся матрицы) по следующим правилам:
   • вместо сложения/вычитания используется дизъюнкция;
   • вместо умножения используется конъюнкция;
   • $1$ выступает в роли истинного значения, а $0$ — ложного;
   • $x \wedge \bar x$ уничтожаются, ну и вообще, можно выполнять обычные булевские преобразования.
3. Получили булевское выражение в дизъюнктивной форме. Каждая конъюнктивная группа в нем соответствует маршруту между выбранными вершинами, а каждая переменная, входящая в группу, обозначает соответствующее ребро. Отрицания можно убрать, они показывают направление прохождения ребер.

Немного запутанно выглядит, да? Рассмотрим на конкретном примере. Возьмем полный граф с тремя вершинами. Ребрам сопоставим следующие переменные:

• $(1, 2)$ — $x$;
• $(1, 3)$ — $y$;
• $(2, 3)$ — $z$.

Структурная матрица тогда получится такой:

$$
A=\left( \begin{array}{ccc}
1 && x && y\\
\bar x && 1 && z \\
\bar y && \bar z && 1
\end{array} \right)
$$

Найдем все маршруты между вершинами 1 и 3. Вычеркнув третью строку и первый столбец, найдем значение минора:

$$
\bar M^3_1 = \left| \begin{array}{cc}
x && y \\
1 && z
\end{array} \right| = (x \wedge z) \vee y
$$

Вот и получилось, что есть два маршрута, один через ребра $x$ и $z$, а второй — через ребро $y$.

Красивый хак, а? Что интересно, как я ни старался, не смог найти описание этого метода в англоязычных источниках. Может, кто-то видел подобное?

P.S. Включите JavaScript для отображения формул. Если не работает, пишите в комменты вместе с версией браузера.