Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
1
Indexable
Never
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct node_t node_t;
typedef struct tree_t tree_t;

typedef struct node_t {
    node_t* parent;
    node_t* left;
    node_t* right;
    int     nbr;
    bool    marked;
} node_t;


void new_node(int nbr, node_t* parent) {
    node_t* node = calloc(1, sizeof(node_t));
    node->nbr = nbr;
    node->parent = parent;
}


typedef struct tree_t {
    node_t**    nodeList;
    node_t*     root;
    int         n;
} tree_t;


void new_tree(int n, node_t* root) {
    tree_t* tree = calloc(1, sizeof(tree_t));
    tree->nodeList = calloc(1, sizeof(node_t*));
    tree->n = n;
    tree->root = root;
}



int randint(int n) {
  if ((n - 1) == RAND_MAX) {
    return rand() + 1;
  } 
  else {
    assert (n <= RAND_MAX)

    int end = RAND_MAX / n;
    assert (end > 0);
    end *= n;
    int r;
    while ((r = rand()) >= end);
    return r % n + 1;
  }
}



bool test_rules(node_t* self) {
    if (!self->marked) {
        if (self->left && self->left->marked && self->right->marked) {
            printf("Marking from rule node %d\n", self->nbr);
            self->marked = true;
            return true;
        }
        if (self->parent && self->parent->marked && (self->parent->left->marked || self->parent->right->marked)){
            printf("Marking from rule node %d\n", self->nbr);
            self->marked = true;
            return true;
        }
        else
            return false;
    }
}


void eval_game(node_t* node, tree_t* tree) {
    if (!node || node->marked)
        return;
    else if (test_rules(node)) {
        eval_game(node->left, tree);
        eval_game(node->right, tree);
        eval_game(node->parent, tree);
        if (node->parent && node->parent->left == node)
            eval_game(node->right, tree);
        else if (node->parent)
            eval_game(node->left, tree);
    }
}


void mark(int nbr, tree_t* tree) {
    node_t* node = tree->nodeList[nbr-1];
    node->marked = true;
    printf("Marking node %d\n", nbr);
    eval_game(node->left, tree);
    eval_game(node->right, tree);
    eval_game(node->parent, tree);
    if (node->parent && node->parent->left == node)
        eval_game(node->right, tree);
    else if (node->parent)
        eval_game(node->left, tree);
}


bool is_done(tree_t* tree) {
    for (int i = 0; i < tree->n; ++i) {
        if (!tree->nodeList[i]->marked)
            return false;
    }
    return true;
}


int roundOne(tree_t* tree):
    int counter = 0;
    while (!is_done(tree)) {
        counter++;
        mark(randint(tree->n), tree)
    }
    return counter;
    

int main() {

    return 0;
}