Covering Array Validator

Question

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:

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.

Answer 1

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;
    while(exp)
    {
        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;
        }
    }
    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 & 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;
    }
    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!".

Answer 2

Python solution

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

Download from here.

Run:

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

Answer 3

Fantom

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
        }
        i++
        if(!done){
          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|{
        vals.remove(row[i])
      }
      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){
        smallArray.sort(compare)
        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]}
        cols--;
        //ignore tuples we already found
        tList = tList.findAll|Int[] list, Int index -> Bool| {!found.contains(index)}
      }
      
      if(!tList.isEmpty){
        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))
    Env.cur.exit
  }
  
  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) {
      results.add(pre)
      return
    }
    
    for(Int i := 0; i < a.size; i++){
      d := a.dup
      d.removeAt(i)
      recurse(pre.dup.add(a[i]), d, results )
    }
  }
}