#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <stddef.h>


// Exercice 1

int aux(int* dims, int dep, int sep, int fin)
{
  return dims[dep] * dims[sep+1] * dims[fin+1];
}

int min_mult(int* dims, int nb_mat)
{
  int** tab = malloc(nb_mat * sizeof(int*)); // création d'un tableau à deux dimensions
  for (int i = 0 ; i < nb_mat ; i++)
  {
    tab[i] = malloc(nb_mat * sizeof(int)); // création d'une ligne du tableau à deux dimensions
    tab[i][i] = 0; // la diagonale initialisée à 0
  }
  for (int bande = 1 ; bande < nb_mat ; bande += 1)
  {
    for (int l = 0 ; l < nb_mat - bande ; l += 1)
    {
      // ligne et colonne de travail
      int l_t = l;
      int c_t = l + bande;
      for (int c = 1 ; c <= bande ; c += 1)
      {
        //ligne et colonne gauche 
        int l_g = l_t;
        int c_g = l_t + c - 1;
        //ligne et colonne bas
        int l_b = l_t + c;
        int c_b = c_t;
        int calcul = tab[l_g][c_g] + tab[l_b][c_b] + aux(dims, l_g, c_g, c_b);
        if (c == 1 || calcul < tab[l_t][c_t]) tab[l_t][c_t] = calcul; // modification systématique à c == 1 (premier tour de boucle) pour éviter un UB
      }          
    }
  }
  int rep = tab[0][nb_mat-1];
  // libération de la mémoire
  for (int i = 0; i < nb_mat; i += 1) free(tab[i]);
  free(tab);
  return rep;
}

int main1()
{
  int dims[] = { 4 , 6 , 2 , 10 , 3 };
  printf("Avec les matrices de l'exemple, le nombre optimal de multiplications est %d.\n", min_mult(dims, 4));
  return 0;
}

// Exercice 2

int rendu_monnaie_optimal(int *pieces, int nombre_pieces, int monnaie)
{
  // Le nombre de pièces optimales pour rendre une valeur entre 0 et monnaie
  /*
      Exemple avec pieces = [1,4,5] et monnaie = 5
      0 1 2 3 4 5 6 7 8
      0 1 2 3 1 1 2 3 2
  */
  int* tab = malloc((monnaie+1) * sizeof(int));
  tab[0] = 0;
  for (int i = 1 ; i <= monnaie ; i += 1)
  {
    tab[i] = -1;
    for (int j = 0 ; j < nombre_pieces ; j+= 1)
    {
      if (pieces[j] <= i && (tab[i] == -1 || tab[i-pieces[j]] < tab[i]-1) && tab[i-pieces[j]] != -1)
      {
        tab[i] = tab[i-pieces[j]] + 1;
      }
    }
  }
  int rep = tab[monnaie];
  free(tab);
  return rep;
}

int main2()
{
  int pieces[] = { 1, 4, 5 };
  printf("%d\n", rendu_monnaie_optimal(pieces, 3, 8));
  return 0;
}

// Exercice 3

// On considère taches comme un tableau de nb_taches tableaux de taille 3, avec début, fin et valeur
// ON SUPPOSE LE TABLEAU TRIÉ PAR FIN CROISSANTE ET PAR VALEUR DÉCROISSANTE À FIN IDENTIQUE
int weighted_interval_scheduling(int** taches, int nb_taches)
{
  int* rep_n = malloc(nb_taches * sizeof(int));
  for (int i = 0 ; i < nb_taches ; i += 1) rep_n[i] = 0;
  rep_n[0] = taches[0][2];
  for (int i = 1 ; i < nb_taches ; i += 1)
  {
    int j = i;
    while (j > -1 && taches[j][1] > taches[i][0]) j -= 1;
    int valeur = taches[i][2];
    if (j > -1) valeur += rep_n[j];
    if (valeur > rep_n[i-1]) rep_n[i] = valeur;
    else rep_n[i] = rep_n[i-1];
  }
  int rep = rep_n[nb_taches-1];
  free(rep_n);
  return rep;
}

int main3()
{
  int tache_1[] = { 0, 3, 1 }; // Échec du glouton par fin croissante : celle-ci est sélectionnée, total 19
  int tache_2[] = { 2, 6, 10 };
  int tache_3[] = { 5, 8, 18 }; // Échec du glouton par valeur décroissante ou par rapport valeur / durée décroissant : celle-ci est sélectionnée, total 19
  int tache_4[] = { 7, 10, 10 };
  int** taches = malloc(4 * sizeof(int*));
  taches[0] = tache_1;
  taches[1] = tache_2;
  taches[2] = tache_3;
  taches[3] = tache_4;
  printf("Valeur optimale pour les tâches renseignées : %d.\n", weighted_interval_scheduling(taches, 4));
  free(taches);
  return 0;
}

// Exercice 4

// Seul le calcul est fait en C. Par ailleurs, toutes les opérations ont un coût de 1 dans cette fonction, le cas général étant là aussi seulement fait en OCaml.

int distance_edition(char* chaine1, char* chaine2)
{
  int n1 = strlen(chaine1);
  int n2 = strlen(chaine2);
  int** distances = malloc((n1+1) * sizeof(int*)); // Initialisation et calcul dans la foulée pour cette matrice !
  distances[0] = malloc((n2+1) * sizeof(int));
  for (int j = 0 ; j <= n2 ; j += 1) distances[0][j] = j;
  for (int i = 1 ; i <= n1 ; i += 1)
  {
    distances[i] = malloc((n2+1) * sizeof(int));
    distances[i][0] = i;
    for (int j = 1 ; j <= n2 ; j += 1)
    {
      distances[i][j] = distances[i-1][j] + 1;
      if (distances[i][j-1] + 1 < distances[i][j]) distances[i][j] = distances[i][j-1] + 1;
      int modif = 1;
      if (chaine1[i-1] == chaine2[j-1]) modif = 0;
      if (distances[i-1][j-1] + modif < distances[i][j]) distances[i][j] = distances[i-1][j-1] + modif;
    }
  }
  int reponse = distances[n1][n2];
  for (int i = 0 ; i <= n1 ; i += 1) free(distances[i]);
  free(distances);
  return reponse;
}

int main4()
{
  char* chaine1 = "DISTANCE";
  char* chaine2 = "LEVENSHTEIN";
  printf("Distance d'édition entre %s et %s : %d.\n", chaine1, chaine2, distance_edition(chaine1, chaine2));
  return 0;
}

// Exercice 5

// Objets : tableau de n tableaux de taille 2 avec le poids puis la valeur. Aucun tri n'est supposé.

int sac_a_dos(int** objets, int nb_objets, int seuil)
{
  int** mat = malloc(nb_objets * sizeof(int*));
  mat[0] = malloc((seuil+1) * sizeof(int));
  for (int j = 0 ; j <= seuil ; j += 1)
  {
    if (j < objets[0][0]) mat[0][j] = 0;
    else mat[0][j] = objets[0][1];
  }
  for (int i = 1 ; i < nb_objets ; i += 1)
  {
    mat[i] = malloc((seuil+1) * sizeof(int));
    for (int j = 0 ; j <= seuil ; j += 1)
    {
      if (j >= objets[i][0])
      {
        int essai = mat[i-1][j-objets[i][0]] + objets[i][1];
        if (essai > mat[i-1][j]) mat[i][j] = essai;
        else mat[i][j] = mat[i-1][j];
      }
      else mat[i][j] = mat[i-1][j];
    }
  }
  int reponse = mat[nb_objets-1][seuil];
  for (int i = 0 ; i < nb_objets ; i += 1) free(mat[i]);
  free(mat);
  return reponse;
}

int main5()
{
  int objetsbis[10][2] = { { 95, 55 } , { 4 , 10 } , { 60 , 47 } , { 32 , 5 } , { 23 , 4 } , { 72 , 50 } , { 80 , 8 } , { 62 , 61 } , { 65 , 85 } , { 46 , 87 } };  int** objets = malloc(10 * sizeof(int*));
  for (int i = 0 ; i < 10 ; i += 1)
  {
    objets[i] = malloc(2 * sizeof(int));
    objets[i][0] = objetsbis[i][0];
    objets[i][1] = objetsbis[i][1];
  }
  int seuil = 269;
  printf("Avec l'instance de test (merci internet), la réponse devrait être 295. On trouve %d.\n", sac_a_dos(objets, 10, seuil));
  for (int i = 0 ; i < 10 ; i += 1) free(objets[i]);
  free(objets);
  return 0;
}

// Exercice 6 en OCaml

// Fonction main

int main()
{
  int zero = main1();
  exit(zero);
}