day12

4 files changed, 438 insertions, 0 deletions

diff --git a/2022/day12.c b/2022/day12.c
new file mode 100644
index 0000000..14b92c8
--- /dev/null
+++ b/2022/day12.c
@@ -0,0 +1,175 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include "util.h"
+
+s32 reduce(s32 (*f)(s32 x, s32 y), s32 arr[], s32 len)
+{
+	s32 ret = arr[0];
+
+	for (s32 i = 1; i < len; ++i) {
+		ret = f(ret, arr[i]);
+	}
+
+	return ret;
+}
+
+s32 mul(s32 x, s32 y)
+{
+	return x * y;
+}
+
+s32 max(s32 x, s32 y)
+{
+	return x > y ? x : y;
+}
+
+s32 count_char_in_string(char c, char *s)
+{
+	s32 count = 0;
+	do
+		if (c == *s)
+			count++;
+	while (*s++);
+	return count;
+}
+
+char *goto_char_in_string(char c, char *s)
+{
+	do
+		if (c == *s)
+			return s;
+	while (*s++);
+	return NULL;
+}
+
+#define PP(arr, y,x) (*(*(arr+y)+x))
+
+char filename[] = "in/day12.ref";
+// char filename[] = "in/day12.pzl";
+
+#define BUF_LEN 10000
+char file_buf[BUF_LEN];
+
+s32 **grid;
+s32 **visited;
+s32 y_len;
+s32 x_len;
+s32 start_y;
+s32 start_x;
+s32 end_y;
+s32 end_x;
+
+s32 traverse(s32 steps,s32 y, s32 x)
+{
+	if (PP(visited,y,x) < steps) {
+		return 42000;
+	}
+	PP(visited,y,x) = steps;
+	// if (PP(visited,y,x) == 1) {
+	// 	return 12345;
+	// }
+	// PP(visited,y,x) = 1;
+
+	if ((x==end_x) && (y==end_y)) {
+		return steps;
+	}
+
+	s32 min = 123456;
+
+	if ( (x+1 < x_len) && (PP(grid,y,x+1) <= (PP(grid,y,x)+1)) ) {
+		s32 a = traverse(steps+1, y, x+1);
+		if (a < min) {
+			min = a;
+		}
+	}
+	if ( (x > 0) && (PP(grid,y,x-1) <= (PP(grid,y,x)+1)) ) {
+		s32 a = traverse(steps+1, y, x-1);
+		if (a < min) {
+			min = a;
+		}
+	}
+	if ( (y+1 < y_len) && (PP(grid,y+1,x) <= (PP(grid,y,x)+1)) ) {
+		s32 a = traverse(steps+1, y+1, x);
+		if (a < min) {
+			min = a;
+		}
+	}
+	if ( (y > 0) && (PP(grid,y-1,x) <= (PP(grid,y,x)+1)) ) {
+		s32 a = traverse(steps+1, y-1, x);
+		if (a < min) {
+			min = a;
+		}
+	}
+
+	return min;
+}
+
+
+int main()
+{
+	int fd = open(filename, O_RDONLY);
+	s32 data_len = read(fd, file_buf, LEN(file_buf));
+
+	if (data_len == -1) {
+		printf("error opening file\n");
+		exit(1);
+	} else if (data_len == LEN(file_buf)) {
+		printf("buffer probably not big enough\n");
+		exit(1);
+	}
+	file_buf[data_len] = '\0';
+
+	y_len = count_char_in_string('\n', file_buf);
+
+
+	grid = malloc(y_len * sizeof(s32*));
+	visited = malloc(y_len * sizeof(s32*));
+	char *start  = file_buf;
+
+	for (s32 y = 0; y < y_len; ++y) {
+		char *end = goto_char_in_string('\n', start);
+		x_len = end - start;
+
+		*(grid+y) = malloc(x_len * sizeof(s32*));
+		*(visited+y) = malloc(x_len * sizeof(s32*));
+
+		for (s32 x = 0; x < x_len; ++x) {
+			char c = *(start + x);
+			if (c == 'S') {
+				start_y = y;
+				start_x = x;
+				c = 'a';
+			} else if (c == 'E') {
+				end_y = y;
+				end_x = x;
+				c = 'z';
+			}
+			*(*(grid+y) + x) = c - 'a';
+			*(*(visited+y) + x) = 123456;
+			// *(*(visited+y) + x) = 0;
+		}
+		start = end+1;
+	}
+	printf("y_len: %d\n", y_len);
+	printf("x_len: %d\n", x_len);
+
+	printf("start y: %d\n", start_y);
+	printf("start x: %d\n", start_x);
+	printf("end y: %d\n", end_y);
+	printf("end x: %d\n", end_x);
+
+
+
+	s32 res1 = 0;
+	s32 res2 = 0;
+
+	res1 = traverse(0, start_y, start_x);
+
+
+	printf("res1: %d\n", res1);
+	printf("res2: %d\n", res2);
+	// asm("int3");
+}
+
diff --git a/2022/day12.py b/2022/day12.py
new file mode 100755
index 0000000..b066a01
--- /dev/null
+++ b/2022/day12.py
@@ -0,0 +1,217 @@
+#!/usr/bin/env python3
+
+# import numpy as np
+from functools import reduce
+from re import findall
+from copy import deepcopy
+import sys
+import time
+
+# filename = "in/day12.ref"
+filename = "in/day12.pzl"
+data = open(filename).read()
+lines = [line for line in data.rstrip('\n').split('\n')]
+# print(lines)
+
+res1 = 0
+res2 = 0
+
+grid = list()
+
+start_x = 0
+start_y = 0
+end_x = 0
+end_y = 0
+for y,line in enumerate(lines):
+    l = list()
+    for x,char in enumerate(line.strip()):
+        if char == 'S':
+            start_x = x
+            start_y = y
+            l.append(0)
+        elif char == 'E':
+            end_x = x
+            end_y = y
+            l.append(25)
+        else:
+            l.append(ord(char) - ord('a'))
+    grid.append(l)
+
+# print('grid', grid)
+# print('end', end_y, end_x)
+
+def print_visited(visited, steps):
+    print('\x1b[2J')
+    for y,l in enumerate(visited):
+        for x,_ in enumerate(l):
+            if visited[y][x] > steps:
+                print('.', end='')
+            else:
+                print('#', end='')
+        print()
+    time.sleep(0.1)
+
+
+# def traverse(grid, visited, steps, y, x):
+#     # if visited[y][x] < steps:
+#     # if visited[y][x] < 12345:
+#         # print('syx', steps, y,x)
+#         # print(steps, visited[y][x])
+#         # return 420000, visited
+#         # visited[y][x] = steps
+
+#     # if steps % 100 == 0:
+#         # print(steps)
+#     print_visited(visited, steps)
+
+#     if x==end_x and y==end_y:
+#         print('steps', steps)
+#         return steps, visited
+
+#     lowest = list()
+#     lowest.append(42000)
+#     if x+1 < len(grid[0]) and grid[y][x+1] <= grid[y][x]+1:
+#         low, visited = traverse(grid, visited, steps+1, y, x+1)
+#         lowest.append(low)
+
+#     if y+1 < len(grid) and grid[y+1][x] <= grid[y][x]+1:
+#         low, visited = traverse(grid, visited, steps+1, y+1, x)
+#         lowest.append(low)
+
+#     if y > 0 and grid[y-1][x] <= grid[y][x]+1:
+#         low, visited = traverse(grid, visited, steps+1, y-1, x)
+#         lowest.append(low)
+
+#     if x > 0 and grid[y][x-1] <= grid[y][x]+1:
+#         low, visited  = traverse(grid, visited, steps+1, y, x-1)
+#         lowest.append(low)
+
+#     return min(lowest), visited
+
+
+# def traverse_same(s, y, x):
+#     for t in tiles:
+#         if (y,x) in t:
+#             # print('already in tiles', y,x)
+#             return s
+#     if (y,x) in s:
+#         # print('already in set', y,x)
+#         return s
+
+#     s.add((y,x))
+#     # if steps % 100 == 0:
+#         # print(steps)
+#         # print_visited(visited, steps)
+
+#     if x+1 < len(grid[0]) and grid[y][x+1] == grid[y][x]:
+#         s.union(traverse_same(s, y, x+1))
+
+#     if x > 0 and grid[y][x-1] == grid[y][x]:
+#         s.union(traverse_same(s, y, x-1))
+
+#     if y+1 < len(grid) and grid[y+1][x] == grid[y][x]:
+#         s.union(traverse_same(s, y+1, x))
+
+#     if y > 0 and grid[y-1][x] == grid[y][x]:
+#         s.union(traverse_same(s, y-1, x))
+
+#     # print(y, x, s)
+#     return s
+
+# sys.setrecursionlimit(10000)
+# visited = [[9999999 for i in l] for l in grid]
+# print(visited)
+# res1, visited = traverse(grid, visited, 0, start_y, start_x)
+
+# tiles = list()
+# tiles_vals = list()
+# yx_to_tile = [[None for i in l] for l in grid]
+
+# for j,l in enumerate(grid):
+#     for i,_ in enumerate(l):
+#         s = traverse_same(set(), j, i)
+#         if len(s) > 0:
+#             for (y,x) in s:
+#                 yx_to_tile[y][x] = len(tiles)
+#             tiles.append(s)
+#             tiles_vals.append(grid[y][x])
+#         # print(y, x, s)
+# for line in grid:
+#     print(line)
+# print(tiles)
+# print(tiles_vals)
+# for line in yx_to_tile:
+#     print(line)
+
+
+def bfs(grid, start_y, start_x, end_y, end_x):
+    visited = set()
+    visited.add((start_y,start_x))
+
+    steps = 0
+    while True:
+        new_visited = set()
+        # print(visited)
+        for (y,x) in visited:
+            if x == end_x and y == end_y:
+                # print('steps', steps, y, x)
+                return steps
+
+            if x+1 < len(grid[0]) and grid[y][x+1] <= grid[y][x]+1:
+                new_visited.add((y, x+1))
+
+            if x > 0 and grid[y][x-1] <= grid[y][x]+1:
+                new_visited.add((y, x-1))
+
+            if y+1 < len(grid) and grid[y+1][x] <= grid[y][x]+1:
+                new_visited.add((y+1, x))
+
+            if y > 0 and grid[y-1][x] <= grid[y][x]+1:
+                new_visited.add((y-1, x))
+
+        visited = visited.union(new_visited)
+        steps += 1
+
+res1 = bfs(grid, start_y, start_x, end_y, end_x)
+
+def bfs2(grid, start_y, start_x, end):
+    visited = set()
+    visited.add((start_y,start_x))
+
+    steps = 0
+    while True:
+        new_visited = set()
+        # print(visited)
+        for (y,x) in visited:
+            if (y,x) in end:
+                # print('steps', steps, y, x)
+                return steps
+
+            if x+1 < len(grid[0]) and grid[y][x+1]+1 >= grid[y][x]:
+                new_visited.add((y, x+1))
+
+            if x > 0 and grid[y][x-1]+1 >= grid[y][x]:
+                new_visited.add((y, x-1))
+
+            if y+1 < len(grid) and grid[y+1][x]+1 >= grid[y][x]:
+                new_visited.add((y+1, x))
+
+            if y > 0 and grid[y-1][x]+1 >= grid[y][x]:
+                new_visited.add((y-1, x))
+
+        visited = visited.union(new_visited)
+        steps += 1
+
+elea = set()
+for y,l in enumerate(grid):
+    for x,_ in enumerate(l):
+        if grid[y][x] == 0:
+            elea.add((y,x))
+# print(elea)
+
+res2 = bfs2(grid, end_y, end_x, elea)
+
+
+print('res1:', res1)
+print('res2:', res2)
+
diff --git a/2022/in/day12.pzl b/2022/in/day12.pzl
new file mode 100644
index 0000000..bee626b
--- /dev/null
+++ b/2022/in/day12.pzl
@@ -0,0 +1,41 @@
+abccccccccaaaaccccaaacaccccaaaaaacccccccccccaaaccccccccccaaaaaaacccccccccccccccccccccccccccccacaaaccccccccccccccccccccccccccccccccccccccccaaaaa
+abccccccccaaaaccaaaaaaaacccaaaaaacccccccccccaaaacccccccccaaaaaaaaaacccccccccccccccaaccccccccaaaaaccaaaccaacccccccccccccccccccccccccccccccaaaaaa
+abcccccccccaacccaaaaaaaaccccaaaaacccccccccccaaaacccccccaaaaaaaaaaaaaccccccccccaaaaaaccccccccaaaaaaaaaaaaaaccccccccccccccccaaaccccccccccccaaaaaa
+abcccccccccccccccaaaaaccccccaacaaccccaacccccaaacccccccaaaaaaaaaaaaaaccccccccccaaaaaaacccccccccaaaaacaaaaaaccccccccccccccccaaccccccccccccccccaaa
+abccccccccccccccccaaaaaccccccccccaaccaacccccccccccccccaaaaacaaaacacacccccaacccaaaaaaaacccccccaaaaacaaaaaaaccccccccccccccccaaacccccccccccccccaaa
+abcccccccccccccccaaaaaaccccccccccaaaaaaccccccccccccccccaaaaaaaacaaaaacaaaaaccccaaaaaaacccccccaacaacaaaaaaaaccccccccaaaaccaakcccccccccccccccccaa
+abcccccccccccccccaaaccacccccccccccaaaaaaacccccccaaaccccccaaaaaacaaaaaccaaaaaccaaaaaaccccccccccccaacaaaaaaaacccccccccaaaakkkklllcccccccccccccccc
+abcccccaaaccccccccccccccccccccccccaaaaaaacccccccaaacacccaaaaaaaaaaaaacaaaaaaccaaaaaacccccccccccccccccaaaccccccccccccaaakkkkkllllcccccccaacccccc
+abccccaaaacccccccccccccccccccccccaaaaaacccccccaccaaaaaccaaaaaaaaaaaaacaaaaccccccccaaccccccccccccccccccaaccccccccccccckkkkkkpllllccccaaaaaaccccc
+abccccaaaacccccccccccccccccaaacccaaaaaacccccccaaaaaaaacccaaaaacaaaaaacccaaaccccccccccccccccccccccccccccccccccccccccckkkkpppppplllcccaaaaacccccc
+abcccccaaaccccccccccccccccaaaacccccccaaccccccccaaaaacccccaaaccccaaacccccccccccccccccccccccccaaccccccccccccccccccjjjkkkkpppppppplllcccaaaaaacccc
+abccccccccccccccccccccccccaaaaccccccccccccccccccaaaaacccccccccccccccccccccccccccccccccccccccaaaaaccccccccccccjjjjjjkkkrppppuppplllccccaaaaacccc
+abccccccccccccccaaaccccccccaaaccccccccccccccccccaacaaccccccccccccccccccccccaaaccccccccaacccaaaaaccccccccccccjjjjjjjjrrrpuuuuuppplllcccccaaacccc
+abcccccaaccaacccaaacacccccccccccccccccccccccccacaaaaccccccccccccccccccccccaaaaaaccccaaaacccaaaaaaccaccccccccjjjrrrrrrrrruuuuuppplllmcccddcccccc
+abcccccaaaaaacaaaaaaaaccccccccccccccccccccccccaacaaaccccccccccccccccccccccaaaaaaccccaaaaaacccaaaaccaaacaaacjjjrrrrrrrrruuuxuuupqqlmmmmddddccccc
+abcccccaaaaaccaaaaaaaaccccccccccccccccccccccccaaaaaccccaacccccccccccccccccaaaaaacccccaaaacccaacccccaaaaaaacjjjrrrrtuuuuuuxxyuvqqqqmmmmmddddcccc
+abaacccaaaaaaccaaaaaccccccccccccccccccaaaaccccaaaaaaccaaaccccccccccccccccccaaaaaccccaaaaaccccccccccaaaaaaccjjjrrrtttuuuuuxxyvvvqqqqqmmmmdddcccc
+abaaccaaaaaaaaccaaaaaccccccccccccccccaaaaaaaaaaaaaaaacaaacaaaccccccccccccccaacaacaacaacaaccccccccaaaaaaaaccijjqqrtttxxxxxxyyvvvvvqqqqmmmmdddccc
+abaaccaaaaaaaacaaaaaaccccccccccccccccaaaaaaaaaaaaaaaaaaaaaaaacccccccccccccccaaacaaaccccccccccaaccaaaaaaaaaciiiqqqttxxxxxxxyyvvvvvvvqqqmmmdddccc
+abaaaccccaaccccaaaccacccccccccccccccccaaaaaaccccaacaaaaaaaaaaccaaaccccccccccaaaaaaaccccccccccaaaaaaaaaaaaaaiiiqqqtttxxxxxxyyyyyyvvvqqqmmmdddccc
+SbaaaccccaacccccccccccccccccccccccccaaaaaaaaccccaacccaaaaaaccaaaaaaccccccccccaaaaaacccccccccccaaaaacaaacaaaaiiiqqqttxxxxEzzyyyyyvvvqqqmmmdddccc
+abaaaccccccccccccccccccccccccccccccaaaaaaaaaaccccccccaaaaaaccaaaaaaccccccccccaaaaaaaaccccccccaaaaaacaaaccaaaiiiqqqtttxxxyyyyyyvvvvqqqmmmdddcccc
+abaccccccaacccccccccccccccccccccccccaaaaaaaaaaaacccccaaaaaaacaaaaaacccccccccaaaaaaaaacccccccaaaaaaaacaaaaaaaiiiqqqtttxxyyyyyyvvvvqqqqnnmeddcccc
+abccccccaaaaccccccccccccaaaccccccccccccaaaaaaaaaaacccaaacaaacaaaaacccccccccaaaaaaaaaacccccccaaaaaaaaccaaaaaaaiiiqqtttxxyyyyyywvrrrrnnnneeeccccc
+abccccccaaaacccccaacccccaaaacccccccccccaaaccaaaaaacccacccccccaaaaacccccccccaaacaaacccccccccccccaacccccccaaaaaiiqqqttxxwywwyyywwrrrnnnneeeeccccc
+abccccccaaaaccaacaaaccccaaaaccccccaacccaacccaaaaaccccccccccccccccccccccccccccccaaacccccccccccccaaccccccaaaaaaiiqqqttwwwwwwwwywwrrrnnneeeecccccc
+abccccccccccccaaaaacccccaaaccccacaaacccccccccaaaaacccccccccccccccccccccccccccccaaacccccccccccccccccccccaaaaaaiiqqpsswwwwsswwwwwrrnnneeeeccccccc
+abcccccccccccccaaaaaacccccccccaaaaacaacccccccaacaacccccaaccccccccccccccccccccccccccccccccccccccccccccccaccaahhhpppssssssssswwwwrrnnneeeaccccccc
+abcccccccccccaaaaaaaacccccccccaaaaaaaacccccaaccccccaaacaaccccccccccccccccccccccccccccccccccccaaaccaccccccccchhhpppsssssssssswwrrrnnneeeaaaacccc
+abcccccccccccaaaaacaacccccccccccaaaaaccaaaaaaccccccaaaaaaccccccccccccccccccccccccccccaaccaaccaaaaaacccccccccchhpppppsspppossrrrrrnnneeeaaaacccc
+abccccccccccccacaaaccccccccccccaaaaacccaaaaaaaacccccaaaaaaaccaaaccccccccaaaacccccccccaaaaaacccaaaaacccccccccchhhpppppppppoosrrrroonffeaaaaacccc
+abccccccccccccccaaaccccccccccccaacaaaccaaaaaaaaccccaaaaaaaaacaaaccccccccaaaacccccccccaaaaaccaaaaaaacccccccccchhhhpppppppoooooooooonfffaaaaccccc
+abcccccccccccccccccccccccaaaccccccaaccccaaaaaaaccccaaaaaaaaaaaaaaaccccccaaaacccccccccaaaaaacaaaaaaaacccccaacchhhhhhhhgggggoooooooofffaaaaaacccc
+abcccccccccccccccccccccccaaaaacccaacccccaaaaaccccccaaaaaacaaaaaaaaccccccaaacccccccccaaaaaaaaaaaaaaaaccccaaacccchhhhhgggggggooooooffffaaaaaacccc
+abccaaacccccccccccccccccaaaaaaccaaaccccaaaaaacccccccccaaacccaaaaacccccccccccccccccccaaaaaaaaccaaacacccccaaacaaachhhggggggggggfffffffcaacccccccc
+abcaaaaccccccccccaacccccaaaaaaccaaacaaaccccaaccccccccccccccaaaaacccccccccccccccccccccccaacccccaaaccccaaaaaaaaaacccccccccaagggffffffcccccccccccc
+abcaaaaccccccccccaaccccccaaaaaaaaaaaaaaccccccccccccccccccccaaaaaaccccccccccccccccccccccaaccccccccccccaaaaaaaaaccccccccccaaacgfffffcccccccccccaa
+abccaaacccccccaaaaaaaacccaaaaaaaaaaaaaaccccccccaaaaaccaaaaaaaaaaaaaacaacccccccccaaaccacccccccccccccccccaaaaacccccccccccaaaaccccccccccccccccccaa
+abccccccccccccaaaaaaaacccccccccaaaaaaccccccccccaaaaaccaaaaaaaaaaaaaacaaaaaacccccaaaaaacccccccccccccccccaaaaaacccccccccccaacccccccccccccccacacaa
+abccccccccccccccaaaacccccccccccaaaaaacccccccccaaaaaacccaaaaaaaaaaaaacaaaaaacccccaaaaaacccccccccccccccccaaaaaaaccccccccccaacccccccccccccccaaaaaa
+abcccccccccccccaaaaaaccccccccccaaaaaaaccccccccaaaaaaccccccaaaaaacccaaaaaaaaccccaaaaaaaaccccccccccccccccaaacaaacccccccccccccccccccccccccccaaaaaa
diff --git a/2022/in/day12.ref b/2022/in/day12.ref
new file mode 100644
index 0000000..86e9cac
--- /dev/null
+++ b/2022/in/day12.ref
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi