daytrie.c

#include <stdio.h>
#include <stdlib.h>

struct trie
{
	struct trie *left, *right;
	int left_count, right_count;
};

static void trie_print_node(struct trie *t)
{
	while(t)
	{
		printf("[%p] -> left (%d): [%p] , right (%d) [%p]\n", t, t->left_count, t->left, t->right_count, t->right);
		if(t->left)
		{
			printf("Left: ");
			t = t->left;
			trie_print_node(t->left);
		}
		if(t->right)
		{
			printf("Right: ");
			trie_print_node(t->right);
		}
	}
}

static struct trie *trie_new(void)
{
	struct trie *t;

	t = malloc(sizeof *t);
	t->left = NULL;
	t->right = NULL;
	t->left_count = 0;
	t->right_count = 0;

	return t;
}

static void trie_push(struct trie **t, const char *val)
{
	while(*val == '0' || *val == '1')
	{
		if(val[0] == '0')
		{
			(*t)->left_count++;
			t = &(*t)->left;
			if(!*t)
				*t = trie_new();
		}
		if(val[0] == '1')
		{
			(*t)->right_count++;
			t = &(*t)->right;
			if(!*t)
				*t = trie_new();
		}
		val++;
	}
	return;
}

static unsigned int co2(struct trie *t)
{
	unsigned int sum = 0;

	while(t)
	{
		if(t->left_count && t->left_count <= t->right_count)
		{
			t = t->left;
			if(!t)
				goto outsum;
			sum <<= 1;
			sum |= 0;
		}
		else
		{
			t = t->right;
			if(!t)
				goto outsum;
			sum <<= 1;
			sum |= 1;
		}
	}

outsum:
	return sum;
}

static unsigned int oxy(struct trie *t)
{
	unsigned int sum = 0;

	while(t)
	{
		if(t->right_count >= t->left_count)
		{
			t = t->right;
			if(!t)
				goto outsum;
			sum <<= 1;
			sum |= 1;
		}
		else
		{
			t = t->left;
			if(!t)
				goto outsum;
			sum <<= 1;
			sum |= 0;
		}
	}

outsum:
	return sum;
}

int main(void)
{
	FILE *f;
	char line[128];
	struct trie *t = trie_new();
	unsigned int co2_sum = 0, oxy_sum = 0;

	f = fopen("day3.txt", "r");

	while(1)
	{
		unsigned int n;

		if(!fgets(line, 128, f))
			goto out;

		trie_push(&t, line);
	}

out:
	co2_sum = co2(t);
	oxy_sum = oxy(t);

	printf("%u * %u = %u\n", co2_sum, oxy_sum, co2_sum * oxy_sum);
	return 0;
}