There was some innovative work handed in, but there were, inevitably, several cases where it appears that people had missed several important point. You can find source versions of the programs below in the solution kit PRAC19A.ZIP on the server. They are not as heavily commented as the ones below, where I have tried to draw attention to the various errors and pitfalls that seemed to come up repeatedly.
Some general comments:
(a) You should ALWAYS put your names and a brief description of the program into the source code.
(b) Several submissions had no commentary at all, and this is just unacceptable.
(c) Practical exercises are usually set with very specific objectives in mind. In this case two major objectives were that you should learn a bit about the stdio library (which I hope everyone except two of you did) and also about using the concept and implementation of a "set". A few groups went off and completely "did their own thing", which means that they lost out on what they should have learned, and got into deep water that I had hoped they would avoid. Please don't do this.
Executable sizes: Turbo Pascal: SIEVE.PAS 3504 SIEVE1.PAS 2960 JPI Modula-2 SIEVE.MOD 21282 SIEVE1.MOD 21220
Task 3
Using cin and cout: Borland C: SIEVE.CPP 14932 SIEVE1.CPP 14788 Microsoft C: SIEVE.CPP 40960 SIEVE1.CPP 40960 Using scanf and printf: Borland C: SIEVE.CPP 10352 SIEVE1.CPP 10192 Microsoft C: SIEVE.CPP 32768 SIEVE1.CPP 32768
These differences are predominantly because of the 'layering' that takes place in the I/O libraries, I suspect. I/O in Pascal is fairly limited, so the I/O library can be very tight. In Modula-2 it is considerably more versatile, but this comes at a price. The price gets grotesquely higher as you opt to use OOP paradigms, obviously!
Code for one of the translations is given here. The others can be found in the prac solution kit.
// Sieve of Eratosthenes for finding primes 2 <= n <= 4000
// P.D. Terry, Rhodes University, 1997
#include "misc.h"
const int Max = 4000;
typedef boolean SIEVES[Max - 1];
void main(void)
{ int i, n, k; // counters
long primes = 0;
SIEVES Uncrossed; // the sieve
printf("Supply largest number to be tested "); // -------
scanf("%d", &n); // ------- note the &
if (n > Max) {
printf("n too large, sorry"); // -------
exit(1);
}
printf("Prime numbers between 2 and %d\n", n); // -------
printf("-----------------------------------\n"); // -------
for (i = 2; i <= n; i++)
Uncrossed[i-2] = true; // clear sieve
for (i = 2; i <= n; i++) { // the passes over the sieve
if (Uncrossed[i-2]) {
if (primes % 10 == 0) putchar('\n'); // -------
primes++;
printf("%5d", i); // ------- note the 5
// now cross out multiples of i
k = i;
do {
Uncrossed[k-2] = false;
k += i;
} while (k <= n);
}
}
exit(0);
}
Most people successfully corrected the silly errors in SIEVE.CLN. The corrected source can be found in the prac solution kit.
After translation from Modula-2 by X2C
Borland C: SIEVE.C 30614 SIEVE1.C 30630 Microsoft C: SIEVE.C 45056 SIEVE1.C 45056
Many people comment that the code produced by X2C is "unreadable". it isn't really, once you get over the shock of seeing long variable names. These are constructed like that to make sure that the generated C code does not contain name clashes. In fact, many Modula-2 programmers write programs using the convention Modulename.Identifier name in many places - it makes it that much easier for maintainers of the code to know whence everything comes. If and when you come to deal with really large C or C++ programs with thousands of identifiers you may come to curse the fact that #include loads so many identifiers into your program code without warning!
The Hailstone problem:
(* Give the program a name, and make sure the world knows who wrote it *)
PROGRAM Hailstone;
(* Solve the hailstone series problem - what is the smallest initial
term so that we get a run of more than Limit terms in the hailstone series
P.D. Terry, Rhodes University, 2000 *)
(* Give the functions names, and make sure the readers will know what they do
and what the parameters are to be used for *)
FUNCTION LengthOfSeries (Term);
(* Compute the length of a series with known first Term *)
(* Declare variable locally wherever you can. Remember that a parameter (like
Term) is effectively local too. *)
VAR
N, Next;
BEGIN
(* Functions like this don't do any "reading" - information is transferred by
the parameter mechanism *)
N := 1;
WHILE Term <> 1 DO BEGIN
N := N + 1;
(* We have to do something like the following to get around the lack of the
ELSE clause in Clang. We do not need brackets in the expressions, as the
system is required to evaluate left to right, and division throws away
remainders *)
IF Term / 2 * 2 <> Term THEN Next := 3 * Term + 1;
IF Term / 2 * 2 = Term THEN Next := Term / 2;
Term := Next;
END;
RETURN N
END;
(* Declare the "global" variables close to the block in which they are used *)
VAR
Start, Limit;
BEGIN
Write('What is the length to exceed?'); Read(Limit);
(* The simplest way to do the search is with a very straightforward
WHILE loop *)
Start := 1;
WHILE LengthOfSeries(Start) < Limit DO Start := Start + 1;
Write('Smallest initial number was ', Start, ' leading to more than ', Limit, ' terms')
END.
Choosing the biggest values from a list without sorting it
Many of the solutions submitted to the next problem suffered from (a) not using procedures as you were asked to do (so that you could learn about procedures) and from (b) falling into the easy trap of assuming that all the elements in the array would be positive, and so could be "cancelled" by overwriting them with a zero. Don't fall into these traps - they can become notoriously difficult to debug.
(* Give the program a name, and make sure the world knows who wrote it *)
PROGRAM FindNLargest;
(* Read a list and find the N largest elements in it without sorting
P.D. Terry, Rhodes University, 2000 *)
(* We need a way of determining the smallest value. Even though we only need
to do this once, it is good style to put the code into a function *)
FUNCTION Smallest (List[], N);
(* Find the smallest element among List[0] .. List[N-1] *)
VAR
I, Min;
BEGIN
Min := List[0];
I := 1;
WHILE I < N DO BEGIN
IF List[I] < Min THEN Min := List[I];
I := I + 1
END;
RETURN Min;
END;
(* Declare the Choose procedure to have all the parameters it need, given them
some usefully helpful names, and make sure there is a comment in the
procedure to help a reader of the code know what it is supposed to do *)
PROCEDURE Choose (AtMost, N, Original[], Wanted[]);
(* Choose the AtMost largest elements from Original[0] ... Original[N-1]
and store (return) them in Wanted[0] ... Wanted[AtMost-1] *)
(* +++ This routine destroys Original as a nasty side effect ++++ *)
VAR
I, MaxPos, Chosen, Min, Max;
BEGIN
(* Not many people performed the check to make sure that there would be
sufficient element to choose from *)
IF AtMost > N THEN BEGIN
Write('Invalid parameters - ', AtMost, ' is larger than ', N); RETURN
END;
(* Find the smallest value so that we can use it to delete large values.
Don't assume anything about the smallest or largest values ever - make the
system find them from the data really being processed *)
Min := Smallest(Original, N);
(* Start the loop to select the required elements *)
Chosen := 0;
WHILE Chosen < AtMost DO BEGIN
(* Each pass will require a re-assessment of what the largest remaining
element is, and hence an inner loop is needed. Don't rely on I being zero
- set it to zero at the start of the loop *)
I := 0;
Max := Original[0];
WHILE I < N DO BEGIN
IF Original[I] > Max THEN BEGIN
Max := Original[I]; (* remember what the biggest value is *)
MaxPos := I (* remember where the biggest value was found *)
END;
I := I + 1;
END;
(* Put the largest value into the destination array and delete it from the
source array *)
Wanted[Chosen] := Max; Chosen := Chosen + 1; (* insert *)
Original[MaxPos] := Min; (* delete *)
END
END;
(* Declare global variables just before the block where they are to be used *)
VAR
I, N, AtMost, Number, Original[100], Wanted[100];
BEGIN
Read(Number);
N := 0;
WHILE Number > 0 DO BEGIN
Original[N] := Number; N := N + 1; Read(Number)
END;
Read(AtMost);
(* Communicate with the procedure by passing it all parameters it needs *)
Choose(AtMost, N, Original, Wanted);
(* A simple loop as usual, to provide the output *)
I := 0;
WHILE I < AtMost DO BEGIN
WRITE(Wanted[I]); I := I + 1
END
END.
The N Queens problem
I think everyone managed to work out how to count the solutions! The solution kit contains the Pascal complete source code, which we need not give here. Most people managed to convert it to Clang too - it looks very similar to Pascal of course, the big difference being that one has to arrange the array subscripts for array C to span a non- negative range.
PROGRAM Queens;
(* Find all solutions to the N Queens problem - how do we place N queens on
an N*N chessboard so that none of them is threatened by any other one.
Code closely based on that by Niklaus Wirth in "Algorithms + Data
Structures = Programs" (Prentice-Hall, 1976; page 145), but generalised
to allow N queens, rather than only 8
Modifications by Pat Terry, Rhodes University, 2000 *)
CONST
Max = 24 (* Maximum board size *);
(* Introduce names for things wherever you can *)
FALSE = 0;
TRUE = 1;
(* I have left these rather silly names untouched. Wirth has a habit of
choosing names like most students do - so that nobody has a clue what
they represent and curses the author for evermore! *)
VAR
A[24], B[48], C[48], X[24], I, N;
PROCEDURE DisplaySolution;
(* Display one solution *)
VAR
I;
BEGIN
I := 1;
WHILE I <= N DO BEGIN Write(X[I]); I := I + 1 END;
Write;
END;
PROCEDURE Try (I, N);
(* Place the I-th queen on the board of size N * N *)
VAR
J;
BEGIN
J := 1;
WHILE J <= N DO BEGIN
(* This "sequential conjunction" evaluation is easy and safe enough here *)
IF A[J] * B[I+J] * C[I-J+N] = 1 THEN BEGIN
X[I] := J;
A[J] := FALSE; B[I+J] := FALSE;
(* Note the way in which we index C to make sure the subscripts are
non-negative *)
C[I-J+N] := FALSE;
IF I < N THEN Try(I+1, N);
IF I >= N THEN DisplaySolution;
A[J] := TRUE; B[I+J] := TRUE; C[I-J+N] := TRUE
END;
J := J + 1;
END
END;
BEGIN
Read(N);
(* We can use RETURN in the main program to EXIT if the program detects a
gross error in the data *)
IF N > Max THEN BEGIN Write('N too large'); RETURN END;
I := 1; WHILE I <= N DO BEGIN A[I] := TRUE; I := I + 1 END;
I := 1; WHILE I <= 2*N DO BEGIN B[I] := TRUE; C[I] := TRUE; I := I + 1 END;
Try(1, N);
END.
How many solutions are there to the N Queens problem? Do you see a trend?
2 3 4 5 6 7 8 9 10 11 12 13
.---------------------------------------------------------------------.
| 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14200 | 73712 |
`---------------------------------------------------------------------'
Clearly the number of solutions is starting to rise very rapidly. If you were very keen you might like to try to estimate the "Order" behaviour from these figures (how?).
To measure the differences in speed between the Clang and Pascal versions of the N Queens program one can try timing the execution. On the machines at my disposal, and using a stop watch, I found that for small values of N the programs ran so fast that measuring the time was difficult. But for larger N, I obtained
N = 11 133MHz Pentium Pascal 1.6 seconds Clang 100 seconds Ratio 64:1 N = 12 133MHz Pentium Pascal 7.4 seconds Clang 540 seconds Ratio 72:1 N = 12 266MHz Pentium Pascal 3.7 seconds Clang 279 seconds Ratio 75:1
This sort of behaviour - 10 to 100 times slower - is typical of interpretive systems. I could probably speed up the Clang interpreter considerably, of course.
This was very disappointing, frankly. Only a small number of groups attempted the problem at all, and only two got close to producing a working solution. Most of those who tried did not use sets at all, and there were some wonderfully complicated and bizarre ways of doing simple things!
I had hoped that you would see the resemblance here to the N-Queens problem - a back-tracking solution is needed. In some ways it is simpler than the Queens problem, because "threatening", essentially, happens once a period has been booked. The one complication not present in the Queens analogy is that one has to be able to handle "placing" a subjects that has no fixed times, or no alternatives, or even no times at all (I don't think anybody saw this, not even the ones who got started).
The problem can be done in just over 130 lines of C++ and about the same in Pascal. Here is the C++ solution; the Pascal one can be found in the solution kit.
Note how I use meaningful identifiers. Much of the code submitted is sorely lacking in that respect. Yes, it takes a little longer to type in. But it really is much easier to follow! And note that I have written code that reads that timetable file and the user's request character by character, and not as strings which then have to be unpacked.
// Backtracking program to see whether a student's choice of subjects for a
// day can be handled within the constraints of the published timetable
// P.D. Terry, Rhodes University, 2000
#include "misc.h"
#include "set.h"
typedef char SUBJECTS;
const int LastPeriod = 9;
const SUBJECTS Available= ' ';
struct TIMES {
Set<LastPeriod> fixedTimes;
Set<LastPeriod> alternTimes;
};
TIMES timetable[255];
SUBJECTS SubjectChoice[100], Day[LastPeriod+1];
void readTimetable() {
/* Read the complete timetable. This is free format, looking like
A 1 3 A5 A6 .
B A2 A4 .
C 1 .
.
where the first letter gives the subject name, and single digits represent
fixed periods and pairs like An represent alternatives. Full stops end
each line and a fullstop terminates the file. */
SUBJECTS subject;
char ch;
FILE *infile = fopen("data", "r");
if (infile == NULL) {
printf("Timetable file could not be found"); exit(EXIT_FAILURE);
}
subject = toupper(getc(infile));
while (subject != '.') {
do {
do ch = getc(infile); while (ch <= ' '); // skip spaces
if (ch != '.')
if (ch == 'A') {
ch = getc(infile); timetable[subject].alternTimes.incl(ch - '0');
}
else timetable[subject].fixedTimes.incl(ch - '0');
} while (ch != '.');
while (getc(infile) != '\n'); // skip to end of line
subject = toupper(getc(infile));
}
}
void readSubjectChoice (int &subjectsTaken) {
/* Read the list of Subjectstaken into the SubjectChoice array. The list
is free format, terminated by a full stop. */
SUBJECTS subject;
printf("\nType in your subject choices A..Z followed by a full stop, or . to quit ");
subjectsTaken = 0;
do {
do subject = getchar(); while (subject <= ' '); // skip spaces
if (subject != '.') {
subjectsTaken++; SubjectChoice[subjectsTaken] = toupper(subject);
}
} while (subject != '.');
while (getchar() != '\n'); // skip to end of line
}
void printSolution (void) {
/* Print out a representation of the Day, showing which subjects must be
taken in each period */
for (int i = 1; i <= LastPeriod; i++) printf("%3d %c", i, Day[i]);
printf("\n");
}
void fitAlternative (int i, int subjectsTaken, int &solutions) {
/* Try to fit the I-th subject of all the SubjectsTaken into the Day, and count
the number of Solutions to the exercise */
if (timetable[SubjectChoice[i]].alternTimes.isempty()) {
// some subjects don't have any alternatives, but we must still handle them
if (i == subjectsTaken) { printSolution(); solutions++; }
else fitAlternative(i+1, subjectsTaken, solutions);
}
else // try to find one that fits
for (int period = 1; period <= LastPeriod; period++) { // try them all
if (timetable[SubjectChoice[i]].alternTimes.memb(period)
&& Day[period] == Available) { // still free
Day[period] = SubjectChoice[i]; // book it
if (i == subjectsTaken) { // all subjects fitted
printSolution(); solutions++;
}
else fitAlternative(i+1, subjectsTaken, solutions);
Day[period] = Available; // release it for next solution
}
}
}
void fitFixed (int subjectsTaken, bool &okay) {
/* Try to fit the fixed periods for all the SubjectsTaken into the Day,
and return Okay if this can be done */
okay = true; // optimistic
for (int i = 1; i <= subjectsTaken; i++)
for (int period = 1; period <= LastPeriod; period++)
if (timetable[SubjectChoice[i]].fixedTimes.memb(period))
if (Day[period] == Available)
Day[period] = SubjectChoice[i]; // book it
else { // report clash
okay = false; printf("%c * %c", SubjectChoice[i], Day[period]); }
}
void main (void) {
int subjectsTaken, sols;
bool okay;
readTimetable();
readSubjectChoice(subjectsTaken);
while (subjectsTaken != 0) {
printf("\n");
for (int period = 1; period <= LastPeriod; period++) Day[period] = Available;
sols = 0;
fitFixed(subjectsTaken, okay);
if (okay) {
printf("Fixed lectures as follows:\n");
printSolution();
printf("Complete timetable as follows:\n");
fitAlternative(1, subjectsTaken, sols);
printf("%d possible timetables", sols);
}
else printf(" clashes\n");
readSubjectChoice(subjectsTaken);
}
}
Here is the Pascal version:
PROGRAM Clashes;
(* Backtracking program to see whether a student's choice of subjects for a
day can be handled within the constraints of the published timetable
P.D. Terry, Rhodes University, 2000 *)
CONST
LastPeriod = 9;
Available = ' ';
TYPE (* named for enhanced understanding on the part of the reader *)
PERIODS = 1 .. LastPeriod;
SUBJECTS = CHAR;
TIMES = RECORD
FixedTimes : SET OF PERIODS;
AlternTimes : SET OF PERIODS;
END;
VAR
TimeTable : ARRAY [SUBJECTS] OF TIMES;
SubjectChoice : ARRAY [1 .. 100] OF SUBJECTS;
SubjectsTaken, Solutions : INTEGER;
Day : ARRAY [PERIODS] OF SUBJECTS;
Okay : BOOLEAN;
Period : PERIODS;
PROCEDURE ReadTimeTable;
(* Read the complete timetable. This is free format, looking like
A 1 3 A5 A6 .
B A2 A4 .
C 1 .
.
where the first letter gives the subject name, and single digits represent
fixed periods and pairs like An represent alternatives. Full stops end
each line and a fullstop terminates the file. *)
VAR
Subject : SUBJECTS;
CH : CHAR;
InFile : TEXT;
BEGIN
FOR Subject := CHR(0) TO CHR(255) DO BEGIN
TimeTable[Subject].FixedTimes := [];
TimeTable[Subject].AlternTimes := []
END;
(*$I- *)
Assign(InFile, 'Data'); Reset(InFile);
IF IOResult <> 0 THEN BEGIN WriteLn('Could not open DATA'); HALT END;
(*$I+ *)
Read(InFile, Subject);
WHILE Subject <> '.' DO BEGIN
Subject := UpCase(Subject);
REPEAT
REPEAT Read(InFile, CH) UNTIL CH > ' '; (* skip spaces *)
IF CH <> '.' THEN
IF CH = 'A'
THEN
BEGIN
Read(InFile, CH);
TimeTable[Subject].AlternTimes :=
TimeTable[Subject].AlternTimes + [ORD(CH) - ORD('0')]
END
ELSE
TimeTable[Subject].FixedTimes :=
TimeTable[Subject].FixedTimes + [ORD(CH) - ORD('0')];
UNTIL CH = '.';
ReadLn(InFile); Read(InFile, Subject);
END
END;
PROCEDURE ReadSubjectChoice (VAR SubjectsTaken : INTEGER);
(* Read the list of Subjectstaken into the SubjectChoice array. The list
is free format, terminated by a full stop. *)
VAR
Subject : SUBJECTS;
BEGIN
Write('Type in your subject choices A..Z followed by a full stop, or . to quit ');
SubjectsTaken := 0;
REPEAT
REPEAT Read(Subject) UNTIL Subject > ' '; (* skip spaces *)
IF Subject <> '.' THEN BEGIN
SubjectsTaken := SubjectsTaken + 1;
SubjectChoice[SubjectsTaken] := UpCase(Subject)
END;
UNTIL Subject = '.';
ReadLn;
END;
PROCEDURE PrintSolution;
(* Print out a representation of the Day, showing which subjects must be
taken in each period *)
VAR
Period : PERIODS;
BEGIN
FOR Period := 1 TO LastPeriod DO Write(Period:3, ' ', Day[Period]);
WriteLn
END;
PROCEDURE FitAlternative (I, SubjectsTaken : INTEGER; VAR Solutions : INTEGER);
(* Try to fit the I-th subject of all the SubjectsTaken into the Day, and count
the number of Solutions to the exercise *)
VAR
Period : PERIODS;
BEGIN
IF TimeTable[SubjectChoice[I]].AlternTimes = []
THEN (* don't forget this - some subjects don't have alternatives *)
IF I = SubjectsTaken
THEN BEGIN PrintSolution; INC(Solutions) END
ELSE FitAlternative(I+1, SubjectsTaken, Solutions)
ELSE (* try to find an alternative that fits *)
FOR Period := 1 TO LastPeriod DO (* try them all *)
IF (Period IN Timetable[SubjectChoice[I]].AlternTimes)
AND (Day[Period] = Available) (* still free *)
THEN BEGIN
Day[Period] := SubjectChoice[I]; (* book it *)
IF I = SubjectsTaken (* all subjects fitted *)
THEN BEGIN PrintSolution; INC(Solutions) END
ELSE FitAlternative(I+1, SubjectsTaken, Solutions);
Day[Period] := Available (* release it for next solution *)
END
END;
PROCEDURE FitFixed (SubjectsTaken : INTEGER; VAR Okay : BOOLEAN);
(* Try to fit the fixed periods for all the SubjectsTaken into the Day,
and return Okay if this can be done *)
VAR
I : INTEGER;
Period : PERIODS;
BEGIN
Okay := TRUE; (* optimistic *)
FOR I := 1 TO SubjectsTaken DO
FOR Period := 1 TO LastPeriod DO
IF (Period IN TimeTable[SubjectChoice[I]].FixedTimes) THEN
IF Day[Period] = Available
THEN Day[Period] := SubjectChoice[I] (* book it *)
ELSE BEGIN (* report the clash *)
Okay := FALSE;
WriteLn(SubjectChoice[I], '*', Day[Period])
END
END;
BEGIN
ReadTimeTable;
ReadSubjectChoice(SubjectsTaken);
WHILE SubjectsTaken <> 0 DO BEGIN
WriteLn;
FOR Period := 1 TO LastPeriod DO Day[Period] := Available;
Solutions := 0;
FitFixed(SubjectsTaken, Okay);
IF Okay
THEN
BEGIN
WriteLn('Fixed lectures as follows:'); PrintSolution;
WriteLn('Complete timetable as follows:');
FitAlternative(1, SubjectsTaken, Solutions);
WriteLn(Solutions, ' possible timetables');
END
ELSE WriteLn(' clashes');
ReadSubjectChoice(SubjectsTaken);
END
END.