From 5d2dbd9a04171f7510b6a35658d243d1cf63e084 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Wed, 15 Dec 2021 09:35:28 +0100
Subject: [PATCH] part one day 15

---
 15a.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)
 create mode 100644 15a.c

diff --git a/15a.c b/15a.c
new file mode 100644
index 0000000..3145541
--- /dev/null
+++ b/15a.c
@@ -0,0 +1,56 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <limits.h>
+#include <string.h>
+
+#define min(a, b) ((a) < (b) ? (a) : (b))
+
+int grid[100][100] = {0};
+int maxx = 0;
+int maxy = 0;
+
+int cache[100][100];
+int minimal_risk(int x, int y)
+{
+	//check bounds
+	if (x < 0 || y < 0 || x >= maxx || y >= maxy)
+		return -1;
+	//check cache
+	if (cache[y][x] != -1)
+		return cache[y][x];
+	//Calculate
+	int d = minimal_risk(x, y+1);
+	int r = minimal_risk(x+1, y);
+	if (d == -1 && r == -1) {
+		printf("shouldn't happen\n");
+		return -1;
+	} else if (d == -1) {
+		cache[y][x] = r + grid[y][x];
+	} else if (r == -1) {
+		cache[y][x] = d + grid[y][x];
+	} else {
+		cache[y][x] = min(d, r) + grid[y][x];
+	}
+	return cache[y][x];
+}
+
+int main()
+{
+	int c, x = 0;;
+	while ( (c = getchar()) != EOF) {
+		if (c == '\n') {
+			maxx = x;
+			x = 0;
+			maxy++;
+		} else {
+			grid[maxy][x++] = c-'0';
+		}
+	}
+	grid[0][0] = 0;
+	for (int y = 0; y<maxy; y++)
+		for (int x = 0; x<maxx; x++)
+			cache[y][x] = -1;
+	cache[maxy-1][maxx-1] = grid[maxy-1][maxx-1];
+
+	printf("%d\n", minimal_risk(0, 0));
+}
-- 
2.20.1