In project management there's a method, called the critical path method, that is used for scheduling activities and for determining which activities' timings are crucial (i.e. critical) and for which activities the schedule offers a timing tolerance.
Your program's task is to order a set of activities chronologically and for each of those activities determine their:
- earliest possible start;
- earliest possible finish;
- latest possible start;
- latest possible finish.
Lastly, your program should mark which subsequent activities make up the longest, uninterrupted path; i.e. the critical path.
The input will be the activities by their name, with their duration (in an unspecified time unit) and with the names of the activities they depend on. For this challenge only so-called finish to start dependencies will be presented as input. In other words: any possibly provided dependencies for a given activity signify that said activity can only start when all the activities, that this activity depends on, have finished. No other forms of dependencies will be presented.
The expected input is in the form of (possibly multiples of):
[F:12;C,B]
Where:
F
signifies the activity's name; an uppercase alphabetic character;12
signifies the duration as a positive integer;C,B
signifies the optional dependencies, as a comma-separated list of activity names.
Here's an example input:
[A:15][B:7][C:9;A,B][D:3;B,C][E:5;C][F:11;D][G:4;D,E,F]
Meaning:
name | duration | dependencies
------+----------+--------------
A | 15 |
B | 7 |
C | 9 | A,B
D | 3 | B,C
E | 5 | C
F | 11 | D
G | 4 | D,E,F
Your program's output will be an ASCII table, in the exact following form, but filled with different data, depending on the input of course (here I'm using the example input, from above, as input):
name | estart | efinish | lstart | lfinish | critical
------+--------+---------+--------+---------+----------
A | 0 | 15 | 0 | 15 | Y
B | 0 | 7 | 8 | 15 | N
C | 15 | 24 | 15 | 24 | Y
D | 24 | 27 | 24 | 27 | Y
E | 24 | 29 | 33 | 38 | N
F | 27 | 38 | 27 | 38 | Y
G | 38 | 42 | 38 | 42 | Y
Where:
- the activities are ordered chronologically ascending by
estart
(and then arbitrarily); estart
is earliest start;efinish
is earliest finish;lstart
is latest start;lfinish
is latest finish;critical
is aY/N
value, signifying whether this activity belongs to the critical path (i.e.lstart - estart = 0
andlfinish - efinish = 0
).
The expected constraints for the input will be:
- The activity names will never exceed
Z
; i.e. the total amount of activities will never exceed 26; - The total duration (i.e. the latest finish of the last activity) will never exceed
9999999
(the width of thelfinish
column, with padding); - The number of dependencies, for any given activity, will never exceed 6;
- The input will never be inconsistent (e.g. no non-existent dependencies, etc.).
The constraints for your program are:
- No use of existing PM/CPM APIs1; you must create the algorithm from scratch.
This is a popularity-contest2; the most elegant solution (or at least, I hope that's what voters will vote for), by popular vote, wins. The winner will be determined 4 days after the submission time of this challenge.
1. If any such API even exists.
2. I want to give the more verbose languages a fair shot at this as well.
J
s,APL
s andGolfScript
s coming up on top in every code-golf challenge. I wanted to see the more verbose languages have a decent shot at this as well, and not be discouraged beforehand already. I agree with you though, that there are probably not that many approaches to be taken in this challenge. \$\endgroup\$