You will write a program to perform scheduling.  As we all
know, tasks sometimes take longer than expected.  Sometimes
when this happens, the final deadline of the project is
affected; sometimes it isn't.  For example, consider the four
tasks A, B, C, and D.  B and C depend on A, which means that
they cannot be started until A is finished. D depends on B and
C, and cannot be started until both B and C are finished:

      .-> B .
    A        :-> D
      `-> C '

Suppose we expect the four tasks to take the following times:

        A: 1 day
        B: 2 days
        C: 3 days
        D: 1 day

Then we don't expect the project to be finished for at least 5
days: one day to complete A and start C; 3 days to complete C
and start D, and another day to finish D.  Any delay in any of
the three tasks A, C, or D will cause the completion date to
slip.  We say that A, C, and D are on the "critical path".
But B is not on the critical path, because B can go on while C
is going on, and can take up to one day longer than expected
without delaying the start of D.

You will write a program which will calculate critical paths.  The
input to the program will be a file in the following format:

        A 1
        B 2 A
        C 3 A
        D 1 B C
        FINAL 0 D

Each line represents one task.  The first field in each line
is the name of the task.  The second field is the expected
duration.  If there are any other fields, they are the names
of other tasks which must be finished before this task can
start.

The program will find all the tasks on the critical path to
the task named FINAL and will print them out, one per line.

It may happen that the input specifies tasks that cannot possibly be
completed.  For example:

        A 1 B
        B 1 A
        FINAL 0 A B

Here A can't start until B is finished, but B can't start until A is
finished.  In such cases, the program should diagnose an error.

NAME
           qotw21.pl

SYNTAX
           qotw21.pl task-file
           cat task-file | qotw21.pl

TASK
           You will write a program to perform scheduling.  As we all
           know, tasks sometimes take longer than expected.  Sometimes
           when this happens, the final deadline of the project is
           affected; sometimes it isn't.  For example, consider the four
           tasks A, B, C, and D.  B and C depend on A, which means that
           they cannot be started until A is finished. D depends on B and
           C, and cannot be started until both B and C are finished:

                .-> B .
              A        :-> D
                `-> C '

           Suppose we expect the four tasks to take the following times:

                  A: 1 day
                  B: 2 days
                  C: 3 days
                  D: 1 day

           Then we don't expect the project to be finished for at least 5
           days: one day to complete A and start C; 3 days to complete C
           and start D, and another day to finish D.  Any delay in any of
           the three tasks A, C, or D will cause the completion date to
           slip.  We say that A, C, and D are on the "critical path".
           But B is not on the critical path, because B can go on while C
           is going on, and can take up to one day longer than expected
           without delaying the start of D.

           You will write a program which will calculate critical paths.  The
           input to the program will be a file in the following format:

                  A 1
                  B 2 A
                  C 3 A
                  D 1 B C
                  FINAL 0 D

           Each line represents one task.  The first field in each line
           is the name of the task.  The second field is the expected
           duration.  If there are any other fields, they are the names
           of other tasks which must be finished before this task can
           start.

           The program will find all the tasks on the critical path to
           the task named FINAL and will print them out, one per line.

           It may happen that the input specifies tasks that cannot possibly be
           completed.  For example:

                  A 1 B
                  B 1 A
                  FINAL 0 A B


           Here A can't start until B is finished, but B can't start until A is
           finished.  In such cases, the program should diagnose an error.

TESTS
           The following problems are tested by the program:

       Is there a task called 'FINAL'?
               If not, the program dies with the message
               C<No task 'FINAL' exists>.

       Are all given predecessor tasks known?
               If not the program dies with
               C<Task 'X' is not defined, but it is a
               preliminary task of task 'Y'>.

       Is a task a direct predecessor of itself?
               If this is the case, the program dies with
               C<Task 'X' is a preliminary task of itself>.

       Is a task a indirect predecessor of itself?
               If this is the case, the program dies with
               C<preliminary circle with task 'X'>.

       Are there any unused tasks for the task 'FINAL'?
               If this is the case, the program gives the warning
               C<unused tasks for 'FINAL' : 'X', 'Y', 'Z'>.

CALCULATIONS
           The following things are calculated by the program:

       The direct predecessors of all tasks.
               (These are given in the input directly.)

       All predecessors of all tasks.
               Therefore we have to cycle through all the predecessors and
               collect them by doing so. (This is done in the function
               C<allpre>.)

       The level (or column) of each task.
               This means in which column the task can be printed. This is
               the first step for plotting the tasks. Tasks with no
               predecessors can be printed in column 0 (the left most column),
               all other tasks can be printed one column after the highest
               column of all its predecessors.

       The direct successors of all tasks.
               Therefore we have to look at all tasks, if the given task
               'X' is a predeccessor of task 'Y', then 'Y' is a successor
               of task 'X'.

       All successors of all tasks.
               Therefore we have to cycle through all the successors and
               collect them by doing so. (This is done in the function
               C<allsuc>.)

       The pathes to the task 'FINAL'.
               Therefore we have to cycle backwards through all the
               predecessors and split the possible pathes for each
               direct predeccessor we find.

DATA STRUCTURES
           The program creates a HoH (hash of hashes), where the name
           of the tasks are the keys and the values are a hash with
           informations about this task. Here is an example for one
           entry of this HoH:

               'FINAL' => {
                            'duration'       => '0',
                            'level'          => 3,
                            'predecessor'    => [
                                                  'D'
                                                ],
                            'predecessorall' => [
                                                  'A',
                                                  'B',
                                                  'C',
                                                  'D'
                                                ],
                            'successor'      => [],
                            'successorall'   => []
                          }

           The name of this HoH is C<%task>.

           The calculated pathes to the task 'FINAL' are stored in an
           AoA (array of arrays) called C<@pathes>. This is the structur
           of the AoA:

               (
                 [
                   'A',
                   'B',
                   'D'
                 ],
                 [
                   'A',
                   'C',
                   'D'
                 ]
               )

           The critical tasks are stored in a simple array called
           C<@maxtasks> and they are printed out one task by line.

EXAMPLES
       The example given in the task description
               crian@blitz:~/perl/qotw> cat qotw21_input1.txt
               A 1
               B 2 A
               C 3 A
               D 1 B C
               FINAL 0 D
               crian@blitz:~/perl/qotw> qotw21.pl qotw21_input1.txt
               A
               C
               D

       Circle predecessors / successors ('A'-'B'-'A')
               crian@blitz:~/perl/qotw> cat qotw21_input2.txt
               A 1 B
               B 1 A
               FINAL 0 A B
               crian@blitz:~/perl/qotw> qotw21.pl qotw21_input2.txt
               preliminary circle with task 'B' at
               ./qotw21.pl line 432, <> line 3.

       Multiple definition of one task ('A')

               crian@blitz:~/perl/qotw> cat qotw21_input3.txt
               A 1 B
               A 1 C
               B 1 C
               FINAL 0 C
               crian@blitz:~/perl/qotw> qotw21.pl qotw21_input3.txt
               Ambigous task definition 'A 1 C' in line 2: task 'A'
               already defined! at ./qotw21.pl line 102, <> line 2.

       Undefined tasks ('C')
               crian@blitz:~/perl/qotw> cat qotw21_input4.txt
               A 1 B
               B 1 C
               FINAL 0 A B
               crian@blitz:~/perl/qotw> qotw21.pl qotw21_input4.txt
               Task 'C' is not defined, but it is a preliminary task
               of task 'B' at ./qotw21.pl line 145, <> line 3.

       Longer circle predecessors / successors ('E'-'F'-'G'-'E')
               crian@blitz:~/perl/qotw> cat qotw21_input5.txt
               A 1
               B 2 A
               C 3 A
               D 1 B C
               E 1 G
               F 1 E
               G 1 F
               FINAL 0 D G
               crian@blitz:~/perl/qotw> qotw21.pl qotw21_input5.txt
               preliminary circle with task 'E' at
               ./qotw21.pl line 432, <> line 8.

       Unused tasks ('E')
               crian@blitz:~/perl/qotw> cat qotw21_input6.txt
               A 1
               B 2 A
               C 3 A
               D 1 B C
               E 12 C
               FINAL 0 D
               crian@blitz:~/perl/qotw> qotw21.pl qotw21_input6.txt
               unused tasks for 'FINAL' : 'E' at
               ./qotw21.pl line 220, <> line 6.
               A
               C
               D