|
|
|
|
December 1999 Programmer's Challenge
Costas Arrays
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Thursday, 9 December 1999
A Costas array of order N is an NxN array of 1s and 0s satisfying two constraints. First, the array must have exactly N 1s and N*(N-1) 0s, with exactly one 1 in each row and column. Second, no two lines between pairs of 1s may have exactly the same length and the same slope. So, for example, there are exactly 12 Costas arrays of order 4:
1000 0001 0010 0010 1000 0001
0010 1000 1000 0100 0001 0100
0001 0010 0100 0001 0100 1000
0100 0100 0001 1000 0010 0010
0100 0100 1000 0001 0100 0010
0010 0001 0100 0010 1000 0001
1000 0010 0001 1000 0010 0100
0001 1000 0010 0100 0001 1000
So why would one care about Costas arrays? Because of the asymmetries imposed by the two constraints, Costas arrays make ideal waveforms for certain sensor applications, reducing ambiguity in interpreting radar and sonar returns. The mathematics are interesting in other ways. For example, according to the CRC Standard Mathematical Tables, the number C(n) of Costas arrays of order n increases as a function of n until n==16, after which it decreases, at least until n==23:
|
n |
C(n) |
n |
C(n) |
|
1 |
1 |
2 |
2 |
|
3 |
4 |
4 |
12 |
|
5 |
40 |
6 |
116 |
|
7 |
200 |
8 |
444 |
|
9 |
760 |
10 |
2160 |
|
11 |
4368 |
12 |
7852 |
|
13 |
12828 |
14 |
17252 |
|
15 |
19612 |
16 |
21104 |
|
17 |
18276 |
18 |
15096 |
|
19 |
10240 |
20 |
6464 |
|
21 |
3536 |
22 |
2052 |
|
23 |
872 |
24 |
>=1 |
The number of Costas arrays of order 24 and greater is the subject of continuing research. Your Challenge is to aid these researchers by writing efficient code to enumerate Costas arrays.
The prototype for the code you should write is:
#if defined(__cplusplus)
extern "C" {
#endif
long /* number of arrays */ EnumerateCostas(
int n, /* enumerate Costas arrays of order n */
long *costasArrays /* preallocated storage for returning your results */
/* row r of array k is in costasArrays[k*n + r], r,k are origin 0 */
);
#if defined(__cplusplus)
}
#endif
Your EnumerateCostas routine will be asked to enumerate all Costas arrays of order n and return the results in the preallocated costasArrays. Each cell of an array is represented by one bit. The bits for row r of the k-th Costas array are to be returned in costasArrays[k*n + r], r=0..n-1, k>=0. The cell representing column c, c=0..n-1, is the bit in 1<<c. EnumerateCostas must produce all valid Costas arrays, with no duplicates, and return the number of arrays produced.
The winner will be the solution that correctly enumerates the Costas arrays in the minimum time.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, Pascal, or Java.
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
