How do I filter an array in C?

First a meta note. Code golf isn't a great way to learn a language. It explicitly optimizes for something that generally isn't valuable (fewer bytes of source code) typically at the expense of aspects that are valuable (idiomatic code, readability, efficiency, effectiveness).

On a less meta note, even for the purposes of code golf, trying to copy a solution from another, quite different, language line by line doesn't really make sense. JavaScript is a dynamically typed language with first-class functions and garbage collection. C is a statically typed language that lacks first-class functions and manages memory manually. In the single line that computes minorMatrix, the JavaScript code has two anonymous functions and performs 3+matrix.length allocations (1 for the filter, 1 for the map, 1 each for the anonymous functions, and 1 each for each call to slice). There are even more implicit or hidden allocations. In C, while certainly not unheard of, using function pointers is not an every-other-line kind of thing like it is in many higher-order languages including JavaScript. Similarly, memory allocation is often minimized because it can be expensive, often you want to use custom allocators, but probably mostly because it's error-prone and awkward to keep track of when to free that memory. A "one-to-one" translation of the JavaScript to C code is likely to be non-idiomatic, inefficient, verbose, and error-prone.

On an even less meta note, the algorithm used to compute the determinant is extremely bad from a performance perspective. It has O(n!) time complexity. This is worse than exponential! For the purposes of code golf this arguably isn't a problem, nevertheless the more efficient O(n^3) algorithm similar to Gaussian elimination, in addition to being dramatically more efficient, is likely more idiomatic and easier to golf. Nevertheless, below I'll stick with the Laplace expansion algorithm.

As you've started to gather, C doesn't include a filter function in its standard library. C has few standard library functions that take function pointers, and, in this case, a fully general purpose filter function is likely to take more code to call than it would be to just inline the implementation, while also being significantly less efficient or convenient. For example, here's a version of a relatively general-purpose filter function, but even then it only works for double arrays:

size_t filter(double *input, size_t len, bool (*predicate)(void *, double, int), void *env, double *output) {
    size_t outputLen = 0;
    for(size_t i = 0; i < len; ++i) {
        if(predicate(env, input[i], i)) {
            output[outputLen++] = input[i];
        }
    }
    return outputLen;
}

In most cases, simply inlining the for-loop would lead to more compact, more readable, and more efficient code.

For your particular use-case, though, it's much better to step back and think about what the code as a whole is trying to accomplish. The minorMatrix computation, for the n = 3 case, takes a matrix like

[ a b c ]
[ d e f ]
[ g h i ]

and produces three 2x2 matrices like the following:

[ _ _ _ ]    [ _ b c ]    [ _ b c ]
[ _ e f ]    [ _ _ _ ]    [ _ e f ]
[ _ h i ]    [ _ h i ]    [ _ _ _ ]

where the _s represent the entries omitted from the original matrix. The JavaScript code accomplishes this by literally creating these 2x2 matrices, but it should be clear that there's no reason to allocate anything. If we keep track of which rows and columns have been omitted, we can just iterate over the rows and columns of the original matrix, skipping the omitted ones. This is particularly easy for the columns, as we are always just omitting the first k columns, so we just need to keep track of a single column offset. The rows are more complicated because any pattern of rows could be omitted. Nevertheless, this can easily be tracked by a bit array. With this approach the filter in the JavaScript code becomes simply setting (and later resetting) a bit in an array.

double laplace_det_helper(double **matrix, size_t n, size_t offset, bool *omitted_rows) {                         
    if (n == offset) {                                                                                        
        return 1.0;                                                                                               
    }                                                                                                             
    double sum = 0.0;                                                                                             
    double s = 1;                                                                                                 
    for (size_t row_index = 0; row_index < n; ++row_index) {                                                      
        if (omitted_rows[row_index]) continue;                                                                    
        omitted_rows[row_index] = true;                                                                           
        sum += s * matrix[row_index][offset] * laplace_det_helper(matrix, n, offset+1, omitted_rows);             
        omitted_rows[row_index] = false;                                                                          
        s *= -1;                                                                                                  
    }                                                                                                             
    return sum;                                                                                                   
}                                                                                                                 
                                                                                                                  
double laplace_det(double **square_matrix, size_t n) {                                                            
    // Should check for an allocation failure but...                                                              
    bool *omitted_rows = (bool *)malloc(sizeof(bool) * n);                                                        
    for (size_t i = 0; i < n; ++i) {                                                                              
        omitted_rows[i] = false;                                                                                  
    }                                                                                                             
    double result = laplace_det_helper(square_matrix, n, 0, omitted_rows);                                        
    free(omitted_rows);                                                                                           
    return result;                                                                                                
}

posted over 2 years ago

CC BY-SA 4.0

Derek Elkins‭

2003 reputation 0 37 197 7

It looks like filter() effectively takes two arguments; the array to be filtered, and a predicate expression resulting in a boolean indicating whether the entry should be included in the output or not.

(I also note that the implementation in your question appears to be at least O(n^2) time complexity, which is pretty bad for anything but the smallest arrays.)

Beginning at the point of not concerning oneself with source code byte count, the tool in C's toolbox that I would reach for for this is either a specialized function for this one usage, or one that takes a pointer to a function that serves the purpose of the filter predicate. The latter is slightly more complex, but also generic as it can accept any predicate function.

The function pointer syntax in C takes some getting used to.

First, write a function that does whatever filtering you want. (For a real-world application, unless I had some highly specialized need, I would first see if there are already-debugged third-party library implementations of this rather than trying to come up with my own implementation.)

int* filter(int* input, bool (*predicate)(int))
{
    int* output;
    while (*input != -1)
    {
        if(predicate(*input))
        {
            // somehow include *input in the output
        }
        input++;
    }
    return output;
}

Then, write a predicate function which will be called once per entry:

bool my_predicate(int value)
{
    return (value & 3) != 0; // or whatever
}

Then put them together:

int* filtered = filter(unfiltered, my_predicate);

Adding some boilerplate this compiles cleanly with gcc -Wall -std=c99 -pedantic-errors -Wextra -Werror.

Reducing the character count in the source code is kind of what code golfing is about as I understand it, so I will leave that part entirely up to you.

posted over 2 years ago

CC BY-SA 4.0

Canina‭

1479 reputation 2 23 149 31