Perform a topological sort (partial ordered sort). For all the partial ordering relationships given between nodes in an input file, output each node in an order that obeys the partial order.
(from "Mastering Algorithms with Perl")
"A Topological sort is a listing of the vertices of a graph in such
an order that all the ordering relations are respected.
...
More precisely: topological sort of a directed acyclic graph is a listing
of the vertices so that for all edges u-v,
u comes before v in the listing."
The program is a filter: it must read from STDIN, and send output to STDOUT.
The input will consist of one or more lines. Each line will consist of a pair of node names separated by a space character. A node name will consist of printable characters (it will match /^[!-~]+\z/), and the entire input will match the following: /^([!-~]+ [!-~]+\n)+\z/ Any line may appear more than once. A node name can occur in both a relationship and as an "isolated" node (same name twice on the same line).
Each input line represents a before/after relationship between two nodes, and implies that the node on the left will occur in the output before the node on the right (unless it's the same node).
An isolated node (one with no ordering relationship) can be included by having an input line with the same node name on both the left and right hand side.
The output shall contain the name of each unique node once and only once, and those names shall be in an order that satisfies the input partial order requirements.
The output shall match the following: /^([!-~]+\n)+\z/
There may be more than one order of nodes that satisfies the input line requirements. Don't worry about it, find any one.
There may be no possible order of nodes that will satisfy the input line requirements (the nodes contain a cycle). In this case, the program shall exit with a non-zero exit code.
All input files have a total size so that they will fit comfortably in memory and still allow you ample memory to play with. Please note that the input file cannot be empty.
You may assume ASCII as the character set but you may not use Unicode-specific semantics.
The tiebreaker favors 1) white space, and then 2) letters.
All output lines must be properly newline terminated. The output shall match the following: /^([!-~]+\n)+\z/
You must not write to STDERR unless there is a cycle (no possible valid output). Then writing to STDERR is OK, and it does not matter what is written to STDERR.
The program return code does matter. If a valid solution is found and written to STDOUT, the return code shall be zero. If there is no valid solution because the nodes contains a cycle, the return code shall be non-zero.
The average runtime of the program must be finite, very finite. Each test case should complete in less than one minute on my nice and slow 200Mhz machine.
The programs can be written as one or more lines. The score is the total number of characters you need (smaller is better). If your program is more than one line, you must count the newlines in between as one character each. The #! line is not counted. If you use options on the #! line, the options themselves are counted, including the leading space and ``-''.
If two (or more) golfers have the same score for the hole, the golfer with the lowest tie break score wins.
All programs must work on perl 5.6.1.
Assume total memory is < 2**32 bytes. The runtime of your programs should be very finite (see above). If your program takes more than a reasonable time to run, it may be deemed "failed" by the referees.
The programs may only use the perl executable, no other executables on the system are allowed (the program may use itself though). You may use any of the perl 5.6.1 standard core modules (perldoc perlmodlib for a list of those core modules). Your solutions must be portable in the sense that it should work on all versions of 5.6.1 everywhere (however, it's perfectly fine to abuse perl 5.6.1 bugs).
When tested, your script will be named tsort.pl, and you must assume your script to have file permissions of 0444 (that is read-only and non-executable for windows folks).
The program file shall start with #!perl.
The rand() function shall not be used.
The program file will have CR characters removed, and then shall consist of only characters that match [ -~\n\t]
Given the input:
code test design code
You are to output the following:
design code test
Given the input:
code test design write_tests design code write_tests test
You are to output one of the following two possible solutions:
design code write_tests test
or:
design write_tests code test
Given the input:
code test design code test design
You are to exit with a non-zero exit code because this input contains a cycle. (The output does not matter.)
The game starts July 1st (05:00 UTC) and ends July 8th (05:00 UTC).
WARNING: new test program!!
A test program (version 1.9) is provided to help screen entries (for those of you who feel courageous, there's also the Games::Golf version - be warned: it's still an experimental module, use at your own risks).
Any program that passes the test program should be submitted. If you are surprised that your solution passed the test program, please submit it anyway! That will help us identify bugs in the test program.
For the test program to work correctly, you will have to name your script tsort.pl and place it in the same directory as your test program. Run the test program:
$ perl tpr04b.pl
to verify that your entries are valid.
Passing the test program does not assure your solution is valid. The referees have the final say.
You can submit your solutions here (you'll notice it's the same page as the Leaderboard).
Do not publish your solutions anywhere. That will spoil the game, as your solutions are meant to be secret. All solutions will be published at the end of the game.
Prizes (provided by O'Reilly and ActiveState) will be awarded to veteran and beginner winners. A prize may also be awarded to any especially interesting artistic and/or unorthodox solutions.
You can track your ranking through the leaderboard here. Beginners are encouraged to enter and there is a separate leaderboard for them.
There is also a special leaderboard for teams. There will be no prizes awarded to the best team, other than the admiration of your fellow golfers. If you are in a team, you can't also play individually.
We encourage you to send feedback as well as your ideas for future holes and tiebreakers to golf@theperlreview.com.
Rick Klement <rklement@pacbell.net>
Steffen Mueller < mail@steffen-mueller.net>
Ido Trivizki <trivizki@bigfoot.com>
Jerome Quelin <jquelin@wanadoo.fr>
If you want to be a referee next month, drop us a note: golf@theperlreview.com