Skip to content

Instantly share code, notes, and snippets.

@zid

zid/daytrie.c Secret

Last active Dec 5, 2021
Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment