aoc

My solutions for the Advent of Code
git clone https://git.tronto.net/aoc
Download | Log | Files | Refs | README

12b.c (1466B)


      1 #include <inttypes.h>
      2 #include <stdio.h>
      3 #include <stdlib.h>
      4 #include <string.h>
      5 
      6 #define N 200
      7 #define T 5
      8 #define isnum(c) (c == '-' || (c >= '0' && c <= '9'))
      9 
     10 char *buf, line[N];
     11 int64_t s, m, n, p, a[N], mem[N][N][N];
     12 
     13 int64_t readl(int64_t nums[], char *buf) {
     14 	int64_t i;
     15 	for (i = 0; *buf; buf++) {
     16 		if (!isnum(*buf)) continue;
     17 		nums[i++] = atoll(buf);
     18 		while (isnum(*buf)) buf++;
     19 	}
     20 	return i;
     21 }
     22 
     23 int64_t f(int64_t j, int64_t i, int64_t k) {
     24 	if (mem[j][i][k] != -1)
     25 		return mem[j][i][k];
     26 	if (i > n || k > a[i])
     27 		return mem[j][i][k] = 0;
     28 
     29 	int64_t ret = 0;
     30 	if (j == m)
     31 		ret = i == n && k == 0;
     32 	if (line[j] == '#' || line[j] == '?')
     33 		ret += f(j+1, i, k+1);
     34 	if ((line[j] == '.' || line[j] == '?') && (k == 0 || k == a[i]))
     35 		ret += f(j+1, i+(k>0), 0);
     36 	return mem[j][i][k] = ret;
     37 }
     38 
     39 int main() {
     40 	while ((buf = fgets(line, N, stdin)) != NULL) {
     41 		n = readl(a, buf);
     42 
     43 		/* Multiply strings by T (1 for part 1, 5 for part 2) */
     44 		for (m = 0; line[m] != ' '; m++) ;
     45 		for (int64_t t = 1; t < T; t++) {
     46 			memcpy(a + t * n, a, n * sizeof(int64_t));
     47 			line[t*(m+1)-1] = '?';
     48 			memcpy(line + t * (m + 1), line, (m + 1));
     49 		}
     50 		m = T*(m+1);
     51 		line[m-1] = '.';
     52 		line[m] = 0;
     53 		n *= T;
     54 		a[n] = 0;
     55 
     56 		/* Reset memoization table */
     57 		for (int64_t j = 0; j <= m; j++)
     58 			for (int64_t i = 0; i <= n; i++)
     59 				for (int64_t k = 0; k <= m; k++)
     60 					mem[j][i][k] = -1;
     61 
     62 		/* Compute solution */
     63 		s += f(0, 0, 0);
     64 	}
     65 
     66 	printf("%" PRId64 "\n", s);
     67 	return 0;
     68 }