Dec 99 Challenge
Volume Number: 15
Issue Number: 12
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Costas Arrays
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)
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<
duplicates, and return the number of arrays produced.
Testing will be constrained to arrays of order 32 or less. 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.
Three Months Ago Winner
Congratulations to our top two leaders in the points contest for finishing first and
second in the September Playfair Challenge. Ernst Munter (Kanata, Ontario) took first
place with a solution that was by far the fastest, and Tom Saxton took second place.
The Playfair Decipher Challenge asked contestants to decrypt an encoded phrase based
on knowing the dictionary of words used in the message and some information about
how the encoding is done. Encoding is based on a keyword from the dictionary, which is
used to create a 5x5 encoding substitution matrix for the letters of the alphabet. The
encoding matrix maps pairs of plaintext letters into pairs of encoded text.
Complicating factors include the fact that the letters 'I' and 'J' are encoded as the same
character. The encoding technique also inserts separator characters ('X' or 'Z') to
separate repeated letters in a pair, in order to prevent double letters from mapping
into an easily detected encoded letter pair. For more information on the problem,
consult the September issue of MacTech, or check out the online version at
<http://www.mactech.com/progchallenge/>.
Ernst's solution thoroughly analyzes the dictionary during the initialization phase. The
SetUpDecocders routine creates a Decoder matrix for each potential keyword in the
dictionary, minus duplicate matrices resulting from similar keywords. The
initialization of the CodeBreaker structure creates a set of LinkedNodes based on the
first three letters of the words in the dictionary. It also registers all letter triplets
(trigraphs) that occur at the beginning or the end of a dictionary word. The decoding
routine loops through all of the words in the dictionary, trying each of them as a
decoding keyword. The trigraphs calculated during initialization are used by the
DecodeCipher routine to prune the decoding process. If decoding is successful to this
point, the CodeBreaker::Spell routine recursively matches the potentially decoded text
to dictionary words. The code is complicated but fast.
Tom Saxton's solution also analyzes the dictionary during initialization, creating a tree
structure. It creates the decoding matrix during the decoding process, not during
initialization. Tom's word matching algorithm is recursive in concept, but iterative in
implementation. Overall, Tom's solution took somewhat more than twice as long as the
winning solution.
The third-place solution by Lad (last name unknown) was nearly as fast as the
second-place solution. It was unique in that it was submitted as a library rather than
as source code. Normally that would have been a disqualification, but since the
September Challenge, in keeping with tradition, allowed solutions to be coded in
assembly language, I decided to score the results.
The table below lists, for each of the five solutions submitted, the total execution time,
code size, data size, and programming language. It also indicates whether a solution
completed all of the test cases correctly. As usual, the number in parentheses after the
entrant's name is the total number of Challenge points earned in all Challenges prior to
this one.
Name Time (msec) Errors Code Size Data Size Language
Ernst Munter (507) 493 no 8052 5580
Tom Saxton (118) 1059 no 6984 443 C
Lad 1132 no 2796 170 Unknown
Rishi Gupta 57503 no 11844 1919 C++
R. B. 90773 yes 4828 638 C++
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 or more points during the past two years. The
numbers below include points awarded over the 24 most recent contests, including
points earned by this month's entrants.
Rank Name Points
1. Munter, Ernst 227
2. Saxton, Tom 116
3. Maurer, Sebastian 70
4. Boring, Randy 66
5. Rieken, Willeke 51
6. Heithcock, JG 39
7. Shearer, Rob 34
8. Brown, Pat 20
9. Hostetter, Mat 20
10. Mallett, Jeff 20
11. Jones, Dennis 12
12. Hart, Alan 11
13. Hewett, Kevin 10
14. Murphy, ACC 10
15. Selengut, Jared 10
16. Smith, Brad 10
17. Strout, Joe 10
18. Varilly, Patrick 10
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the
first person to suggest a Challenge that I use. The points you can win are:
1st place ›20 points
2nd place ›10 points
3rd place ›7 points
4th place ›4 points
5th place ›2 points
finding bug ›2 points
suggesting Challenge ›2 points
Here is Ernst's winning Playfair solution:
Playfair.cp
Copyright © 1999 Ernst Munter
/*
September 6, 1999.
Submission to MacTech Programmer's Challenge for September 99.
Copyright © 1999, Ernst Munter, Kanata, ON, Canada.
"Playfair Decipher
Version 2
Problem Statement
---------
Given a dictionary, a cipher text, and the encoding method, break the
code and return the deciphered plaintext.
Solution
----
My strategy is to decode the ciphertext with each possible keyword
until a plain text results which is accepted by the spell checker.
In InitPlayfair() the dictionary is scanned twice.
First, the set of decoders, one for each keyword, is constructed.
Because similar keywords can result in identical coding matrices,
redundant matrices are discarded where the keywords are within a
certain distance of each other in the dictionary.
Secondly, a spell check tree is built which indexes all words in the
dictionary that are distinct in the first 5 characters (stem). Longer
words are checked by indexing to the stem, and scanning the group of
words which share the same stem directly in the dictionary.
In addition, all trigraphs (sequences of 3 chars) in the dictionary
words and digraphs marking start and end of each word are collected.