WIP Day 18

3 files changed, 416 insertions, 0 deletions

diff --git a/19/input/18 b/19/input/18
new file mode 100644
index 0000000..a9ec2f1
--- /dev/null
+++ b/19/input/18
@@ -0,0 +1,81 @@
+#################################################################################
+#..........c#.............E.......#.....#.....#...#.........#...#...............#
+#.#########.#.#.#################.#.#####.#.#.#.#.#.#######.#.#.#.#########.#####
+#.#...R...#.#.#.#.#.....#.....#.#.#....t#.#.#.#.#.#.#.....#...#...#.......#.....#
+###.#####.#.#G#.#.#.#.###.#.#.#.#.#####.###.###.#.#.###.#.###############.#####.#
+#...#.....#...#.#...#.....#.#...#.....#.#...#...#.#...#.#p........#...........#.#
+#.#####.#######.#####.#####.#########V#.#.###.###.###.#.#######.#.#.#####.#####.#
+#.#...#.....#...#...#.....#...#...#...#.#...#...#...#.#.#.....#.#.#.....#.#.....#
+#.#.#W#####.#.###.#.#########.#.#.#.###.#.#.###.###.#.###.###.#.#.#.###.###.###.#
+#...#.#.#...#.#...#.....#.....#.#...#...#.#...#.#.#.#...#.#...#.#.#...#.#...#.#.#
+#####.#.#.###.#.#.#####.#.#.###.#####.###.#.#.#.#.#.###.#.#.###.#.#####.#.###.#.#
+#.....#.#...#.#d#.#...#o#.#.#...#.#.....#.#.#.#.#.#...#j#.#x#...#.......#.#.#...#
+#.#####.###.#.#.###.#.#.#.###.###.#.###.#.#.#.#.#.###.#.#.#.#.###.#####.#.#.#.###
+#.....#...#...#.....#.#.#...#.#.....#...#.#.#.#.....#.#...#...#...#...#.#.#.#.#.#
+#.###.###.###.#######.#.#.#.#.#####.#.###.#.#######.#.#####.#####.#.#.###.#.#.#.#
+#.#.#...#.....#...#...#.#.#.#.....#.#...#.#.#.......#...#...#...#.#.#.....#.#.#.#
+#.#A###.#.#######.#.###Q###.#####.#####.#.#.#.#######.###.###.#.###.#######.#.#.#
+#.#...#.#.........#...#...#...#...#.....#.#.........#.....#.#.#...#.#.......#w#.#
+#.#.#.#.#########.###.###.###.#.###.###.#####.###########.#.#.###.#.#####.#.#.#.#
+#...#.#...#.......#..s#.....#.#...#.#.#.#...#.#.........#...#.#...#.#...#.#...#.#
+###.#####.#########.#######.#.###.#.#.#.#.#.#.#.#######.###.#.#.###.#.#.###.###.#
+#...#...#.......#...#...#...#...#...#...#.#.#.#.#...#...#...#.#...#...#...#.....#
+#.###.#.#######.#.#.###.#.#####.#####.###.#.###.#.#.#.#.#########.#.#####.#####.#
+#n..#.#.......#.#.#...#.#.....#.....#...#.#.....#.#.#.#.#.....#...#.....#.....#a#
+###.#.#######.#.#.#####.#####.#.###.###.#.#######.#.#.#.#.#.###.#######.#####.#.#
+#...#.#.....#...#.....#.#...#.#...#...#.#.#.....#.#...#.#.#.#...#.....#.....#.#.#
+#.###.#.###.#########.#K#.###B###.#####.#.#.###.#.#######.#.#.#####.#.#####.#.#.#
+#.#.#.....#.#.......#...#...#...#...#...#.#...#.#.....#...#...#...#.#...#...#.#.#
+#.#.#######.#.#####.#######.###.###.#.###.###.#.#####.#.#######.#.#.#.###.###.#.#
+#...#...#...#...#i#...#.......#...#.....#.#...#.#...#...#.....#.#.#.#.#...#.#.#.#
+###.#.###.#####.#.#.###.#.#######.#####.#.#.#####.#.#####.###.#.#.#.#.#.###.#.#.#
+#...#.#...#.....#.#...#.#.......#...#...#.#.......#.....#...#...#.#.#.......#.#.#
+#.###.#.#.#.#####.###.#.#######.###.#.###.#######.###.#.###.#####.###.#######.###
+#.#...#.#.#.#.....#...#...#.#...#...#...#...#...#...#.#.....#...#...#.#.....#...#
+#.###.#.###.#.###.#.#.###.#.#.###.#####.###.#.#.###.#.#######.#.###.###.###.###.#
+#...#.#.#...#..z#.#.#...#.#.#...#.#.....#...#.#.#...#.....#.#.#...#.....#.#...#.#
+###.#.#.#.###.#.#.#.#####.#.###.#.#.#####.###.#.#########.#.#.###.#######.###.#.#
+#.#...#.#...#.#.#.#.......#...#...#...#.#.....#.........#.#.#.#...#.......#...#.#
+#.###.#.###.#.#.###########.#.#######.#.###############.#.#.#.#.###.#.#####.###.#
+#.....#.....#.#.......H.....#........................h....#...#.....#...........#
+#######################################.@.#######################################
+#....m....#.#.........#.....#.............#...#...............#.........#.......#
+#.#.#####.#.#.#######.#.#####.###.#####.#.#.#.#.#.#.###########.#####.#.#.#.#####
+#.#.#.....#.#...#...#.#.#.....#.#.#...#.#.#.#...#.#.#.....#.....#.I...#...#.#...#
+#.#.###.###.###.#.#.#.#.#.#####.#.#.#.#.#.#.#####.###.###.#.#####.#####.#####.#.#
+#.#...#.......#.#.#...#.#.......#.#.#.#.#...#...#.......#...#.....#...#.#.....#.#
+#.###.#######.#.#.#####.#######.#.#.#.#.#####.#.#######.#####.#####.###.#.#####.#
+#...#.....#...#.#.#.......#.....#...#.#.#.....#.....#.#.#...#.....#.....#.#....b#
+#.#######.#.###.#.#######.#.#########.###.#########.#.#.###.#####.#.#####.#.#####
+#.#.......#u..#.#.......#.#...#.#...#...#.#...#.#...#.......Z.#...#...#q..#.#...#
+###.###########.#######.#.###.#.#.#.#.#.#.#.#.#.#.###.#########.#######.###.#.#.#
+#...#.L.......#...#...#.#...#...#.#.#.#.#...#.#.#.#...#.........#.......#...#.#.#
+#.###.#######.###.###.#.#.#.#.###.#.###.#####.#.#.#.###.#####.###.#######U#####.#
+#y....#.....#...#.....#.#.#...#...#.....#.....#.#.#...#...#.#.#...#.....#.......#
+#.#####.#######.#####.#.#######.#######.#.#####.#.#######.#.#.#.#####.#########.#
+#.#..f..#.......#.....#...#.....#.....#.#...#.......#.....#...#.#...#.#.......#.#
+#.#.#####.#####.#.#######.#.#####.###.#.#.#.#######.#.#######.#.#.#.#M#.###.###.#
+#.#.#...#.....#.#...#.....#...#.....#.#.#.#.....#.#.#.#.....#.#.#.#...#...#.....#
+#.#.#.#.#.###.#.###.#.#####.#.#####.###.#######.#.#.#.#.###.###.#.#.#####.#######
+#...#.#.#...#.#...#.#.#...#.#.....#.#...#.......#.#...#.#.#.....#.#.#.F...#.....#
+#####.#.###.#.#####.#.#.###.#####.#.#.###.#######.#.###.#.#.#####.###.#######.#Y#
+#.....#...#.#.....#.#.#...#.....#.#.#...#.....#...#.#...#.#.#.#.......#.......#.#
+#.#######.#######.#.###.#.###.###.#.###.#.###.#.###.#.###.#.#.#######.###.#####.#
+#.#...............#...#.#.#...#...#.....#...#.#.#...#.#...O.#.......#.....#.....#
+#.#############.#####.#.#.#.###.###.#######.#.#.#.###D#############.#######.#####
+#.........#...#.#...#.#.#...#.#.#.#.#...#...#.#.#...#.....#.......#...#...#.....#
+#########.#.#.###.#.#.#.#####.#.#.#.#.#######.#C###.#####.#.#.#######.###.#####.#
+#.....#...#.#...#r#.#.#.......#.#.#.#...#.....#...#.#...#...#.S.#..k..#.....#...#
+#.###.#.#.#.###.#.#.#.#########.#.#.#.#.#.#####.#.#.###.#######.#.#####.#####.###
+#.#.#.#.#.#.#.#...#.#.#...#...#.#...#.#.#.#.....#.#.....#.....#...#...........#.#
+#.#.#.#.#.#.#.#####.#.#.#.#.#.#.#.#####.#.#.#.#####.#####.###.#####.###########.#
+#.#.....#.#...#.#...#.#.#.#.#v..#.......#.#.#.#.....#...#...#.#...#...#.......#.#
+#.###########.#.#.#.#.#.#.#.###########.#.###.#.#####.#.###.#.#.#.###.#.#.###.#P#
+#...............#.#.#..e#...#...#.T.....#...#.#.#.....#...#.#...#.....#.#.#l#...#
+#.###############.#.#########.###.#######.#.#.#.#.#######.#.###########.#.#.###.#
+#.#.........#.....#.#...#.......#.#.....#.#.#...#.#.....#...#.J...#...#.#.#.....#
+#.#######.#.#.#######.#.#.#####.#.#.###.#.#.#####.#.###.#####.###.###.#.#.###.###
+#.........#.#.....#...#.#.....#...#.#.#.#.#.#.....#.#.........#.#...#...#.X.#...#
+###########.#####.#.###.#####.#####.#.#.#.#.#.#######.#########.###.#######.###.#
+#...............#.....#.............#..g#.#.......N...#.....................#...#
+#################################################################################
diff --git a/19/py/d18.gv b/19/py/d18.gv
new file mode 100644
index 0000000..f4892e4
--- /dev/null
+++ b/19/py/d18.gv
@@ -0,0 +1,89 @@
+graph G {
+c -- G
+E -- V
+E -- G
+E -- R
+R -- W
+R -- G
+t -- V
+t -- h
+t -- H
+t -- Z
+t -- I
+t -- T
+t -- v
+p -- x
+V -- h
+V -- H
+V -- Z
+V -- I
+V -- T
+V -- v
+W -- A
+W -- n
+W -- B
+d -- o
+d -- s
+o -- Q
+j -- x
+j -- w
+j -- h
+A -- n
+A -- B
+Q -- B
+w -- a
+w -- h
+s -- K
+n -- B
+i -- z
+z -- H
+H -- h
+H -- Z
+H -- I
+H -- T
+H -- v
+h -- Z
+h -- I
+h -- T
+h -- v
+m -- u
+m -- y
+I -- Z
+I -- C
+I -- T
+I -- v
+I -- N
+I -- Y
+b -- U
+b -- q
+Z -- T
+Z -- v
+q -- O
+q -- D
+L -- y
+L -- r
+U -- F
+y -- f
+M -- F
+M -- Y
+F -- Y
+Y -- N
+Y -- C
+O -- D
+D -- S
+C -- N
+r -- g
+r -- T
+S -- k
+v -- e
+v -- T
+P -- l
+P -- X
+T -- g
+l -- X
+J -- N
+J -- X
+start -- h
+start -- t
+start -- v
+}
diff --git a/19/py/d18.py b/19/py/d18.py
new file mode 100644
index 0000000..61a5cb0
--- /dev/null
+++ b/19/py/d18.py
@@ -0,0 +1,246 @@
+import time
+import collections
+import heapq as heap
+import sys
+
+f = open("../input/18", "r").readlines()
+
+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 path(start: tuple, end:tuple, board:dict, keys={}, doors={}, draw_search=False):
+    ''' Find the shortest path between two points '''
+    if start == end:
+        return collections.deque()
+    visited = set()
+    h = []
+    heap.heappush(h, (0, start, collections.deque()))
+    while True:
+        if len(h) == 0:
+            print(visited)
+            return
+        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
+            if n in keys or n in doors:
+                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.0075)
+                print(draw(board, keys=keys, doors=doors, path=new_path, visited=visited))
+                print(end)
+                print(n)
+
+def avail_keys(map: dict, pos: tuple, keys: dict, visited_keys: set, doors: dict, dead=set(), draw_search=False) -> list:
+    ''' Return a list of tuples consisting of ( dist, pos ) '''
+    visited = set()
+    avail = []
+    q = collections.deque()
+    q.append((0, pos))
+    while len(q) != 0:
+        cur = q.popleft()
+        if cur[1] in keys and keys[cur[1]] not in visited_keys:
+            avail.append(cur)
+            continue
+        for n in neighbours(cur[1]):
+            if n in map and map[n] == "#":
+                continue
+            if n in dead:
+                continue
+            if n in doors and doors[n].lower() not in visited_keys:
+                continue
+            if n in visited:
+                continue
+            visited.add(n)
+            q.append((cur[0]+1, n))
+            if draw_search:
+                print(draw(map, keys=keys, doors=doors, visited=visited, dead=dead))
+                print(visited_keys)
+                time.sleep(0.01)
+    return avail
+
+def avail_keys_doors(map: dict, pos: tuple, keys: dict, doors: dict, dead=set(), draw_search=False) -> list:
+    ''' Return a list of tuples consisting of ( dist, pos ) '''
+    visited = set()
+    avail = []
+    q = collections.deque()
+    q.append((0, pos))
+    while len(q) != 0:
+        cur = q.popleft()
+        if cur[1] in keys and cur[1] != pos:
+            avail.append((cur[0], cur[1], keys[cur[1]]))
+            continue
+        if cur[1] in doors and cur[1] != pos:
+            avail.append((cur[0], cur[1], doors[cur[1]]))
+            continue
+        for n in neighbours(cur[1]):
+            if n in map and map[n] == "#":
+                continue
+            if n in dead:
+                continue
+            if n in visited:
+                continue
+            visited.add(n)
+            q.append((cur[0]+1, n))
+            if draw_search:
+                print(draw(map, keys=keys, doors=doors, visited=visited, dead=dead))
+                print(visited_keys)
+                time.sleep(0.01)
+    return avail
+
+def draw(map, pos=None, keys={}, doors={}, path={}, visited={}, dead=set()) -> str:
+    min_x=max_x=min_y=max_y = 0
+    for p in map:
+        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 pos is not None and point == pos:
+                s += "@"
+            elif point in keys:
+                s += keys[point]
+            elif point in doors:
+                s += doors[point]
+            elif point in path:
+                s += "\u2591"
+            elif point in visited:
+                s += "."
+            elif point in dead:
+                s += "X"
+            elif point in map:
+                if map[point] == "#":
+                    s += "\u2588"
+                else:
+                    s += " "
+            else:
+                s += "."
+    return s
+
+def pos(s, keys, doors):
+    for iter in (keys, doors):
+        for k, v in keys.items():
+            if s == v:
+                return k
+
+walls = set()
+walkables = set()
+map = {}
+dead = set()  # dead ends, tiles which are effectivly walls
+keys = {}
+doors = {}
+keys_doors = {}
+for y in range(len(f)):
+    for x in range(len(f[y].strip())):
+        if f[y][x] == "@":
+            start = (x,y)
+            map[(x,y)] = "."
+        elif f[y][x].isalpha():
+            if f[y][x].isupper():
+                doors[(x,y)] = f[y][x]
+                keys_doors[(x,y)] = f[y][x]
+            else:
+                keys[(x,y)] = f[y][x]
+                keys_doors[(x,y)] = f[y][x]
+            map[(x,y)] = "?"
+        elif f[y][x] == "#":
+            map[(x,y)] = "#"
+            walls.add((x,y))
+        elif f[y][x] == ".":
+            map[(x,y)] = "."
+            walkables.add((x,y))
+
+for _ in range(10):
+    ends = set()
+    intersections = set()
+    for tile in walkables:
+        num_walls = 0
+        for n in neighbours(tile):
+            if n in walls or n in dead:
+                num_walls += 1
+        if num_walls == 3:
+            ends.add(tile)
+        if num_walls < 2:
+            intersections.add(tile)
+
+    for end in ends:
+        cur = end
+        while cur not in intersections and cur not in keys and cur not in doors:
+            # is normal point
+            dead.add(cur)
+            if cur in walkables:
+                walkables.remove(cur)
+            for n in neighbours(cur):
+                if n not in walls and n not in dead:
+                    cur = n
+                    break
+
+paths = {}
+start_paths = {}
+
+# GRAPH: {node: [children as tuples with name and distance]}
+graph = {}
+
+for ent, s in keys_doors.items():
+    for avail in avail_keys_doors(map, ent, keys, doors, draw_search=False):
+        paths[(s, avail[2])] = avail[0]
+        graph[s] = graph.get(s, []) + [(avail[2], avail[0])]
+used = set()
+for path in paths:
+    if (path[1], path[0]) in used:
+        continue
+    print(path[0],"--",path[1])
+    used.add((path[0], path[1]))
+for avail in avail_keys(map, start, keys, set(), doors):
+    start_paths[("@", keys[avail[1]])] = avail[0]
+    print("start", "->", keys[avail[1]])
+
+print(graph)
+h = []
+
+for path, dist in start_paths.items():
+    visited = []
+    unlocked = set()
+    visited.append(path[1])
+    heap.heappush(h, (dist, path[1], visited, unlocked))
+
+m = 0
+while True:
+    cur = heap.heappop(h)
+    dist = cur[0]
+    last = cur[1]
+    visited = cur[2]
+    unlocked = cur[3]
+
+    if len(unlocked) > m:
+        m = len(unlocked)
+        print(m, visited)
+        if len(unlocked) == len(keys):
+            break
+
+    neighbours = graph[last]
+    for n in neighbours:
+        if n[0] in visited:
+            continue
+        if n[0].isupper() and n[0] not in unlocked:
+            continue
+        visited = visited.copy()
+        unlocked = unlocked.copy()
+        visited.append(n[0])
+        if n[0].islower():
+            unlocked.add(n[0].upper())
+        heap.heappush(h, (dist+n[1], n[0], visited.copy(), unlocked.copy()))