summaryrefslogtreecommitdiffstats
path: root/19/py
diff options
context:
space:
mode:
Diffstat (limited to '19/py')
-rw-r--r--19/py/d01.py28
-rw-r--r--19/py/d02.py49
-rw-r--r--19/py/d03.py83
-rw-r--r--19/py/d04.py65
-rw-r--r--19/py/d05.py34
-rw-r--r--19/py/d06.py87
-rw-r--r--19/py/d07.py80
-rw-r--r--19/py/d08.py38
-rw-r--r--19/py/d09.py27
-rw-r--r--19/py/d10.py261
-rw-r--r--19/py/d11.py165
-rw-r--r--19/py/d12.py126
-rw-r--r--19/py/d13.py132
-rw-r--r--19/py/d14.py77
-rw-r--r--19/py/d15.py276
-rw-r--r--19/py/d16.py46
-rw-r--r--19/py/d17.py305
-rw-r--r--19/py/intcode.py153
-rw-r--r--19/py/main.py52
19 files changed, 2084 insertions, 0 deletions
diff --git a/19/py/d01.py b/19/py/d01.py
new file mode 100644
index 0000000..d1c57c8
--- /dev/null
+++ b/19/py/d01.py
@@ -0,0 +1,28 @@
+import math
+import sys
+
+def get_fuel(mass):
+ fuel = math.floor(mass / 3) - 2
+ return 0 if fuel <= 0 else fuel + get_fuel(fuel)
+
+def pt1(_in):
+ s = 0
+ for line in _in:
+ mass = int(line)
+ if mass == 0:
+ break
+ fuel = math.floor(mass / 3) - 2
+ s += fuel
+ return s
+
+def pt2(input):
+ return sum([get_fuel(int(line)) for line in input])
+
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/01", "r").readlines()
+ cProfile.run("pt1(input)")
+ cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d02.py b/19/py/d02.py
new file mode 100644
index 0000000..6b5aa0a
--- /dev/null
+++ b/19/py/d02.py
@@ -0,0 +1,49 @@
+import sys
+
+def pt1(input):
+ program = [int(x) for x in input[0].split(",")]
+
+ memory = program.copy()
+ memory[1] = 12
+ memory[2] = 2
+
+ pointer = 0
+ while True:
+ if memory[pointer] == 99:
+ break
+ elif memory[pointer] == 1:
+ memory[memory[pointer+3]] = memory[memory[pointer+1]] + memory[memory[pointer+2]]
+ elif memory[pointer] == 2:
+ memory[memory[pointer+3]] = memory[memory[pointer+1]] * memory[memory[pointer+2]]
+ pointer += 4
+ return memory[0]
+
+def pt2(input):
+ program = [int(x) for x in input[0].split(",")]
+
+ for n in range(100):
+ for v in range(100):
+ memory = program.copy()
+ memory[1] = n
+ memory[2] = v
+
+ pointer = 0
+ while True:
+ if memory[pointer] == 99:
+ break
+ elif memory[pointer] == 1:
+ memory[memory[pointer+3]] = memory[memory[pointer+1]] + memory[memory[pointer+2]]
+ elif memory[pointer] == 2:
+ memory[memory[pointer+3]] = memory[memory[pointer+1]] * memory[memory[pointer+2]]
+ pointer += 4
+ if memory[0] == 19690720:
+ return (n, v, n*100 + v)
+
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/02", "r").readlines()
+ cProfile.run("pt1(input)")
+ cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d03.py b/19/py/d03.py
new file mode 100644
index 0000000..70bf9f0
--- /dev/null
+++ b/19/py/d03.py
@@ -0,0 +1,83 @@
+from profilehooks import coverage
+import math
+
+def intersection(l1, l2):
+ l1 = set(l1)
+ l2 = set(l2)
+ return [value for value in l2 if value in l1]
+
+def man_dist(point):
+ return abs(point[0]) + abs(point[1])
+
+#@coverage
+def pt1(input):
+ wire1 = []
+ wire2 = []
+ for wire, moves in zip((wire1, wire2), (input[0], input[1])):
+ x = 0
+ y = 0
+ dx = 0
+ dy = 0
+ for move in moves.split(","):
+ if move[0] == "D":
+ dx = 0
+ dy = -1
+ elif move[0] == "U":
+ dx = 0
+ dy = 1
+ elif move[0] == "R":
+ dx = 1
+ dy = 0
+ elif move[0] == "L":
+ dx = -1
+ dy = 0
+ for i in range(int(move[1:])):
+ x += dx
+ y += dy
+ wire.append((x, y))
+ points = intersection(wire1, wire2)
+ dist = man_dist(points[0])
+ for point in points[1:]:
+ dist = min(dist, man_dist(point))
+ return dist
+
+#@coverage
+def pt2(input):
+ wire1 = {}
+ wire2 = {}
+ # wire {(x,y) : dist}
+ for wire, moves in zip((wire1, wire2), (input[0], input[1])):
+ x = 0
+ y = 0
+ dx = 0
+ dy = 0
+ steps = 0
+ for move in moves.split(","):
+ if move[0] == "D":
+ dx = 0
+ dy = -1
+ elif move[0] == "U":
+ dx = 0
+ dy = 1
+ elif move[0] == "R":
+ dx = 1
+ dy = 0
+ elif move[0] == "L":
+ dx = -1
+ dy = 0
+ for i in range(int(move[1:])):
+ x += dx
+ y += dy
+ steps += 1
+ wire[(x, y)] = steps
+
+ points = intersection(list(wire1.keys()), list(wire2.keys()))
+ length = wire1[points[0]] + wire2[points[0]]
+ for point in points[1:]:
+ length = min(length, wire1[point] + wire2[point])
+ return length
+
+if __name__ == "__main__":
+ input = open("../input/03", "r").readlines()
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d04.py b/19/py/d04.py
new file mode 100644
index 0000000..c9bcbf3
--- /dev/null
+++ b/19/py/d04.py
@@ -0,0 +1,65 @@
+from collections import Counter
+
+def isIncreasing(num):
+ s = list(str(num))
+ n = int(s[0])
+ n_i = 0
+ for sp in s[1:]:
+ n_i += 1
+ if int(sp) < n:
+ for i in range(n_i, 6):
+ s[i] = str(n)
+ return False, int("".join(s))
+ n = int(sp)
+ return (True,)
+
+def pt1(input):
+ def containsDouble(num):
+ s = str(num)
+ amounts = [0 for _ in range(10)]
+ for c in s:
+ amounts[int(c)] += 1
+ c = Counter(amounts)
+ return c[0] + c[1] < 10
+
+ amount = 0
+ n = 357253
+ while n < 892942 + 1:
+ inc = isIncreasing(n)
+ if inc[0] == True:
+ if containsDouble(n):
+ amount += 1
+ n += 1
+ else:
+ n = inc[1]
+ return amount
+
+def pt2(input):
+ def containsDouble(num):
+ s = str(num)
+ amounts = [0 for _ in range(10)]
+ for c in s:
+ amounts[int(c)] += 1
+ c = Counter(amounts)
+ if c[0] + c[1] < 10:
+ return c[2] >= 1
+
+ amount = 0
+ n = 357253
+ while n < 892942 + 1:
+ inc = isIncreasing(n)
+ if inc[0] == True:
+ if containsDouble(n):
+ amount += 1
+ n += 1
+ else:
+ n = inc[1]
+ return amount
+
+if __name__ == "__main__":
+ import cProfile
+
+ cProfile.run("pt1([])")
+ cProfile.run("pt2([])")
+ print(pt1([]))
+ print(pt2([]))
diff --git a/19/py/d05.py b/19/py/d05.py
new file mode 100644
index 0000000..1415b99
--- /dev/null
+++ b/19/py/d05.py
@@ -0,0 +1,34 @@
+import intcode
+
+def pt1(input):
+ program = [int(x) for x in input[0].split(",")]
+ c = intcode.Computer(program)
+ c.input = 1
+ output = []
+ while c.memory[c.pointer] != 99:
+ c.step()
+ if c.output != None:
+ output.append(c.output)
+ c.output = None
+ return output
+
+def pt2(input):
+ program = [int(x) for x in input[0].split(",")]
+ c = intcode.Computer(program)
+ c.input = 5
+ output = []
+ while c.memory[c.pointer] != 99:
+ c.step()
+ if c.output != None:
+ output.append(c.output)
+ c.output = None
+ return output
+
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/05", "r").readlines()
+ cProfile.run("pt1(input)")
+ cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d06.py b/19/py/d06.py
new file mode 100644
index 0000000..0b54362
--- /dev/null
+++ b/19/py/d06.py
@@ -0,0 +1,87 @@
+from typing import Iterable
+import sys
+
+class Tree(object):
+ # https://stackoverflow.com/a/28015122
+ def __init__(self, name='root', children=None):
+ self.name = name
+ self.children = []
+ self.parent = None
+ if children is not None:
+ for child in children:
+ self.add_child(child)
+ def add_child(self, node):
+ self.children.append(node)
+ node.parent = self
+
+ def __eq__(self, other):
+ if isinstance(other, Tree):
+ return self.name == other.name
+ return False
+ def parents(self):
+ return [self.parent] + self.parent.parents() if self.parent != None\
+ else []
+
+def gen_tree(input):
+ trees = {}
+ seen = set() # seen trees. contains only IDs
+ leafs = {}
+
+ for orbit in input:
+ orbit = orbit.split(")")
+ #print(orbit)
+ if not orbit[0] in seen:
+ trees[orbit[0]] = Tree(orbit[0])
+ seen.add(orbit[0])
+
+ # hook up each child to its parent (since every parent now exists)
+ for orbit in input:
+ orbit = orbit.rstrip().split(")")
+ if orbit[1] in seen:
+ trees[orbit[0]].add_child(trees[orbit[1]])
+ else:
+ leafs[orbit[1]] = Tree(orbit[1])
+ trees[orbit[0]].add_child(leafs[orbit[1]])
+ for k in trees:
+ pass
+ #print(trees[k], trees[k].children)
+
+ trees.update(leafs)
+ return trees
+
+sum_depths = 0
+def pt1(input):
+ tree = gen_tree(input)
+ depth = 0
+ depths = {}
+ def count_children(tree, depth):
+ global sum_depths # fusk-rekursion? ville bara att det skulle fungera
+ sum_depths += depth
+ depths[tree.name] = depth
+ for child in tree.children:
+ count_children(child, depth+1)
+ count_children(tree["COM"], 0)
+ return sum_depths
+
+def pt2(input):
+ # find common parent and distance to it
+ tree = gen_tree(input)
+ src_parents = tree["YOU"].parent.parents()
+ tar_parents = tree["SAN"].parent.parents()
+ src_dist = 0
+ for src_parent in src_parents:
+ src_dist += 1
+ tar_dist = 0
+ for tar_parent in tar_parents:
+ tar_dist += 1
+ if src_parent == tar_parent:
+ return (src_parent.name, src_dist, tar_dist, src_dist + tar_dist)
+
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/06", "r").readlines()
+ cProfile.run("pt1(input)")
+ cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d07.py b/19/py/d07.py
new file mode 100644
index 0000000..7ab2fe6
--- /dev/null
+++ b/19/py/d07.py
@@ -0,0 +1,80 @@
+import intcode
+import itertools
+import queue
+
+def pt1(input):
+ program = [int(x) for x in input[0].split(",")]
+ highest_signal = 0
+ highest_sequence = None
+ for phase_seq in list(itertools.permutations(list(range(0,5)))):
+ q = queue.Queue(5)
+ for phase in phase_seq:
+ q.put(phase)
+ amps = [intcode.Computer(program) for _ in range(5)]
+ for amp in amps:
+ amp.input = q.get()
+ signal = 0
+ for amp in amps:
+ while True:
+ amp.step()
+ if amp.input is None:
+ amp.input = signal
+ if amp.output is not None:
+ signal = amp.output
+ amp.output = None
+ break
+ if signal > highest_signal:
+ highest_signal = signal
+ highest_sequence = phase_seq
+ return (highest_sequence, highest_signal)
+
+def pt2(input):
+ program = [int(x) for x in input[0].split(",")]
+ highest_signal = 0
+ highest_sequence = None
+ for phase_seq in list(itertools.permutations(list(range(5,10)))):
+ q = queue.Queue(5)
+ for phase in phase_seq:
+ q.put(phase)
+ amps = [intcode.Computer(program) for _ in range(5)]
+ for amp in amps:
+ amp.input = q.get()
+
+ signal = 0
+ current_amp = 0
+ while True:
+ amp = amps[current_amp]
+ amp.step()
+ if amp.input is None:
+ if amp.phase_read == False:
+ amp.phase_read = True
+ amp.input = signal
+ else:
+ pass
+ if amp.output is not None:
+ signal = amp.output
+ amp.output = None
+ current_amp = (current_amp + 1) % 5
+ if amps[current_amp].phase_read == True:
+ amps[current_amp].input = signal
+ continue
+ if amp.memory[amp.pointer] == 99:
+ if current_amp == 4:
+ break
+ current_amp = (current_amp + 1) % 5
+ amps[current_amp].input = signal
+ continue
+ if signal > highest_signal:
+ highest_signal = signal
+ highest_sequence = phase_seq
+ return (highest_sequence, highest_signal)
+
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/07", "r").readlines()
+ cProfile.run("pt1(input)")
+ cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
+
diff --git a/19/py/d08.py b/19/py/d08.py
new file mode 100644
index 0000000..7df2aec
--- /dev/null
+++ b/19/py/d08.py
@@ -0,0 +1,38 @@
+def count(layer, num):
+ return sum([row.count(num) for row in layer])
+
+def pt1(input):
+ img = []
+ least_zeroes = 150 # max
+ n = 0
+ for l in range(100):
+ layer = [[int(input[0][l*25*6 + y*25 + x]) for x in range(25)] for y in range(6)]
+ if count(layer, 0) < least_zeroes:
+ least_zeroes = count(layer, 0)
+ n = count(layer, 1) * count(layer, 2)
+ img.append(layer)
+ return n
+
+def pt2(input):
+ img = [[[int(input[0][l*25*6 + y*25 + x]) for x in range(25)] for y in range(6)] for l in range(100)]
+ result = img[0]
+ for layer in img[1:]:
+ for x in range(25):
+ for y in range(6):
+ if result[y][x] == 2:
+ result[y][x] = layer[y][x]
+ str_res = []
+ for row in result:
+ str_res.append("\n ")
+ for c in row:
+ str_res.append('\u2588' if c == 1 else ' ')
+ return "".join(str_res)
+
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/08", "r").readlines()
+ cProfile.run("pt1(input)")
+ cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d09.py b/19/py/d09.py
new file mode 100644
index 0000000..ada6763
--- /dev/null
+++ b/19/py/d09.py
@@ -0,0 +1,27 @@
+import intcode
+
+def do(input, code):
+ program = [int(x) for x in input.split(",")]
+ c = intcode.Computer(program)
+ c.input = code
+ output = []
+ while True:
+ c.step()
+ #print(c.relative_base, c.pointer, c.memory)
+ if c.SIG_HALT:
+ break
+ if c.output is not None:
+ output.append(c.output)
+ c.output = None
+ return output
+
+def pt1(input):
+ return do(input[0], 1)
+
+def pt2(input):
+ return do(input[0], 2)
+
+if __name__ == "__main__":
+ input = open("../input/09", "r").readlines()
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d10.py b/19/py/d10.py
new file mode 100644
index 0000000..0d918d9
--- /dev/null
+++ b/19/py/d10.py
@@ -0,0 +1,261 @@
+import math
+import os
+import queue
+import sys
+import time
+
+def red(dcoord):
+ dx = dcoord[0]
+ dy = dcoord[1]
+ if dx == 0:
+ return (0, (1 if dy > 0 else -1))
+ if dy == 0:
+ return ((1 if dx > 0 else -1), 0)
+ gcd = math.gcd(dx, dy)
+ return (dx // gcd, dy // gcd)
+
+def angle(x, y): # from y-axis, clockwise
+ if x >= 0 and y > 0:
+ return math.atan(abs(x/y))
+ if x > 0 and y <= 0:
+ return math.atan(abs(y/x)) + math.pi/2
+ if x <= 0 and y < 0:
+ return math.atan(abs(x/y)) + math.pi
+ else:
+ return math.atan(abs(y/x)) + 3*math.pi / 2
+
+def pt1(input):
+ asteroids = set()
+ res = {}
+
+ max_x = len(input[0].rstrip())
+ max_y = len(input)
+
+ for y in range(max_y):
+ for x in range(max_x):
+ if input[y][x] == "#":
+ asteroids.add((x,y))
+
+ for a in asteroids:
+ candidates = set(asteroids.copy())
+ candidates.remove(a)
+ seen = set()
+ while len(candidates) > 0:
+ c = candidates.pop()
+ seen.add(c)
+ dx = c[0] - a[0]
+ dy = c[1] - a[1]
+ x = a[0]
+ y = a[1]
+ x += dx
+ y += dy
+ dx, dy = red((dx, dy))
+ x += dx
+ y += dy
+ while x < max_x and y < max_y and x >= 0 and y >= 0:
+ if (x, y) in candidates:
+ candidates.remove((x, y))
+ if (x, y) in seen:
+ seen.remove((x, y))
+ x += dx
+ y += dy
+ res[a] = seen
+
+ best = [0, 0, 0]
+ for coord in res:
+ amount = len(res[coord])
+ if amount > best[0]:
+ best = [amount, coord, res[coord]]
+ return (best[1], best[0])
+
+def pt2(input):
+ asteroids = set()
+ res = {}
+
+ max_x = len(input[0].rstrip())
+ max_y = len(input)
+
+ for y in range(max_y):
+ for x in range(max_x):
+ if input[y][x] == "#":
+ asteroids.add((x,y))
+
+ for a in asteroids:
+ candidates = set(asteroids.copy())
+ candidates.remove(a)
+ seen = set()
+ while len(candidates) > 0:
+ c = candidates.pop()
+ seen.add(c)
+ dx = c[0] - a[0]
+ dy = c[1] - a[1]
+ x = a[0]
+ y = a[1]
+ x += dx
+ y += dy
+ dx, dy = red((dx, dy))
+ x += dx
+ y += dy
+ while x < max_x and y < max_y and x >= 0 and y >= 0:
+ if (x, y) in candidates:
+ candidates.remove((x, y))
+ if (x, y) in seen:
+ seen.remove((x, y))
+ x += dx
+ y += dy
+ res[a] = seen
+
+ best = [0, 0, 0]
+ for coord in res:
+ amount = len(res[coord])
+ if amount > best[0]:
+ best = [amount, coord, res[coord]]
+ asteroids.remove(best[1])
+ x0 = best[1][0]
+ y0 = best[1][1]
+
+ angles = {}
+ q = queue.Queue()
+ for a in asteroids:
+ angles[a] = angle(a[0] - x0, y0 - a[1])
+
+ for k, v in sorted(angles.items(), key=lambda item: item[1]):
+ if k in best[2]:
+ q.put(k)
+
+ destroyed = 1
+ while not q.empty():
+ asteroid = q.get()
+ if destroyed == 200:
+ return (asteroid, asteroid[0]*100 + asteroid[1])
+ asteroids.remove(asteroid)
+ destroyed += 1
+
+ # add next asteroid behind to queue
+ dx = asteroid[0] - x0
+ dy = asteroid[1] - y0
+ x = x0
+ y = y0
+ x += dx
+ y += dy
+ dx, dy = red((dx, dy))
+ x += dx
+ y += dy
+ while x < max_x and y < max_y and x >= 0 and y >= 0:
+ if (x, y) in asteroids:
+ q.put((x, y))
+ break
+ x += dx
+ y += dy
+
+def print_map(coords, w, h):
+ time.sleep(0.01)
+ os.system("clear")
+ s = ""
+ for y in range(w):
+ for x in range(h):
+ s += (coords[(x, y)] + " ") if (x,y) in coords else " "
+ s += "\n"
+ print(s)
+
+def visualize(input):
+ asteroids = set()
+ res = {}
+
+ max_x = len(input[0].rstrip())
+ max_y = len(input)
+
+ for y in range(max_y):
+ for x in range(max_x):
+ if input[y][x] == "#":
+ asteroids.add((x,y))
+
+ #print_map(asteroids, max_x, max_y)
+
+ for a in asteroids:
+ print(a)
+ time.sleep(3)
+ candidates = set(asteroids.copy())
+ candidates.remove(a)
+ seen = set()
+ while len(candidates) > 0:
+ #print(len(candidates))
+ time.sleep(0.02)
+ union = {a: "\u2588"}
+ for c in candidates:
+ union[c] = "C"
+ for s in seen:
+ union[s] = "s"
+ print_map(union, max_x, max_y)
+ c = candidates.pop()
+ seen.add(c)
+ dx = c[0] - a[0]
+ dy = c[1] - a[1]
+ x = a[0]
+ y = a[1]
+ x += dx
+ y += dy
+ dx, dy = red((dx, dy))
+ x += dx
+ y += dy
+ while x < max_x and y < max_y and x >= 0 and y >= 0:
+ if (x, y) in candidates:
+ candidates.remove((x, y))
+ if (x, y) in seen:
+ seen.remove((x, y))
+ x += dx
+ y += dy
+ res[a] = seen
+
+ best = [0, 0, 0]
+ for coord in res:
+ amount = len(res[coord])
+ if amount > best[0]:
+ best = [amount, coord, res[coord]]
+ asteroids.remove(best[1])
+ x0 = best[1][0]
+ y0 = best[1][1]
+
+ angles = {}
+ q = queue.Queue()
+ for a in asteroids:
+ angles[a] = angle(a[0] - x0, y0 - a[1])
+
+ for k, v in sorted(angles.items(), key=lambda item: item[1]):
+ if k in best[2]:
+ q.put(k)
+
+ destroyed = 1
+ while not q.empty():
+ #print_map(asteroids, max_x, max_y)
+ asteroid = q.get()
+ if destroyed == 200:
+ return (asteroid, asteroid[0]*100 + asteroid[1])
+ asteroids.remove(asteroid)
+ destroyed += 1
+
+ # add next asteroid behind to queue
+ dx = asteroid[0] - x0
+ dy = asteroid[1] - y0
+ x = x0
+ y = y0
+ x += dx
+ y += dy
+ dx, dy = red((dx, dy))
+ x += dx
+ y += dy
+ while x < max_x and y < max_y and x >= 0 and y >= 0:
+ if (x, y) in asteroids:
+ q.put((x, y))
+ break
+ x += dx
+ y += dy
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/10","r").readlines()
+ visualize(input)
+ #cProfile.run("pt1(input)")
+ #cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d11.py b/19/py/d11.py
new file mode 100644
index 0000000..e9b280c
--- /dev/null
+++ b/19/py/d11.py
@@ -0,0 +1,165 @@
+import intcode
+import time
+
+
+def draw(colors, ship, direction):
+ min_x, max_x, min_y, max_y = 0, 0, 0, 0
+ ship_c = ""
+ if direction == 0:
+ ship_c = "^"
+ elif direction == 1:
+ ship_c = "<"
+ elif direction == 2:
+ ship_c = "v"
+ elif direction == 3:
+ ship_c = ">"
+ for color in colors:
+ min_x = min(min_x, color[0])
+ max_x = max(max_x, color[0])
+ min_y = min(min_y, color[1])
+ max_y = max(max_y, color[1])
+ s = ""
+ for y in range(min_y, max_y+1):
+ s += "\n"
+ for x in range(min_x, max_x+1):
+ if (x,y) == ship:
+ s += ship_c
+ elif (x,y) in colors:
+ c = colors[(x,y)]
+ s += "\u2588" if c == 1 else " "
+ else:
+ s += "."
+ return s
+
+def pt1(input):
+ program = [int(x) for x in input[0].split(",")]
+ x=y = 0
+ direction = 0
+ # 0 is up
+ # 1 is left
+ # 2 is down
+ # 3 is right
+ # 4 is up (again)
+ # turning left is direction += 1
+ # turning right is direction -= 1
+ # direction is direction % 4
+ colors = {} # (x,y): 1/0 (1 = white, 0 = black)
+
+ got_color = False
+ c = intcode.Computer(program)
+ while c.memory[c.pointer] != 99:
+ # input
+ #print(x, y)
+ #draw(colors, (x,y), direction % 4)
+ #input()
+ #time.sleep(0.1)
+ c.input = colors.get((x, y), 0)
+ c.step()
+ if c.output is not None:
+ if not got_color:
+ colors[(x, y)] = c.output
+ c.output = None
+ got_color = True
+ elif got_color:
+ direction += (1 if c.output == 0 else -1)
+ dir = direction % 4
+ if dir == 0:
+ y -= 1
+ elif dir == 1:
+ x -= 1
+ elif dir == 2:
+ y += 1
+ elif dir == 3:
+ x += 1
+ got_color = False
+ c.output = None
+ return len(colors)
+
+def pt2(input):
+ program = [int(x) for x in input[0].split(",")]
+ x=y = 0
+ direction = 0
+ # 0 is up
+ # 1 is left
+ # 2 is down
+ # 3 is right
+ # 4 is up (again)
+ # turning left is direction += 1
+ # turning right is direction -= 1
+ # direction is direction % 4
+ colors = {(0,0): 1} # (x,y): 1/0 (1 = white, 0 = black)
+
+ got_color = False
+ c = intcode.Computer(program)
+ while c.memory[c.pointer] != 99:
+ c.input = colors.get((x, y), 0)
+ c.step()
+ if c.output is not None:
+ if not got_color:
+ colors[(x, y)] = c.output
+ c.output = None
+ got_color = True
+ elif got_color:
+ direction += (1 if c.output == 0 else -1)
+ dir = direction % 4
+ if dir == 0:
+ y -= 1
+ elif dir == 1:
+ x -= 1
+ elif dir == 2:
+ y += 1
+ elif dir == 3:
+ x += 1
+ got_color = False
+ c.output = None
+ return draw(colors, (0,0), 0)
+
+def visualize(input):
+ program = [int(x) for x in input[0].split(",")]
+ x=y = 0
+ direction = 0
+ # 0 is up
+ # 1 is left
+ # 2 is down
+ # 3 is right
+ # 4 is up (again)
+ # turning left is direction += 1
+ # turning right is direction -= 1
+ # direction is direction % 4
+ colors = {(0,0): 1} # (x,y): 1/0 (1 = white, 0 = black)
+
+ got_color = False
+ c = intcode.Computer(program)
+ while c.memory[c.pointer] != 99:
+ time.sleep(0.002)
+ print(draw(colors, (x,y), direction % 4))
+ c.input = colors.get((x, y), 0)
+ c.step()
+ if c.output is not None:
+ if not got_color:
+ colors[(x, y)] = c.output
+ c.output = None
+ got_color = True
+ elif got_color:
+ direction += (1 if c.output == 0 else -1)
+ dir = direction % 4
+ if dir == 0:
+ y -= 1
+ elif dir == 1:
+ x -= 1
+ elif dir == 2:
+ y += 1
+ elif dir == 3:
+ x += 1
+ got_color = False
+ c.output = None
+
+if __name__ == "__main__":
+ import cProfile
+
+ input = open("../input/11", "r").readlines()
+ cProfile.run("pt1(input)")
+ cProfile.run("pt2(input)")
+ print(pt1(input))
+ print(pt2(input))
+ visualize(input)
diff --git a/19/py/d12.py b/19/py/d12.py
new file mode 100644
index 0000000..878acc6
--- /dev/null
+++ b/19/py/d12.py
@@ -0,0 +1,126 @@
+import itertools
+#import primefac
+
+class Moon(object):
+ def __init__(self, x, y, z):
+ self.x = x
+ self.y = y
+ self.z = z
+ self.dx = 0
+ self.dy = 0
+ self.dz = 0
+
+ def step(self):
+ self.x += self.dx
+ self.y += self.dy
+ self.z += self.dz
+
+ def gx(self, other):
+ if self.x < other.x:
+ self.dx += 1
+ other.dx -= 1
+
+ def gy(self, other):
+ if self.y < other.y:
+ self.dy += 1
+ other.dy -= 1
+
+ def gz(self, other):
+ if self.z < other.z:
+ self.dz += 1
+ other.dz -= 1
+
+ def gravity(self, other):
+ self.gx(other)
+ self.gy(other)
+ self.gz(other)
+
+ def get_x(self):
+ return self.x, self.dx
+
+ def get_y(self):
+ return self.y, self.dy
+
+ def get_z(self):
+ return self.z, self.dz
+
+ def get(self):
+ return self.get_x, self.get_y, self.get_z
+
+def pt1(input):
+ return
+ moons = []
+
+ for line in input:
+ dims = line.rstrip().split(",")
+ x = int(dims[0][3:])
+ y = int(dims[1][3:])
+ z = int(dims[2][3:-1])
+ moons.append(Moon(x, y, z))
+
+ for _ in range(1000):
+ for pair in itertools.permutations(moons, 2):
+ pair[0].gravity(pair[1])
+ for moon in moons:
+ moon.step()
+
+ tot = 0
+ for moon in moons:
+ pot = abs(moon.x) + abs(moon.y) + abs(moon.z)
+ kin = abs(moon.dx) + abs(moon.dy) + abs(moon.dz)
+ tot += pot*kin
+ return tot
+
+def get_cycle(init_pos, init_vel):
+ initial = tuple(init_pos)
+ pos = init_pos.copy()
+ vel = init_vel.copy()
+ iters = 0
+ while 1:
+ for i, j in itertools.permutations(range(4), 2):
+ if i == j:
+ continue
+ if pos[i] < pos[j]:
+ vel[i] += 1
+ vel[j] -= 1
+ for i in range(4):
+ pos[i] += vel[i]
+ iters += 1
+ if pos[0] == initial[0] and pos[1] == initial[1] and \
+ pos[2] == initial[2] and pos[3] == initial[3] and \
+ vel[0] == 0 and vel[1] == 0 and \
+ vel[2] == 0 and vel[3] == 0:
+ return iters
+
+def pt2(input):
+ return
+ moons = []
+ xs = 0
+ ys = 0
+ zs = 0
+
+ for line in input:
+ dims = line.rstrip().split(",")
+ x = int(dims[0][3:])
+ y = int(dims[1][3:])
+ z = int(dims[2][3:-1])
+ moons.append(Moon(x, y, z))
+
+ xs = get_cycle([moon.x for moon in moons], [0 for _ in range(4)])
+ ys = get_cycle([moon.y for moon in moons], [0 for _ in range(4)])
+ zs = get_cycle([moon.z for moon in moons], [0 for _ in range(4)])
+
+ factors = [primefac.factorint(n) for n in (xs, ys, zs)]
+ nums = {}
+ for factor in factors:
+ for n in factor:
+ nums[n] = max(nums.get(n, 0), factor[n])
+ ans = 1
+ for n in nums:
+ ans *= n ** nums[n]
+ return ans
+
+if __name__ == "__main__":
+ input = open("../input/12", "r").readlines()
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d13.py b/19/py/d13.py
new file mode 100644
index 0000000..3dbc5fb
--- /dev/null
+++ b/19/py/d13.py
@@ -0,0 +1,132 @@
+import intcode
+import queue
+import time
+
+def pt1(input):
+ c = intcode.Computer([int(x) for x in input[0].split(",")])
+ buffer_out = []
+ screen = {}
+ while c.memory[c.pointer] != 99:
+ c.step()
+ if c.output is not None:
+ buffer_out.append(c.output)
+ c.output = None
+ if len(buffer_out) == 3:
+ screen[(buffer_out[0], buffer_out[1])] = buffer_out[2]
+ buffer_out = []
+ blocks = 0
+ for p in screen:
+ if screen[p] == 2:
+ blocks += 1
+ return blocks
+
+
+def pt2(input):
+ def draw(screen, points):
+ ball_x = 0
+ paddle_x = 0
+ min_x = max_x = min_y = max_y = 0
+ for p in screen:
+ if p == (-1,0):
+ points = screen[p]
+ elif screen[p] == 3:
+ paddle_x = p[0]
+ elif screen[p] == 4:
+ ball_x = p[0]
+ return points, ball_x, paddle_x
+
+ c = intcode.Computer([int(x) for x in input[0].split(",")])
+ c.memory[0] = 2
+
+ screen = {}
+ buffer_out = []
+ points = 0
+ ball_x = paddle_x = 0
+
+ while c.memory[c.pointer] != 99:
+ if c.SIG_INPUT:
+ points, ball_x, paddle_x = draw(screen, points)
+ if paddle_x < ball_x:
+ c.input = 1
+ elif paddle_x > ball_x:
+ c.input = -1
+ else:
+ c.input = 0
+ c.step()
+ if c.output is not None:
+ buffer_out.append(c.output)
+ c.output = None
+ if len(buffer_out) == 3:
+ screen[(buffer_out[0], buffer_out[1])] = buffer_out[2]
+ buffer_out = []
+ return c.memory[386]
+
+def visualize(input):
+ def draw(screen, points):
+ ball_x = 0
+ paddle_x = 0
+ min_x = max_x = min_y = max_y = 0
+ for p in screen:
+ min_x = min(min_x, p[0])
+ max_x = max(max_x, p[0])
+ min_y = min(min_y, p[1])
+ max_y = max(max_y, p[1])
+ s = ""
+ for y in range(min_y-1, max_y+1):
+ for x in range(min_x-1, max_x+1):
+ if (x,y) in screen:
+ if (x,y) == (-1,0):
+ points = screen[(x,y)]
+ elif screen[(x,y)] == 0:
+ s += " "
+ elif screen[(x,y)] == 1:
+ s += "\u2588"
+ elif screen[(x,y)] == 2:
+ s += "#"
+ elif screen[(x,y)] == 3:
+ s += "-"
+ paddle_x = x
+ elif screen[(x,y)] == 4:
+ s += "O"
+ ball_x = x
+ else: # (x,y) not in screen
+ s += " "
+ s += "\n"
+ return s, points, ball_x, paddle_x
+
+ c = intcode.Computer([int(x) for x in input[0].split(",")])
+ c.memory[0] = 2
+
+ screen = {}
+ buffer_out = []
+ frame_n = 0
+ points = 0
+ ball_x = paddle_x = 0
+
+ while c.memory[c.pointer] != 99:
+ if c.SIG_INPUT:
+ time.sleep(0.01)
+ frame_n += 1
+ frame, points, ball_x, paddle_x = draw(screen, points)
+ print(frame)
+ if paddle_x < ball_x:
+ c.input = 1
+ elif paddle_x > ball_x:
+ c.input = -1
+ else:
+ c.input = 0
+ c.step()
+ if c.output is not None:
+ buffer_out.append(c.output)
+ c.output = None
+ if len(buffer_out) == 3:
+ screen[(buffer_out[0], buffer_out[1])] = buffer_out[2]
+ buffer_out = []
+
+if __name__ == "__main__":
+ import cProfile
+
+ _input = open("../input/13", "r").readlines()
+ print(pt1(_input))
+ print(pt2(_input))
+ #visualize(_input)
diff --git a/19/py/d14.py b/19/py/d14.py
new file mode 100644
index 0000000..1d628a4
--- /dev/null
+++ b/19/py/d14.py
@@ -0,0 +1,77 @@
+import math
+
+class Chem(object):
+ def __init__(self, name, created):
+ self.name = name
+ self.created = created
+
+ self.amount = 0
+ self.left_over = 0
+ self.producers = {}
+
+ def add_producer(self, producer, amount):
+ self.producers[producer] = amount
+
+ def produce(self, to_create):
+ if self.name == "ORE":
+ self.amount += to_create
+ return
+ if self.left_over > 0:
+ if self.left_over < to_create:
+ to_create -= self.left_over
+ self.left_over = 0
+ else:
+ self.left_over -= to_create
+ to_create = 0
+ productions = math.ceil(to_create / self.created)
+ self.amount += productions * self.created
+ self.left_over += productions * self.created - to_create
+ for producer, amount in self.producers.items():
+ producer.produce(productions * amount)
+
+ def __repr__(self):
+ return str((self.name, self.amount))
+
+def read_chems(input):
+ chems = {"ORE": Chem("ORE", 1)}
+ for line in input:
+ output = line.strip().split(" => ")[1]
+ chems[output.split(" ")[1]] = Chem(output.split(" ")[1], int(output.split(" ")[0]))
+
+ for line in input:
+ inputs = line.strip().split(" => ")[0]
+ output = line.strip().split(" => ")[1]
+ for i in inputs.split(", "):
+ chems[output.split(" ")[1]] \
+ .add_producer(chems[i.split(" ")[1]], int(i.split(" ")[0]))
+ return chems
+
+def pt1(input, amount=1):
+ chems = read_chems(input)
+ chems["FUEL"].produce(amount)
+ return chems["ORE"].amount
+
+def pt2(input):
+ low, high = 0, int(1e9)
+ target = 1000000000000
+ prev_guess = 0
+ while low != high:
+ guess = (low+high) // 2
+ if guess == prev_guess:
+ break
+ prev_guess = guess
+ chems = read_chems(input)
+ chems["FUEL"].produce(guess)
+ if chems["ORE"].amount == target:
+ break
+ elif chems["ORE"].amount > target:
+ high = guess
+ else:
+ low = guess
+ #print(low, guess, high)
+ return guess
+
+if __name__ == "__main__":
+ input = open("../input/14", "r").readlines()
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/d15.py b/19/py/d15.py
new file mode 100644
index 0000000..b2a9b10
--- /dev/null
+++ b/19/py/d15.py
@@ -0,0 +1,276 @@
+import intcode
+import heapq as heap
+import collections
+import time
+
+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, draw_search=False):
+ 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)
+ if draw_search:
+ print(draw(board, path=cur[2], visited=visited))
+ return cur[2]
+ if n in visited or n not in board or board[n] == "#":
+ continue
+ new_path = collections.deque(cur[2])
+ new_path.append(n)
+ visited.add(n)
+ 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(",")])
+
+ 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
+ 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[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
+ 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
+
+ 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
+ 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
+ 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.005)
+ print(draw(board, droid=(cur_x, cur_y)))
+ c.output = None
+
+ 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
+ steps += 1
+
+if __name__ == "__main__":
+ input = open("../input/15", "r").readlines()
+ print(pt1(input))
+ print(pt2(input))
+ visualize(input)
diff --git a/19/py/d16.py b/19/py/d16.py
new file mode 100644
index 0000000..93b52d2
--- /dev/null
+++ b/19/py/d16.py
@@ -0,0 +1,46 @@
+def do(input, phases=100, repeats=1):
+ nums = []
+ for i in range(repeats):
+ nums += [int(x) for x in input[0].strip()]
+
+ for phase in range(phases):
+ #print(phase)
+ new_list = []
+ for i in range(len(nums)): # position of number to calculate
+ new_num = 0
+ for k in range(len(nums)):
+ mod = (k+1) % (4*(i+1))
+ if mod >= i + 1 and mod < 2*i + 2:
+ new_num += nums[k]
+ elif mod >= 3*i + 3:
+ new_num -= nums[k]
+ new_list.append(abs(new_num) % 10)
+ nums = new_list
+ return "".join([str(n) for n in nums[:8]])
+
+def pt1(input):
+ return do(input, phases=100, repeats=1)
+
+def pt2(input, phases=100, repeats=10000):
+ offset = int(input[0][:7])
+ nums = []
+ for i in range(repeats):
+ nums += [int(x) for x in input[0].strip()]
+ nums = nums[offset:]
+ for phase in range(phases):
+ #print(phase)
+ nums = nums[::-1]
+ new_nums = []
+ n = sum(nums)
+ while len(nums) != 0:
+ new_nums.append(abs(n) % 10)
+ n -= nums.pop()
+ nums = new_nums
+ return "".join([str(n) for n in nums[:8]])
+
+if __name__ == "__main__":
+ input = open("../input/16", "r").readlines()
+ ans1 = pt1(input)
+ ans2 = pt2(input)
+ print(ans1)
+ print(ans2)
diff --git a/19/py/d17.py b/19/py/d17.py
new file mode 100644
index 0000000..b12e03a
--- /dev/null
+++ b/19/py/d17.py
@@ -0,0 +1,305 @@
+import intcode
+from collections import deque
+import heapq as heap
+import time
+
+def draw(view, intersections={}, robot=None, direction=None):
+ min_x=max_x=min_y=max_y = 0
+ for p in view:
+ 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, max_y+1):
+ s += "\n"
+ for x in range(min_x, max_x+1):
+ point = (x, y)
+ if robot is not None and point == robot:
+ if direction == 0:
+ s += ">"
+ elif direction == 1:
+ s += "v"
+ elif direction == 2:
+ s += "<"
+ elif direction == 3:
+ s += "^"
+ else:
+ s += "D"
+ elif point in intersections:
+ s += "O"
+ elif point in view:
+ s += view[point] * 1
+ else:
+ s += " " * 1
+ 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_infront(robot, direction):
+ dx=dy = 0
+ if direction == 0:
+ dx = 1
+ elif direction == 1:
+ dy = 1
+ elif direction == 2:
+ dx = -1
+ else:
+ dy = -1
+ return (robot[0]+dx, robot[1]+dy)
+
+def get_behind(robot, direction):
+ dx=dy = 0
+ if direction == 0:
+ dx = -1
+ elif direction == 1:
+ dy = -1
+ elif direction == 2:
+ dx = 1
+ else:
+ dy = 1
+ return (robot[0]+dx, robot[1]+dy)
+
+def get_turn(robot, direction, point):
+ dx = point[0] - robot[0]
+ dy = point[1] - robot[1]
+ if dx == 1:
+ turn_direction = 0
+ elif dy == 1:
+ turn_direction = 1
+ elif dx == -1:
+ turn_direction = 2
+ else:
+ turn_direction = 3
+ if direction == turn_direction:
+ return None
+ if (direction + 1) % 4 == turn_direction:
+ return "R"
+ elif (direction - 1) % 4 == turn_direction:
+ return "L"
+ else:
+ return False
+
+def get_direction(direction, turn):
+ if turn == "L":
+ return (direction - 1) % 4
+ elif turn == "R":
+ return (direction + 1) % 4
+ else:
+ return False
+
+def get_turnable_points(scaffolds, robot, direction):
+ valid = set()
+ for n in neighbours(robot):
+ if n in scaffolds and n != get_behind(robot, direction):
+ valid.add(n)
+ return list(valid)
+
+def pt1(input):
+ c = intcode.Computer([int(x) for x in open("../input/17", "r").readlines()[0].split(",")])
+
+ view = {}
+ scaffolds = []
+ buffer = ""
+ x=y = 0
+ while not c.SIG_HALT:
+ c.step()
+ if c.SIG_INPUT:
+ print("input??")
+ break
+ if c.SIG_OUTPUT:
+ if c.output == 10:
+ y += 1
+ x = 0
+ elif c.output == 35:
+ view[(x,y)] = "#"
+ scaffolds.append((x,y))
+ x += 1
+ elif c.output == 46:
+ view[(x,y)] = "."
+ x += 1
+ else:
+ view[(x,y)] = "#"
+ scaffolds.append((x,y))
+ robot = (x,y)
+ if c.output == 60: # <
+ direction = 2
+ elif c.output == 62: # >
+ direction = 0
+ elif c.output == 94: # ^
+ direction = 3
+ elif c.output == 86 or c.output == 118: # V or v
+ direction = 1
+ else:
+ print("????????????????")
+ break
+ x += 1
+ buffer = ""
+ c.output = None
+ c.SIG_OUTPUT = False
+ #print(draw(view))
+
+ intersections = set()
+ al_sum = 0
+ for s in scaffolds:
+ ns = 0
+ for n in neighbours(s):
+ if n in scaffolds:
+ ns += 1
+ if ns == 4:
+ intersections.add(s)
+ al_sum += s[0] * s[1]
+ #print(intersections)
+ #print(draw(view, intersections=intersections, robot=robot, direction=direction))
+ return al_sum
+
+def pt2(input):
+ c = intcode.Computer([int(x) for x in open("../input/17", "r").readlines()[0].split(",")])
+
+ view = {}
+ scaffolds = []
+ buffer = ""
+ x=y = 0
+ while not c.SIG_HALT:
+ c.step()
+ if c.SIG_INPUT:
+ print("input??")
+ break
+ if c.SIG_OUTPUT:
+ if c.output == 10:
+ y += 1
+ x = 0
+ elif c.output == 35:
+ view[(x,y)] = "#"
+ scaffolds.append((x,y))
+ x += 1
+ elif c.output == 46:
+ view[(x,y)] = "."
+ x += 1
+ else:
+ view[(x,y)] = "#"
+ scaffolds.append((x,y))
+ robot = (x,y)
+ if c.output == 60: # <
+ direction = 2
+ elif c.output == 62: # >
+ direction = 0
+ elif c.output == 94: # ^
+ direction = 3
+ elif c.output == 86 or c.output == 118: # V or v
+ direction = 1
+ else:
+ print("????????????????")
+ break
+ x += 1
+ buffer = ""
+ c.output = None
+ c.SIG_OUTPUT = False
+ #print(draw(view))
+
+ intersections = set()
+ for s in scaffolds:
+ ns = 0
+ for n in neighbours(s):
+ if n in scaffolds:
+ ns += 1
+ if ns == 4:
+ intersections.add(s)
+
+ '''
+ For each path, take steps until a wall is reached. When a wall is reached, tuirn
+ towards the next unvisited point. Repeat until the end is reached.
+
+ Structure of a deque-element:
+ Each search-element consists of a single tuple. The tuple contains
+ - The robot's position
+ - The robot's direction (after turning)
+ - The instruction-set up to that point
+ - The current WIP instruction
+ - All points that have been visited (as a set)
+
+ Structure of the instruction-set:
+ The instruction-set consists of a list of tuples. The tuples contain
+ - A turn-instruction
+ - The number of steps to take (after turning)
+ For example:
+ [(R,8), (R,8), (R,4), (R,4), (R,8)]
+ '''
+
+ current = None
+ direction = 2
+ paths = deque()
+ visited = set()
+ visited.add(robot)
+ paths.append((robot, direction, [], ["L", 0], visited))
+ while True:
+ if current is None:
+ current = paths.popleft()
+ robot = current[0]
+ direction = current[1]
+ instruction_set = current[2]
+ wip_instruction = current[3]
+ visited = current[4].copy()
+ if len(visited) == len(scaffolds):
+ #print("len(visited) == len(scaffolds)")
+ instruction_set.append(wip_instruction)
+ break
+ if get_infront(robot, direction) not in scaffolds:
+ # wall in front. save
+ instruction_set.append(wip_instruction)
+ avail_points = get_turnable_points(scaffolds, robot, direction)
+ if len(avail_points) == 0:
+ if len(visited) == len(scaffolds):
+ break
+ else:
+ current = None
+ continue
+ wip_instruction = [get_turn(robot, direction, avail_points[0]), 0]
+ direction = get_direction(direction, get_turn(robot, direction, avail_points[0]))
+ paths.append((robot, direction, instruction_set, wip_instruction, visited))
+ current = None
+ else: # wall not in front
+ '''
+ if robot in intersections and wip_instruction[1] != 0:
+ # queue intersections
+ new_instruction_set = instruction_set.copy()
+ new_instruction_set.append(wip_instruction.copy())
+ paths.append((robot, get_direction(direction, "L"), \
+ new_instruction_set.copy(), ["L", 0], visited))
+ paths.append((robot, get_direction(direction, "R"), \
+ new_instruction_set.copy(), ["R", 0], visited))
+ '''
+ # take step
+ robot = get_infront(robot, direction)
+ visited.add(robot)
+ wip_instruction[1] += 1
+
+ #print(instruction_set)
+ s = ""
+ for instruction in instruction_set:
+ s += str(instruction[0]) + "," + str(instruction[1]) + "\n"
+ #print(s)
+
+ c.reset()
+ c.memory[0] = 2
+ c.queue_ascii("A,A,B,C,C,A,C,B,C,B")
+ c.queue_ascii("L,4,L,4,L,6,R,10,L,6")
+ c.queue_ascii("L,12,L,6,R,10,L,6")
+ c.queue_ascii("R,8,R,10,L,6")
+ c.queue_ascii("n")
+ c.SIG_ASCII = True
+ output = []
+ while not c.SIG_HALT:
+ c.step()
+ if c.SIG_OUTPUT:
+ output.append(c.output)
+ c.output = None
+ c.SIG_OUTPUT = False
+ return output[-1]
+
+if __name__ == "__main__":
+ input = open("../input/17", "r")
+ print(pt1(input))
+ print(pt2(input))
diff --git a/19/py/intcode.py b/19/py/intcode.py
new file mode 100644
index 0000000..6079250
--- /dev/null
+++ b/19/py/intcode.py
@@ -0,0 +1,153 @@
+from collections import deque
+param_amount = {1:3, 2:3, 3:1, 4:1, 5:2, 6:2, 7:3, 8:3, 9:1, 99:0}
+
+ADD = 1
+MUL = 2
+IN = 3
+OUT = 4
+JNZ = 5
+JEZ = 6
+LET = 7
+EQV = 8
+BAS = 9
+HAL = 99
+
+class Computer(object):
+ def __init__(self, program):
+ self.program = program
+ self.memory_size = len(self.program)
+
+ self.reset()
+
+ def reset(self):
+ self.memory = self.program.copy()
+ self.extra_memory = {}
+ self.instruction_cache = {}
+ self.pointer = 0
+ self.phase_read = False # for day 7
+ self.relative_base = 0
+
+ self.input = None
+ self.input_queue = deque()
+ self.output = None
+
+ self.SIG_INPUT = False
+ self.SIG_ASCII = False
+ self.SIG_OUTPUT = False
+ self.SIG_HALT = False
+
+ def parse_op(self, op):
+ # if op in self.instruction_cache:
+ # return self.instruction_cache[op]
+ code = op % 100
+ ops = str(op).zfill(param_amount[code]+2)
+ self.instruction_cache[op] = [code] + [int(x) for x in ops[:-2][::-1]]
+ return self.instruction_cache[op]
+ #return [code] + [(op // 10**(i+2)) % 10**(i+1) for i in range(param_amount[code])]
+
+ def clear_flags(self):
+ self.input = None
+ self.output = None
+
+ def write(self, addr, val):
+ if addr >= self.memory_size:
+ self.extra_memory[addr] = val
+ else:
+ self.memory[addr] = val
+
+ def get(self, addr):
+ if addr >= self.memory_size:
+ return self.extra_memory.get(addr, 0)
+ return self.memory[addr]
+
+ def get_param(self, inst, num):
+ if inst[num] == 0:
+ return self.get(self.get(self.pointer + num))
+ elif inst[num] == 1:
+ return self.get(self.pointer + num)
+ elif inst[num] == 2:
+ return self.get(self.relative_base + self.get(self.pointer + num))
+
+ def write_param(self, inst, num, val):
+ if inst[num] == 0:
+ self.write(self.get(self.pointer + num), val)
+ elif inst[num] == 1:
+ self.write(self.pointer + num, val)
+ elif inst[num] == 2:
+ self.write(self.relative_base + self.get(self.pointer + num), val)
+
+ def queue_input(self, data: list):
+ for val in data:
+ self.input_queue.append(data)
+
+ def queue_ascii(self, data: str, newline=True):
+ for c in data:
+ if c == "\n":
+ self.input_queue.append(10)
+ else:
+ self.input_queue.append(ord(c))
+ if newline:
+ self.input_queue.append(10)
+
+ def step(self):
+ if self.SIG_OUTPUT and self.output is None:
+ self.SIG_OUTPUT = False
+ if self.SIG_INPUT and self.input is not None:
+ self.SIG_INPUT = False
+
+ inst = self.parse_op(self.memory[self.pointer])
+ if inst[0] == HAL:
+ self.SIG_HALT = True
+ return
+ elif inst[0] == ADD:
+ self.write_param(inst, 3, \
+ self.get_param(inst, 1) + self.get_param(inst, 2))
+ self.pointer += 4
+ elif inst[0] == MUL:
+ self.write_param(inst, 3, \
+ self.get_param(inst, 1) * self.get_param(inst, 2))
+ self.pointer += 4
+ elif inst[0] == IN:
+ if self.SIG_ASCII and len(self.input_queue) != 0:
+ self.input = self.input_queue.popleft()
+ if self.input is None:
+ self.SIG_INPUT = True
+ return
+ self.write_param(inst, 1, self.input)
+ self.input = None
+ self.SIG_INPUT = False
+ self.pointer += 2
+ elif inst[0] == OUT:
+ if self.SIG_OUTPUT:
+ return
+ self.output = self.get_param(inst, 1)
+ self.SIG_OUTPUT = True
+ self.pointer += 2
+ elif inst[0] == JNZ:
+ if self.get_param(inst, 1) != 0:
+ self.pointer = self.get_param(inst, 2)
+ else:
+ self.pointer += 3
+ elif inst[0] == JEZ:
+ if self.get_param(inst, 1) == 0:
+ self.pointer = self.get_param(inst, 2)
+ else:
+ self.pointer += 3
+ elif inst[0] == LET:
+ self.write_param(inst, 3, 1 if \
+ self.get_param(inst, 1) < self.get_param(inst, 2) \
+ else 0)
+ self.pointer += 4
+ elif inst[0] == EQV:
+ self.write_param(inst, 3, 1 if \
+ self.get_param(inst, 1) == self.get_param(inst, 2) \
+ else 0)
+ self.pointer += 4
+ elif inst[0] == BAS:
+ self.relative_base += self.get_param(inst, 1)
+ self.pointer += 2
+ else:
+ print(self.memory)
+ print(self.pointer)
+ print("invalid instruction", self.memory[self.pointer])
+ print(inst)
diff --git a/19/py/main.py b/19/py/main.py
new file mode 100644
index 0000000..c45bac7
--- /dev/null
+++ b/19/py/main.py
@@ -0,0 +1,52 @@
+import time
+
+import d01
+import d02
+import d03
+import d04
+import d05
+import d06
+import d07
+import d08
+import d09
+import d10
+import d11
+import d12
+import d13
+import d14
+import d15
+import d16
+import d17
+
+mods = [d01, d02, d03, d04, d05, d06, d07, d08, d09, d10, \
+ d11, d12, d13, d14, d15, d16, d17]
+
+skip = [12, 16]
+
+timings = [[0 for _ in range(2)] for _ in range(len(mods))]
+#clock_type = time.CLOCK_MONOTONIC
+
+for mod, day in zip(mods, range(len(mods))):
+ if day+1 in skip:
+ continue
+ print("Day", str(day+1).zfill(2))
+ #t0 = time.clock_gettime_ns(clock_type)
+ print("Part", 1, mod.pt1(open("../input/" + str(day+1).zfill(2), "r").readlines()))
+ #timings[day][0] = time.clock_gettime_ns(clock_type) - t0
+ #t0 = time.clock_gettime_ns(clock_type)
+ print("Part", 2, mod.pt2(open("../input/" + str(day+1).zfill(2), "r").readlines()))
+ #timings[day][1] = time.clock_gettime_ns(clock_type) - t0
+
+#print()
+#tot = 0
+#for day in range(len(timings)):
+# for part in range(2):
+# tot += timings[day][part]
+#for day in range(len(timings)):
+# if day+1 in skip:
+# print("day {0} skipped".format(str(day+1)))
+# else:
+# for part in range(2):
+# print("day {0}-{1}: {2:.2f}ms\t({3:.1f}%)".format(str(day+1).zfill(2), part+1, \
+# timings[day][part] / 1000000, 100*timings[day][part] / tot))
+#print("sum", tot / 1000000, "ms")
generated by cgit v1.2.1 (git 2.18.0) at 2025-12-14 05:57:36 +0100