aoc21_15-heap.c

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

#define MAX_WIDTH 100
#define MAX_HEIGHT 100
#define QUEUE_CAP 4096

struct position {
	unsigned risk_level;
	unsigned total_risk;
	int visited;
};

struct queue_item {
	size_t x;
	size_t y;
};

static struct position
	cavern[MAX_HEIGHT * 5][MAX_WIDTH * 5];
static size_t width;
static size_t height;

static void enqueue(size_t, size_t, unsigned);
static const struct queue_item *pop(void);

static void
read_map(void) {
	int c;
	size_t x, y;

	x = 0;
	y = 0;

	while ((c = getchar()) != EOF)
		if (c == '\n') {
			assert(x != 0);
			if (!width)
				width = x;
			else
				assert(x == width);

			y++;
			x = 0;
		}
		else {
			assert(x < MAX_WIDTH);
			assert(y < MAX_HEIGHT);
			cavern[y][x].risk_level = c - '0';
			x++;
		}
	
	assert(x == 0);
	height = y;
}

static void
expand_map(void) {
	size_t x, y;
	int i, j;
	struct position *dest;

	for (y = 0; y < height; y++)
		for (x = 0; x < width; x++)
			for (i = 0; i < 5; i++)
				for (j = 0; j < 5; j++) {
					dest = &cavern[j * height + y][i * width + x];
					dest->risk_level = cavern[y][x].risk_level + i + j;
					if (dest->risk_level > 9)
						dest->risk_level -= 9;
				}

	width *= 5;
	height *= 5;
}

static void
update_neighbor(size_t x2, size_t y2, size_t x1, size_t y1) {
	unsigned sum;

	if (cavern[y2][x2].visited)
		return;

	sum = cavern[y1][x1].total_risk + cavern[y2][x2].risk_level;
	if (sum < cavern[y2][x2].total_risk) {
		cavern[y2][x2].total_risk = sum;
		enqueue(x2, y2, sum);
	}
}

static void
find_lowest_total_risk(void) {
	const struct queue_item *curr;
	size_t x, y;

	for (y = 0; y < height; y++)
		for (x = 0; x < width; x++) {
			cavern[y][x].total_risk = UINT_MAX;
			cavern[y][x].visited = 0;
		}

	cavern[0][0].total_risk = 0;
	enqueue(0, 0, 0);

	while ((curr = pop())) {
		x = curr->x;
		y = curr->y;

		if (x == width - 1 && y == height - 1) {
			printf("%u\n", cavern[y][x].total_risk);
			break;
		}

		if (x > 0)
			update_neighbor(x - 1, y, x, y);

		if (x < width - 1)
			update_neighbor(x + 1, y, x, y);

		if (y > 0)
			update_neighbor(x, y - 1, x, y);

		if (y < height - 1)
			update_neighbor(x, y + 1, x, y);

		cavern[y][x].visited = 1;
	}
}

int
main(void) {
	read_map();
	find_lowest_total_risk();
	expand_map();
	while (pop());
	find_lowest_total_risk();
}

struct heap_node {
	unsigned priority;
	struct queue_item value;
};

static struct heap_node queue[QUEUE_CAP];
static size_t queue_len;

static void sink(void);
static void swim(void);

static void
enqueue(size_t x, size_t y, unsigned priority) {
	assert(queue_len < QUEUE_CAP);
	queue[queue_len].priority = priority;
	queue[queue_len].value.x = x;
	queue[queue_len].value.y = y;
	queue_len++;
	swim();
}

static const struct queue_item *
pop(void) {
	static struct queue_item old;

	if (queue_len == 0)
		return NULL;

	old = queue[0].value;
	queue_len--;
	queue[0] = queue[queue_len];
	sink();

	return &old;
}

static void
swim(void) {
	size_t i, parent;
	struct heap_node temp;

	for (i = queue_len - 1; i > 0; i = parent) {
		parent = (i - 1) / 2;
		if (queue[parent].priority < queue[i].priority)
			break;

		temp = queue[i];
		queue[i] = queue[parent];
		queue[parent] = temp;
	}
}

static void
sink(void) {
	size_t parent, left, right, min;
	struct heap_node temp;

	for (parent = 0; ; parent = min) {
		left = parent * 2 + 1;
		right = parent * 2 + 2;

		min = parent;

		if (left < queue_len &&
				queue[left].priority < queue[min].priority)
			min = left;

		if (right < queue_len &&
				queue[right].priority < queue[min].priority)
			min = right;

		if (min == parent)
			return;

		temp = queue[min];
		queue[min] = queue[parent];
		queue[parent] = temp;
	}
}

aoc21_15.c

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

#define MAX_WIDTH 100
#define MAX_HEIGHT 100
#define COLUMNS 5
#define ROWS 5

struct position {
	unsigned risk_level;
	unsigned total_risk;
	int visited;
};

struct queue_item {
	size_t x, y;
};

static struct position
	cave[MAX_HEIGHT*COLUMNS][MAX_WIDTH*ROWS];
static size_t width;
static size_t height;

static void enqueue(size_t, size_t, unsigned);
static const struct queue_item *dequeue(void);

static void
read_map(void) {
	int c;
	size_t x, y;

	x = 0;
	y = 0;

	while ((c = getchar()) != EOF)
		if (c == '\n') {
			assert(x != 0);
			if (!width)
				width = x;
			else
				assert(x == width);

			y++;
			x = 0;
		}
		else {
			assert(x < MAX_WIDTH);
			assert(y < MAX_HEIGHT);
			cave[y][x].risk_level = c-'0';
			x++;
		}
	
	assert(x == 0);
	height = y;
}

static void
expand_map(void) {
	size_t x, y;
	int i, j;
	struct position *dest;

	for (y = 0; y < height; y++)
	 for (x = 0; x < width; x++)
	  for (i = 0; i < COLUMNS; i++)
	   for (j = 0; j < ROWS; j++) {
		dest = &cave[j*height + y][i*width + x];
		dest->risk_level = cave[y][x].risk_level + i+j;
		if (dest->risk_level > 9)
			dest->risk_level -= 9;
	   }

	width *= COLUMNS;
	height *= ROWS;
}

static void
update_neighbor(size_t x2, size_t y2, size_t x1, size_t y1) {
	unsigned sum;

	if (cave[y2][x2].visited)
		return;

	sum = cave[y1][x1].total_risk + cave[y2][x2].risk_level;
	if (sum < cave[y2][x2].total_risk) {
		cave[y2][x2].total_risk = sum;
		enqueue(x2, y2, sum);
	}
}

static void
find_lowest_total_risk(void) {
	size_t x, y;
	const struct queue_item *cur;

	for (y = 0; y < height; y++)
		for (x = 0; x < width; x++) {
			cave[y][x].total_risk = UINT_MAX;
			cave[y][x].visited = 0;
		}

	cave[0][0].total_risk = 0;
	enqueue(0, 0, 0);

	while ((cur = dequeue())) {
		x = cur->x;
		y = cur->y;

		if (x == width-1 && y == height-1) {
			printf("%u\n", cave[y][x].total_risk);
			break;
		}

		if (x > 0)
			update_neighbor(x-1, y, x, y);

		if (x < width-1)
			update_neighbor(x+1, y, x, y);

		if (y > 0)
			update_neighbor(x, y-1, x, y);

		if (y < height-1)
			update_neighbor(x, y+1, x, y);

		cave[y][x].visited = 1;
	}
}

int
main(void) {
	read_map();
	find_lowest_total_risk();
	expand_map();
	while (dequeue());
	find_lowest_total_risk();
}

struct list_item {
	struct queue_item value;
	struct list_item *more;
};

struct list {
	unsigned priority;
	struct list_item *head;
	struct list *next;
};

static struct {
	struct list *lists;
	struct list_item *items;
} recycler;

static struct list *queue;

static void
insert(struct list_item *item, unsigned priority) {
	struct list **prev, *next;
	struct list *new;

	prev = &queue;
	while ((next = *prev) && priority > next->priority)
		prev = &(*prev)->next;

	if (next && priority == next->priority) {
		item->more = next->head;
		next->head = item;
	}
	else {
		item->more = NULL;

		if (recycler.lists) {
			new = recycler.lists;
			recycler.lists = recycler.lists->next;
		}
		else {
			new = malloc(sizeof *new);
			assert(new != NULL);
		}

		new->priority = priority;
		new->head = item;
		new->next = next;
		*prev = new;
	}
}

static void
enqueue(size_t x, size_t y, unsigned priority) {
	struct list_item *new;

	if (recycler.items) {
		new = recycler.items;
		recycler.items = recycler.items->more;
	}
	else {
		new = malloc(sizeof *new);
		assert(new != NULL);
	}

	new->value.x = x;
	new->value.y = y;
	insert(new, priority);
}

static void
shift(const struct list_item *front) {
	struct list *old;

	if (front->more) {
		queue->head = front->more;
	}
	else {
		old = queue;
		queue = queue->next;
		old->next = recycler.lists;
		recycler.lists = old;
	}
}

static const struct queue_item *
dequeue(void) {
	static struct list_item *old;

	if (old) {
		old->more = recycler.items;
		recycler.items = old;
		old = NULL;
	}

	if (!queue)
		return NULL;

	old = queue->head;
	shift(old);
	return &old->value;
}