// Arup Guha
// Solution to CIS 3362 Homework #2 Question #3

#include <stdio.h>

#define SIZE 3
#define ALPHA 26
#define NO_SOL -1

void printSol(int cols[]);
void fillKey(char* fileName, int key[][SIZE]);
void fillIdentity(int id[][SIZE]);
int solve(int key[][SIZE], int col[]);
int isSol(int key[][SIZE], int col[], int tryval);
int power(int base, int exp);

int main() {

    // Read in the matrix to invert.
    int key[SIZE][SIZE];
    fillKey("hill1.txt", key);


    // Stores the identity.
    // Since the transpose is the same, we'll be passing in
    // rows of this matrix to our solve function, instead of
    // columns, even though columns is what we really want to
    // pass in, symbolically.
    int identity[SIZE][SIZE];
    fillIdentity(identity);

    // Get the solution, column by column.
    int i, columns[SIZE], noSol = 0;
    for (i=0; i<SIZE; i++) {
        columns[i] = solve(key, identity[i]);
        if (columns[i] == NO_SOL) {
            noSol = 0;
            break;
        }
    }

    // Print it!
    if (!noSol) {
        printSol(columns);
    }
    else {
        printf("Sorry, there was no solution.\n");
    }

    return 0;
}

// Prints the solution represented by cols, where each item of cols
// stores a full column of information stored in base 26.
void printSol(int cols[]) {

    int i, copy[SIZE];
    for (i=0; i<SIZE; i++)
        copy[i] = cols[i];

    // Unpack information.
    int inv[SIZE][SIZE];
    int row, col;
    for (row = 0; row<SIZE; row++) {
        for (col = SIZE-1; col>=0; col--) {

            // Retrieve the next value of the column and advance.
            inv[col][row] = copy[row]%ALPHA;
            copy[row] /= ALPHA;
        }
    }

    // Here we print.
    for (row=0; row<SIZE; row++) {
        for (col=0; col<SIZE; col++)
            printf("%d\t", inv[row][col]);
        printf("\n");
    }
}

// reads in the key from the file named fileName into
// key. key must be 10 x 10 or smaller.
void fillKey(char* fileName, int key[][SIZE]) {
    int i,j;
    FILE* ifp = fopen(fileName, "r");
    for (i=0; i<SIZE; i++)
        for (j=0; j<SIZE; j++)
            fscanf(ifp, "%d", &key[i][j]);
    fclose(ifp);
}

// Just fills in id to be the identity matrix of SIZE x SIZE.
void fillIdentity(int id[][SIZE]) {

    int i,j;
    for (i=0; i<SIZE; i++) {
        for (j=0; j<SIZE; j++) {
            if (i == j)
                id[i][j] = 1;
            else
                id[i][j] = 0;
        }
    }
}

// Returns the column of values that solve the matrix equation:
// key * x = col. x is packed into a single integer in base 26,
// since each valid solution only has elements from [0, 25].
int solve(int key[][SIZE], int col[]) {

    // Try all solutions and return if you find one.
    int i;
    for (i=0; i<power(ALPHA, SIZE); i++) {

        if (isSol(key, col, i))
            return i;
    }

    // Indicate no solution
    return NO_SOL;
}

// Returns true if tryval is the packed information for the
// column x such taht key * x = col.
int isSol(int key[][SIZE], int col[], int tryval) {

    // Make sure each of SIZE equations is valid.
    int i, j;
    for (i = 0; i<SIZE; i++) {

        // Unpack and calculate this equation.
        int ans = 0, usetry = tryval;
        for (j = SIZE-1; j>=0; j--) {
            ans = (ans + key[i][j]*usetry)%26;
            usetry /= ALPHA;
        }

        // If this isn't a match, this equation is false.
        if (ans != col[i])
            return 0;
    }

    // If we get here, everything checked out!
    return 1;
}

// Regular int power function.
int power(int base, int exp) {

    int ans = 1, i;
    for (i=0; i<exp; i++)
        ans = ans*base;
    return ans;
}