# Determine the critical path

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 a Y/N value, signifying whether this activity belongs to the critical path (i.e. lstart - estart = 0 and lfinish - 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 the lfinish 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 2; 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.

• Personally, this would be more interesting for me as a code-golf challenge. There is an exact spec with zero variability, and I don't see too many different algorithms one could apply, which makes it perfect to optimize for low char count. – Claudiu Mar 12 '14 at 17:16
• @Claudiu I see where you're coming from, but I just got a little bored with seeing the Js, APLs and GolfScripts 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. – Decent Dabbler Mar 12 '14 at 17:58

### GolfScript

A GolfScript solution - just because it can be done.

# Parse input
'['-']'%:I{[.1<\2>';'/(~\{','/{{\1<=}+I?I?}/}%0]}%

# Determine estart iteratively
{:A{[~{A=~@+\;\;}2$%+$-1=]}%.A=!}do

# Invert dependencies
A{~@+\;\;}%$-1=:M; [.,,]zip{[~{\~\2=@?0<{;}*}+[A.,,]zip%\:^~;;@^3=M]}% # Determine lfinish iteratively {:A{[~{A=~\;\;\-\;}3$%+0=]}%.A=!}do # Print results # Formats numbers (right aligned, 7 chars) {" "\+-7>}:F; " name | estart | efinish | lstart | lfinish | critical \n" "------+--------+---------+--------+---------+----------\n" @{" "\(" |"@.2=F" | "@.~;@+\;F" |"@.~\;\;\-F" | "@.3=F" | "@~-\;+!"NY"1/=n}%  Example (online): > [A:15][B:7][C:9;A,B][D:3;B,C][E:5;C][F:11;D][G:4;D,E,F] 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  • This is like that scene in Chasing Amy when the normally laconic Silent Bob launches into an extended monologue. – Jonathan Van Matre Mar 12 '14 at 17:00 • Sure it's epic, but how is it elegant? The only thing that doesn't look like line noise are those two string literals at the end :-) – John Dvorak Mar 20 '14 at 8:23 ## C#, many many characters. using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApplication2 { class Program { static char[] COLON = { ':' }; static char[] SEMI_COLON = { ';' }; static char[] COMMA = { ',' }; static char[] BRACE = { ']' }; static void Main(string[] args) { int step = 0; List<Activity> i = new List<Activity>(); Console.Write("Enter input: "); string s = Console.ReadLine().Replace("[", null); foreach (string x in s.Split(BRACE, StringSplitOptions.RemoveEmptyEntries)) { string[] y = x.Split(SEMI_COLON); Activity n = new Activity(x.Split(COLON)[0], Int32.Parse(y[0].Split(COLON)[1])); n.Name = x.Split(COLON)[0]; n.Dependencies = (y.Length > 1) ? y[1].Split(COMMA).ToList() : new List<string>(); i.Add(n); } do { List<string> d = i.Where(x => x.Done()).Select(y => y.Name).ToList(); foreach (Activity working in i.Where(x => x.Dependencies.Except(d).Count() == 0 && !x.Done())) working.Step(step); step++; } while (i.Count(x => !x.Done()) > 0); foreach (Activity a in i) { Activity next = i.OrderBy(x => x.EFinish).Where(x => x.Dependencies.Contains(a.Name)).FirstOrDefault(); a.LFinish = (next == null) ? a.EFinish : next.EStart; a.LStart = a.LFinish - a.Duration; } Console.WriteLine(" name | estart | efinish | lstart | lfinish | critical"); Console.WriteLine("------+--------+---------+--------+---------+----------"); foreach (Activity a in i) { Console.Write(a.Name.PadLeft(5) + " |"); Console.Write(a.EStart.ToString().PadLeft(7) + " |"); Console.Write(a.EFinish.ToString().PadLeft(8) + " |"); Console.Write(a.LStart.ToString().PadLeft(7) + " |"); Console.Write(a.LFinish.ToString().PadLeft(8) + " |"); string critical = (a.LFinish - a.EFinish == 0 && a.LStart - a.EStart == 0) ? "Y" : "N"; Console.WriteLine(critical.PadLeft(9)); } Console.WriteLine("Hit any key to exit."); Console.ReadKey(); } } class Activity { public string Name {get ; set;} public int Duration {get ; set;} public List<string> Dependencies {get ; set;} public int EStart {get ; set;} public int EFinish {get ; set;} public int LStart { get; set; } public int LFinish { get; set; } private int steps = 0; public Activity(string name, int time) { EStart = -1; EFinish = 0; LStart = 0; LFinish = 0; Name = name; Duration = time; steps = time; } public void Step(int count) { EStart = (EStart == -1) ? count : EStart; if (--steps == 0) EFinish = count + 1; } public bool Done() { return steps == 0; } } }  I would hesitate to call this "the most elegant solution", but it trades the verbosity of C# for ease of parsing input and formatting output (and has Linq). I basically just loops through all of the activities and increments a time counter if all their dependencies have been completed until all of them are done. That gives the earliest starts and earliest finishes. The latest finish for each is simply the earliest start among activities that have it as a dependency, and the latest start is the activity duration minus the latest start. # Haskell, 39 LoC import Control.Exception.Base (assert) import Data.List import Data.Maybe (fromJust) import Text.Printf splitBefore x = groupBy (\_ y -> x /= y) data Activity = Activity {aName :: Char, aLength :: Int, depNames :: [Char]} deriving (Eq, Ord, Show) instance Read Activity where readsPrec _ ('[' : aName : ':' : rest1) = let [(aLength, rest2)] = reads rest1 :: [(Int, String)] (rest3, ']':rest) = span (/= ']') rest2 depNames = map (\[_,x] -> x) splitBefore ',' $rest3 in [(Activity {aName = aName, aLength = aLength, depNames = depNames},rest)] main = getLine >>= putStrLn . \input -> let activities = map read$ splitBefore '[' $input :: [Activity] activityByName a = fromJust . find ((a ==) . aName)$ activities
dependencies = map activityByName . depNames
dependents a = filter ((a elem) . dependencies) $activities estart a = case dependencies a of [] -> 0 ds -> maximum$ map efinish ds
efinish  a = estart a + aLength a
critLength = maximum $map efinish$ activities
lfinish  a = case dependents a of
[] -> critLength
ds -> minimum $map lstart ds lstart a = lfinish a - aLength a critical a = estart a == lstart a format a = printf " %4c | %6d | %7d | %6d | %7d | %8c " (aName a) (estart a) (efinish a) (lstart a) (lfinish a) (if critical a then 'Y' else 'N') in unlines$ " name | estart | efinish | lstart | lfinish | critical "
: "------+--------+---------+--------+---------+----------"
: map format activities