Perl Golf на YAPC::Russia 2014
Мы в 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). Не то чтобы это сильно помогало. Но всё же.
Если вы вдруг смогли сделать ещё более короткое решение, или придумать какой-нибудь особо удачный трюк — не стесняйтесь поделиться, с удовольствием добавлю ваше решение в публикацию.
