2022-day7.c

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

struct dir
{
	char *name;
	struct dir *parent;
	struct dir *child[1021];
	int childs;
	unsigned long size;
};

static struct dir root = {
	.name = "/",
	.parent = NULL
};

static struct dir *cwd = &root;

static struct dir *newdir(const char *name)
{
	struct dir *d;

//	printf("New dir named '%s'\n", name);
	d = malloc(sizeof *d);
	d->name = strdup(name);
	d->parent = NULL;
	d->child[0] = NULL;
	d->childs = 0;
	d->size = 0;

	return d;
}

static struct dir *finddir(const char *name)
{
	int i;

	for(i = 0; i < cwd->childs; i++)
		if(strcmp(name, cwd->child[i]->name) == 0)
			return cwd->child[i];

	return NULL;
}

static unsigned long p1sum;
static unsigned long totalsize;
static unsigned long lowscore;

static unsigned long dump(struct dir *d)
{
	int i;
	unsigned long size = d->size;

	for(i = 0; i < d->childs; i++)
		size += dump(d->child[i]);

	/* Part 1 */
	if(size <= 100000)
		p1sum += size;

	/* Part 2 */
	if(totalsize)
	{
		unsigned long target = 30000000UL-(70000000UL-totalsize);

		if(lowscore && size >= target && size < lowscore)
			lowscore = size;

		if(!lowscore && size >= target)
			lowscore = size;
	}

	return size;
}

static void cd(const char *name)
{
	struct dir *t;

	if(name[0] == '.')
	{
		cwd = cwd->parent;
		return;
	}

	t = finddir(name);
	if(t)
	{
		cwd = t;
		return;
	}

	t = newdir(name);
	t->parent = cwd;
	cwd->child[cwd->childs++] = t;
	cwd = t;
}

int main(void)
{
	FILE *f;
	char line[4096];

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

	while(1)
	{
		if(!fgets(line, 4096, f))
			break;

		line[strlen(line)-1] = 0;

		if(line[0] == '$')
		{
			if(line[2] == 'c')
			{
				cd(&line[5]);
			}
			continue;
		}
/*
		else if(line[0] == 'd')
		{
			struct dir *t;

			t = newdir(name);
			t->parent = cwd;
			cwd->child[cwd->childs++] = t;
			continue;
		}
	}
*/
		else if(line[0] >= '0' && line[0] <= '9')
		{
			cwd->size += strtol(line, NULL, 10);
		}
	}

	totalsize = dump(&root);
	printf("p1: %lu\n", p1sum);

	dump(&root);
	printf("p2: %lu\n", lowscore);
	return 0;
}