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. Are all given predecessor tasks known? If not the program dies with C. Is a task a direct predecessor of itself? If this is the case, the program dies with C. Is a task a indirect predecessor of itself? If this is the case, the program dies with C. Are there any unused tasks for the task 'FINAL'? If this is the case, the program gives the warning C. 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.) 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.) 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