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
). Не те щоб це сильно допомагало. Але все ж.
 
Якщо ви раптом змогли зробити ще більш короткий рішення, або придумати який-небудь особливо вдалий трюк — не соромтеся поділитися, із задоволенням додам ваше рішення в публікацію.
 
 
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.