advent of code 2023 day 12 in C with dynamic programming

day12.c

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

#define ENSURE(p) ({__typeof(p) _p = p; assert(_p); _p; })

typedef struct {
	size_t dot;
	size_t hash;
} Evaluation;

size_t handle_dot(Evaluation *restrict mat, size_t i, size_t j, size_t rows, size_t cols, char const *restrict seq, size_t const *restrict num) {
	return mat[(i-1) * cols + j].hash + mat[(i-1) * cols + j].dot;
}

size_t handle_hash(Evaluation *restrict mat, size_t i, size_t j, size_t rows, size_t cols, char const *restrict seq, size_t const *restrict num) {
	size_t current_seq_index = i - 1;
	size_t current_num_index = j - 1;

	if (num[current_num_index] > i) {
		return 0; // sequence too short due to string limits
	}

	size_t range_start_index = current_seq_index - num[current_num_index] + 1;

	for (size_t k = range_start_index; k <= current_seq_index; ++k) {
		if (seq[k] == '.') { 
			return 0; // sequence too short due to interleaved '.'
		}
	}

	return mat[(i - num[current_num_index]) * cols + j - 1].dot;
}

Evaluation handle_jolly(Evaluation *restrict mat, size_t i, size_t j, size_t rows, size_t cols, char const *restrict seq, size_t const *restrict num) {
	size_t hash = handle_hash(mat, i, j, rows, cols, seq, num);
	size_t dot  = handle_dot(mat, i, j, rows, cols, seq, num);
	return (Evaluation){ .hash = hash, .dot = dot};
}

size_t count(char const * restrict seq, size_t const * restrict num, size_t num_count) {
	size_t seq_count = strlen(seq);

	size_t cols = num_count + 1;
	size_t rows = seq_count + 1;

	Evaluation *mat = ENSURE(calloc(rows * cols, sizeof(Evaluation)));
	size_t first_hash_pos = ENSURE(strchrnul(seq, '#')) - seq;

	// prefixes of the sequence without any hashes
	for (size_t i = 0; i < first_hash_pos + 1; ++i) { mat[i * cols + 0].dot = 1; }

	for (size_t i = 1; i < rows; ++i) {
		for (size_t j = 1; j < cols; ++j) {
			switch (seq[i - 1]) {
				case '.': mat[i * cols + j].dot  = handle_dot(mat, i, j, rows, cols, seq, num); break;
				case '#': mat[i * cols + j].hash = handle_hash(mat, i, j, rows, cols, seq, num); break;
				case '?': mat[i * cols + j]      = handle_jolly(mat, i, j, rows, cols, seq, num); break;
				default : assert(false && "unreachable");
			}
		}
	}
	
	size_t result = mat[rows * cols - 1].hash + mat[rows * cols - 1].dot;
	free(mat);
	return result;
}

int main () {
	char   seq_buf[1024];
	size_t num_buf[128];

	FILE * in = fopen("input.txt", "r");
	size_t part_1 = 0;
	size_t part_2 = 0;
	while (fscanf(in, "%s", seq_buf) == 1) {
		size_t num_count = 0;
		do {
			fscanf(in, "%zu", &num_buf[num_count++]);
		} while(fgetc(in) == ',');

		part_1 += count(seq_buf, num_buf, num_count);

		size_t len = strlen(seq_buf) + 1;
		seq_buf[len - 1] = '?';
		for (size_t i = 0; i < len; ++i) {
			seq_buf[1 * len + i] = seq_buf[i];
			seq_buf[2 * len + i] = seq_buf[i];
			seq_buf[3 * len + i] = seq_buf[i];
			seq_buf[4 * len + i] = seq_buf[i];
		}
		seq_buf[5 * len - 1] = '\0';

		for (size_t i = 0; i < num_count; ++i) {
			num_buf[1 * num_count + i] = num_buf[i];
			num_buf[2 * num_count + i] = num_buf[i];
			num_buf[3 * num_count + i] = num_buf[i];
			num_buf[4 * num_count + i] = num_buf[i];
		}

		part_2 += count(seq_buf, num_buf, num_count * 5);
	}
	printf("%zu\n", part_1);
	printf("%zu\n", part_2);
}