Initial Query

Rewrite this function in C. You can assume that the input is a 2d matrix correctly formatted. Call it rref(int** matrix, int rows, int cols, int graphlen) where the size is matrix[rows][cols]. Return an int** of used_for_row. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]

LLM Generation

Query

Rewrite this function in C. You can assume that the input is a 2d matrix correctly formatted. Call it rref(int** matrix, int rows, int cols, int graphlen) where the size is matrix[rows][cols]. Return an int** of used_for_row. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]

Output

Okay, here is the C implementation of the `rref` function. **Assumptions:** 1. The input `matrix` is a dynamically allocated 2D array (`int**`) where `matrix[i]` points to a dynamically allocated array of `cols` integers. 2. The caller is responsible for freeing the memory allocated for the returned `int**` array (both the inner arrays and the outer array). 3. The value `PH = 16` is used as in the Python code. 4. The returned `int** used_for_row` will have `rows` inner arrays. Each inner array `used_for_row[i]` will contain the sorted indices of the original rows that contribute to the final row `i`, terminated by a `-1` sentinel value. 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h> // For assertions (optional, can be removed)

#define PH 16

// Helper function for correct modulo arithmetic (handles negative results)
int mod(int a, int m) {
    return (a % m + m) % m;
}

// Helper function to swap two integer pointers (used for rows)
void swap_int_ptr(int** a, int** b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}

// Helper function to swap two boolean pointers (used for tracking arrays)
void swap_bool_ptr(bool** a, bool** b) {
    bool* temp = *a;
    *a = *b;
    *b = temp;
}

// Comparison function for qsort
int compare_ints(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

/**
 * @brief Computes the Reduced Row Echelon Form (RREF) of a matrix modulo PH
 *        and tracks the original rows contributing to each final row.
 *        The input matrix is modified in place.
 *
 * @param matrix The input matrix (rows x cols). Modified in place.
 * @param rows Number of rows in the matrix.
 * @param cols Number of columns in the matrix.
 * @param graphlen Parameter influencing normalization/elimination strategy.
 * @return int** An array of arrays. result[i] contains the sorted indices
 *               of original rows contributing to final row i, terminated by -1.
 *               Returns NULL on allocation failure. Caller must free the result.
 */
int** rref(int** matrix, int rows, int cols, int graphlen) {
    if (!matrix || rows <= 0 || cols <= 0) {
        return NULL; // Invalid input
    }

    int extra = 0;
    int col = 0; // Represents the current row index we are trying to find a pivot for

    // --- Initialization of used_for_row tracking ---
    // Use boolean arrays for efficient union operations
    bool** temp_used_for_row = (bool**)malloc(rows * sizeof(bool*));
    if (!temp_used_for_row) {
        perror("Failed to allocate memory for temp_used_for_row pointers");
        return NULL;
    }
    for (int i = 0; i < rows; ++i) {
        // calloc initializes memory to zero (false)
        temp_used_for_row[i] = (bool*)calloc(rows, sizeof(bool));
        if (!temp_used_for_row[i]) {
            perror("Failed to allocate memory for temp_used_for_row inner array");
            // Clean up previously allocated rows
            for (int j = 0; j < i; ++j) {
                free(temp_used_for_row[j]);
            }
            free(temp_used_for_row);
            return NULL;
        }
        temp_used_for_row[i][i] = true; // Row i initially depends only on original row i
    }

    // --- Initial Modulo Operation ---
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            matrix[r][c] = mod(matrix[r][c], PH);
        }
    }

    // --- Main RREF Loop ---
    // Loop while we have columns to process and rows to use as pivots
    while (col < rows && col + extra < cols) {
        int pivot_col = col + extra; // Current column being considered for pivot

        // --- Find Pivot Row ---
        if (mod(matrix[col][pivot_col], PH) == 0) {
            int other_row = -1;
            // Find the last row below 'col' with a non-zero entry in pivot_col
            for (int r = rows - 1; r > col; --r) {
                 if (mod(matrix[r][pivot_col], PH) != 0) {
                    other_row = r;
                    break;
                }
            }

            if (other_row == -1) {
                // All entries below (and at) matrix[col][pivot_col] are zero.
                // Check if the entire column is zero (Python used np.all)
                bool all_zero = true;
                 for(int r = 0; r < rows; ++r) { // Check *entire* column
                     if (mod(matrix[r][pivot_col], PH) != 0) {
                         all_zero = false;
                         // Python code found the *last* non-zero row. If it was < col, it skipped.
                         // Let's replicate that specific check.
                         int last_nonzero = -1;
                         for(int r_check = rows - 1; r_check >= 0; --r_check) {
                            if (mod(matrix[r_check][pivot_col], PH) != 0) {
                                last_nonzero = r_check;
                                break;
                            }
                         }
                         if (last_nonzero < col) {
                             all_zero = true; // Treat as if all zero for pivot purposes here
                         } else {
                             // This case implies a non-zero element exists >= col,
                             // but matrix[col][pivot_col] was 0 and the loop above
                             // didn't find one > col. This means the non-zero must be at 'col'.
                             // This state shouldn't be reached if logic is sound, but handle defensively.
                             // The original code would have skipped the column if other < col.
                             // If other_row == -1 here, it means non-zeros only exist <= col.
                             // If matrix[col][pivot_col] is 0, and non-zeros only exist < col, skip.
                             bool non_zero_above = false;
                             for(int r_check = 0; r_check < col; ++r_check) {
                                if (mod(matrix[r_check][pivot_col], PH) != 0) {
                                    non_zero_above = true;
                                    break;
                                }
                             }
                             if (non_zero_above) {
                                 all_zero = true; // Skip column if only non-zeros are above
                             } else {
                                 // This implies matrix[col][pivot_col] must be the only non-zero >= col
                                 // but we are in the block where it's 0. Contradiction?
                                 // Let's trust the initial check and skip if other_row == -1.
                                 all_zero = true;
                             }
                         }
                         break; // Exit the outer check loop
                     }
                 }

                if (all_zero) {
                    extra++; // Skip this column
                    continue; // Go to the next iteration of the while loop
                }
                // If we reach here, it means other_row must have been found > col,
                // but the initial check matrix[col][pivot_col] == 0 failed?
                // Let's re-check the logic flow. The Python code finds the *last* non-zero row `other`.
                // If `other < col`, it skips. If `other >= col` and `matrix[col][pivot_col] == 0`, it swaps `col` and `other`.
                // Let's re-implement the search for `other` more directly.

                other_row = -1; // Reset
                for (int r = rows - 1; r >= 0; --r) { // Find last non-zero in column
                    if (mod(matrix[r][pivot_col], PH) != 0) {
                        other_row = r;
                        break;
                    }
                }

                if (other_row == -1 || other_row < col) { // No suitable pivot found in this column
                    extra++;
                    continue;
                }
                // else: other_row >= col. Since matrix[col][pivot_col] is 0, other_row must be > col.
                 // Swap row 'col' and 'other_row'
                swap_int_ptr(&matrix[col], &matrix[other_row]);
                swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]);
            } else {
                 // Found a suitable row 'other_row' > col
                 // Swap row 'col' and 'other_row'
                swap_int_ptr(&matrix[col], &matrix[other_row]);
                swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]);
            }
        }
        // Now, matrix[col][pivot_col] is guaranteed to be non-zero (mod PH)

        // --- Pivot Normalization ---
        int pivot_val = mod(matrix[col][pivot_col], PH);
        int multiplier = 1; // Default multiplier

        if (pivot_col < graphlen) {
            // Assert equivalent: Check if pivot is 1 or -1 (mod PH)
            // assert(pivot_val == 1 || pivot_val == PH - 1);
            if (pivot_val != 1 && pivot_val != PH - 1) {
                 fprintf(stderr, "Assertion failed: pivot_val (%d) not 1 or %d at row %d, col %d (graphlen part)\n", pivot_val, PH-1, col, pivot_col);
                 // Handle error appropriately, maybe return NULL after cleanup?
                 // For now, proceed using pivot_val as multiplier.
            }
             multiplier = pivot_val; // Multiply row by pivot to make pivot element 1 (since 1*1=1, -1*-1=1 mod PH)

        } else {
            // Assert equivalent: Check if pivot is 2 or -2 (mod PH)
            // assert(pivot_val == 2 || pivot_val == PH - 2);
             if (pivot_val != 2 && pivot_val != PH - 2) {
                 fprintf(stderr, "Assertion failed: pivot_val (%d) not 2 or %d at row %d, col %d (non-graphlen part)\n", pivot_val, PH-2, col, pivot_col);
                 // Handle error appropriately
             }

            // Python code: pivot //= 2; matrix[col] *= pivot
            // If pivot_val = 2, pivot //= 2 gives 1. Row *= 1. Pivot element becomes 2*1 = 2.
            // If pivot_val = 14 (PH-2), pivot //= 2 gives 7. Row *= 7. Pivot element becomes 14*7 = 98 = 2 (mod 16).
            // So, the goal is to make the pivot element 2 (mod PH).
            // We need to find multiplier such that pivot_val * multiplier = 2 (mod PH)
            // This isn't generally possible.
            // Let's follow the Python code's effect: multiply by (pivot_val // 2)
             multiplier = (pivot_val == 2) ? 1 : 7; // Integer division equivalent for 2 and 14
        }

        // Apply multiplier to the pivot row
        for (int c = 0; c < cols; ++c) {
            matrix[col][c] = mod(matrix[col][c] * multiplier, PH);
        }
        // After this step:
        // if pivot_col < graphlen, matrix[col][pivot_col] is 1 (mod PH)
        // if pivot_col >= graphlen, matrix[col][pivot_col] is 2 (mod PH)

        // --- Elimination ---
        for (int i = 0; i < rows; ++i) {
            if (i == col) continue; // Skip pivot row itself

            int factor = mod(matrix[i][pivot_col], PH);
            if (factor == 0) continue; // Already zero in this column

            // Update used_for_row[i] = used_for_row[i] | used_for_row[col]
            for (int k = 0; k < rows; ++k) {
                if (temp_used_for_row[col][k]) {
                    temp_used_for_row[i][k] = true;
                }
            }

            // Perform elimination based on pivot column index
            if (pivot_col < graphlen) {
                // Standard Gaussian elimination: R_i = R_i - factor * R_col
                // Since matrix[col][pivot_col] is 1 (mod PH), we multiply R_col by 'factor'
                for (int c = 0; c < cols; ++c) {
                    matrix[i][c] = mod(matrix[i][c] - factor * matrix[col][c], PH);
                }
            } else {
                // Special elimination: R_i = R_i - R_col (repeatedly)
                // Since matrix[col][pivot_col] is 2 (mod PH)
                // This only works correctly if the underlying field is effectively GF(2)
                // or if all 'factor' values are multiples of 2.
                // Replicating the Python 'while' loop:
                while (mod(matrix[i][pivot_col], PH) != 0) {
                     for (int c = 0; c < cols; ++c) {
                        matrix[i][c] = mod(matrix[i][c] - matrix[col][c], PH);
                    }
                }
            }
             // Ensure row i is reduced mod PH (redundant if mod() used correctly inside, but safe)
             // for (int c = 0; c < cols; ++c) {
             //    matrix[i][c] = mod(matrix[i][c], PH);
             // }
        }

        col++; // Move to the next row/pivot
    } // End while loop

    // --- Construct the final result from temp_used_for_row ---
    int** result = (int**)malloc(rows * sizeof(int*));
    if (!result) {
        perror("Failed to allocate memory for result pointers");
        // Clean up temp_used_for_row
        for (int i = 0; i < rows; ++i) free(temp_used_for_row[i]);
        free(temp_used_for_row);
        return NULL;
    }

    for (int i = 0; i < rows; ++i) {
        int count = 0;
        for (int k = 0; k < rows; ++k) {
            if (temp_used_for_row[i][k]) {
                count++;
            }
        }

        // Allocate space for indices + 1 for the -1 sentinel
        result[i] = (int*)malloc((count + 1) * sizeof(int));
        if (!result[i]) {
            perror("Failed to allocate memory for result inner array");
            // Clean up previously allocated result rows and temp_used_for_row
            for (int j = 0; j < i; ++j) free(result[j]);
            free(result);
            for (int k = 0; k < rows; ++k) free(temp_used_for_row[k]);
            free(temp_used_for_row);
            return NULL;
        }

        // Fill the result array with indices
        int current_idx = 0;
        for (int k = 0; k < rows; ++k) {
            if (temp_used_for_row[i][k]) {
                result[i][current_idx++] = k;
            }
        }
        result[i][current_idx] = -1; // Add sentinel

        // Sort the indices (as Python code returned sorted lists)
        qsort(result[i], count, sizeof(int), compare_ints);

        // Free the temporary boolean array for this row
        free(temp_used_for_row[i]);
    }

    // Free the outer temporary array
    free(temp_used_for_row);

    return result;
}

// --- Example Usage (Optional) ---
void print_matrix(int** matrix, int rows, int cols) {
    printf("Matrix (%dx%d):\n", rows, cols);
    for (int i = 0; i < rows; ++i) {
        printf("  [");
        for (int j = 0; j < cols; ++j) {
            printf("%3d", matrix[i][j]);
        }
        printf(" ]\n");
    }
}

void print_used_for_row(int** used_rows, int rows) {
    printf("Used For Row:\n");
    for (int i = 0; i < rows; ++i) {
        printf("  Row %d: [", i);
        int* current = used_rows[i];
        while (*current != -1) {
            printf("%d", *current);
            current++;
            if (*current != -1) {
                printf(", ");
            }
        }
        printf("]\n");
    }
}

void free_matrix(int** matrix, int rows) {
    if (!matrix) return;
    for (int i = 0; i < rows; ++i) {
        free(matrix[i]);
    }
    free(matrix);
}

void free_used_for_row(int** used_rows, int rows) {
     // Same implementation as free_matrix, just different name for clarity
    if (!used_rows) return;
    for (int i = 0; i < rows; ++i) {
        free(used_rows[i]);
    }
    free(used_rows);
}


int main() {
    // Example matching the logic (adjust values as needed)
    int rows = 4, cols = 5, graphlen = 2;

    // Allocate matrix
    int** matrix = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; ++i) {
        matrix[i] = (int*)malloc(cols * sizeof(int));
    }

    // Initialize matrix (example data)
    // [[1, 0, 1, 2, 5],
    //  [0, 1, 1, 14, 3],
    //  [0, 0, 0, 2, 8],
    //  [1, 1, 0, 0, 9]]
    matrix[0][0] = 1; matrix[0][1] = 0; matrix[0][2] = 1; matrix[0][3] = 2; matrix[0][4] = 5;
    matrix[1][0] = 0; matrix[1][1] = 1; matrix[1][2] = 1; matrix[1][3] = 14; matrix[1][4] = 3;
    matrix[2][0] = 0; matrix[2][1] = 0; matrix[2][2] = 0; matrix[2][3] = 2; matrix[2][4] = 8;
    matrix[3][0] = 1; matrix[3][1] = 1; matrix[3][2] = 0; matrix[3][3] = 0; matrix[3][4] = 9;


    printf("Original Matrix:\n");
    print_matrix(matrix, rows, cols);
    printf("Graphlen: %d, PH: %d\n\n", graphlen, PH);

    int** used_rows = rref(matrix, rows, cols, graphlen);

    if (used_rows) {
        printf("Matrix after RREF (mod %d):\n", PH);
        print_matrix(matrix, rows, cols);
        printf("\n");
        print_used_for_row(used_rows, rows);

        // Free allocated memory
        free_used_for_row(used_rows, rows);
    } else {
        printf("RREF function failed (likely memory allocation error).\n");
    }

    free_matrix(matrix, rows); // Free the matrix itself

    return 0;
}
**Explanation and Key Changes:** 1. **Includes:** Added necessary headers (`stdio.h`, `stdlib.h`, `stdbool.h`, `assert.h`). 2. **`PH` Define:** Defined `PH` as 16. 3. **`mod` Function:** Included a helper function for correct modulo arithmetic, ensuring positive results. 4. **Swap Helpers:** Added `swap_int_ptr` and `swap_bool_ptr` for clarity when swapping rows in the matrix and the tracking arrays. 5. **`used_for_row` Tracking:** * Instead of sets, `bool** temp_used_for_row` is used. `temp_used_for_row[i][k] = true` means original row `k` contributes to current row `i`. * It's initialized so `temp_used_for_row[i][i]` is `true` initially. * The union operation (`|=` in Python) becomes a loop: `if (temp_used_for_row[col][k]) { temp_used_for_row[i][k] = true; }`. 6. **Memory Management:** * `malloc` and `calloc` are used for dynamic allocation. * Error checking is added after allocations. In case of failure during `temp_used_for_row` allocation, partially allocated memory is freed. Similar cleanup is done if allocation for the final `result` fails. * The temporary boolean arrays are freed after their contents are transferred to the final `result`. * The `main` function demonstrates how to free the returned `used_rows` and the original `matrix`. 7. **Algorithm Translation:** * The core `while` loop structure and the logic for finding pivots, swapping rows, normalizing pivots, and performing elimination are translated step-by-step. * The two different normalization/elimination strategies based on `pivot_col < graphlen` are implemented. * The potentially confusing `pivot //= 2` logic is translated based on its *effect* in the Python code (making the pivot element 2 mod 16 in the `else` case). * The `while (mod(matrix[i][pivot_col], PH) != 0)` loop for the second elimination type is directly translated. 8. **Return Value Construction:** * After the RREF process, the code iterates through `temp_used_for_row`. * For each row `i`, it counts how many original rows contributed (`count`). * It allocates an `int` array of size `count + 1` for `result[i]`. * It fills `result[i]` with the indices `k` where `temp_used_for_row[i][k]` was true. * A `-1` sentinel is added at the end of each `result[i]`. * `qsort` is used to sort the indices in each `result[i]` array, matching the Python output format. 9. **Assertions:** The Python `assert` statements are commented out but noted. You can enable C's `assert` by uncommenting or add explicit `if` checks and error handling if needed. 10. **Example Usage:** A `main` function is provided to demonstrate how to allocate a matrix, call `rref`, print the results, and free memory. This C code aims to be a faithful translation of the provided Python logic, including its specific handling of pivots based on `graphlen` and the modulo arithmetic. Remember to compile with a C compiler (like GCC): `gcc your_file_name.c -o your_executable -lm` (though `-lm` isn't strictly needed here as `abs` is in `stdlib.h`).

Extract Code

I extracted the following code from that output: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h> // For assertions (optional, can be removed)

#define PH 16

// Helper function for correct modulo arithmetic (handles negative results)
int mod(int a, int m) {
    return (a % m + m) % m;
}

// Helper function to swap two integer pointers (used for rows)
void swap_int_ptr(int** a, int** b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}

// Helper function to swap two boolean pointers (used for tracking arrays)
void swap_bool_ptr(bool** a, bool** b) {
    bool* temp = *a;
    *a = *b;
    *b = temp;
}

// Comparison function for qsort
int compare_ints(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

/**
 * @brief Computes the Reduced Row Echelon Form (RREF) of a matrix modulo PH
 *        and tracks the original rows contributing to each final row.
 *        The input matrix is modified in place.
 *
 * @param matrix The input matrix (rows x cols). Modified in place.
 * @param rows Number of rows in the matrix.
 * @param cols Number of columns in the matrix.
 * @param graphlen Parameter influencing normalization/elimination strategy.
 * @return int** An array of arrays. result[i] contains the sorted indices
 *               of original rows contributing to final row i, terminated by -1.
 *               Returns NULL on allocation failure. Caller must free the result.
 */
int** rref(int** matrix, int rows, int cols, int graphlen) {
    if (!matrix || rows <= 0 || cols <= 0) {
        return NULL; // Invalid input
    }

    int extra = 0;
    int col = 0; // Represents the current row index we are trying to find a pivot for

    // --- Initialization of used_for_row tracking ---
    // Use boolean arrays for efficient union operations
    bool** temp_used_for_row = (bool**)malloc(rows * sizeof(bool*));
    if (!temp_used_for_row) {
        perror("Failed to allocate memory for temp_used_for_row pointers");
        return NULL;
    }
    for (int i = 0; i < rows; ++i) {
        // calloc initializes memory to zero (false)
        temp_used_for_row[i] = (bool*)calloc(rows, sizeof(bool));
        if (!temp_used_for_row[i]) {
            perror("Failed to allocate memory for temp_used_for_row inner array");
            // Clean up previously allocated rows
            for (int j = 0; j < i; ++j) {
                free(temp_used_for_row[j]);
            }
            free(temp_used_for_row);
            return NULL;
        }
        temp_used_for_row[i][i] = true; // Row i initially depends only on original row i
    }

    // --- Initial Modulo Operation ---
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            matrix[r][c] = mod(matrix[r][c], PH);
        }
    }

    // --- Main RREF Loop ---
    // Loop while we have columns to process and rows to use as pivots
    while (col < rows && col + extra < cols) {
        int pivot_col = col + extra; // Current column being considered for pivot

        // --- Find Pivot Row ---
        if (mod(matrix[col][pivot_col], PH) == 0) {
            int other_row = -1;
            // Find the last row below 'col' with a non-zero entry in pivot_col
            for (int r = rows - 1; r > col; --r) {
                 if (mod(matrix[r][pivot_col], PH) != 0) {
                    other_row = r;
                    break;
                }
            }

            if (other_row == -1) {
                // All entries below (and at) matrix[col][pivot_col] are zero.
                // Check if the entire column is zero (Python used np.all)
                bool all_zero = true;
                 for(int r = 0; r < rows; ++r) { // Check *entire* column
                     if (mod(matrix[r][pivot_col], PH) != 0) {
                         all_zero = false;
                         // Python code found the *last* non-zero row. If it was < col, it skipped.
                         // Let's replicate that specific check.
                         int last_nonzero = -1;
                         for(int r_check = rows - 1; r_check >= 0; --r_check) {
                            if (mod(matrix[r_check][pivot_col], PH) != 0) {
                                last_nonzero = r_check;
                                break;
                            }
                         }
                         if (last_nonzero < col) {
                             all_zero = true; // Treat as if all zero for pivot purposes here
                         } else {
                             // This case implies a non-zero element exists >= col,
                             // but matrix[col][pivot_col] was 0 and the loop above
                             // didn't find one > col. This means the non-zero must be at 'col'.
                             // This state shouldn't be reached if logic is sound, but handle defensively.
                             // The original code would have skipped the column if other < col.
                             // If other_row == -1 here, it means non-zeros only exist <= col.
                             // If matrix[col][pivot_col] is 0, and non-zeros only exist < col, skip.
                             bool non_zero_above = false;
                             for(int r_check = 0; r_check < col; ++r_check) {
                                if (mod(matrix[r_check][pivot_col], PH) != 0) {
                                    non_zero_above = true;
                                    break;
                                }
                             }
                             if (non_zero_above) {
                                 all_zero = true; // Skip column if only non-zeros are above
                             } else {
                                 // This implies matrix[col][pivot_col] must be the only non-zero >= col
                                 // but we are in the block where it's 0. Contradiction?
                                 // Let's trust the initial check and skip if other_row == -1.
                                 all_zero = true;
                             }
                         }
                         break; // Exit the outer check loop
                     }
                 }

                if (all_zero) {
                    extra++; // Skip this column
                    continue; // Go to the next iteration of the while loop
                }
                // If we reach here, it means other_row must have been found > col,
                // but the initial check matrix[col][pivot_col] == 0 failed?
                // Let's re-check the logic flow. The Python code finds the *last* non-zero row `other`.
                // If `other < col`, it skips. If `other >= col` and `matrix[col][pivot_col] == 0`, it swaps `col` and `other`.
                // Let's re-implement the search for `other` more directly.

                other_row = -1; // Reset
                for (int r = rows - 1; r >= 0; --r) { // Find last non-zero in column
                    if (mod(matrix[r][pivot_col], PH) != 0) {
                        other_row = r;
                        break;
                    }
                }

                if (other_row == -1 || other_row < col) { // No suitable pivot found in this column
                    extra++;
                    continue;
                }
                // else: other_row >= col. Since matrix[col][pivot_col] is 0, other_row must be > col.
                 // Swap row 'col' and 'other_row'
                swap_int_ptr(&matrix[col], &matrix[other_row]);
                swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]);
            } else {
                 // Found a suitable row 'other_row' > col
                 // Swap row 'col' and 'other_row'
                swap_int_ptr(&matrix[col], &matrix[other_row]);
                swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]);
            }
        }
        // Now, matrix[col][pivot_col] is guaranteed to be non-zero (mod PH)

        // --- Pivot Normalization ---
        int pivot_val = mod(matrix[col][pivot_col], PH);
        int multiplier = 1; // Default multiplier

        if (pivot_col < graphlen) {
            // Assert equivalent: Check if pivot is 1 or -1 (mod PH)
            // assert(pivot_val == 1 || pivot_val == PH - 1);
            if (pivot_val != 1 && pivot_val != PH - 1) {
                 fprintf(stderr, "Assertion failed: pivot_val (%d) not 1 or %d at row %d, col %d (graphlen part)\n", pivot_val, PH-1, col, pivot_col);
                 // Handle error appropriately, maybe return NULL after cleanup?
                 // For now, proceed using pivot_val as multiplier.
            }
             multiplier = pivot_val; // Multiply row by pivot to make pivot element 1 (since 1*1=1, -1*-1=1 mod PH)

        } else {
            // Assert equivalent: Check if pivot is 2 or -2 (mod PH)
            // assert(pivot_val == 2 || pivot_val == PH - 2);
             if (pivot_val != 2 && pivot_val != PH - 2) {
                 fprintf(stderr, "Assertion failed: pivot_val (%d) not 2 or %d at row %d, col %d (non-graphlen part)\n", pivot_val, PH-2, col, pivot_col);
                 // Handle error appropriately
             }

            // Python code: pivot //= 2; matrix[col] *= pivot
            // If pivot_val = 2, pivot //= 2 gives 1. Row *= 1. Pivot element becomes 2*1 = 2.
            // If pivot_val = 14 (PH-2), pivot //= 2 gives 7. Row *= 7. Pivot element becomes 14*7 = 98 = 2 (mod 16).
            // So, the goal is to make the pivot element 2 (mod PH).
            // We need to find multiplier such that pivot_val * multiplier = 2 (mod PH)
            // This isn't generally possible.
            // Let's follow the Python code's effect: multiply by (pivot_val // 2)
             multiplier = (pivot_val == 2) ? 1 : 7; // Integer division equivalent for 2 and 14
        }

        // Apply multiplier to the pivot row
        for (int c = 0; c < cols; ++c) {
            matrix[col][c] = mod(matrix[col][c] * multiplier, PH);
        }
        // After this step:
        // if pivot_col < graphlen, matrix[col][pivot_col] is 1 (mod PH)
        // if pivot_col >= graphlen, matrix[col][pivot_col] is 2 (mod PH)

        // --- Elimination ---
        for (int i = 0; i < rows; ++i) {
            if (i == col) continue; // Skip pivot row itself

            int factor = mod(matrix[i][pivot_col], PH);
            if (factor == 0) continue; // Already zero in this column

            // Update used_for_row[i] = used_for_row[i] | used_for_row[col]
            for (int k = 0; k < rows; ++k) {
                if (temp_used_for_row[col][k]) {
                    temp_used_for_row[i][k] = true;
                }
            }

            // Perform elimination based on pivot column index
            if (pivot_col < graphlen) {
                // Standard Gaussian elimination: R_i = R_i - factor * R_col
                // Since matrix[col][pivot_col] is 1 (mod PH), we multiply R_col by 'factor'
                for (int c = 0; c < cols; ++c) {
                    matrix[i][c] = mod(matrix[i][c] - factor * matrix[col][c], PH);
                }
            } else {
                // Special elimination: R_i = R_i - R_col (repeatedly)
                // Since matrix[col][pivot_col] is 2 (mod PH)
                // This only works correctly if the underlying field is effectively GF(2)
                // or if all 'factor' values are multiples of 2.
                // Replicating the Python 'while' loop:
                while (mod(matrix[i][pivot_col], PH) != 0) {
                     for (int c = 0; c < cols; ++c) {
                        matrix[i][c] = mod(matrix[i][c] - matrix[col][c], PH);
                    }
                }
            }
             // Ensure row i is reduced mod PH (redundant if mod() used correctly inside, but safe)
             // for (int c = 0; c < cols; ++c) {
             //    matrix[i][c] = mod(matrix[i][c], PH);
             // }
        }

        col++; // Move to the next row/pivot
    } // End while loop

    // --- Construct the final result from temp_used_for_row ---
    int** result = (int**)malloc(rows * sizeof(int*));
    if (!result) {
        perror("Failed to allocate memory for result pointers");
        // Clean up temp_used_for_row
        for (int i = 0; i < rows; ++i) free(temp_used_for_row[i]);
        free(temp_used_for_row);
        return NULL;
    }

    for (int i = 0; i < rows; ++i) {
        int count = 0;
        for (int k = 0; k < rows; ++k) {
            if (temp_used_for_row[i][k]) {
                count++;
            }
        }

        // Allocate space for indices + 1 for the -1 sentinel
        result[i] = (int*)malloc((count + 1) * sizeof(int));
        if (!result[i]) {
            perror("Failed to allocate memory for result inner array");
            // Clean up previously allocated result rows and temp_used_for_row
            for (int j = 0; j < i; ++j) free(result[j]);
            free(result);
            for (int k = 0; k < rows; ++k) free(temp_used_for_row[k]);
            free(temp_used_for_row);
            return NULL;
        }

        // Fill the result array with indices
        int current_idx = 0;
        for (int k = 0; k < rows; ++k) {
            if (temp_used_for_row[i][k]) {
                result[i][current_idx++] = k;
            }
        }
        result[i][current_idx] = -1; // Add sentinel

        // Sort the indices (as Python code returned sorted lists)
        qsort(result[i], count, sizeof(int), compare_ints);

        // Free the temporary boolean array for this row
        free(temp_used_for_row[i]);
    }

    // Free the outer temporary array
    free(temp_used_for_row);

    return result;
}

// --- Example Usage (Optional) ---
void print_matrix(int** matrix, int rows, int cols) {
    printf("Matrix (%dx%d):\n", rows, cols);
    for (int i = 0; i < rows; ++i) {
        printf("  [");
        for (int j = 0; j < cols; ++j) {
            printf("%3d", matrix[i][j]);
        }
        printf(" ]\n");
    }
}

void print_used_for_row(int** used_rows, int rows) {
    printf("Used For Row:\n");
    for (int i = 0; i < rows; ++i) {
        printf("  Row %d: [", i);
        int* current = used_rows[i];
        while (*current != -1) {
            printf("%d", *current);
            current++;
            if (*current != -1) {
                printf(", ");
            }
        }
        printf("]\n");
    }
}

void free_matrix(int** matrix, int rows) {
    if (!matrix) return;
    for (int i = 0; i < rows; ++i) {
        free(matrix[i]);
    }
    free(matrix);
}

void free_used_for_row(int** used_rows, int rows) {
     // Same implementation as free_matrix, just different name for clarity
    if (!used_rows) return;
    for (int i = 0; i < rows; ++i) {
        free(used_rows[i]);
    }
    free(used_rows);
}


int main() {
    // Example matching the logic (adjust values as needed)
    int rows = 4, cols = 5, graphlen = 2;

    // Allocate matrix
    int** matrix = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; ++i) {
        matrix[i] = (int*)malloc(cols * sizeof(int));
    }

    // Initialize matrix (example data)
    // [[1, 0, 1, 2, 5],
    //  [0, 1, 1, 14, 3],
    //  [0, 0, 0, 2, 8],
    //  [1, 1, 0, 0, 9]]
    matrix[0][0] = 1; matrix[0][1] = 0; matrix[0][2] = 1; matrix[0][3] = 2; matrix[0][4] = 5;
    matrix[1][0] = 0; matrix[1][1] = 1; matrix[1][2] = 1; matrix[1][3] = 14; matrix[1][4] = 3;
    matrix[2][0] = 0; matrix[2][1] = 0; matrix[2][2] = 0; matrix[2][3] = 2; matrix[2][4] = 8;
    matrix[3][0] = 1; matrix[3][1] = 1; matrix[3][2] = 0; matrix[3][3] = 0; matrix[3][4] = 9;


    printf("Original Matrix:\n");
    print_matrix(matrix, rows, cols);
    printf("Graphlen: %d, PH: %d\n\n", graphlen, PH);

    int** used_rows = rref(matrix, rows, cols, graphlen);

    if (used_rows) {
        printf("Matrix after RREF (mod %d):\n", PH);
        print_matrix(matrix, rows, cols);
        printf("\n");
        print_used_for_row(used_rows, rows);

        // Free allocated memory
        free_used_for_row(used_rows, rows);
    } else {
        printf("RREF function failed (likely memory allocation error).\n");
    }

    free_matrix(matrix, rows); // Free the matrix itself

    return 0;
}

Run Code Interpreter

Running the following program: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h> // For assertions (optional, can be removed)

#define PH 16

// Helper function for correct modulo arithmetic (handles negative results)
int mod(int a, int m) {
    return (a % m + m) % m;
}

// Helper function to swap two integer pointers (used for rows)
void swap_int_ptr(int** a, int** b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}

// Helper function to swap two boolean pointers (used for tracking arrays)
void swap_bool_ptr(bool** a, bool** b) {
    bool* temp = *a;
    *a = *b;
    *b = temp;
}

// Comparison function for qsort
int compare_ints(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

/**
 * @brief Computes the Reduced Row Echelon Form (RREF) of a matrix modulo PH
 *        and tracks the original rows contributing to each final row.
 *        The input matrix is modified in place.
 *
 * @param matrix The input matrix (rows x cols). Modified in place.
 * @param rows Number of rows in the matrix.
 * @param cols Number of columns in the matrix.
 * @param graphlen Parameter influencing normalization/elimination strategy.
 * @return int** An array of arrays. result[i] contains the sorted indices
 *               of original rows contributing to final row i, terminated by -1.
 *               Returns NULL on allocation failure. Caller must free the result.
 */
int** rref(int** matrix, int rows, int cols, int graphlen) {
    if (!matrix || rows <= 0 || cols <= 0) {
        return NULL; // Invalid input
    }

    int extra = 0;
    int col = 0; // Represents the current row index we are trying to find a pivot for

    // --- Initialization of used_for_row tracking ---
    // Use boolean arrays for efficient union operations
    bool** temp_used_for_row = (bool**)malloc(rows * sizeof(bool*));
    if (!temp_used_for_row) {
        perror("Failed to allocate memory for temp_used_for_row pointers");
        return NULL;
    }
    for (int i = 0; i < rows; ++i) {
        // calloc initializes memory to zero (false)
        temp_used_for_row[i] = (bool*)calloc(rows, sizeof(bool));
        if (!temp_used_for_row[i]) {
            perror("Failed to allocate memory for temp_used_for_row inner array");
            // Clean up previously allocated rows
            for (int j = 0; j < i; ++j) {
                free(temp_used_for_row[j]);
            }
            free(temp_used_for_row);
            return NULL;
        }
        temp_used_for_row[i][i] = true; // Row i initially depends only on original row i
    }

    // --- Initial Modulo Operation ---
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            matrix[r][c] = mod(matrix[r][c], PH);
        }
    }

    // --- Main RREF Loop ---
    // Loop while we have columns to process and rows to use as pivots
    while (col < rows && col + extra < cols) {
        int pivot_col = col + extra; // Current column being considered for pivot

        // --- Find Pivot Row ---
        if (mod(matrix[col][pivot_col], PH) == 0) {
            int other_row = -1;
            // Find the last row below 'col' with a non-zero entry in pivot_col
            for (int r = rows - 1; r > col; --r) {
                 if (mod(matrix[r][pivot_col], PH) != 0) {
                    other_row = r;
                    break;
                }
            }

            if (other_row == -1) {
                // All entries below (and at) matrix[col][pivot_col] are zero.
                // Check if the entire column is zero (Python used np.all)
                bool all_zero = true;
                 for(int r = 0; r < rows; ++r) { // Check *entire* column
                     if (mod(matrix[r][pivot_col], PH) != 0) {
                         all_zero = false;
                         // Python code found the *last* non-zero row. If it was < col, it skipped.
                         // Let's replicate that specific check.
                         int last_nonzero = -1;
                         for(int r_check = rows - 1; r_check >= 0; --r_check) {
                            if (mod(matrix[r_check][pivot_col], PH) != 0) {
                                last_nonzero = r_check;
                                break;
                            }
                         }
                         if (last_nonzero < col) {
                             all_zero = true; // Treat as if all zero for pivot purposes here
                         } else {
                             // This case implies a non-zero element exists >= col,
                             // but matrix[col][pivot_col] was 0 and the loop above
                             // didn't find one > col. This means the non-zero must be at 'col'.
                             // This state shouldn't be reached if logic is sound, but handle defensively.
                             // The original code would have skipped the column if other < col.
                             // If other_row == -1 here, it means non-zeros only exist <= col.
                             // If matrix[col][pivot_col] is 0, and non-zeros only exist < col, skip.
                             bool non_zero_above = false;
                             for(int r_check = 0; r_check < col; ++r_check) {
                                if (mod(matrix[r_check][pivot_col], PH) != 0) {
                                    non_zero_above = true;
                                    break;
                                }
                             }
                             if (non_zero_above) {
                                 all_zero = true; // Skip column if only non-zeros are above
                             } else {
                                 // This implies matrix[col][pivot_col] must be the only non-zero >= col
                                 // but we are in the block where it's 0. Contradiction?
                                 // Let's trust the initial check and skip if other_row == -1.
                                 all_zero = true;
                             }
                         }
                         break; // Exit the outer check loop
                     }
                 }

                if (all_zero) {
                    extra++; // Skip this column
                    continue; // Go to the next iteration of the while loop
                }
                // If we reach here, it means other_row must have been found > col,
                // but the initial check matrix[col][pivot_col] == 0 failed?
                // Let's re-check the logic flow. The Python code finds the *last* non-zero row `other`.
                // If `other < col`, it skips. If `other >= col` and `matrix[col][pivot_col] == 0`, it swaps `col` and `other`.
                // Let's re-implement the search for `other` more directly.

                other_row = -1; // Reset
                for (int r = rows - 1; r >= 0; --r) { // Find last non-zero in column
                    if (mod(matrix[r][pivot_col], PH) != 0) {
                        other_row = r;
                        break;
                    }
                }

                if (other_row == -1 || other_row < col) { // No suitable pivot found in this column
                    extra++;
                    continue;
                }
                // else: other_row >= col. Since matrix[col][pivot_col] is 0, other_row must be > col.
                 // Swap row 'col' and 'other_row'
                swap_int_ptr(&matrix[col], &matrix[other_row]);
                swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]);
            } else {
                 // Found a suitable row 'other_row' > col
                 // Swap row 'col' and 'other_row'
                swap_int_ptr(&matrix[col], &matrix[other_row]);
                swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]);
            }
        }
        // Now, matrix[col][pivot_col] is guaranteed to be non-zero (mod PH)

        // --- Pivot Normalization ---
        int pivot_val = mod(matrix[col][pivot_col], PH);
        int multiplier = 1; // Default multiplier

        if (pivot_col < graphlen) {
            // Assert equivalent: Check if pivot is 1 or -1 (mod PH)
            // assert(pivot_val == 1 || pivot_val == PH - 1);
            if (pivot_val != 1 && pivot_val != PH - 1) {
                 fprintf(stderr, "Assertion failed: pivot_val (%d) not 1 or %d at row %d, col %d (graphlen part)\n", pivot_val, PH-1, col, pivot_col);
                 // Handle error appropriately, maybe return NULL after cleanup?
                 // For now, proceed using pivot_val as multiplier.
            }
             multiplier = pivot_val; // Multiply row by pivot to make pivot element 1 (since 1*1=1, -1*-1=1 mod PH)

        } else {
            // Assert equivalent: Check if pivot is 2 or -2 (mod PH)
            // assert(pivot_val == 2 || pivot_val == PH - 2);
             if (pivot_val != 2 && pivot_val != PH - 2) {
                 fprintf(stderr, "Assertion failed: pivot_val (%d) not 2 or %d at row %d, col %d (non-graphlen part)\n", pivot_val, PH-2, col, pivot_col);
                 // Handle error appropriately
             }

            // Python code: pivot //= 2; matrix[col] *= pivot
            // If pivot_val = 2, pivot //= 2 gives 1. Row *= 1. Pivot element becomes 2*1 = 2.
            // If pivot_val = 14 (PH-2), pivot //= 2 gives 7. Row *= 7. Pivot element becomes 14*7 = 98 = 2 (mod 16).
            // So, the goal is to make the pivot element 2 (mod PH).
            // We need to find multiplier such that pivot_val * multiplier = 2 (mod PH)
            // This isn't generally possible.
            // Let's follow the Python code's effect: multiply by (pivot_val // 2)
             multiplier = (pivot_val == 2) ? 1 : 7; // Integer division equivalent for 2 and 14
        }

        // Apply multiplier to the pivot row
        for (int c = 0; c < cols; ++c) {
            matrix[col][c] = mod(matrix[col][c] * multiplier, PH);
        }
        // After this step:
        // if pivot_col < graphlen, matrix[col][pivot_col] is 1 (mod PH)
        // if pivot_col >= graphlen, matrix[col][pivot_col] is 2 (mod PH)

        // --- Elimination ---
        for (int i = 0; i < rows; ++i) {
            if (i == col) continue; // Skip pivot row itself

            int factor = mod(matrix[i][pivot_col], PH);
            if (factor == 0) continue; // Already zero in this column

            // Update used_for_row[i] = used_for_row[i] | used_for_row[col]
            for (int k = 0; k < rows; ++k) {
                if (temp_used_for_row[col][k]) {
                    temp_used_for_row[i][k] = true;
                }
            }

            // Perform elimination based on pivot column index
            if (pivot_col < graphlen) {
                // Standard Gaussian elimination: R_i = R_i - factor * R_col
                // Since matrix[col][pivot_col] is 1 (mod PH), we multiply R_col by 'factor'
                for (int c = 0; c < cols; ++c) {
                    matrix[i][c] = mod(matrix[i][c] - factor * matrix[col][c], PH);
                }
            } else {
                // Special elimination: R_i = R_i - R_col (repeatedly)
                // Since matrix[col][pivot_col] is 2 (mod PH)
                // This only works correctly if the underlying field is effectively GF(2)
                // or if all 'factor' values are multiples of 2.
                // Replicating the Python 'while' loop:
                while (mod(matrix[i][pivot_col], PH) != 0) {
                     for (int c = 0; c < cols; ++c) {
                        matrix[i][c] = mod(matrix[i][c] - matrix[col][c], PH);
                    }
                }
            }
             // Ensure row i is reduced mod PH (redundant if mod() used correctly inside, but safe)
             // for (int c = 0; c < cols; ++c) {
             //    matrix[i][c] = mod(matrix[i][c], PH);
             // }
        }

        col++; // Move to the next row/pivot
    } // End while loop

    // --- Construct the final result from temp_used_for_row ---
    int** result = (int**)malloc(rows * sizeof(int*));
    if (!result) {
        perror("Failed to allocate memory for result pointers");
        // Clean up temp_used_for_row
        for (int i = 0; i < rows; ++i) free(temp_used_for_row[i]);
        free(temp_used_for_row);
        return NULL;
    }

    for (int i = 0; i < rows; ++i) {
        int count = 0;
        for (int k = 0; k < rows; ++k) {
            if (temp_used_for_row[i][k]) {
                count++;
            }
        }

        // Allocate space for indices + 1 for the -1 sentinel
        result[i] = (int*)malloc((count + 1) * sizeof(int));
        if (!result[i]) {
            perror("Failed to allocate memory for result inner array");
            // Clean up previously allocated result rows and temp_used_for_row
            for (int j = 0; j < i; ++j) free(result[j]);
            free(result);
            for (int k = 0; k < rows; ++k) free(temp_used_for_row[k]);
            free(temp_used_for_row);
            return NULL;
        }

        // Fill the result array with indices
        int current_idx = 0;
        for (int k = 0; k < rows; ++k) {
            if (temp_used_for_row[i][k]) {
                result[i][current_idx++] = k;
            }
        }
        result[i][current_idx] = -1; // Add sentinel

        // Sort the indices (as Python code returned sorted lists)
        qsort(result[i], count, sizeof(int), compare_ints);

        // Free the temporary boolean array for this row
        free(temp_used_for_row[i]);
    }

    // Free the outer temporary array
    free(temp_used_for_row);

    return result;
}

// --- Example Usage (Optional) ---
void print_matrix(int** matrix, int rows, int cols) {
    printf("Matrix (%dx%d):\n", rows, cols);
    for (int i = 0; i < rows; ++i) {
        printf("  [");
        for (int j = 0; j < cols; ++j) {
            printf("%3d", matrix[i][j]);
        }
        printf(" ]\n");
    }
}

void print_used_for_row(int** used_rows, int rows) {
    printf("Used For Row:\n");
    for (int i = 0; i < rows; ++i) {
        printf("  Row %d: [", i);
        int* current = used_rows[i];
        while (*current != -1) {
            printf("%d", *current);
            current++;
            if (*current != -1) {
                printf(", ");
            }
        }
        printf("]\n");
    }
}

void free_matrix(int** matrix, int rows) {
    if (!matrix) return;
    for (int i = 0; i < rows; ++i) {
        free(matrix[i]);
    }
    free(matrix);
}

void free_used_for_row(int** used_rows, int rows) {
     // Same implementation as free_matrix, just different name for clarity
    if (!used_rows) return;
    for (int i = 0; i < rows; ++i) {
        free(used_rows[i]);
    }
    free(used_rows);
}


int __delete_this__main() {
    // Example matching the logic (adjust values as needed)
    int rows = 4, cols = 5, graphlen = 2;

    // Allocate matrix
    int** matrix = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; ++i) {
        matrix[i] = (int*)malloc(cols * sizeof(int));
    }

    // Initialize matrix (example data)
    // [[1, 0, 1, 2, 5],
    //  [0, 1, 1, 14, 3],
    //  [0, 0, 0, 2, 8],
    //  [1, 1, 0, 0, 9]]
    matrix[0][0] = 1; matrix[0][1] = 0; matrix[0][2] = 1; matrix[0][3] = 2; matrix[0][4] = 5;
    matrix[1][0] = 0; matrix[1][1] = 1; matrix[1][2] = 1; matrix[1][3] = 14; matrix[1][4] = 3;
    matrix[2][0] = 0; matrix[2][1] = 0; matrix[2][2] = 0; matrix[2][3] = 2; matrix[2][4] = 8;
    matrix[3][0] = 1; matrix[3][1] = 1; matrix[3][2] = 0; matrix[3][3] = 0; matrix[3][4] = 9;


    printf("Original Matrix:\n");
    print_matrix(matrix, rows, cols);
    printf("Graphlen: %d, PH: %d\n\n", graphlen, PH);

    int** used_rows = rref(matrix, rows, cols, graphlen);

    if (used_rows) {
        printf("Matrix after RREF (mod %d):\n", PH);
        print_matrix(matrix, rows, cols);
        printf("\n");
        print_used_for_row(used_rows, rows);

        // Free allocated memory
        free_used_for_row(used_rows, rows);
    } else {
        printf("RREF function failed (likely memory allocation error).\n");
    }

    free_matrix(matrix, rows); // Free the matrix itself

    return 0;
}



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

int main() {

int arr0[] = {1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
int arr1[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10};
int arr2[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20};
int arr3[] = {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20};
int arr4[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11};
int arr5[] = {0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr6[] = {0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0};
int arr7[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, -30};
int arr8[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr9[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, -20};
int arr10[] = {1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
int arr11[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr12[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11};
int arr13[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -14};
int arr14[] = {0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10};
int arr15[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, -30};
int arr16[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10};
int arr17[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10};
int arr18[] = {0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11};
int arr19[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13};
int arr20[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11};
int arr21[] = {0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10};
int arr22[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, -20};
int arr23[] = {0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10};
int arr24[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11};
int arr25[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13};
int arr26[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr27[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13};
int arr28[] = {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr29[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr30[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr31[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11};
int arr32[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, -10};
int arr33[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13};
int arr34[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11};
int arr35[] = {0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -9};
int arr36[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, -20};
int arr37[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -40};
int arr38[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int* arr[] = {arr0, arr1, arr2, arr3, arr4, arr5, arr6, arr7, arr8, arr9, arr10, arr11, arr12, arr13, arr14, arr15, arr16, arr17, arr18, arr19, arr20, arr21, arr22, arr23, arr24, arr25, arr26, arr27, arr28, arr29, arr30, arr31, arr32, arr33, arr34, arr35, arr36, arr37, arr38};
int** got = rref(arr, 39, 49, 37);


int answer = got[3][0]+got[3][1]+got[3][2]+got[3][3]+got[3][4]+got[3][5]+got[3][6];
int expected = 146;
if (answer != expected) {
    printf("Wrong answer; got %d instead of %d.\n", answer, expected);
    exit(1);
}
printf("All tests passed\n");
}
And got the output: All tests passed

Substring Evaluation

Testing if the previous output contains the string All tests passed: True