I’ve completed my OCaml implementation of problem 2a in the BCS programming contest.

The problem:

2A Software Dependencies

Writers of software installer packages have to cope with inter-dependencies between packages - instances where package A can only work if package B is already installed. Your task is to write a dependency validator, which takes a list of packages already installed and a list of packages the user wishes to install, and reports back (a) whether or not the installation is possible; and (b) in what order packages will be installed.

For example, assume we have a computer that already has packages A and B installed. We wish to install packages C and D. Package C depends on packages A and D, and package D depends on package B. The installation can go ahead, but the new packages must be installed in the order (D, C) because of C’s dependency on D.

The input to your program will be a set of lines. Each line has a pair of strings, each enclosed in parentheses (). The first string in each pair states the list of packages already installed on the target computer (which could be empty), separated by commas:

(A,B)

The second string lists the packages (at least one) and their dependencies; each package name is followed by a colon and then one or more package names, representing the packages upon which that element depends. The latter list’s elements are separated by semi-colons:

(C:A;D,D:B)

Note that is possible for a package to have no dependencies, in which case just the package identifier will be listed. You may assume that there will be no cyclic dependencies (e.g. A depends on B and B depends on A).

Each package name comprises one or more letters. Your program should disregard whitespace, which may be included in the strings except within a package name.

If all dependencies are satisfied, your program should output the order in which the packages should be installed, in the form exemplified in the sample output, below; where items are not constrained by dependencies, the names should be listed in alphabetical order. Case should be ignored in all instances (i.e. “Pkg” is the same as “PKG”).

If there is a problem with the dependency check, you should report “Dependency check failed:” and then list the failed dependencies as shown in the sample output, in alphabetical order of the package name before the colon.

You may assume a maximum of 10 distinct package names.

Sample input

() (B,A)
(A,B) (C:A;D,D:B)
(A,B) (C:E)
(A,B) (C:A;B;E,D:F)
(A,B) (C:A;B;D;E;F,E:A,D:F)

Sample output

Install order: A,B
Install order: D,C
Dependency check failed: C:E
Dependency check failed: C:E, D:F
Dependency check failed: C:D;F, D:F

You can download my example data file, which has the sample input and some more stuff. Running the program will yield a Prog2a.out file containing the result.