OCaml written specification Your program must take as input a list of dependent tasks and either output a valid order in which to perform them or the single word cycle.

Your program will accept a number of lines of textual input (via standard input). There are no command-line argumentsyou must always read from standard input. Do not open a named file. Instead, always read from standard input.

That text input will contain a non-zero but even number of lines. Every two lines represent a pair of tasks. The first line gives the name of a task, the second line gives the name of a task that it depends on. This text input is also called the task list.

The task list will contain only standard ASCII characters (no UTF/8 Unicode or special accents). The goal is to test programming and program language concepts, not your internationalization abilities.

Each task name starts at the beginning of the line and extends all the way up to (but not including) the end of that line. So the newline or carriage return characters or are not part of the task name. Each task name is at most 60 characters long. (This limit is to make any C implementation easier. Other languages, e.g., Python, OCaml, and Cool, support longer strings natively, and can thus ignore this length limit.)

Example task list named example.list:

learn C read the C tutorial do PA1 learn C The interpretation is that in order to learn C one must first read the C tutorial and that in order to do PA1 one must first learn C. Desired output for this example:

read the C tutorial learn C do PA1 If the task list containts a cycle of any size, your program should output exactly and only the word cycle. Example cyclic input:

get a job have experience have experience work on a job work on a job get a job Even if the task list contains a few non-cyclic parts, any single cycle forces you to output only the word cycle.

Always output to standard output only. Do not write anything to stderr.

There is no fixed limit on the number of lines in the task list, although there will always be an even number of lines greater than zero.

Two tasks with the same name are really just the same task. Use standard string equality.

Duplicated pairs of tasks are not allowed. For example:

learn C read the C tutorial do PA1 learn C learn C read the C tutorial that task list is not valid input because the pair learn C/read the C tutorial appears twice. Program behavior if the task list contains a duplicate pair is undefined. You will not be tested on it.

Your program may not cause any other file I/O to be performed, such as creating a temporary file to keep track of some intermediate sorting results or writing to stderr (or even causing the interpreter to write a warning to stderr). You do not need any such temporary files or stderr-printing to solve this problem.

3 Specification Choosing Among Unconstrained Tasks If there are multiple outstanding unconstrained tasks, your program should output them in ascending ASCII alphabetical order. That is, if you ever have two or more tasks, each of which has no remaining dependencies, output the one that comes first ASCII-alphabetically. (This constraint makes your program deterministic; for any given input there is only one correct output.) Example:

learn C understand C pointers learn C read the C tutorial do PA1 learn C Because r comes before u, your output should be:

read the C tutorial understand C pointers learn C do PA1 To put it another way, consider this task list:

B A C D C E Which yields a dependency graph like this:

A D E | \ / B C The proper ordering for this set of tasks is A B D E C. Note that B comes before D and E, even though B depends on A. This is because, once A is finished, B is free to go and it comes first alphabetically. You may want to consider this requirement when you pick your sorting algorithm. Given this requirement the answer A D E B C is incorrect and will receive no credit.

This problem is just topological sort not-so-cleverly disguised. Below is a coded example of a program that does something similar named unsort.ml

(* OCAML: Reverse-sort the lines from standard input *) let lines = ref [] in (* store the lines; a 'ref' is a mutable pointer *) try while true do (* we'll read all the lines until something stops us *) lines := (read_line ()) :: !lines (* read one line, add it to the list *) (* X :: Y makes a new list with X as the head element and Y as the rest *) (* !reference loads the current value of 'reference' *) (* reference := value assigns value into reference *) done (* read_line will raise an exception at the end of the file *) with _ -> begin (* until we reach the end of the file *) let sorted = List.sort (* sort the linst *) (fun line_a line_b -> (* how do we compare two lines? *) compare line_b line_a) (* in reverse order! *) (* (fun (argument) -> body) is an anonymous function *) !lines (* the list we are sorting *) in (* let ... in introduces a new local variable *) List.iter print_endline sorted (* print them to standard output *) (* List.iter applies the function 'print_endline' to every element * in the list 'sorted' *) end