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

// Exercice 1

bool bien_parenthese(char* s)
{
  int ouv = 0;
  int i = 0;
  while (ouv >= 0 && s[i] != '\0')
  {
    if (s[i] == '(') ouv += 1;
    else if (s[i] == ')') ouv -= 1;
    i += 1;
  }
  return ouv == 0;
}

int main1()
{
  char bp[] = "(Ceci (est) une) chaine (bien) (par(en(th)ésée))";
  if (bien_parenthese(bp)) printf("La chaine bp est bien parenthésée.\n");
  else printf("La chaine bp est mal parenthésée.\n");

  char mp[] = ")Ceci est une chaine mal parenthésée(";
  if (bien_parenthese(mp)) printf("La chaine mp est bien parenthésée.\n");
  else printf("La chaine mp est mal parenthésée.\n");

  char mp2[] = "(Ceci est une autre chaine mal parenthésée";
  if (bien_parenthese(mp2)) printf("La chaine mp2 est bien parenthésée.\n");
  else printf("La chaine mp2 est mal parenthésée.\n");

  return 0;
}

// Exercice 2 en OCaml

// Exercice 3

// On réutilise la structure de pile bornée, car on dispose d'une borne supérieure sur la taille : la moitié de la taille de la chaîne (si on dépasse, la réponse ne peut pas être vrai).
// Pour autant, on ne veut pas avoir à gérer les cas où on dépasse de la taille de la pile, donc la capacité sera tout de même la taille de la chaîne.

int* creer_pileb(int capacite)
{
  int* p = malloc((capacite+1) * sizeof(int));
  p[0] = 0;
  return p;
}

void empiler_pileb(int* p, int capacite, int x)
{
  assert(p[0] < capacite);
  p[0] += 1;
  p[p[0]] = x;
}

int depiler_pileb(int* p)
{
  assert(p[0] > 0);
  int reponse = p[p[0]];
  p[0] -= 1;
  return reponse;
}

bool est_vide_pileb(int* p)
{
  return p[0] == 0;
}

bool bien_parenthese_code(int s[], int taille)
{
  int* pile = creer_pileb(taille);
  bool toutvabien = true;
  for (int i = 0 ; i < taille && toutvabien ; i += 1)
  {
    if (s[i] > 0) empiler_pileb(pile, taille, s[i]);
    else if (s[i] < 0)
    {
      if (est_vide_pileb(pile)) toutvabien = false;
      else
      {
        int moins_s_i = depiler_pileb(pile);
        if (moins_s_i != -s[i]) toutvabien = false;
      }
    }
  }
  if (!est_vide_pileb(pile)) toutvabien = false;
  free(pile);
  return toutvabien;
}

int main3()
{
  int bp[] = { 5, 7, 5, 0, 0, -5, -7, 0, -5 };
  if (bien_parenthese_code(bp, 9)) printf("Le tableau bp est bien parenthésé.\n");
  else printf("Le tableau bp est mal parenthésé.\n");

  int mp[] = { 1, 2, 3, 4, -1, -2, -3, -4 };
  if (bien_parenthese_code(mp, 8)) printf("Le tableau mp est bien parenthésé.\n");
  else printf("Le tableai mp est mal parenthésé.\n");

  int mp2[] = { 1, 2, -2, -1, 2, 3, -3, 2 };
  if (bien_parenthese_code(mp2, 8)) printf("Le tableau mp2 est bien parenthésé.\n");
  else printf("Le tableau mp2 est mal parenthésé.\n");

  return 0;
}

// Exercice 4 en OCaml

// Exercice 5 en OCaml

// Exercice 6 en OCaml

// Exercice 7

// On reprend la structure de liste chaînée de l'exercice 4 du TP précédent… avec des chaînes au lieu d'entiers au niveau des valeurs
// Certaines opérations élémentaires sont retirées car non utilisées. D'autres sont faites directement sur les tableaux associatifs, tant qu'à faire.
// La taille des chaînes est limitée, comme on peut le voir.

struct m_l_c_c { char cle[32]; char valeur[32]; struct m_l_c_c* suivant; };
typedef struct m_l_c_c mclc;

struct l_c_c { mclc* debut; };
typedef struct l_c_c clc;

clc creer_clc()
{
  clc l = { .debut = NULL };
  return l;
}

void retirer_clc(clc* l, mclc* m)
{
  assert(m != NULL);
  mclc* p = l->debut;
  if (p == m)
  {
    l->debut = m->suivant;
    free(m);
    return;
  }
  while (p != NULL && p->suivant != m)
  {
    p = p->suivant;
  }
  assert(p != NULL);
  p->suivant = m->suivant;
  free(m);
}

void inserer_tete_clc(clc* l, char* cle, char* valeur)
{
  assert(strlen(cle) < 32 && strlen(valeur) < 32);
  mclc* xm = malloc(sizeof(mclc));
  strcpy(xm->cle, cle);
  strcpy(xm->valeur, valeur);
  xm->suivant = l->debut;
  l->debut = xm;
}

struct t_h_c { clc* support; int capacite; };
typedef struct t_h_c cth;

// Exercice 8

int hachage(char* chaine)
{
  long int premier = 999999937;
  long int eval = 0;
  for (int i = 0 ; chaine[i] != '\0' ; i += 1)
  {
    eval = eval * (long int) 256 + (long int) chaine[i];
  }
  return (int) (eval % premier);
}

cth creer_cth(int capacite)
{
  cth res = { .support = malloc(capacite * sizeof(clc)), .capacite = capacite };
  for (int i = 0 ; i < capacite ; i += 1) res.support[i] = creer_clc();
  return res;
}

bool tester_appartenance_cth(cth t, char* cle)
{
  int position = hachage(cle) % t.capacite;
  clc l = t.support[position];
  mclc* m = l.debut;
  while (m != NULL && strcmp(m->cle, cle)) m = m->suivant;
  return m != NULL;
}

char* acceder_cth(cth t, char* cle)
{
  int position = hachage(cle) % t.capacite;
  clc l = t.support[position];
  mclc* m = l.debut;
  while (m != NULL && strcmp(m->cle, cle)) m = m->suivant;
  assert(m != NULL);
  return m->valeur;
}

void modifier_cth(cth t, char* cle, char* nv_valeur)
{
  int position = hachage(cle) % t.capacite;
  clc l = t.support[position];
  mclc* m = l.debut;
  while (m != NULL && strcmp(m->cle, cle)) m = m->suivant;
  assert(m != NULL);
  strcpy(m->valeur, nv_valeur);
}

void inserer_cth(cth t, char* cle, char* valeur)
{
  assert (!tester_appartenance_cth(t, cle));
  int position = hachage(cle) % t.capacite;
  inserer_tete_clc(&t.support[position], cle, valeur);
}

void supprimer_cth(cth t, char* cle) // Pas utilisée dans les exercices suivants…
{
  int position = hachage(cle) % t.capacite;
  clc l = t.support[position];
  mclc* m = l.debut;
  while (m != NULL && strcmp(m->cle, cle)) m = m->suivant;
  assert (m != NULL);
  retirer_clc(&l, m);
}

void free_cth(cth t) // Fonction utile pour ne pas tout écrire à chaque fois
{
  for (int i = 0 ; i < t.capacite ; i += 1)
  {
    clc l = t.support[i];
    while (l.debut != NULL) retirer_clc(&l, l.debut);
  }
  free(t.support);
}

// Exercice 9

char plus_frequent(char* chaine)
{
  cth occurrences = creer_cth(64); // 64 en première approximation
  char reponse = '\0';
  int nboccmax = 0;
  char caractere[2];
  caractere[1] = 0;
  for (int i = 0 ; chaine[i] != '\0'; i += 1)
  {
    caractere[0] = chaine[i];
    if (tester_appartenance_cth(occurrences, caractere))
    {
      int nbocc = atoi(acceder_cth(occurrences, caractere)) + 1;
      if (nbocc > nboccmax)
      {
        nboccmax = nbocc;
        reponse = chaine[i];
      }
      char nbocc_plus_un_str[32];
      sprintf(nbocc_plus_un_str, "%d", nbocc);
      modifier_cth(occurrences, caractere, nbocc_plus_un_str);
    }
    else inserer_cth(occurrences, caractere, "1");
  }
  free_cth(occurrences);
  return reponse;
}

// Exercice 10

bool identiques(int* tab1, int taille1, int* tab2, int taille2) // On pourrait imaginer une seule variable pour la taille et ne pas tester l'égalité
{
  if (taille1 != taille2) return false;
  cth diffoccurrences = creer_cth(64); // Une petite astuce : partager la table de hachage
  int nbdiff = 0;
  for (int i = 0 ; i < taille1 ; i += 1)
  {
    char tab1istr[32];
    sprintf(tab1istr, "%d", tab1[i]);
    if (tester_appartenance_cth(diffoccurrences, tab1istr))
    {
      int nbocc = atoi(acceder_cth(diffoccurrences, tab1istr)) + 1;
      if (nbocc == 0) nbdiff -= 1;
      else if (nbocc == 1) nbdiff += 1;
      char nbocc_plus_un_str[32];
      sprintf(nbocc_plus_un_str, "%d", nbocc);
      modifier_cth(diffoccurrences, tab1istr, nbocc_plus_un_str);
    }
    else
    {
      inserer_cth(diffoccurrences, tab1istr, "1");
      nbdiff += 1;
    }
    char tab2istr[32];
    sprintf(tab2istr, "%d", tab2[i]);
    if (tester_appartenance_cth(diffoccurrences, tab2istr))
    {
      int nbocc = atoi(acceder_cth(diffoccurrences, tab2istr)) - 1;
      if (nbocc == 0) nbdiff -= 1;
      else if (nbocc == -1) nbdiff += 1;
      char nbocc_plus_un_str[32];
      sprintf(nbocc_plus_un_str, "%d", nbocc);
      modifier_cth(diffoccurrences, tab2istr, nbocc_plus_un_str);
    }
    else
    {
      inserer_cth(diffoccurrences, tab2istr, "-1");
      nbdiff += 1;
    }
  }
  free_cth(diffoccurrences);
  return nbdiff == 0;
}

// Exercice 11

char* vers_romain(int n)
{
  assert(0 < n && n < 4000);
  char unites[4][2] = { "I", "X", "C", "M" };
  char cinquaines[3][2] = { "V", "L", "D" };
  char formats[10][5] = { "", "u", "uu", "uuu", "uc", "c", "cu", "cuu", "cuuu", "uU" };
  char* rep = malloc(16);
  for (int i = 0 ; i < 16 ; i += 1) rep[i] = '\0';
  int dixpuissancei = 1000;
  for (int i = 3 ; i > -1 ; i -= 1)
  {
    int r = n / dixpuissancei;
    char* format = formats[r];
    int tailleformat = strlen(format);
    for (int j = 0 ; j < tailleformat ; j += 1)
    {
      if (format[j] == 'u') strcat(rep, unites[i]);
      else if (format[j] == 'c') strcat(rep, cinquaines[i]);
      else if (format[j] == 'U') strcat(rep, unites[i+1]);
      else assert (false);
    }
    n -= r * dixpuissancei;
    dixpuissancei /= 10;
  }
  return rep;
}

int depuis_romain(char* s)
{
  cth valeurs_speciales = creer_cth(16);
  inserer_cth(valeurs_speciales, "CM", "900");
  inserer_cth(valeurs_speciales, "CD", "400");
  inserer_cth(valeurs_speciales, "XC", "90");
  inserer_cth(valeurs_speciales, "XL", "40");
  inserer_cth(valeurs_speciales, "IX", "9");
  inserer_cth(valeurs_speciales, "IV", "4");  
  cth valeurs = creer_cth(16);
  inserer_cth(valeurs, "M", "1000");
  inserer_cth(valeurs, "D", "500");
  inserer_cth(valeurs, "C", "100");
  inserer_cth(valeurs, "L", "50");
  inserer_cth(valeurs, "X", "10");
  inserer_cth(valeurs, "V", "5");
  inserer_cth(valeurs, "I", "1");
  int rep = 0;
  int i = 0;
  int taille = strlen(s);
  while (i < taille)
  {
    bool avancer = false;
    if (i < taille - 1)
    {
      char spec[3];
      spec[0] = s[i];
      spec[1] = s[i+1];
      spec[2] = '\0';
      if (tester_appartenance_cth(valeurs_speciales, spec))
      {
        rep += atoi(acceder_cth(valeurs_speciales, spec));
        i += 2;
        avancer = true;
      }
    }
    if (!avancer)
    {
      char norm[2];
      norm[0] = s[i];
      norm[1] = '\0';
      rep += atoi(acceder_cth(valeurs, norm));
      i += 1;
    }
  }
  char* verif = vers_romain(rep);
  bool test = strcmp(verif, s) == 0;
  free(verif);
  free_cth(valeurs_speciales);
  free_cth(valeurs);
  assert(test);
  return rep;
}

// Exercice 12

char* construit_proteine(char* adn)
{
  cth acides_amines = creer_cth(1024);
  inserer_cth(acides_amines, "UCA", "S"); // Sérine
  inserer_cth(acides_amines, "UCC", "S");
  inserer_cth(acides_amines, "UCG", "S");
  inserer_cth(acides_amines, "UUC", "F"); // Phénylalanine 
  inserer_cth(acides_amines, "UUU", "F");
  inserer_cth(acides_amines, "UUA", "L"); // Leucine 
  inserer_cth(acides_amines, "UUG", "L");
  inserer_cth(acides_amines, "UAC", "Y"); // Tyrosine 
  inserer_cth(acides_amines, "UAU", "Y");
  inserer_cth(acides_amines, "UAA", "STOP"); // Codon Stop 
  inserer_cth(acides_amines, "UAG", "STOP");
  inserer_cth(acides_amines, "UGC", "C"); // Cystéine 
  inserer_cth(acides_amines, "UGU", "C");
  inserer_cth(acides_amines, "UGA", "STOP");
  inserer_cth(acides_amines, "UGG", "W"); // Tryptophane 
  inserer_cth(acides_amines, "CUA", "L");
  inserer_cth(acides_amines, "CUC", "L");
  inserer_cth(acides_amines, "CUG", "L");
  inserer_cth(acides_amines, "CUU", "L");
  inserer_cth(acides_amines, "CCA", "P"); // Proline 
  inserer_cth(acides_amines, "CCC", "P");
  inserer_cth(acides_amines, "CCG", "P");
  inserer_cth(acides_amines, "CCU", "P");
  inserer_cth(acides_amines, "CAC", "H"); // Histidine 
  inserer_cth(acides_amines, "CAU", "H");
  inserer_cth(acides_amines, "CAA", "Q"); // Glutamine 
  inserer_cth(acides_amines, "CAG", "Q");
  inserer_cth(acides_amines, "CGA", "R"); // Arginine 
  inserer_cth(acides_amines, "CGC", "R");
  inserer_cth(acides_amines, "CGG", "R");
  inserer_cth(acides_amines, "CGU", "R");
  inserer_cth(acides_amines, "AUA", "I"); // Isoleucine 
  inserer_cth(acides_amines, "AUC", "I");
  inserer_cth(acides_amines, "AUU", "I");
  inserer_cth(acides_amines, "AUG", "M"); // Méthionine 
  inserer_cth(acides_amines, "ACA", "T"); // Thréonine 
  inserer_cth(acides_amines, "ACC", "T");
  inserer_cth(acides_amines, "ACG", "T");
  inserer_cth(acides_amines, "ACU", "T");
  inserer_cth(acides_amines, "AAC", "N"); // Asparagine 
  inserer_cth(acides_amines, "AAU", "N");
  inserer_cth(acides_amines, "AAA", "K"); // Lysine 
  inserer_cth(acides_amines, "AAG", "K");
  inserer_cth(acides_amines, "AGC", "S");
  inserer_cth(acides_amines, "AGU", "S");
  inserer_cth(acides_amines, "AGA", "R");
  inserer_cth(acides_amines, "AGG", "R");
  inserer_cth(acides_amines, "GUA", "V"); // Valine 
  inserer_cth(acides_amines, "GUC", "V");
  inserer_cth(acides_amines, "GUG", "V");
  inserer_cth(acides_amines, "GUU", "V");
  inserer_cth(acides_amines, "GCA", "A"); // Alanine 
  inserer_cth(acides_amines, "GCC", "A");
  inserer_cth(acides_amines, "GCG", "A");
  inserer_cth(acides_amines, "GCU", "A");
  inserer_cth(acides_amines, "GAC", "D"); // Acide Aspartique 
  inserer_cth(acides_amines, "GAU", "D");
  inserer_cth(acides_amines, "GAA", "E"); // Acide Glutamique 
  inserer_cth(acides_amines, "GAG", "E");
  inserer_cth(acides_amines, "GGA", "G"); // Glycine 
  inserer_cth(acides_amines, "GGC", "G");
  inserer_cth(acides_amines, "GGG", "G");
  inserer_cth(acides_amines, "GGU", "G");
  inserer_cth(acides_amines, "start", "AUG"); // Méthionine, on renverse exceptionnellement l'ordre ici 

  int taille_adn = strlen(adn);
  char* arn = malloc(taille_adn+1);
  for (int i = 0 ; i < taille_adn ; i += 1)
  {
    if (adn[i] == 'A') arn[i] = 'U';
    else if (adn[i] == 'T') arn[i] = 'A';
    else if (adn[i] == 'G') arn[i] = 'C';
    else arn[i] = 'G';
  }
  arn[taille_adn] = '\0';
  char* proteine = malloc(taille_adn / 3 - 1); // maximum possible
  proteine[0] = '\0';
  bool debut = false;
  bool stop = false;
  int i = 0;
  char chaine_start[4];
  char tranche[4];
  tranche[3] = '\0';
  strcpy(chaine_start, acceder_cth(acides_amines, "start"));
  while (i < taille_adn - 2 && !stop)
  {
    for (int j = 0 ; j < 3 ; j += 1) tranche[j] = arn[i+j];
    if (!debut && strcmp(tranche, chaine_start) == 0)
    {
      debut = true;
      i += 3;
    }
    else if (debut)
    {
      char aa[5];
      strcpy(aa, acceder_cth(acides_amines, tranche));
      if (strcmp(aa, "STOP") == 0) stop = true;
      else strcat(proteine, aa);
      i += 3;
    }
    else i += 1;
  }
  free(arn);
  free_cth(acides_amines);
  assert(stop);
  return proteine;
}

int main()
{
  char* s = "GCCTAAGACTACTACCGTTGTGCGTAAACACTCATTCAGTACTACGACTA";
  char* proteine = construit_proteine(s);
  printf("%s\n", proteine);
  free(proteine);
  return 0;
}