/* License: AGPLv3 or later. https://www.gnu.org/licenses/licenses.html
 * 
* Exercise 10 - Matrix Multiplication (Week 11)
* Name : Manish
* Student Login : *****
*
* Compile as:
* $ gcc -Wall -std=c11 -o ex10 ex10.c
*/

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


int* array = NULL;
int* memo = NULL;
int matrices = 0;

int best(int i, int j);
int min(int i, int j);

int main(void)
{
    printf("Enter file name: ");
    // Assuming filename/file path will not be longer than 256 characters
    char filename[257];
    scanf("%s", filename);
    
    FILE* file = fopen(filename, "r");
    if (!file)
    {
        perror(filename);
        exit(EXIT_FAILURE);
    }

    if (fscanf(file, " %d ", &matrices) != EOF)
    {;
        array = malloc(sizeof(int) * (matrices + 1));
        memo = malloc(sizeof(int) * matrices);
        if (matrices > 0 && (array == NULL || memo == NULL))
        {
            fprintf(stderr, " Failed to allocate memory \n");
            return 1;
        }
    }

    // Read and push matrix dimensions to array
    fscanf(file, " %d %d ", &array[0], &array[1]); // first matrix dimensions
    int row ;
    int col;
    for (int i = 1; i < matrices; i++)
    {
        fscanf(file, " %d %d ", &row, &col);
        // row of current matrix must match column of previous matrix
        if (row == array[i])
            array[i] = row;
        else
        {
            fprintf(
                stderr,
                " Rows , columns mismatch , multiplication not possible \n"
            );
            exit(1);
        }
        array[i + 1] = col;
    }
    fclose(file);
    // Initialize memorization array elements to 0 s
    for ( int i =0; i < matrices * matrices ; i ++)
        memo[i] = 0;
    
    // Compute and print minimum multiplications needed
    printf ( "%d\n", best(1, matrices));

    free ( array ) ;

    return 0;
}

int best(int i, int j)
{
    if (i == j)
        return 0;
    if (memo[matrices * i + j] != 0)
        return memo[matrices * i + j];
    int b = INT_MAX;
    for (int k = i; k < j; k++)
        b = min(b, (array[i-1] * array[j] * array[k]) + best(i,  k) + best(k+1, j));
    memo[matrices * i + j] = b;
    return b;
}

int min(int i, int j)
{
    return i < j ? i : j;
}