• MacTech Network:
  • Tech Support
  • |
  • MacForge.net
  • |
  • Apple News
  • |
  • Register Domains
  • |
  • SSL Certificates
  • |
  • iPod Deals
  • |
  • Mac Deals
  • |
  • Mac Book Shelf

MAC TECH

  • Home
  • Magazine
    • About MacTech in Print
    • Issue Table of Contents
    • Subscribe
    • Risk Free Sample
    • Back Issues
    • MacTech DVD
  • Archives
    • MacTech Print Archives
    • MacMod
    • MacTutor
    • FrameWorks
    • develop
  • Forums
  • News
    • MacTech News
    • MacTech Blog
    • MacTech Reviews and KoolTools
    • Whitepapers, Screencasts, Videos and Books
    • News Scanner
    • Rumors Scanner
    • Documentation Scanner
    • Submit News or PR
    • MacTech News List
  • Store
  • Apple Expo
    • by Category
    • by Company
    • by Product
  • Job Board
  • Editorial
    • Submit News or PR
    • Writer's Kit
    • Editorial Staff
    • Editorial Calendar
  • Advertising
    • Benefits of MacTech
    • Mechanicals and Submission
    • Dates and Deadlines
    • Submit Apple Expo Entry
  • User
    • Register for Ongoing Raffles
    • Register new user
    • Edit User Settings
    • Logout
  • Contact
    • Customer Service
    • Webmaster Feedback
    • Submit News or PR
    • Suggest an article
  • Connect Tools
    • MacTech Live Podcast
    • RSS Feeds
    • Twitter

 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".

 
MacTech Only Search:
Community Search:

 
 
 

 
 
 
 
 
  • SPREAD THE WORD:
  • Slashdot
  • Digg
  • Del.icio.us
  • Reddit
  • Newsvine
  • Generate a short URL for this page:



MacTech Magazine. www.mactech.com
Toll Free 877-MACTECH, Outside US/Canada: 805-494-9797
MacTech is a registered trademark of Xplain Corporation. Xplain, "The journal of Apple technology", Apple Expo, Explain It, MacDev, MacDev-1, THINK Reference, NetProfessional, Apple Expo, MacTech Central, MacTech Domains, MacNews, MacForge, and the MacTutorMan are trademarks or service marks of Xplain Corporation. Sprocket is a registered trademark of eSprocket Corporation. Other trademarks and copyrights appearing in this printing or software remain the property of their respective holders.
All contents are Copyright 1984-2010 by Xplain Corporation. All rights reserved. Theme designed by Icreon.
 
Nov. 20: Take Control of Syncing Data in Sow Leopard' released
Nov. 19: Cocktail 4.5 (Leopard Edition) released
Nov. 19: macProVideo offers new Cubase tutorials
Nov. 18: S Stardom anounces Safe Capsule, a companion piece for Apple's
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live
Nov. 17: Ableton releases Max for Live