The Rosetta Stone

Due:
11:00 pm, Monday February 8, 2021

Max grace days: 2

Overview

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 a second language of your choice. Both of your implementations will have exactly the same interface, will otherwise adhere to the same specification, and should behave in exactly the same way.

Specification

Your program must take 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.

The 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 the task, the second line gives the name of the 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 rest 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 list name.

Example task list:

learn OCaml
read the OCaml tutorial
do assignment 1
learn OCaml

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

read the OCaml tutorial
learn OCaml
do assignment 1

If the task list contains a cycle of any size, then 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 standard error.

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:

learn OCaml
read the OCaml tutorial
do assignment 1
learn OCaml
learn OCaml
read the OCaml tutorial

is not valid input because the pair learn OCaml/read the OCaml tutorial appears twice. Program behavior if the task contains 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 standard error (or even causing the interpreter to write a warning to standard error). You do not need any such temporary files or standard error printing to solve this problem.

If there are multiple outstanding unconstrained tasks, then 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, then output the one that comes firs ASCII-alphabetically. (This constraint makes your program deterministic; for any given input there is only one correct output.) Example:

learn OCaml
understand higher-order functions
learn OCaml
read the OCaml tutorial
do assignment 1
learn OCaml

Because r comes before u, your output should be:

read the OCaml tutorial
understand higher-order functions
learn OCaml
do assignment 1

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

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 the hint directory that is part of the starter code. You can use those programs as starting points.

Building and maintaining an explicit graph structure is probably overkill.

Building and Testing

The programs can be run with the following commands:

For this programming assignment, the following resources are available in the assignment starter code to aid in implementation and testing:

Turning in the Assignment

For assignment 1 you must turn in a zip file containing two source files and two other files. Use the following names:

  1. rosetta.ml – OCaml implementation
  2. rosetta.x – second Implementation (where x is an appropriate file extension)

You must also submit these two files:

  1. testcase.list - a valid task list that you made up
  2. README – your README file

The README 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.

To submit the assignment, execute the command:

~schwesin/bin/submit-rosetta.bash <zip file name>

on the Linux server where <zip file name> is the name of your zip file.

Grading Criteria

Grading (out of 25 points):