Pull to refresh
48.02
REG.RU
Домены, хостинг, серверы

Perl Golf на YAPC::Russia 2014

Reading time 3 min
Views 3.8K


Мы в 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). Не то чтобы это сильно помогало. Но всё же.

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



Несколько решений из комментариев к посту:


107 символовxtender
160 символовbrom_portret
81 символbiophreak

Спасибо всем, кто уделил время конкурсу!
Tags:
Hubs:
+10
Comments 34
Comments Comments 34

Articles

Information

Website
www.reg.ru
Registered
Founded
Employees
501–1,000 employees
Location
Россия
Representative
Рег.ру