From 2d2b30491c4987e84b4b828a7705993aaa1bb5bb Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 12 Dec 2023 19:13:24 +0100 Subject: Added solution for 12 --- 2023/12/12b.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) create mode 100644 2023/12/12b.c (limited to '2023/12/12b.c') diff --git a/2023/12/12b.c b/2023/12/12b.c new file mode 100644 index 0000000..97efd95 --- /dev/null +++ b/2023/12/12b.c @@ -0,0 +1,68 @@ +#include +#include +#include +#include + +#define N 200 +#define T 5 +#define isnum(c) (c == '-' || (c >= '0' && c <= '9')) + +char *buf, line[N]; +int64_t s, m, n, p, a[N], mem[N][N][N]; + +int64_t readl(int64_t nums[], char *buf) { + int64_t i; + for (i = 0; *buf; buf++) { + if (!isnum(*buf)) continue; + nums[i++] = atoll(buf); + while (isnum(*buf)) buf++; + } + return i; +} + +int64_t f(int64_t j, int64_t i, int64_t k) { + if (mem[j][i][k] != -1) + return mem[j][i][k]; + if (i > n || k > a[i]) + return mem[j][i][k] = 0; + + int64_t ret = 0; + if (j == m) + ret = i == n && k == 0; + if (line[j] == '#' || line[j] == '?') + ret += f(j+1, i, k+1); + if ((line[j] == '.' || line[j] == '?') && (k == 0 || k == a[i])) + ret += f(j+1, i+(k>0), 0); + return mem[j][i][k] = ret; +} + +int main() { + while ((buf = fgets(line, N, stdin)) != NULL) { + n = readl(a, buf); + + /* Multiply strings by T (1 for part 1, 5 for part 2) */ + for (m = 0; line[m] != ' '; m++) ; + for (int64_t t = 1; t < T; t++) { + memcpy(a + t * n, a, n * sizeof(int64_t)); + line[t*(m+1)-1] = '?'; + memcpy(line + t * (m + 1), line, (m + 1)); + } + m = T*(m+1); + line[m-1] = '.'; + line[m] = 0; + n *= T; + a[n] = 0; + + /* Reset memoization table */ + for (int64_t j = 0; j <= m; j++) + for (int64_t i = 0; i <= n; i++) + for (int64_t k = 0; k <= m; k++) + mem[j][i][k] = -1; + + /* Compute solution */ + s += f(0, 0, 0); + } + + printf("%" PRId64 "\n", s); + return 0; +} -- cgit v1.3