Untitled

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

typedef struct node_t node_t;
typedef struct tree_t tree_t;

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


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


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


tree_t* new_tree(int n) {
    tree_t* tree = calloc(1, sizeof(tree_t));
    tree->nodeList = calloc(n, sizeof(node_t*));
    tree->n = n;
    tree->root = new_node(1, NULL);
    tree->nodeList[0] = tree->root; 
    for(int i = 2; i < n + 1; i += 2) {
        node_t* left = new_node(i, tree->nodeList[i/2-1]);
        node_t* right = new_node(i+1, tree->nodeList[i/2-1]);
        tree->nodeList[i-1]= left;
        tree->nodeList[i/2-1]->left = left;
        tree->nodeList[i] = right;
        tree->nodeList[i/2-1]->right = right;
    }
    return tree;
}


int randint(int n) {
    return rand() % (n) + 1;

}



bool test_rules(node_t* self) {
    if (!self->marked) {
        if (self->left && self->left->marked && self->right->marked) {
            printf("Marking node %d from rule \n", self->nbr);
            self->marked = true;
            return true;
        }
        if (self->parent && self->parent->marked && (self->parent->left->marked || self->parent->right->marked)){
            printf("Marking node %d from rule \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) {
    int a = 1;
    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 roundTwo(tree_t* tree){
    int counter;
    int markOrder[tree->n];

    for (int i = 0; i < tree->n; ++i) {
        markOrder[i] = i+1;
    }
    for (int i = tree->n-1; i > 0; --i) {
        int r = randint(i);
        int temp = markOrder[i];
        markOrder[i] = markOrder[r];
        markOrder[r] = temp;
    }
    counter = 0;
    while (!is_done(tree)) {
        counter ++;
        mark(markOrder[counter], tree);
    }
    return counter;
}


int main() {
    srand(time(0)); /*Seed setter for rand().*/
    tree_t* tree = new_tree(7);
    int result = roundOne(tree);
    printf("RESULT ROUND 1: %d\n", result);
    tree = new_tree(7);
    result = roundTwo(tree);
    printf("RESULT ROUND 2: %d\n", result);
    return 0;
}