Untitled
unknown
plain_text
2 years ago
4.8 kB
4
Indexable
#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; }
Editor is loading...