Perl Golf at YAPC :: Russia 2014



    We at REG.RU are terribly fond of participating in interesting events. So loved that even they themselves began to organize them. For example, on June 13-14, with the sponsorship of the company and the active participation of colleagues, we held the next conference of perl-programmers YAPC :: Russia 2014 . As always, a great company gathered, the time was pleasant and useful. In addition, the venue for the conference this year was St. Petersburg for the first time, and even in the midst of white nights! Some funny pictures from the event can be seen on social networks ( VKontakte and Facebook ), and on YouTube we even posted some of the reports (and still do not lose hope to post the rest).

    Among other cultural activities, I decided to repeatexperience of last year’s conference YAPC :: Europe and again to hold the Perl Golf competition.

    Here we have this problem this time:

    Erdös number


    Pal Erdös is a famous Hungarian mathematician.
    Erdös has written 1,475 articles in his life, many of which were co-written. Traditionally, in mathematics, a joint article is the exception rather than the rule; therefore, the presence of such a large number of co-authors gave rise to the concept of “ Erdös number ” in the mathematics folklore .

    This number is defined as follows:
    • at Erdos itself it is zero,
    • for Erdoшаs direct co-authors, this number is equal to one,
    • co-authors of people with an Erdös number equal to n have an Erdös number n + 1.
    © Wikipedia

    In this case, one must take into account that the shortest, that is, the minimum possible number, is selected from several connection options.

    Input:
    The first line contains the name of the scientist for whom you need to determine the Erdös number. The following lines contain a list of publications: the names of the authors, separated by commas and spaces, and the name of the work, separated by a colon. The given surname may not be present in any publication.

    Example:
    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
    

    Data is submitted to STDIN:
    cat data | perl golf.pl
    

    Problem:
    Print the Erdös number for a given scientist. If there is no connection with Erdös, print Inf.

    You can check the health of the solution with the attached set of tests:
    prove test.pl
    

    The size of the solution can be calculated using the script golfcount.pl:
    perl golfcount.pl golf.pl
    

    The text of the task, a set of tests and auxiliary scripts are on the github .

    Solutions were tested on perl version 5.16.0; later versions may have warnings about smartmatch experimentation.

    Surprisingly, the battle for victory in the competition unfolded fierce. Participants sent improved versions of their solutions literally until the last minutes before summing up and fought for each character. And the decisions themselves turned out to be more diverse than last time. Here is the final standings :

    1 (137 characters) - Victor Sapunkov
    2 (139 characters) - Nikolai Shulyakovsky
    3 (140 characters) - Denis Ibaev
    4 (156 characters) - Pavel Shcherbinin
    5 (180 characters) - Sergey Romanov
    6 (190 characters) - Evgeny Breikin
    7 (200 characters) - Dmitry Latin
    8 (205 characters) - Ilya Kolesnikov
    9 (243 characters) - Evgeny Vostrov
    10 (393 characters) - Dmitry Tigrov

    Won, as usual, the solution with the most active use of regexp. Who would doubt that. It looks like this:
    #!/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
    

    All participants received prizes from REG.RU, as well as a large cart of attention and respect from colleagues.



    I propose to all who are not indifferent to the wisdom of Pearl to test their strength and try to surpass the results of the contestants. Well, or at least try to figure out how their solutions work. To make it easier to do this, next to each solution ( golf.pl) lies a copy of it in a formatted form ( golf_formatted.pl). Not that it really helped. But still.

    If you suddenly could make an even shorter decision, or come up with some particularly successful trick - do not hesitate to share, I will gladly add your decision to the publication.



    A few solutions from the post comments:


    107 characters - xtender
    160 characters - brom_portret
    81 characters - biophreak

    Thanks to everyone who took the time to compete!

    Also popular now: