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;
    int         marks;
};


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->marks = 0;
    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, tree_t* tree) {
    if (!self->marked) {
        if (self->hasChild && self->left->marked && self->right->marked) {
            //printf("Marking node %d from rule \n", self->nbr);
            self->marked = true;
            tree->marks++;
            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;
            tree->marks++;
            return true;
        }
        else
            return false;
    }
}


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


void mark(int nbr, tree_t* tree) {
    node_t* node = tree->nodeList[nbr-1];
    if (!node->marked) {
        node->marked = true;
        tree->marks++;
        if (node->hasChild){
            eval_game(node->left, tree);
            eval_game(node->right, tree);
        }
        if (node->nbr > 1 && node->parent->left == node) {
            eval_game(node->parent->right, tree);
            eval_game(node->parent, tree);
        }
        else if (node->nbr > 1) {
            eval_game(node->parent->left, tree);
            eval_game(node->parent, tree);
        }
    }
    
}


int round_one(tree_t* tree){
    int counter = 0;
    while (tree->marks < tree->n) {
        counter++;
        mark(randint(tree->n), tree);
    }
    return counter;
}


int round_two(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 (tree->marks < tree->n) {
        counter ++;
        mark(markOrder[counter], tree);
    }
    return counter;
}


int round_three(tree_t* tree){
    int counter = 0;
    while (tree->marks < tree->n){
        int nodeNbrs[tree->n];
        int temp = 0;
        for (int i = 0; i < tree->n; ++i) {
            if (!tree->nodeList[i]->marked) {
                nodeNbrs[temp] = tree->nodeList[i]->nbr;
                temp++;
            }
        }
        int r = randint(temp-1);
        counter++;
        mark(nodeNbrs[r], tree);
    }
    return counter;
}


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


void free_node(node_t* node) {
    free(node);
}


void free_tree(tree_t* tree) {
    for (int i = 0; i < tree->n; i++) {
        free_node(tree->nodeList[i]);
    }
    free(tree->nodeList);
    free(tree);
}


int main() {
    srand(time(0)); /*Seed setter for rand().*/
    int size = 1;
    FILE *fp = fopen("outfile", "w");
    for (int i = 0; i < size; ++i) {
        tree_t* tree = new_tree(1 << 20 - 1); /*Syntactic anti-sugar*/
        int result = round_one(tree);
        fprintf(fp, "%d, ", result);
        free(tree);
    }
    return 0;
}