3
\$\begingroup\$

This is the followup question to this previous CodeGolf question about Covering Arrays (the details of what Covering Arrays are and how they are formatted at the NIST website are there).

In this challenge, we won't just be validating covering arrays - we will try to minimize them. Finding minimal Covering Arrays, in general, is a very tough research-level question, and is of interest due to their applications in software/hardware testing, among other fields.

What we will do here is, given some Covering Arrays from NIST, try to minimize them as much as possible. I picked the following covering arrays (with their .txt.zip files as the links - unzipping the file gives the .txt desired file):

What you will do is try to minimize the N in each CA to get the smallest possible for each. There are a number of possible techniques:

  • Combining other CAs to form the desired CA
  • Metaheuristics, such as simulated annealing or tabu search
  • Any other technique!

Scoring

Your score will be the sum of the N of all 5 CAs that you create. For example, if I did not do anything and turned in the 5 CAs given above, my score would be 13+159+2337+29963+125683 = 158155.

The winner will be the person with the lowest score. Any method of generating the CAs works - you should provide the source code you used to generate the CA as well as say which CA verifier you used (either on the linked question or somewhere else online). Also, any programming language is allowed.

Formatting

You also need to provide the CAs that you generate, in the same format as the NIST CAs. Don't worry about finding the "don't care" positions that are in the original CAs. Since some of the CAs are large, you will need to host the files somewhere for other users to download and verify correctness.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.