Untitled

#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;
    bool    hasChild;
};


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;
        tree->nodeList[i/2-1]->hasChild = true;
    }
    return tree;
}


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



bool test_rules(node_t* self) {
    if (!self->marked) {
        if (self->hasChild && self->left->marked && self->right->marked) {
            printf("Marking node %d from rule \n", self->nbr);
            self->marked = true;
            return true;
        }
        if (self->nbr > 1 && 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)) {
        if (node->hasChild){
            eval_game(node->left, tree);
            eval_game(node->right, tree);
        }
        if (node->nbr > 1 && node->parent->left == node) {
            eval_game(node->right, tree);
            eval_game(node->parent, tree);
        }
        else if (node->nbr > 1) {
            eval_game(node->left, tree);
            eval_game(node->parent, tree);
        }
    }
}


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


void printTree(tree_t* tree) {
    for (int i = 0; i < tree->n; ++i) {
        printf("Node %d\n", tree->nodeList[i]->nbr);
    }
}


int main() {
    srand(time(0)); /*Seed setter for rand().*/
    tree_t* tree = new_tree(7);
    printTree(tree);
    mark(4,tree);
    mark(6,tree);
    mark(1,tree);
    mark(5,tree);
    printf("%d\n", is_done(tree));
    /* 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;
}