This assignment is due by 2:00 p.m. on Thursday, 25 September.
See the assignment turn-in page (last modified on 3 November 2003) for instructions on
turning in your assignment.
Shredding a document involves taking a rectangular piece of paper and
turning it into strips, called shreds, by repeatedly making cuts parallel
to one of the document's edges; all cuts are made parallel to the same edge.
Unshredding a document involves taking a set of shreds and re-arranging
them to form the original document.
Write a program that unshreds a shredded document; the document consists of a
single sheet of paper. Your program should read a set of shreds from std-in
and write the same shreds to std-out ordered so that two adjacent shreds in
output were adjacent in the original document.
Input to your program consists of a sequence of zero or more edges. Each
edge is separated from the next by a sequence of zero or or more blank lines. A
blank line is sequence of zero or more space characters terminated by a
newline; a
space character is any non-newline character for which
isspace() return true. The first edge may be proceeded, and the last edge
may be followed, by zero or more blank lines.
Each edge contains zero or more intervals describing the ink that appears on
the edge; each edge ends in a newline. Each interval contains two integer
coordinates delimiting an ink patch; all intervals on an edge are disjoint. If
an edge contains no ink, it consists of the single digit 0. Adjacent
coordinates are separated by at least one space character.
Starting with the first edge read, consecutive pairs of edges define a shred.
It is an error if input contains an odd number of edges. Each shred input is
in one of four orientations: normal, rotated, reversed, and reversed rotated;
different input shreds may be in different orientations.
For example, the shred
would be represented by the input
20 10
15 15
The input
0
0
represents a blank shred; a shred with no ink along either edge.
All shreds read from std-in belong to the same document, and std-in contains
all the shreds needed to reconstruct the document.
Output gets written to std-out and has the same format as input: a sequence of
zero or more shreds separated by blank lines. Output should contain the same
shreds as input, although the output shreds may be re-ordered and re-oriented
from what they were when input.
The final orientation of shreds does not matter, as long as all shreds have the
same orientation.
Because the input shreds don't contain all the information they could, it is
possible that there are several different documents that could have produced
the same set of input shreds. Your program may reconstruct any one of these
documents.
If your program detects an error condition, it should print an informative
error message to std-err and exit with no further processing.
The program make-shreds writes a set of shreds to
std-out. Because make-shreds generates a new set of shreds each time it's
run, you may find it more convenient to send the output of make-shreds to a
file and then take input from the file:
$ ./make-shreds > shreds
$ ./your-program < shreds
The program show-shreds reads a set of shreds from
std-in and displays them. show-shreds takes an optional command-line
argument which is interpreted as the name of a file containing a set of
unordered shreds. If you give a command-line argument, show-shreds will
compare the input shreds to the shreds it read from std-in and make sure
they're the same. Probably the easiest way to use show-threds in this way
is
./make-shreds | tee input | ./unshred | ./show-shreds input
tee is a program that reads data from std-in and writes the data to
std-out, but also writes the data to the file who's name is given on the
command line. In the example above, tee creates a copy of the input
shreds in the file named input.
show-shreds uses the X Window System. You must be sitting in front of a
system that's running the X window system to to use show-shreds; if you
are sitting in front of a system that's not running the X window system, you
can't use show-shreds.
The programs make-shreds and show-shreds can be found in the
assignment directory
/export/home/class/cs-509/pa1
You can find my answer to the assignment in the same directory. Remember, the
objective of this assignment is to unshred documents; the objective is not to
faithfully reproduce the behavior of my solution. If my solution's wrong and
you copy the error, you're going to lose points.
This page last modified on 21 November 2003.