A covering array is an N by k array in which each element is one of {0, 1, ..., v-1} (so v symbols in total), and for any t columns chosen (so an N x t array) contains all possible v^t tuples at least once. The applications of Covering Arrays range from software and hardware testing, interaction testing, and many other fields. A research question (and which will be a follow-up to this question) is to find the minimal Covering Array of given t,k,and v; an analogue of this would be designing a software system with the minimal number of tests required to test all t-way interactions of the system. Only for t=v=2 is the optimal case known for all k (some values of t and v have some optimal CA designs for one value of k, but this is not the common case).

Here, we focus on validation of Covering Arrays, as this is a very time-consuming process for very large Covering Arrays.

Input: A file that contains the Covering Array. The format is described in Scoring below.

Output: Valid if the input is a valid covering array, and Invalid if it is not.

Goal: in any language you want, write a program that validates if the input is a covering array in the fastest time. I will run programs on my machine, which is a Mac Pro 3.5 Ghz 6-Core Intel Xeon E5 (2013) with 16 GB RAM (1866 MHz).


  1. Any language is allowed, as long as it can read from a file, where the filename is given as input.
  2. All you need to print is Valid or Invalid, nothing else.
  3. No third-party libraries; you can only use the libraries/modules that are already built-in to the language.
  4. No use of the Internet for validation (i.e., the validation must be done within the program itself).
  5. You are allowed to have multi-threading/multi-core solutions. However, I will test it on the machine described above.
  6. If your program requires a compilation, describe in your answer what compilation options that you selected (i.e., like g++ -O3 validator.cpp ca.5.6^7.txt).

Scoring: the total score is the total amount of time in milliseconds to produce all of the valid outputs. I will test your program against a number of CAs, and it reports the total amount of time required to execute validation of all sample CAs as input. The CAs will be selected from this link (the text files are provided there, and is linked to from the first link above also).

The format of the files posted there is provided as follows: the first line of the file is N, the name of the file is ca.t.v^k.txt, and the next N rows of the file contain k space-separated integers.

Fastest code (i.e., lowest score) wins!

Edit: after looking at some sample covering arrays on the site, the format is not entirely consistent. If you can change (or provide the file) the format to match the format described above, that would be very helpful.

  • \$\begingroup\$ Lowest score wins, right? I think I understand the requirements, but your challenge would probably benefit from some examples, i.e. at least one valid and one invalid instance. \$\endgroup\$
    – Oliphaunt
    Jun 22, 2015 at 14:05
  • \$\begingroup\$ Although your first link does provide examples. So maybe just point at that once more. \$\endgroup\$
    – Oliphaunt
    Jun 22, 2015 at 14:12
  • \$\begingroup\$ @Oliphaunt Thank you, I'll correct it. \$\endgroup\$ Jun 22, 2015 at 14:17
  • 1
    \$\begingroup\$ @Ryan is it okay to use the C standard math library (#include <math.h>)? As you probably know, it's a part of the c stdlib, but it was separated from the other parts because it is relatively big ... \$\endgroup\$ Jun 23, 2015 at 15:11
  • \$\begingroup\$ @ThomasOltmann Yes that's okay. \$\endgroup\$ Jun 23, 2015 at 18:16

3 Answers 3


C, 7.29min for ca.5.4^64.txt on an Intel Core i5-4570 + 8GB ram

Update: Sometimes gives wrong results

I've compiled it with gcc -O3 cav.c -o cav. Simply run it with the CA file's name as first (and only) parameter. In my case: ./cav ca.2.2^4.txt

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

int t, v, k, N; /* initial parameters */
uint16_t *ca; /* The CA */
uint16_t *cia; /* Column index array - the columns we selected to compare */
uint8_t *combos;
int num_combos; /* Size of the combo 'hash map' (see compareColumns()) */

int ipow(int base, int exp) /* basic integer pow function 'stolen' from StackOverflow ;) */
    int result = 1;
        if(exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    return result;

char compareColumns(int base, int child)
    int pos = base, maxpos = k - child, child_dec = child - 1;
    if(child == 0)
        while(pos != maxpos)
            cia[child] = pos++;
            memset(combos, 0, num_combos);
            int rv = 0; /* The offset in the CA for the current row */
            int n;
            for(n = 0; n < N; n++) /* For every row */
                int key = 0; /* This is basically a HashMap key, using the same algorithm that you use for accessing 2D data in a 1D array. */
                int df = 1; /* Dimension factor - needed for the hash-map-key-like algorithm */
                int i;
                for(i = 0; i < t; i++) /* For every selected column */
                    key += df * ca[cia[i] + rv]; /* Calculate the key */
                    df *= v;
                combos[key] = 1; /* Set the 'boolean' at 'key' in the 'hash map' to 1 */
                rv += k;
            if(memchr(combos, 0, num_combos) != NULL) /* If there are still any 0s (any needed combinations that aren't found), exit immediately! */
                return 0;
        while(pos != maxpos)
            cia[child] = pos++;
            if(!compareColumns(pos, child_dec))
                return 0;
    return 1;

int main(int argc, char **argv)
    /* Fetch user input & allocate memory */
    sscanf(argv[1], "ca.%d.%d^%d.txt", &t, &v, &k);

    FILE *file = fopen(argv[1], "r");
    fscanf(file, "%d", &N);

    int num_vals = k * N, i;
    num_combos = ipow(v, t);

    ca  = (uint16_t*)malloc(num_vals * sizeof(uint16_t));
    cia = (uint16_t*)malloc(t * sizeof(uint16_t));
    combos = (uint8_t*)malloc(num_combos * sizeof(uint8_t));

    for(i = 0; i < num_vals; i++)
        int val;
        fscanf(file, " %d", &val);
        ca[i] = val;

    /* The main algorithm implementation */
    if(compareColumns(0, t - 1))

    /* Free memory */
    return 0;

I'll try to explain: I'll begin with compareColumns: if it has children (int child), it goes through (allmost) all the columns and kicks off a new call to compareColumns after each step, which itself then walks from the last position of its parent until the end (minus it's own children) of the CA. However, if the function is called with no children (child = 0), it will take all the selected rows and generate something like a hash map key from it. This key will then be used to set a specific cell of the array combos to 1. At the end, it checks if all cells of 'combos' are 1 (i.e. if all combinations appeared at least once). If all cells are 1, it will proceed. If at least one cell is 0, it will abort immediately and print "Invalid!".

  • \$\begingroup\$ how does your algorithm work like ? \$\endgroup\$
    – Abr001am
    Jun 23, 2015 at 18:28
  • \$\begingroup\$ I run into a Segmentation fault: 11 when I ran this (even for small CAs). \$\endgroup\$ Jun 23, 2015 at 19:57
  • \$\begingroup\$ @Thomas Oltmann I have an algorithm similar in my head, please try to explain more to avoid putting same algorithm \$\endgroup\$
    – Abr001am
    Jun 23, 2015 at 20:30
  • \$\begingroup\$ @Ryan i ran it here with stdin input without using files and gave me this result for ca.2.2^2000.txt: Success time: 0.68 memory: 2144 signal:0 Valid! \$\endgroup\$
    – Abr001am
    Jun 23, 2015 at 21:48
  • 1
    \$\begingroup\$ @Ryan I'm currently trying to find the most memory wasting arrays via gdb and valgrind. :) \$\endgroup\$ Jun 24, 2015 at 13:31

Python solution

Uses multiprocessing package to test validity of each v-set of columns selected from the input matrix.

Download from here.


$ python main.py ca.t.v^k.txt

  • \$\begingroup\$ This reports one of the CAs (specifically, ca.3.4^19.txt) on the site as Invalid. \$\endgroup\$ Jul 5, 2015 at 20:29
  • \$\begingroup\$ It was a bug. Fixed now. \$\endgroup\$
    – jkklapp
    Jul 7, 2015 at 17:02
  • \$\begingroup\$ Seems good, looks like it works well! I'll test it for speed later. \$\endgroup\$ Jul 7, 2015 at 20:08
  • \$\begingroup\$ @Ryan did you got to test the speed? \$\endgroup\$
    – jkklapp
    Jul 28, 2015 at 14:08
  • \$\begingroup\$ I didn't need to as there were no other submissions that worked (and I could test). If there is another submission, I will test and report times. But if I remember correctly, some of the strength 4 arrays took a few seconds for verification. \$\endgroup\$ Jul 28, 2015 at 22:09


Mostly just a brute force solution, except it does a few preliminary checks ahead of time and uses a binary search to find tuples in each sub-array. I think Fantom optimizes most built in stuff, like the sorts and array manipulations, pretty well under-the-hood. Note: Replaces "-" with : "0" for simplicity.

To Run

Download Fantom from the link in the title, and set up your system variables using instructions here. Save in a file called isCA.fan
run as fan isCA.fan "pathToFile"

class isCA
  public static Void main(Str[] args){

    Int start := Duration.nowTicks;
    //Initialize everything
    path := "file:" + args.first
    params := path.split(File.sep.chars.first).last.split('.')
    t := Int.fromStr(params[1])
    params = params[2].split('^')
    v := Int.fromStr(params[0])
    k := Int.fromStr(params[1])
    StrArray := File(Uri.fromStr(path)).in.readAllLines[1..-1]
    array := StrArray.map |Str line -> Str[]| {line.replace("- ", "0 ")[0..-2].split(' ').map |Str s ->Int| {Int.fromStr(s)}}
    //echo("t: $t\n v: $v\nk: $k")
    //Comparison function
    compare := |Int[] a, Int[] b -> Int| {
      Int i := 0
      result := -1
      done := false
      while(i < a.size - 1 && !done){
        if(a[i] != b[i]){ 
          result = a[i] <=> b[i]
          done = true
          return a[i] <=> b[i]
      return result
    //Basic checks to speed up the Not Valid time
    array = array.sort(compare).unique
    //Each column contains each value
    k.times|Int i|{
      vals := Range(0, v, true).toList
      array.each |Int[] row|{
      if(!vals.isEmpty){ respond(false, start)}
    //umm, I guess I'll start with the brute-force method until I think of something better
    vals := Range(0,v,true).toList
    tuples := permutations(vals)
    temp := [,]
    t.times{ temp.add(1)}
    (k - t).times{ temp.add(0) }
    colBins := permutations(temp).unique
    colBins.each |Int[] bin| {
      //Construct columns
      smallArray := array.map |Int[] row -> Int[]|{
        r := [,]
        row.each |Int a, Int index|{ if(bin[index] == 1){r.add(a)}}
        return r
      tList := tuples.dup
      Int cols := t
      //Binary search the array
      while(cols >= v){
        found := [,]
        tList.each|Int[] tuple, Int index|{
          Int find := smallArray.binarySearch(tuple, compare)
          //echo("Found $tuple at $find in $smallArray")
          if(find >= 0){found.add(index)}
        //Remove first col and try again
        smallArray = smallArray.map|Int[] a -> Int[]| {return a[1..-1]}
        //ignore tuples we already found
        tList = tList.findAll|Int[] list, Int index -> Bool| {!found.contains(index)}
        echo("Cols $bin does not contain $tList")
        respond(false, start)
    respond(true, start)
  private static Void respond(Bool b, Int start){
    if(b) echo("Valid")
    else echo("Not Valid")
    echo("Time: " + (Duration.nowTicks() - start))
  private static Int[][] permutations(Int[] a){
    result := [,]
    recurse([,], a, result)
    return result
  private static Void recurse(Int[] pre, Int[] a, Int[][] results){
    //echo("Recursing $pre\nwith $a")
    if(a.isEmpty) {
    for(Int i := 0; i < a.size; i++){
      d := a.dup
      recurse(pre.dup.add(a[i]), d, results )
  • \$\begingroup\$ I can't find a way to install Fantom on Mac OS X. \$\endgroup\$ Jul 7, 2015 at 20:11
  • \$\begingroup\$ Ooh, Hmm, never used it on OS X, I'll have to look into that, sorry! \$\endgroup\$
    – Cain
    Jul 7, 2015 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.