// Arup Guha
// 12/5/2023
// Solution to Q1 of COP 3502 Section 1 Part B Exam

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

void freesq(int** sq, int n);
void print(int** sq, int n);
int** diagcount(int n) ;
int** diagcount_alt(int n);
int** diagcount_alt2(int n);
int** diagcount_alt3(int n);

// Quick test.
int main() {
    int** mysq = diagcount(5);
    print(mysq,5);
    freesq(mysq,5);
    return 0;
}

// Frees the array pointed to by sq assuming it's n by n.
void freesq(int** sq, int n) {
    for (int i=0; i<n; i++)
        free(sq[i]);
    free(sq);
}

// Prints the array pointed to by sq assuming it's n by n.
void print(int** sq, int n) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
            printf("%d ", sq[i][j]);
        printf("\n");
    }
}

// Solution #1
int** diagcount(int n) {

    // Allocate space.
    int** sq = calloc(n, sizeof(int*));
    for (int i=0; i<n; i++)
        sq[i] = calloc(n, sizeof(int));

    // 0 based diagonal I am on, overall.
    for (int d=0; d<2*n-1; d++) {

        // Starting row.
        int start = d < n ? 0 : d-n+1;

        // Number to draw.
        int draw = d < n ? d+1 : 2*n-1-d;

        // This draws a diagonal from top right to bottom left of the same number.
        for (int i=start; d-i>=0 && i<n; i++)
            sq[i][d-i] = draw;
    }

    return sq;
}

// Solution #2
int** diagcount_alt(int n) {

    // Allocate space.
    int** sq = calloc(n, sizeof(int*));
    for (int i=0; i<n; i++)
        sq[i] = calloc(n, sizeof(int));

    // formula for top left diagonals.
    for (int d=0; d<n; d++)
        for (int i=0; i<=d; i++)
            sq[i][d-i] = d+1;

    // formula for bottom right diagonals.
    for (int d=n; d<2*n-1; d++)
        for (int i=d-n+1; i<n; i++)
            sq[i][d-i] = 2*n-1-d;

    return sq;
}

// Solution #3
int** diagcount_alt2(int n) {

    // Allocate space.
    int** sq = calloc(n, sizeof(int*));
    for (int i=0; i<n; i++)
        sq[i] = calloc(n, sizeof(int));

    // Here we put the formula in a ternary operator for both sides (top left, bottom right).
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            sq[i][j] = (i+j+1) <= n ? i+j+1 : 2*n-1-i-j;

    return sq;
}

// Solution #4
int** diagcount_alt3(int n) {

    // Allocate space.
    int** sq = calloc(n, sizeof(int*));
    for (int i=0; i<n; i++)
        sq[i] = calloc(n, sizeof(int));

    // Here we recognize the symmetry about the main diagonal...
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            sq[i][j] = abs(n - abs(n-i-j-1));

    return sq;
}