The Rosetta Stone aided linguistic understanding by providing the same text in three different languages. In this project you will implement the same simple program in two separate languages: OCaml and Cool. Both of your implementations will have exactly the same interface, will otherwise adhere to the same specification, and should behave exactly the same way.
In PA2 through PA5 you will write an interpreter for Cool, so it is important that you learn how Cool works now.
For this assignment, you must work alone. Subsequent assignments will allow you to work in pairs.
Your program must take in 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 arguments — you 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 \r or \n 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. Cool and OCaml both support longer strings natively, and can thus ignore this length limit.)
Example task list:
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:
If the task list containts a cycle of any size, your program should output exactly and only the word cycle. Example cyclic input:
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 it is not zero and it is even).
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:
... 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.
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:
Because r comes before u, your output should be:
To put it another way, consider this task list:
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. Feel free to look up how to do toposort on the internet (but remember that you must turn in your own work; you may not copy someone else's code and claim it as your own).
Take a look at the files in pa1-hint.zip. You could do worse than using them as starting points.
If you're having trouble writing anything reasonable in Cool, don't forget to look at the other example Cool programs.
Building and maintaining an explicit graph structure is probably overkill.
A number of Video Guides are provided to help you get started on this assignment on your own. The Video Guides are walkthroughs in which the instructor manually completes and narrates, in real time, a similar assignment. They include coding, testing and debugging elements.
If you are still stuck, you can post on the forum, approach the TAs, or approach the professor. The use of online instructional content outside of class weakly approximates a flipped classroom model. Click on a video guide to begin, at which point you can watch it fullscreen or via Youtube if desired.
Reminder: You can watch YouTube videos at 1.5x speed with full audio.
Because you receive extra credit for a working Python (or Ruby, if you prefer) implementation (see the Grading Rubric below), we recommend that you complete the task in Python first. That way you can be sure that you understand the toposort algorithm in a familiar language before you try it in an unfamiliar one. Once you have it working in Python, you translate that into Cool or OCaml (see the Video Guides for an example of doing the same problem in Python and then OCaml). The automated grading server will grade any Python implementation you submit, giving you useful feedback on algorithmic correctness. This "Python-first" approach ends up being mathematically optimal for most students.
PA1c is a checkpoint to make sure that you do not fall behind on PA1. You have about two weeks to complete all of PA1, but if you try to do it all at the last minute you're probably doomed to failure.
For the one-week PA1c checkpoint, you must have one of the implementations done. This separates the project into two phases: (0) Can I write this program at all? and (1) Can I write this program in multiple languages?
For PA1c you must turn in a zip file containing one source file. Use the following names:
Students considering the optional Legacy Grading Contract should decide before submitt PA1c.
For PA1c you must turn in a zip file containing two source files and two other files. Use the following names:
The testcase.list file should contain a valid novel task list (it may or may not contain a cycle — your choice).
The readme.txt file should be a plain ASCII text file (not a Word file, not an RTF file, not an HTML file) describing your design decisions. Which language did you start with? How did you store the (implicit) graph? Which language was the hardest? One or two English paragraphs should suffice. Spelling, grammar, capitalization and punctuation all count.
The submission grading server will accept and report on any of the following languages, if you happen to submit them:
Note that only the Cool and OCaml implementations are required for your grade. The others cannot hurt you in any way, but can provide extra credit if you complete them perfectly.
PA1 Grading (out of 25 points):