9 Aug 2002 fxn   » (Master)

The TPR(0,4c) finished today at 5 UTC. There was a lot of activity in the last hours, including changes in the top of the leaderboard. It was a very exciting night, in my timezone 5 UTC is 7 AM and we were receiving submissions all the night, until the end.

66 golfers played in this tournament, they submitted 507 solutions in total, 231 for the factorial and 276 for the postorder. The winner among the veterans was Juho Snellman, and Markus Laire was the winner in the beginner's category.

The winning solution for the factorial (where the script had to print to stdout the rightmost non-zero digit of the factorial of the argument, in the range 0..9999, followed by a newline) was this 44 by Juho Snellman:

    #!perl -l
    $_*=$`%9e9,??for+1=~?0*$?..pop;print$`%10

In that program the range operator has to its left the value returned by +1=~?0*$? (the purpose of the + is to improve the tiebraker compared to an everyday space after the for), and the argument to its right (pop()ped because shift() is longer). The regexp there is then silently reused in ?? to remove trailing zeroes in conjuction with $`, a clever trick. The modulus let's the program deal with parameters in the specified range. Normally one would use 1e6 to do the computations with the last six digits, but, again, 9e9 solves the problem as well and has a better tiebraker.

The winning solution for the postorder (where the script received the preorder and the inorder of a binary tree with nodes in 'A'..'Z' and had to print its postorder and a newline) was this amazing 49 that was found by three golfers, Stephen Turner, Rick Klement, and Eugene van der Pijll:

    #!perl
    s~~
    @ARGV~;print$1until!s~(.)(?=(.).*\2.*\1| )~~s

The first substitution is a golfish way to initialize $_ to a newline followed by the arguments joined with a space in between. The algorithm uses the fact that the node to be printed in each iteration is the leftmost in the inorder whose immediately following node, if any, appears earlier in the preorder. The way it prints the mandatory newline is elegant.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!