Min Max

cat ../sources/minmax.c

/* [[file:../org/minmax.org::*Includes][Includes:1]] */
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
/* Includes:1 ends here */

/**
 * \file minmax.c
 * \author Arthur Barraux
 * \brief Documentation pour le programme résolvant le problème Minimax Exercise
 * de codingame \version 1.0 \date 23 avril 2024
 */

/* [[file:../org/minmax.org::*Structures][Structures:1]] */

/**
 * \struct Maillon_int
 * \brief Structure maillon pour une liste d'entier
 */

typedef struct Maillon_int {
  int value;                /**< Valeur du Maillon*/
  struct Maillon_int *next; /**< Pointeur vers le prochian Maillon*/
} Maillon_int;

typedef struct {
  Maillon_int *head;
} int_list;
/**
 *\struct node_t
 *\brief Structure noeud d'un arbre*/
typedef struct node {
  int value;              /**< Valeur du noeud*/
  struct node **children; /**< Pointeur vers le premier Maillon de la liste des
                          enfants de ce noeud*/
} node_t;
/* Structures:1 ends here */
/* [[file:../org/minmax.org::*Fonctions][Fonctions:1]] */

/**
 * \fn bool nl_is_empty(Maillon_node *maillon)
 * \brief Teste si une Maillon est vide
 * \param maillon Un élément de type Maillon
 * \return 1 si le Maillon est NULL sinon 0 */
bool have_children(node_t *tree) { return tree->children != NULL; }

void il_append(int_list *liste, int value) {
  Maillon_int *new = malloc(sizeof(Maillon_int));
  new->value = value;
  new->next = liste->head;
  liste->head = new;
}
/**
 * \fn Maillon_int *il_pop(Maillon_int *maillon)
 * \brief Enlève le premier élément de la liste */
void il_pop(int_list *liste) {
  Maillon_int *new_head = liste->head->next;
  free(liste->head);
  liste->head = new_head;
}

/**
 * \fn node_t *create_tree(int depth, int max_depth, int branching_factor)
 * \brief Créer un arbre de prondeur max_depth et de nombre de branche par noeud
 * égal à branching_factor
 * \param depth profondeur de laquelle on commence l'arbre
 * \param max_depth Profondeur max de l'arbre
 * \param branching_factor Nombre de branches par noeuds
 * \return Renvoie la racine de l'arbre */
node_t *create_tree(int depth, int max_depth, int branching_factor,
                    int_list *leafs, node_t *tree) {
  if (depth == max_depth) {
    tree->value = leafs->head->value;
    il_pop(leafs);
    return tree;
  }
  for (int i = 0; i < pow(branching_factor, depth); ++i) {
    // printf("%d\n", i);
    for (int j = 0; j < branching_factor; ++j) {
      node_t *node =
          create_tree(depth + 1, max_depth, branching_factor, leafs, tree);
      tree->children[j] = node;
    }
  }
}

void search_min(int branching_factor, int *leafs, int nb_leafs, int *beta) {
  int i;
  for (i = 0; i < nb_leafs; ++i) {
    if (leafs[i - i % branching_factor] > leafs[i]) {
      *beta = leafs[i];
    }
  }
}

void search_max(int branching_factor, int *leafs, int nb_leafs, int *alpha) {
  int i;
  for (i = 0; i < nb_leafs; ++i) {
    if (leafs[i - i % branching_factor] < leafs[i]) {
      *alpha = leafs[i];
    }
  }
}

int alphabeta(node_t *node, int depth, int alpha, int beta, int is_max) {
  int value;
  int result;
  if (depth == 0) {
    return node->value;
  }
  if (is_max) {
    value = -1000;
    for (int i = 0; i < 4; ++i) {
      node_t *child = node->children[i];
      result = alphabeta(child, depth - 1, alpha, beta, 0);
      if (value < result) {
        value = result;
      }
      if (value > alpha) {
        alpha = value;
      }
      if (value >= beta) {
        break;
      }
    }
    return value;
  } else {
    value = 1000;
    for (int i = 0; i < 4; ++i) {
      node_t *child = node->children[i];
      result = alphabeta(child, depth - 1, alpha, beta, 1);
      if (value < result) {
        value = result;
      }
      if (value < beta) {
        beta = value;
      }
      if (value <= alpha) {
        break;
      }
    }
    return value;
  }
}

void il_show(int_list *liste) {
  for (Maillon_int *m = liste->head; m != NULL; m = m->next) {
    printf("%d -> ", m->value);
  }
  printf("\n");
}

void tree_show(node_t *tree) {
  if (!have_children(tree)) {
    printf("%d ", tree->value);
  }
  for (int i = 0; i < 4; ++i) {
    tree_show(tree->children[i]);
  }
}

/* Fonctions:1 ends here */

/* [[file:../org/minmax.org::*Main][Main:1]] */
/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/

int main() {
  int D;
  int B;
  int i;
  int temp;
  node_t *test = malloc(sizeof(node_t));
  int alpha = -1000, beta = 1000;
  scanf("%d %d", &D, &B);
  int nb_leafs = pow(B, D);
  int_list *leafs = malloc(sizeof(int_list));
  for (i = 0; i < nb_leafs; ++i) {
    scanf("%d", &temp);
    il_append(leafs, temp);
  }
  il_show(leafs);
  node_t *tree = malloc(sizeof(node_t));
  create_tree(0, D, B, leafs, tree);
  // tree_show(tree);
  //  Write an answer using printf(). DON'T FORGET THE TRAILING \n
  //  To debug: fprintf(stderr, "Debug messages...\n");

  int result = alphabeta(tree, D, alpha, beta, D % 2);
  // printf("%d 0\n", result);

  return 0;
}
/* Main:1 ends here */