PA1: Rosetta Stone
Goal
The Rosetta Stone aided linguistic understanding by providing the same text in three different languages. In this programming assignment you will implement the same program in two separate languages: Ocaml and another of your choice (those that can be compiled/run on the dept's Linux machine, e.g., Python, C). You can also implement the program in Cool for extra credit.
All of your implementations will have exactly the same interface, will otherwise adhere to the same specification, and should behave exactly the same way.
For this assignment, you must work alone. Subsequent assignments will allow you to work in pairs.
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 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. Other languages, e.g., Python, OCaml, and Cool,
support longer strings natively, and can thus ignore this length limit.)
Example task list
learn C
read the C tutorial
do PA1
learn C
read the C tutorial
learn C
do PA1
The means 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.
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.
Example duplicate
learn C
read the C tutorial
do PA1
learn C
learn C
read the C tutorial
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.
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
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.
Commentary
Hint
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).
Tests
For this programming assignment, two coding resources are available:
- pa1-hint.zip --- provides concrete implementations of "task list reversal" (a similar, but simpler, problem) in several languages.
- pa1-testcases.zip --- includes a number of test inputs and expected outputs so that you can test your programs before submitting
Take a look at the files in pa1-hint.zip. You could do worse than
using them as starting points.
Building and maintaining an explicit graph structure is probably overkill.
You should first solve the problem in your favorite language, e.g., Python, and then just translate your solution to Ocaml and/or Cool.
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?
Video Guides
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.
Note
These video guides are from a previous offering of a similar course at the University of Virginia by Wes Weimer. 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.
These videos are considered an outside resource for completing this
assignment. Be sure to note these videos in your readme.txt if you use
them.
Turn-In and Grading
What to Turn In for PA1
PA1c
PA1c is a checkpoint to make sure that you do not fall behind on PA1. For PA1c checkpoint, you must have one of the implementations done. This separates the PA into two phases: (1) Can I write this program at all? and (2) Can I write this program in multiple languages?
For PA1c you must turn in a zip file containing one source file
in any language. Use rosetta.{ml,py,cl} for OCaml/Python/Cool implementation.
If your code does not build or run, you will simply get a 0 for the assignment.
PA1
For PA1 you must turn in a zip file containing two source files (Ocaml and another one of your choice) and Cool file if you go for the extra credit. Use the following names:
rosetta.{ml,py,cl}--- OCaml/Python/Cool implementationreadme.txt- a README file
The readme.txt file should be a plain ASCII text file (not a Word
file, not an RTF file, not an HTML file) describing how to run your
program and 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.
See an example of a readme.txt file
Note: if you did the extra credit, explicitly state that here and describe how you did it.
Grading Rubric
PA1 Grading (out of 25 points)
- 20 points : autograding
- 10 points : autograder tests for PA1c
- 10 points : autograder tests for PA1
- Each failed test removes one point, to a minimum of 0/10, even if there are more tests than total points.
- 5 points : for a clear description in your README
- 5 : thorough discussion of design decisions (including language comparisons) and choice of test cases; a few paragraphs of coherent English sentences should be fine
- 2 : vague or hard to understand; omits important details
- 0 : little to no effort, or submitted an RTF/DOC/PDF file instead of plain TXT
- 10 points: EXTRA CREDIT, implementation in Cool (will be tested similarly as autograding and requires descriptions in README)