2021-day9.c

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

static int map[100][100];

struct q
{
	int y, x;
	struct q *next;
};

static int in(struct q **l, int y, int x)
{
	struct q *t;

	for(t = *l; t; t = t->next)
		if(t->x == x && t->y == y)
			return 1;
	return 0;
}

static struct q *new(int y, int x)
{
	struct q *t = malloc(sizeof *t);
	t->y = y;
	t->x = x;
	t->next = NULL;
	return t;
}

static void push(struct q **l, int y, int x)
{
	struct q *t;

	if(in(l, y, x))
		return;

	t = *l;
	*l = new(y, x);
	(*l)->next = t;

	if(y > 0 && map[y-1][x] < 9)
		push(l, y-1, x);
	if(y < 99 && map[y+1][x] < 9)
		push(l, y+1, x);
	if(x > 0 && map[y][x-1] < 9)
		push(l, y, x-1);
	if(x < 99 && map[y][x+1] < 9)
		push(l, y, x+1);
}

static int count(struct q **l)
{
	struct q *t;
	int c = 0;

	for(t = *l; t; t = t->next)
		c++;

	return c;
}

static int basin(int y, int x)
{
	struct q *l = NULL;

	push(&l, y, x);

	return count(&l);
}

static int N(int y, int x)
{
	int m = map[y][x];
	int fail = 0;

	if(y < 99)
		fail += map[y+1][x] <= m;

	if(y > 0)
		fail += map[y-1][x] <= m;

	if(x > 0)
		fail += map[y][x-1] <= m;

	if(x < 99)
		fail += map[y][x+1] <= m;

	return fail;
}

int main(void)
{
	FILE *f;
	char line[128];
	f = fopen("day9.txt", "r");

	for(int y = 0; y < 100; y++)
	{
		if(!fgets(line, 128, f))
			goto out;

		printf("'%s'\n", line);
		for(int x = 0; x < 100; x++)
			map[y][x] = line[x] - '0';
	}
	unsigned int sum = 0;
	int h[3] = {0,0,0};
	out:

	for(int y = 0; y < 100; y++)
	{
		for(int x = 0; x < 100; x++)
		{
			if(!N(y, x))
			{
				int n;
				printf("Basin at %d, %d\n", y, x);
				sum += map[y][x] + 1;
				n = basin(y, x);
				if(n > h[2])
				{
					h[0] = h[1];
					h[1] = h[2];
					h[2] = n;
				} else if(n > h[1])
				{
					h[0] = h[1];
					h[1] = n;
				} else if(n > h[0])
				{
					h[0] = n;
				}
			}
		}
	}
	printf("Sum: %u\n", sum);
	printf("best 3: %d %d %d\n", h[0], h[1], h[2]);
	return 0;
}