day12

1 files changed, 217 insertions, 0 deletions

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)
+