Мы в REG.RU страшно любим участвовать в интересных мероприятиях. Настолько любим, что даже сами стали их организовывать. Например, 13-14 июня, при спонсорской помощи компании и активном участии коллег, мы провели очередную конференцию perl-программистов YAPC::Russia 2014. Как всегда, собралась отличная компания, время было проведено приятно и полезно. К тому же, местом проведения конференции в этом году впервые стал Санкт-Петербург, да ещё и в разгар белых ночей! Немного весёлых картинок с мероприятия можно увидеть в соцсетях (ВКонтакте и Фейсбук), а на YouTube мы даже выложили часть докладов (и всё ещё не теряем надежды выложить остальные).
Помимо прочего культурного досуга, я решил повторить опыт прошлогодней конференции YAPC::Europe и снова провести конкурс Perl Golf.
Вот такая у нас в этот раз была задачка:
Число Эрдёша
Пал Э́рдёш — знаменитый венгерский математик.
Эрдёш написал за свою жизнь 1475 статей, причём многие из этих работ были созданы в соавторстве. Традиционно в математике совместная статья является скорее исключением, чем правилом, поэтому наличие такого большого числа соавторов породило в фольклоре математиков понятие «число Эрдёша».
Это число определяется следующим образом:
- у самого Эрдёша оно равно нулю,
- у непосредственных соавторов Эрдёша это число равно единице,
- соавторы людей с числом Эрдёша, равным n, имеют число Эрдёша n+1.
© Wikipedia
При этом нужно учесть, что из нескольких вариантов связей выбирается самый короткий, т. е. минимально возможное число.
Входные данные:
Первая строка содержит фамилию учёного, для которого нужно определить число Эрдёша. Последующие строки содержат список публикаций: фамилии авторов через запятую и пробел, и название работы, отделённое двоеточием. Заданная фамилия может не присутствовать ни в одной публикации.
Пример:
Chen
Smith, Martin, Erdos: Newtonian forms of prime factor matrices
Erdos, Reisig: Stuttering in petri nets
Smith, Chen: First oder derivates in structured programming
Jablonski, Hsueh: Selfstabilizing data structures
Данные подаются на STDIN:
cat data | perl golf.pl
Задача:
Вывести число Эрдёша для заданного учёного. В случае, если связи с Эрдёшем нет — вывести Inf.
Проверить работоспособность решения можно приложенным набором тестов:
prove test.pl
Размер решения можно посчитать с помощью скрипта
golfcount.pl:perl golfcount.pl golf.pl
Текст задачи, набор тестов и вспомогательные скрипты лежат на ГитХабе.
Решения проверялись на perl версии 5.16.0, на более поздних версиях могут быть предупреждения об экспериментальности smartmatch.
На удивление, схватка за победу в конкурсе развернулась ожесточённая. Участники присылали улучшенные версии своих решений буквально до последних минут перед подведением итогов и боролись за каждый символ. Да и сами решения получились более разнообразными, чем в прошлый раз. Вот как выглядела итоговая турнирная таблица:
1 (137 символов) — Виктор Сапунков
2 (139 символов) — Николай Шуляковский
3 (140 символов) — Денис Ибаев
4 (156 символов) — Павел Щербинин
5 (180 символов) — Сергей Романов
6 (190 символов) — Евгений Брейкин
7 (200 символов) — Дмитрий Латин
8 (205 символов) — Илья Колесников
9 (243 символов) — Евгений Востров
10 (393 символов) — Дмитрий Тигров
Победило, как обычно, решение с наиболее активным использованием регэкспов. Кто бы сомневался. Выглядит оно так:
#!/usr/bin/perl -0np
$i=$_;$_=unpack('%32W',$i);$o=length$i>249;s/\s*(^|$)\s*//mg;s/69/0/;s/83/1/;s/67/{2-$o}/e;s/73/Inf/;s/^$//;s/\s+//g;s/\s*\z\s*/\n/m
Все участники получили призы от компании REG.RU, а также большую тележку внимания и уважения от коллег.
Всем неравнодушным к премудростям Перла предлагаю проверить свои силы и попытаться превзойти результаты конкурсантов. Ну или хотя бы попробовать разобраться, как работают их решения. Чтобы проще было это делать, рядом с каждым решением (golf.pl) лежит его копия в отформатированном виде (golf_formatted.pl). Не то чтобы это сильно помогало. Но всё же.
Если вы вдруг смогли сделать ещё более короткое решение, или придумать какой-нибудь особо удачный трюк — не стесняйтесь поделиться, с удовольствием добавлю ваше решение в публикацию.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий