In this programming project, you will gain faimiliarity with snail, the programming language we will be implementing this semester. You will implement a nontrivial algorithm in the language.
Project 2 allows you to familiarize yourself with the snail programming language and practice implementing foundational algorithms. Having a non-trivial understanding of the langauge will help you to properly implement its semantics in future projects.
You may work in teams of two for this project.
Working in teams of two (or individually), create and submit the following five (5) artifacts:
p2.sl, that contains your implementation of the program specified below.
test-1.txt.
readme.txt that
describes your implementation and design decisions.
references.txt
providing a citation for each resource you used (excluding class
notes, and assigned readings) to complete the assignment. For
example, if you found a Stack Overflow answer helpful, provide a
link to it. Additionally, provide a brief description of how the
resource helped you.
team.txt containing
the SLU email IDs of the students who worked on the artifacts.
Create a snail program, p2.sl. 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. This
problem is just
topological sort not-so-cleverly disguised.
Feel free to look up how to do toposort on the internet and cite
your references (but remember that you must turn in your own work;
you may not copy someone else's code and claim it as your own).
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.
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.
The interpretation is that in order to learn C one must first read the C tutorial and that in order to do P1 one must first learn C.
If the task list contains a cycle of any size, your program should output exactly and only the word cycle.
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. In snail, this is the only form of output supported.
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 and will not be tested.
The above 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.
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.)
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.
For this programming assignment, three coding resources are provided to you:
Documentation is your friend! here are some external resources you might find helpful:
Take a look at both revsort.sl and
revsort-list.sl. You could do worse than using one
or both of these as a starting point. It might also be helpful to
review the repositiory of example snail programs.
There are different kinds of graph structures you could use to represent the tasks read in from standard input. An adjacency list (a list of lists) is likely sufficient here.
Because you receive extra credit for a working Python or Reason implementation (see the Grading Rubric below), I recommend that you attempt the task in one of these languages 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, you can translate that into snail.
It is possible to use a text file as input to snail. This is known as input redirection. You can also redirect output to a file. The syntax for this is shown below.
# redirect input for program
snail p2.sl < /path/to/input/file
# redirect output for program
snail p2.sl > /path/to/output/file
# these can be combined
snail p2.sl < input > output
If you are still stuck, you can post on Piazza or approch the professor.
Video guides are provided to help you get started with various aspects of this project. Note that there may be errors and mistakes in these videos. You should not blindly follow the steps taken in these videos!
You must turn in a tar.gz file containing these files:
readme.txt: your README file references.txt: your file of citationstest-1.txt: a valid novel task list (it may or may not contain a cycle — your choice) p2.sl (contains your program for P2) p2.py or p2.re
for extra credit.
team.txt: a file listing only the SLU
email IDs of both team members (see below). If you are working
alone, you should turn in a file with just your email ID.
The readme.txt file should be a plain UTF-8 text
file (not a Word file, not an RTF file, not an HTML file)
describing your design decisions. What library functions did you use?
How did you store the (implicit) graph in P2? What was the biggest
challenge of using snail? One or two English paragraphs should
suffice. Spelling, grammar, capitalization and punctuation all count.
Note, you can use the CS-364 Makefile to generate a
submission archive:
make fullsubmit
The Makefile is available here.
Be sure to update the IDENTIFIER and EXECUTABLE
variables appropriately.
You may complete this assignment in a team of two. Teamwork imposes burdens of communication and coordination, but has the benefits of more thoughtful designs and cleaner programs. Team programming is also the norm in the professional world.
Students on a team are expected to participate equally in the effort and to be thoroughly familiar with all aspects of the joint work. Both members bear full responsibility for the completion of assignments. Partners turn in one solution for each programming assignment; each member receives the same grade for the assignment. If a partnership is not going well, the instructor will help to negotiate new partnerships. Teams may not be dissolved in the middle of an assignment.
If you are working in a team, both team members should
submit to SLUGS. All submissions should include the file
team.txt, a two-line, two-word flat UTF-8 text file
that contains the email ID of both teammates. Don't include the
@stlawu.edu bit. Example: If
sjtime10 and
kaangs10 are working together, both
kaangs10 and sjtime10 should submit
fullsubmit.tar.gz with a team.txt file
that contains:
kaangs10
sjtime10
Then, sjtime10 and kaangs10 will both
receive the same grade for that submission.
P2 Grading (out of 50 points):
test-1.txt file