summaryrefslogtreecommitdiffstats
path: root/solutions
diff options
context:
space:
mode:
Diffstat (limited to 'solutions')
-rw-r--r--solutions/py/d15.py337
-rw-r--r--solutions/py/main.py4
2 files changed, 221 insertions, 120 deletions
diff --git a/solutions/py/d15.py b/solutions/py/d15.py
index 7315d1a..9ee3f65 100644
--- a/solutions/py/d15.py
+++ b/solutions/py/d15.py
@@ -3,96 +3,51 @@ import heapq as heap
import collections
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:
- if board[point] == "#":
- s += "\u2588" * size
- elif board[point] == "S":
- s += "\u2591" * size
- else:
- s += " " * size
- else:
- s += "." * size
- return s
-
def neighbours(p):
return [(p[0]+1, p[1]), (p[0]-1, p[1]), \
(p[0], p[1]+1), (p[0], p[1]-1)]
-def get_path(start, end, board):
- #print("get_path", start, end)
+def get_path(start, end, board, draw_search=False):
if start == end:
return collections.deque()
visited = set()
h = []
heap.heappush(h, (0, start, collections.deque()))
while True:
- #print("h", h)
cur = heap.heappop(h)
for n in neighbours(cur[1]):
- #print("n", n)
if n == end:
- #print("done")
cur[2].append(n)
- #print(cur[2])
+ if draw_search:
+ print(draw(board, path=cur[2], visited=visited))
return cur[2]
- if n in visited:
- #print("visited")
+ if n in visited or n not in board or board[n] == "#":
continue
- if n not in board:
- #print("not in board")
- continue
- if board[n] == "#":
- #print("wall")
- continue
- #print("adding")
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))
+ if draw_search:
+ time.sleep(0.005)
+ print(draw(board, path=new_path, visited=visited))
+
+def pt1(input):
+ cur_x = cur_y = 0
+ q = collections.deque()
+ q.append((0,0))
+ path = collections.deque()
+ board = {}
+ board[(0,0)] = "."
+
+ c = intcode.Computer([int(x) for x in input[0].split(",")])
-cur_x = cur_y = 0
-q = collections.deque()
-q.append((0,0))
-path = collections.deque()
-board = {}
-board[(0,0)] = "."
-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(q) == 0:
- print("queue empty")
- break
- c.step()
- if c.SIG_INPUT:
- direction = 0
- prev_x, prev_y = cur_x, cur_y
- if auto:
+ while not c.SIG_HALT:
+ if len(q) == 0:
+ break
+ c.step()
+ if c.SIG_INPUT:
+ direction = 0
+ prev_x, prev_y = cur_x, cur_y
if len(path) == 0:
# find new path
for n in neighbours((cur_x, cur_y)):
@@ -100,7 +55,6 @@ while not c.SIG_HALT:
q.append(n)
if (cur_x, cur_y) in q:
q.remove((cur_x, cur_y))
- #print(q)
next = q.pop()
path = get_path((cur_x, cur_y), next, board)
next_step = path.popleft()
@@ -119,63 +73,208 @@ while not c.SIG_HALT:
else:
print("invalid path")
break
- else: # manual
- next_step = input()
- if next_step == "w":
+ c.input = direction
+ c.SIG_INPUT = False
+ if c.SIG_OUTPUT:
+ 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)] = "S"
+ oxygen = (cur_x, cur_y)
+ else:
+ break
+ c.output = None
+ c.SIG_OUTPUT = False
+ return len(get_path((0,0), oxygen, board))
+
+def pt2(input):
+ cur_x = cur_y = 0
+ q = collections.deque()
+ q.append((0,0))
+ path = collections.deque()
+ board = {}
+ board[(0,0)] = "."
+ oxygen = (0,0)
+
+ c = intcode.Computer([int(x) for x in input[0].split(",")])
+
+ while not c.SIG_HALT:
+ if len(q) == 0:
+ break
+ c.step()
+ if c.SIG_INPUT:
+ direction = 0
+ prev_x, prev_y = cur_x, cur_y
+ if len(path) == 0:
+ # find new path
+ for n in neighbours((cur_x, cur_y)):
+ if n not in q and n not in board:
+ q.append(n)
+ if (cur_x, cur_y) in q:
+ q.remove((cur_x, cur_y))
+ next = q.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 == "s":
+ elif next_step[1] == cur_y+1:
direction = 2
cur_y += 1
- elif next_step == "a":
+ elif next_step[0] == cur_x-1:
direction = 3
cur_x -= 1
- elif next_step == "d":
+ elif next_step[0] == cur_x+1:
direction = 4
cur_x += 1
else:
- continue
- c.input = direction
+ print("invalid path")
+ break
+ c.input = direction
+ c.SIG_INPUT = False
+ if c.SIG_OUTPUT:
+ 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)] = "S"
+ oxygen = (cur_x, cur_y)
+ else:
+ break
+ c.output = None
+ c.SIG_OUTPUT = False
+
+ steps = 0
+ visited = set(oxygen)
+ cur_layer = []
+ next_layer = [oxygen]
+ while True:
+ cur_layer = next_layer.copy()
+ next_layer = []
+ for p in cur_layer:
+ for n in neighbours(p):
+ if n in board and board[n] != "#" and n not in visited:
+ visited.add(n)
+ next_layer.append(n)
+ if len(next_layer) == 0:
+ break
steps += 1
- c.SIG_INPUT = False
- if c.SIG_OUTPUT:
- time.sleep(0.01)
- print(draw(board, droid=(cur_x, cur_y)))
- if c.output == 0:
- #print("found wall")
- board[(cur_x, cur_y)] = "#"
- cur_x, cur_y = prev_x, prev_y
- elif c.output == 1:
- #print("found empty")
- board[(cur_x, cur_y)] = "."
- elif c.output == 2:
- #print("found oxygen at", (cur_x, cur_y))
- board[(cur_x, cur_y)] = "S"
- oxygen = (cur_x, cur_y)
- else:
+ return steps
+
+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" * 2
+ elif path is not None and point in path:
+ s += "\u2591" * 2
+ elif visited is not None and point in visited:
+ s += "." * 2
+ elif point in board:
+ if board[point] == "#":
+ s += "\u2588" * 2
+ elif board[point] == "S":
+ s += "\u2591" * 2
+ else:
+ s += " " * 2
+ else:
+ s += "." * 2
+ return s
+
+def visualize(input):
+ cur_x = cur_y = 0
+ q = collections.deque()
+ q.append((0,0))
+ path = collections.deque()
+ board = {}
+ board[(0,0)] = "."
+
+ c = intcode.Computer([int(x) for x in input[0].split(",")])
+
+ while not c.SIG_HALT:
+ if len(q) == 0:
+ break
+ c.step()
+ if c.SIG_INPUT:
+ direction = 0
+ prev_x, prev_y = cur_x, cur_y
+ if len(path) == 0:
+ # find new path
+ for n in neighbours((cur_x, cur_y)):
+ if n not in q and n not in board:
+ q.append(n)
+ if (cur_x, cur_y) in q:
+ q.remove((cur_x, cur_y))
+ next = q.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
+ c.input = direction
+ c.SIG_INPUT = False
+ if c.SIG_OUTPUT:
+ 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)] = "S"
+ oxygen = (cur_x, cur_y)
+ else:
+ break
+ time.sleep(0.0075)
+ print(draw(board, droid=(cur_x, cur_y)))
+ c.output = None
+ c.SIG_OUTPUT = False
+
+ get_path((0,0), oxygen, board, draw_search=True)
+
+ steps = 0
+ visited = set(oxygen)
+ cur_layer = []
+ next_layer = [oxygen]
+ while True:
+ cur_layer = next_layer.copy()
+ next_layer = []
+ for p in cur_layer:
+ for n in neighbours(p):
+ if n in board and board[n] != "#" and n not in visited:
+ visited.add(n)
+ next_layer.append(n)
+ if len(next_layer) == 0:
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(len(get_path((0,0), oxygen, board)))
-print(steps)
-
-steps = 0
-visited = set(oxygen)
-cur_layer = []
-next_layer = [oxygen]
-while True:
- cur_layer = next_layer.copy()
- next_layer = []
- for p in cur_layer:
- for n in neighbours(p):
- if n in board and board[n] != "#" and n not in visited:
- visited.add(n)
- next_layer.append(n)
- if len(next_layer) == 0:
- break
- steps += 1
-print(steps)
+ steps += 1
+
+if __name__ == "__main__":
+ input = open("../input/15", "r").readlines()
+ print(pt1(input))
+ print(pt2(input))
+ visualize(input)
diff --git a/solutions/py/main.py b/solutions/py/main.py
index db4150e..aa7a4e2 100644
--- a/solutions/py/main.py
+++ b/solutions/py/main.py
@@ -13,8 +13,10 @@ import d10
import d11
import d12
import d13
+import d14
+import d15
-mods = [d01, d02, d03, d04, d05, d06, d07, d08, d09, d10, d11, d12, d13]
+mods = [d01, d02, d03, d04, d05, d06, d07, d08, d09, d10, d11, d12, d13, d14, d15]
timings = [[0 for _ in range(2)] for _ in range(len(mods))]
clock_type = time.CLOCK_MONOTONIC
generated by cgit v1.2.1 (git 2.18.0) at 2025-12-14 19:38:59 +0100