|
January 2000 Programmer's Challenge
Latin Squares
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Friday, 4 February 2000
A Latin Square of order N is an NxN array of numbers, where each number from 1..N occurs exactly once in each row and in each column. Your Challenge this month is to construct Latin Squares that are minimal, in the sense that each must form the smallest NxN digit base N number, where the digits are read off column by column, one row at a time. [We use the digits 1..N instead of 0..N-1, so the numbers aren’t really base N, but you get the idea.]
The prototype for the code you should write is:
#if defined(__cplusplus)
extern "C" {
#endif
void LatinSquares(
short n, /* dimension of the Latin Square to be generated */
short *latinSquare /* set latinSquare[c + r*n] to square value row r, col c */
);
#if defined(__cplusplus)
}
#endif
For example,
1234
2341
4123
3412
is a Latin Square with the value 1234234141233412. It is not the minimal Latin Square of order 4, however, since the following Latin Square,
1234
2143
3412
4321
forms the smaller number 1234214334124321.
The dimension of the squares you must generate will be less than 2**16. The winner will be the solution that correctly computes minimal Latin Squares in the least amount of execution time. Code size and code elegance, in that order, will be the tiebreakers, in the event two solutions are within 1% of one another in execution time. All Latin Squares must be computed at execution time — entries that precompute solutions will be disqualified.
This month’s Challenge was suggested by Aaron Montgomery, who earns 2 Challenge points for making the suggestion
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C, C++, or Pascal. Solutions in Java will also be accepted, but Java entries must be accompanied by a test driver that uses the interface provided in the problem statement.
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the
Programmer's Challenge mailing list. It will be posted to the list on
or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com
with the subject "subscribe challenge-A". You can also join the
discussion list by sending a message with the subject "subscribe
challenge-D".
|
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
