The submissions received were very varied, but on the whole of rather reasonable quality. There was some innovative work handed in, but there was evidence that people had missed several important points. You can find complete source versions of the program solutions in the solution kit PRAC19A.ZIP on the server. This file also contains C# versions of the solutions for people who might be interested.
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 almost no commentary at all, and this is just unacceptable. In particular, supply commentary at the start of each method as to what it sets out to do, and on the significance of the parameters/arguments.
(c) The pracs in this course are deliberately set to extend you, in the hope that you will learn a lot from each one. Their completion requires that you apply yourself steadily throughout the week, and not just on Thursday afternoon and the following Thursday morning!
(d) A large number of submissions were received that had not made proper use of the IO, InFile and OutFile classes as you had been told to do. These library classes are designed to make text based I/O as simple as possible without having to deal with buffered readers, exceptions, string tokenizers and all that stuff that you were probably subjected to in CSC 102, but without realising that the best thing to do with bizarre code is to hide its details in a well-designed library. Have a look at the solutions below, where hopefully you will see that the I/O aspects have been made very simple indeed.
The first tasks were fairly straightforward, though several groups obviously had not bothered to see whether the extended sieve programs would execute properly. The Pascal compiler only uses 16-bit INTEGER arithmetic (-32768 .. 32767) but it appears to allow large sieve sizes, as arrays can also be indexed by so-called long variables. Since it regards an integer as a signed 16-bit number, an extra limitation is imposed - an array indexed by an integer cannot have an upper subscript greater than 32767. But it's even worse than that! Consider the code:
K := I (* now cross out multiples of I *);
REPEAT
Uncrossed[K] := FALSE; K := K + I
UNTIL (K > N);
When I becomes large enough, K+I really should become larger than 32767, but the overflow means that it appears to go negative (think back to your CSC 201 course). This happens for the first time after detecting the prime number 16411, so that the maximum effective sieve with the code above is really only 16410.
We can extend the range of the algorithm by a trick which I did not expect you to discover, but which may be worth pointing out. Replace the above code by
K := I (* now cross out multiples of I *);
REPEAT
Uncrossed[K] := FALSE; K := K + I
UNTIL (K > N) OR (K < I)
which looks ridiculous, but when K gets too large and then overflows, since it appears to become negative it will then also appear to be less than I.
Much the same sort of behaviour happens in the 16-bit Modula-2 compiler. (Incidentally, the JPI Modula-2 compiler is much older (1989) than the Free Pascal one (2005).) The type CARDINAL used in the Modula-2 code is implemented as an unsigned 16-bit number, so it might at first appear that we can use a sieve of about 65000 elements. However, when we reach the prime number 32771 the value of K + I overflows. This time we can still use a coding trick like that above, but we have to run the compiler in "optimized" mode to suppress the overflow detection that it normally provides. All rather subtle - up till now you probably have not really written or run code that falls foul of overflow or rounding errors, but they can be very awkward in serious applications.
The 32-bit compilers don't seem to have this problem (or at least, it would be much harder to reproduce it), but, of course, the amount of real memory available to them is limited)
There were several specious reasons thought up to explain why the executables were of such differing sizes. It is not true that this is a function of the sieve size to any marked degree, as the code and data areas are handled separately. The real reasons are that the efficiency of code generation differs markedly from one compiler to another, and that some implementations build in a great deal more extraneous code than others - you could see this in the smaller executable when some compilers were run in "optimizing" mode. The C and C++ executables differ enormously in size - no doubt due to the vast amounts of code needed to support the iostream library.
The Borland 5.5 and WatCom C/C++ compilers are 32-bit ones, rather than 16-bit ones. But even allowing for this, they suffer from bizarre code bloat for small applications. There may be command line parameters and options that one can set to try to produce tighter code, but I have not bothered to experiment further. Some (most) of the overheads may relate to the fact that they have to produces "Windows" compatible programs. Compilers like this are clearly designed with an "everyone has 1GB of memory and 200GB of disk space, and if they don't they should go and buy more" philosophy.
The "executable" produced from the C# compiler are not true executables in the same sense as those produced by the C++ and Pascal compilers, as the code in them still has to be "Jitted" into its final form.
The limitation imposed by the Parva system on the sieve size is entirely due to the fact that the interpreter system only allows for about 50000 words of memory - which has to hold the pseudo-code and all variables. The limit on the sieve size was about 49000. This could have been extended simply by modifying the interpreter, and then recompiling it, but you were not in a position to do that.
Interestingly, it does not seem to make a difference if the Free Pascal compiler you were using is used in optimizing mode or not. An earlier release used in previous years was quite different - for example the Sieve program compiled to 15872 bytes in ordinary mode and to 14848 bytes in optimized mode.
.---------------------------------------------------------------------------. | | Sieve | Queens | Empty | | | | Code Size | Code Size | Code Size | | | | | | | | | Free Pascal | 31 744 | 32 256 | 28 672 | Sieve limit 16410 | |-----------------+-----------+-----------+-----------+---------------------| | Optimized | | | | | | Free Pascal | 31 744 | 32 256 | 28 672 | Sieve limit 16410 | |-----------------+-----------+-----------+-----------+---------------------| | Modula-2 | 18 609 | 18 874 | 11 946 | Sieve limit 32770 | |-----------------+-----------+-----------+-----------+---------------------| | Optimized M-2 | 18 549 | 18 492 | 11 946 | Sieve limit 32770 | |-----------------+-----------+-----------+-----------+---------------------' | Borland C | 66 560 | | 52 224 | |-----------------+-----------+-----------+-----------| | Borland C++ | 149 504 | | 47 104 | |-----------------+-----------+-----------+-----------| | Watcom C | 37 376 | | 27 648 | |-----------------+-----------+-----------+-----------| | Watcom C++ | 51 712 | | 22 528 | |-----------------+-----------+-----------+-----------| | C# | 28 672 | 28 672 | 16 896 | |-----------------+-----------+-----------+-----------+---------------------. | Parva | N/A | N/A | N/A | Sieve limit 49000 | |-----------------+-----------+-----------+-----------+---------------------' | Modula-2 via | 62 976 | 63 488 | 62 464 | | Borland C | | | | `-----------------------------------------------------'
The corrected code is very simple. A few groups got it badly wrong, with braces in the wrong places.
void main() {
// Sieve of Eratosthenes for finding primes 2 <= n <= 49000 (Parva version)
// P.D. Terry, Rhodes University, 2007
const Max = 49000;
bool[] Uncrossed = new bool[Max]; // the sieve
int i, n, k, it, iterations, primes = 0; // counters
read("How many iterations? ", iterations);
read("Supply largest number to be tested ", n);
if (n > Max) {
write("n too large, sorry");
return;
}
it = 1;
while (it <= iterations) {
primes = 0;
write("Prime numbers between 2 and " , n, "\n");
write("-----------------------------------\n");
i = 2;
while (i <= n) { // clear sieve
Uncrossed[i-2] = true;
i = i + 1;
}
i = 2;
while (i <= n) { // the passes over the sieve
if (Uncrossed[i-2]) {
if (primes - (primes/8)*8 == 0)
write("\n"); // ensure line not too long
primes = primes + 1;
write(i, "\t");
k = i; // now cross out multiples of i
Uncrossed[k-2] = false;
k = k + i;
while (k <= n) {
Uncrossed[k-2] = false;
k = k + i;
}
}
i = i + 1;
}
it = it + 1;
write("\n");
}
write(primes, " primes");
}
It was very easy to discover how many solutions can be found to the N Queens problem. Some people noticed that the number of distinctly different solutions would have been lower, as the total included reflections and rotations as though they were distinct.
2 3 4 5 6 7 8 9 10 11 12
.-----------------------------------------------------------------------.
| 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14200 |
`-----------------------------------------------------------------------'
Clearly the number of solutions rises very rapidly. Some groups rashly put forward unjustified claims that the number of solutions rose "exponentially". If you were very keen you might like to try to estimate the O(N) behaviour rather better from these figures (how?).
Several students complained that the C code generated by the X2C system was "unreadable", and "not what we would have written ourselves". There can be no dispute with the second of those arguments, but if you take a careful look at the generated C code, it is verbose, rather than unreadable, because long identifier names have been used. This is actually not such a bad thing - at least one can tell the "origin" of any identifier, since the original module in which it was declared is incorporated into its name, and this is is a very useful trick, both for large programs, and (more especially) when one has to contend with the miserable rules that C has for controlling identifier name spaces. In fact, in the days when I used Modula regularly, I used a convention similar to this of my own accord, and have carried it over into my other coding, as you will see in several places in the book. Some of the other "unreadability" presumably relates to the fact that the X2C system is obliged to translate the CARDINAL type to the unsigned int type, which is not one some of you will ever have used - this explains all those funny casts and capital Us that you saw. Some people commented that "maintaining the C code generated would be a nightmare". Well, maybe, but the point of using a tool like this is that you can develop and maintain your programs in Modula-2 and then simply convert them to C when you want to get them compiled on some other machine. So normally a user of Xtacy would not read or edit the C code at all!
The times (seconds) taken to execute the various programs are shown below (figures in brackets are for runs on my 1.04GHz laptop, others for the 3.00 GHz lab machines). In all cases the systems ran on Windows XP.
.--------------------------------------------------------------------------------. | Sieve: Iterations 10 000 | Size of sieve 16 000 | |--------------------------+-----------------------------------------------------| | Queens: Iterations 100 | Board Size 11 | | |--------------------------+-----------------+-----------------------------------| | | Sieve | Queens | Queens1 | |--------------------------+-----------------+-----------------+-----------------| | Free Pascal | (9.2) 4.4 | (5.5) 3.2 | (5.2) 3.1 | |--------------------------+-----------------+-----------------+-----------------| | Free Pascal (optimized) | (8.6) 4.2 | (5.7) 3.1 | (5.0) 2.9 | |--------------------------+-----------------+-----------------+-----------------| | Modula-2 | (5.7) 2.4 | (9.2) 7.5 | (7.4) 6.6 | |--------------------------+-----------------+-----------------+-----------------| | Modula-2 (optimized) | (2.3) 1.8 | (8.0) 5.8 | (5.6) 4.3 | |--------------------------+-----------------+-----------------+-----------------| | C | (3.8) 2.2 | | | |--------------------------+-----------------+-----------------+-----------------| | C++ | (4.1) 2.1 | | | |--------------------------+-----------------+-----------------+-----------------| | Modula-2 (via BCC) | (25.2) 6.3 | (11.0) 4.6 | (10.7) 4.3 | |--------------------------+-----------------+-----------------+-----------------| | C# | (3.7) 3.2 | (3.8) 2.9 | (4.0) 2.8 | |--------------------------+-----------------+-----------------+-----------------| | Java (with JIT) | (6.6) 3.0 | (5.4) 2.6 | (5.3) 2.8 | |--------------------------+-----------------+-----------------+-----------------| | Java -Xint (interpret) | (74.3) 46.6 | (33.3) 23.6 | (37.8) 27.2 | |--------------------------+-----------------+-----------------+-----------------| | Parva | (1080) 448.0 | (434) 178.0 | (425) 186.0 | |--------------------------+-----------------+-----------------+-----------------| | Parva (optimized) | (810.0) 360.0 | (324) 139.0 | (326) 139.0 | `--------------------------------------------------------------------------------'
We note several points of interest:
(a) The Parva interpreted system is about two orders of magnitude slower than the native-code systems. Even here we can see the benefits of using an optimizing system, simple though this is (later we shall discuss this in more detail).
(b) In deriving these figures some experimentation was first needed so as to find parameters that would yield times sufficiently long to make comparisons meaningful. The times were obtained by simple use of a stopwatch, and of course there is always an element of reaction time in such measurements. The output statements were commented out so that all that was really being measured was the time for the algorithms themselves.
(c) The Java system, when JITed, is way better than when the JVM runs in pure interpreter mode.
(d) Even allowing for the reaction time phenomenon, there are some strange anomalies here. One might expect the execution times to be very closely related to the processor clock speeds, and that the ratio of times measured on the laptop and the lab machines for each application would have been the same, but clearly they are not. I expect that the differences - which are quite marked - can be put down to the different interior architectures of the processors themselves, but I have not had time to explore this further.
The solutions submitted were of very mixed quality. There were a few that I felt demonstrated excellent and enviable maturity in approach and coding skills. But there were a few that were still very incomplete, some that wrere completely confused, and some that showed that their authors prefer cutting and pasting code dozens of times in the editor rather than thinking through the simple mathematics required for a clean solution.
Here is code for the system I derived that derives the possibilities from the evidence, and then applies these systematically. Take a careful look at how I have tried to use the sets to best advantage and to guard against user errors - numbers out of range, numbers no longer assignable and so on.
This system will not solve all the puzzles in the kit. I am sure it could be improved still further. If you want to experiment further, look in the solution kit.
// Simple Sudoku helper - hints are given, and use made of the fact that each number
// must appear in each of the 3 x 3 sub squares.
// All hints are automatically applied (computer effectively plays as far as it can)
// PD Terry, Rhodes University, August 2007
import java.util.*;
import Library.*;
class sud4 {
static int count = 0, hints;
static SymSet range = new SymSet(new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8});
static SymSet all = new SymSet(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9});
static SymSet [] [] valid = new SymSet[9] [9];
static SymSet [] [] small = new SymSet[3] [3];
static int [] [] map = new int[9] [9];
static int [] [] hint = new int[9] [9];
static boolean stillPossible;
static void predictor() {
// predict obvious and not so obvious cells that can be fixed
hints = 0;
// look for "singles"
for (int row = 0; row <= 8; row++)
for (int col = 0; col <= 8; col++)
if (valid[row][col].members() == 1)
for (int i = 1; i <= 9; i++)
if (valid[row][col].contains(i)) { hint[row][col] = i; hints++; }
// look for numbers that only appear once in a row
for (int row = 0; row <= 8; row++)
for (int i = 1; i <= 9; i++) {
int inRow = 0, r1 = 0, c1 = 0;
for (int col = 0; col <= 8; col++)
if (valid[row][col].contains(i)) { inRow++; r1 = row; c1 = col; }
if (inRow == 1 & hint[r1][c1] == 0) { hint[r1][c1] = i; hints++; }
}
// look for numbers that only appear once in a column
for (int col = 0; col <= 8; col++)
for (int i = 1; i <= 9; i++) {
int inCol = 0, r1 = 0, c1 = 0;
for (int row = 0; row <= 8; row++)
if (valid[row][col].contains(i)) { inCol++; r1 = row; c1 = col; }
if (inCol == 1 & hint[r1][c1] == 0) { hint[r1][c1] = i; hints++; }
}
// look for "hidden singles"
for (int row = 0; row <= 2; row++)
for (int col = 0; col <= 2; col++) {
SymSet unused = all.difference(small[row][col]);
for (int i = 1; i <= 9; i++)
if (unused.contains(i)) {
int inBox = 0, r1 = 0, c1 = 0, keep = 0;
for (int r = 0; r <= 2; r++)
for (int c = 0; c <= 2; c++)
if (valid[3*row + r][3*col + c].contains(i)) {
keep = i; inBox++; r1 = 3*row + r; c1 = 3*col + c;
}
if (inBox == 1 && hint[r1][c1] == 0) { hint[r1][c1] = keep; hints++; }
}
}
}
static void fixAndUpdate() {
// incorporate the effects of the 3 x 3 sub matrices and
// display the matrix of assignable values and the matrix of already assigned values
int
row, col, subRow, subCol;
// eliminate elements from large matrix already assigned to the small submatrices
stillPossible = false;
for (row = 0; row <= 8; row++)
for (col = 0; col <= 8; col++) {
small[row/3][col/3].incl(map[row][col]);
hint[row][col] = 0;
}
for (row = 0; row <= 8; row++)
for (col = 0; col <= 8; col++) {
valid[row][col] = valid[row][col].difference(small[row/3][col/3]);
if (!valid[row][col].isEmpty()) stillPossible = true;
}
// draw the matrix of assignable values
IO.writeLine("Still assignable");
IO.writeLine(" 0 1 2 3 4 5 6 7 8 ");
IO.writeLine(" |=============+=============+=============|");
for (row = 0; row <= 8; row++) {
for (subRow = 0; subRow <= 2; subRow++) {
if (subRow == 1) { IO.write(row, 3); IO.write(" | "); } else IO.write(" | ");
for (col = 0; col <= 8; col++) {
for (subCol = 0; subCol <= 2; subCol++) {
int n = subRow*3 + 1 + subCol;
if (valid[row][col].contains(n)) IO.write(n, 1); else IO.write(" ");
};
if ((col + 1) % 3 == 0) IO.write(" | "); else IO.write(".");
};
IO.writeLine();
};
if ((row + 1) % 3 == 0)
IO.writeLine(" |=============+=============+=============|");
else
IO.writeLine(" |----+---+----+----+---+----+----+---+----|");
};
IO.writeLine();
// determine the cells that can be uniquely identified
predictor();
// draw the map of known and (predicted numbers)
IO.writeLine("Already assigned\n");
IO.write(" "); // top ruler line
for (col = 0; col <= 8; col++) { IO.write(col, 3); IO.write(" "); }
IO.writeLine();
IO.writeLine();
for (row = 0; row <= 8; row++) {
IO.write(row, 3); IO.write(": ");
for (col = 0; col <= 8; col++) {
if (map[row][col] == 0)
if (hint[row][col] != 0) IO.write(" (" + hint[row][col] + ")");
else IO.write(" .. ");
else { IO.write(map[row][col], 3); IO.write(" "); }
}
IO.writeLine();
}
IO.writeLine();
IO.write(" "); // bottom ruler line
for (col = 0; col <= 8; col++) { IO.write(col, 3); IO.write(" "); }
IO.writeLine();
IO.writeLine();
IO.write(count); IO.writeLine(" squares known. " + hints + " predictions");
}
static void claim(int row, int col, int n) {
// enter n into the map and eliminate it from the rows and columns of valid
map[row][col] = n; count++;
for (int r = 0; r <= 8; r++) valid[r][col].excl(n);
for (int c = 0; c <= 8; c++) valid[row][c].excl(n);
valid[row][col] = new SymSet();
}
public static void main(String[] args) {
int row, col, n;
// attempt to open data file
if (args.length != 1) {
IO.writeLine("Usage: Sudoku dataFile");
System.exit(1);
}
InFile data = new InFile(args[0]);
if (data.openError()) {
IO.writeLine("cannot open " + args[0]);
System.exit(1);
}
for (row = 0; row <= 8; row++) // initialize the valid matrix
for (col = 0; col <= 8; col++)
valid[row][col] = all.copy();
for (row = 0; row <= 2; row++) // initialise 3 x 3 matrices
for (col = 0; col <= 2; col++)
small[row][col] = new SymSet();
for (row = 0; row <= 8; row++) // read in the initial map
for (col = 0; col <= 8; col++) {
n = data.readInt();
if (n != 0) // check for self-consistency
if (valid[row][col].contains(n))
claim(row, col, n);
else { // we blew it
IO.writeLine("Invalid data (" + n + ") - line " + row + " column " + col);
System.exit(1);
}
}
fixAndUpdate(); // display initial matrices and map
do { // one move at a time
if (hints != 0) { // move that will apply predictions
IO.writeLine("Press any key to apply all predictions"); IO.readLine();
for (row = 0; row <= 8; row++)
for (col = 0; col <= 8; col++)
if (hint[row][col] != 0) claim(row, col, hint[row][col]);
fixAndUpdate();
}
else { // human move
IO.writeLine("Your move - row[0..8] col [0..8] value [1..9] (0 to give up)? ");
row = IO.readInt(); col = IO.readInt(); n = IO.readInt();
if (n == 0) System.exit(0);
if (range.contains(row) && range.contains(col) && valid[row][col].contains(n)) {
// check that it is available
claim(row, col, n);
fixAndUpdate();
}
else IO.writeLine("******* Invalid");
}
} while (count != 81 && stillPossible);
if (!stillPossible) IO.writeLine("\nNo more moves possible");
} // main
} // sud4