PA1c is due 1/10 at 11:50pm.
PA1 is due 1/17 at 11:50pm.
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: 1) Cool, and 2) another of your choice among OCaml, Python, JavaScript, Haskell, Ruby, or C. 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 PA6, you will write a compiler for Cool, so it is important that you learn how Cool works now.
To practice or test your skills, you may also submit additional implementations in C, Haskell, JavaScript, Python, or Ruby. These will be tested but are not necessary for your grade.
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 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:
... 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.
You could solve the problem in the Python, Ruby or OCaml first (depending on where you are most comfortable) and then just translate your solution. Translating into Cool, Haskell, JavaScript or C will not be as easy, however.
Use this as an opportunity to see what you like about various languages. What do you think of Python's enforced tabbing? How about ML's abysmal error reporting? Ruby's below-par execution speed? Haskell's IO Monad? JavaScript's more asynchronous I/O model? C's general hideousness?
For bonus brownie points, try to make any OCaml, Haskell, JavaScript, Ruby or Python implementation as functional as possible (e.g., eschew side effects).
NOTE: Some of these video guides are from a previous offering of a similar course at the University of Virginia. The assignment for this semester has changed slightly. While they are still relevant, you are responsible for completing the assignment according to this course's grading rubric.
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.
While you may be comfortable starting with Python, I strongly recommend providing an implementation in OCaml.
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:
Feel free to include additional rosetta.whatever files in your zip file if you are considering PA1 extra credit (see below).
For PA1 you must turn in a zip file containing two source files and two other files. Use the following names:
You are eligible for 1 point of extra credit for additional implementations. Please include all of your rosetta.whatever files in a single zip. You must also submit these two files:
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 a Cool and one other implementation 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):