Covering Array Validator 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). 

Rules:


Any language is allowed, as long as it can read from a file, where the filename is given as input.
All you need to print is Valid or Invalid, nothing else.
No third-party libraries; you can only use the libraries/modules that are already built-in to the language.
No use of the Internet for validation (i.e., the validation must be done within the program itself).
You are allowed to have multi-threading/multi-core solutions. However, I will test it on the machine described above.
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.
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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;stdint.h&gt;

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;
    while(exp)
    {
        if(exp &amp; 1)
            result *= base;
        exp &gt;&gt;= 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 &lt; 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 &lt; 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;
        }
    }
    else
    {
        while(pos != maxpos)
        {
            cia[child] = pos++;
            if(!compareColumns(pos, child_dec))
                return 0;
        }
    }
    return 1;
}

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

    FILE *file = fopen(argv[1], "r");
    fscanf(file, "%d", &amp;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 &lt; num_vals; i++)
    {
        int val;
        fscanf(file, " %d", &amp;val);
        ca[i] = val;
    }
    fclose(file);

    /* The main algorithm implementation */
    if(compareColumns(0, t - 1))
        printf("Valid!\n");
    else
        printf("Invalid!\n");

    /* Free memory */
    free(combos);
    free(cia);
    free(ca);
    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!".