elimination tournament

tournament.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>

struct t_team {
	char *name;
	// TODO insert array of players here
};

struct t_node {
	// pointers to the teams
	struct t_team *team_a, *team_b;
	// score of each team, maybe start as `-1`
	int goals_a, goals_b;
	// children nodes, in case of first round, would be NULL
	struct t_node *left, *right;
};
// utility
#define TALLOC (struct t_node*)malloc(sizeof(struct t_node))

#define T_LEVEL 3
#define T_CHOSEN 255

static int chosen = 0;

#define TEAM_COUNT 8
static struct t_team teams[] = {
	{"porto"},
	{"benfica"},
	{"sporting"},
	{"braga"},
	{"famalicao"},
	{"leiria"},
	{"vitoria"},
	{"santa clara"}
};

// round names

static char * rounds[] = {
	"final",
	"semi-final",
	"quarter-final",
	"eight-final"	// not needed i guess
};

struct t_team* pick_team()
{
	/*
		to get random from array, we keep a 8bit number (`chosen`)
		and set the bits until all have been populated

		to test if a bit has already been set (team was already chosen)
		we xor that bit, if the result is less than the variable,
		then we are resetting the bit (to 0), that would mean the team
		was already chosen/picked
	*/
	int choice, bit, test;
	while(1) {
		choice = random() % TEAM_COUNT;
		bit = 1 << choice;
		test = chosen ^ bit;
		if(test > chosen) {
			chosen = test;
			break;
		}
	}

	return teams + choice;	// to return a pointer
}

void populate_tournament(struct t_node *node, int level)
{
	if(level == T_LEVEL) {
		node->team_a = pick_team();
		node->team_b = pick_team();
		return;
	}

	struct t_node *left, *right;

	// left
	left = TALLOC;
	if(left == NULL) {
		fprintf(stderr, "memory blown\n");
		exit(1);
	}
	//left->parent = node;
	left->goals_a = left->goals_b = -1;
	left->team_a = left->team_b = NULL;
	populate_tournament(left, level+1);

	// and right
	right = TALLOC;
	if(right == NULL) {
		fprintf(stderr, "memory blown\n");
		exit(1);
	}
	//right->parent = node;
	right->goals_a = right->goals_b = -1;
	right->team_a = right->team_b = NULL;
	populate_tournament(right, level+1);

	node->left = left;
	node->right = right;
}

/*
	simulate match, return a pointer to the winning team

	recursive
*/
struct t_team * do_tournament(struct t_node *node, int round)
{
	// if this is the first round, these teams will be set
	if(node->team_a == NULL) {
		node->team_a = do_tournament(node->left, round +1);
	}
	if(node->team_b == NULL) {
		node->team_b = do_tournament(node->right, round +1);
	}

	// now for this match

	// they both start at `-1` (equal)
	while(node->goals_a == node->goals_b) {
		node->goals_a = random() % 4;
		node->goals_b = random() % 4;
	}

	// print match info
	// identation
	for(int i=0;i<(T_LEVEL-round);i++) {
		putchar('\t');
	}
	printf(
		"%s %d - %d %s\n",
		node->team_a->name,
		node->goals_a,
		node->goals_b,
		node->team_b->name
	);

	return node->goals_a > node->goals_b ? node->team_a : node->team_b;
}

int main(int argc, char**argv)
{
	// seed random
	srandom(time(NULL));

	// 8 teams, so up to quarter-finals
	// 3 levels on the binary tree
	// get first (final) node
	//printf("alloc final\n");
	struct t_node *final = TALLOC;
	//printf("populating\n");
	populate_tournament(final, 1);
	//printf("running\n");
	struct t_team *winner = do_tournament(final, 0);

	printf("Winner: %s\n", winner->name);

	return 0;
}