1 files changed, 188 insertions, 0 deletions
diff --git a/solutions/py/d15.py b/solutions/py/d15.py
new file mode 100644
index 0000000..59e5c3c
--- /dev/null
+++ b/solutions/py/d15.py
@@ -0,0 +1,188 @@
+import intcode
+import heapq as heap
+import collections
+import queue
+import time
+
+size = 2
+def draw(board, droid=None, path=None, visited=None):
+    min_x=max_x=min_y=max_y = 0
+    for p in board:
+        min_x = min(p[0], min_x)
+        max_x = max(p[0], max_x)
+        min_y = min(p[1], min_y)
+        max_y = max(p[1], max_y)
+    s = ""
+    for y in range(min_y-1, max_y+2):
+        s += "\n"
+        for x in range(min_x-1, max_x+2):
+            point = (x, y)
+            if droid is not None and point == droid:
+                s += "D"*size
+            elif path is not None and point in path:
+                s += "\u2591"*size
+            elif visited is not None and point in visited:
+                s += "."*size
+            elif point in board:
+                s += ("\u2588" if board[point] == "#" else " ")*size
+            else:
+                s += "."*size
+    return s
+
+def dist(a, b):
+    return abs(a[0] - b[0]) + abs(a[1] -b[1])
+
+def neighbours(p):
+    ''' Return all neighbours to p in a tuple '''
+    return [(p[0]+1, p[1]), (p[0]-1, p[1]), \
+            (p[0], p[1]+1), (p[0], p[1]-1)]
+
+def get_path(p_start, p_end, board):
+    #print("get_path", p_start, p_end)
+    '''
+    Return a path as a deque between p_start and p_end given some board-state
+
+    The path is guaranteed valid but not guaranteed the shortest
+    '''
+    if p_start == p_end:
+        # already at destination, no path 
+        return collections.deque()
+    visited = set()
+    h = []
+    heap.heappush(h, (0, p_start, collections.deque()))
+    while True:
+        cur = heap.heappop(h)
+        for n in neighbours(cur[1]):
+            if n == p_end:
+                # done
+                cur[2].append(n)
+                return cur[2]
+            if n in visited:
+                continue
+            if n not in board:
+                # unknown point
+                continue
+            if board[n] == "#":
+                # wall
+                continue
+            new_path = collections.deque(cur[2])
+            new_path.append(n)
+            visited.add(n)
+            heap.heappush(h, (dist(p_start, n), n, new_path))
+
+def get_short_path(start, end, board):
+    '''
+    Return the shortest path between start and end given some board-state
+
+    The path is guaranteed valid and the shortest available
+    '''
+    if start == end:
+        return collections.deque()
+    visited = set()
+    h = []
+    heap.heappush(h, (0, start, collections.deque()))
+    while True:
+        cur = heap.heappop(h)
+        for n in neighbours(cur[1]):
+            if n == end:
+                cur[2].append(n)
+                return cur[2]
+            if n in visited:
+                continue
+            if n not in board:
+                continue
+            if board[n] == "#":
+                continue
+            new_path = collections.deque(cur[2])
+            new_path.append(n)
+            visited.add(n)
+            #print(draw(board, path=new_path, visited=visited))
+            #time.sleep(0.01)
+            heap.heappush(h, (cur[0] + 1, n, new_path))
+
+cur_x = cur_y = 0
+stack = collections.deque()
+stack.append((0,0))
+path = collections.deque()
+board = {}
+oxygen = (0,0)
+
+f = open("../input/15", "r").readlines()
+c = intcode.Computer([int(x) for x in f[0].split(",")])
+
+auto = True
+steps = 0
+while not c.SIG_HALT:
+    if auto and len(stack) == 0:
+        print("stack empty")
+        break
+    c.step()
+    if c.SIG_INPUT:
+        direction = 0
+        prev_x, prev_y = cur_x, cur_y
+        if auto:
+            if len(path) == 0:
+                # find new path
+                for n in neighbours((cur_x, cur_y)):
+                    if n not in stack and n not in board:
+                        stack.append(n)
+                next = stack.pop()
+                path = get_path((cur_x, cur_y), next, board)
+            next_step = path.popleft()
+            if next_step[1] == cur_y-1:
+                direction = 1
+                cur_y -= 1
+            elif next_step[1] == cur_y+1:
+                direction = 2
+                cur_y += 1
+            elif next_step[0] == cur_x-1:
+                direction = 3
+                cur_x -= 1
+            elif next_step[0] == cur_x+1:
+                direction = 4
+                cur_x += 1
+            else:
+                print("invalid path")
+                break
+        else:  # manual
+            next_step = input()
+            if next_step == "w":
+                direction = 1
+                cur_y -= 1
+            elif next_step == "s":
+                direction = 2
+                cur_y += 1
+            elif next_step == "a":
+                direction = 3
+                cur_x -= 1
+            elif next_step == "d":
+                direction = 4
+                cur_x += 1
+            else:
+                continue
+        c.input = direction
+        steps += 1
+        c.SIG_INPUT = False
+    if c.SIG_OUTPUT:
+        # time.sleep(0.075)
+        # print(draw(board, droid=(cur_x, cur_y)))
+        if c.output == 0:
+            board[(cur_x, cur_y)] = "#"
+            cur_x, cur_y = prev_x, prev_y
+        elif c.output == 1:
+            board[(cur_x, cur_y)] = "."
+        elif c.output == 2:
+            board[(cur_x, cur_y)] = "O"
+            print("found oxygen at", (cur_x, cur_y))
+            oxygen = (cur_x, cur_y)
+        else:
+            break
+        c.output = None
+        c.SIG_OUTPUT = False
+        if not auto:
+            print(draw(board, (cur_x, cur_y)))
+print(draw(board))
+print(draw(board, path=get_path((0,0), oxygen, board)))
+print(draw(board, path=get_short_path((0,0), oxygen, board)))
+print(len(get_short_path((0,0), oxygen, board)))
+print(steps)