Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs

Dashboard
Notifications
Mark all as read
Q&A

How do I filter an array in C?

+1
−2

No, I'm not trying to get the full program written completely in C by you guys. I only need some way to implement the functionalities of each function I found confusing.

In this challenge in Code Golf CD, I have to make a program that computes the determinant of a two-dimensional array. It also has a program written in JavaScript that solves the challenge which looks like this:

function laplaceDet(matrix) {
	if (matrix.length === 1) return matrix[0][0];

	let sum = 0;
	for (let rowIndex = 0; rowIndex < matrix.length; ++rowIndex) {
		let minorMatrix = matrix.filter((_, index) => index !== rowIndex)
			          .map(row => row.slice(1));
		sum += ((-1) ** rowIndex) * matrix[rowIndex][0] * laplaceDet(minorMatrix);
	}
	return sum;
}

I want to challenge myself into using C for solving the challenge. First, I'll need to reimplement the program, whereas the golfing part will be dealt with later, although I've already been golfing it. Here's what I got so far.

Why'd I stop? There's a function named filter() and I'm not so sure how to get it implemented, and since C has no maps (at least I think none exist in C), it's also difficult to complete the program without it.

So I'll have to improvise... How? How do I implement the filter() method, maybe without using a function to save bytes, and what's a C equivalent to the line of code matrix.filter((_, index) => index !== rowIndex).map(row => row.slice(1));?

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

1 comment thread

I don't know how you normally approach those things. I usually start with getting something working b... (2 comments)

2 answers

+4
−0

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;                                                                                                
}

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+3
−1

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.

Why does this post require moderator attention?
You might want to add some details to your flag.

2 comment threads

Missing and misleading details (2 comments)
Complexity (1 comment)

Sign up to answer this question »