Restructure day 18

3 files changed, 183 insertions, 148 deletions

diff --git a/19/input/18 b/19/input/18-1
index a9ec2f1..c8c0fc8 100644
--- a/19/input/18
+++ b/19/input/18-1
@@ -39,7 +39,7 @@
 #.###.#.###.#.#.###########.#.#######.#.###############.#.#.#.#.###.#.#####.###.#
 #.....#.....#.#.......H.....#........................h....#...#.....#...........#
 #######################################.@.#######################################
-#....m....#.#.........#.....#.............#...#...............#.........#.......#
+#....m....#.#.........#.....#.................#...............#.........#.......#
 #.#.#####.#.#.#######.#.#####.###.#####.#.#.#.#.#.#.###########.#####.#.#.#.#####
 #.#.#.....#.#...#...#.#.#.....#.#.#...#.#.#.#...#.#.#.....#.....#.I...#...#.#...#
 #.#.###.###.###.#.#.#.#.#.#####.#.#.#.#.#.#.#####.###.###.#.#####.#####.#####.#.#
diff --git a/19/input/18-2 b/19/input/18-2
new file mode 100644
index 0000000..95216e1
--- /dev/null
+++ b/19/input/18-2
@@ -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.py b/19/py/d18.py
index 144eb4e..3208dcb 100644
--- a/19/py/d18.py
+++ b/19/py/d18.py
@@ -39,35 +39,7 @@ def draw(map, pos=None, keys={}, doors={}, path={}, visited={}, dead=set()) -> s
                 s += "."
     return s
 
-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:
-            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)
-
-def avail(map, start, items, dead, ignore=set(), ignore_except=set()):
+def avail(map, start, items, dead, ignore=set()):
     visited = set()
     avail = []
     q = collections.deque()
@@ -80,94 +52,12 @@ def avail(map, start, items, dead, ignore=set(), ignore_except=set()):
             avail.append((dist, pos, items[pos]))
             continue
         for n in neighbours(pos):
-            if n in ignore and n not in ignore_except:
-                continue
-            if n in map and map[n] == "#":
-                continue
-            if n in dead:
-                continue
-            if n in visited:
+            if (n in map and map[n] == "#") or n in dead or n in visited or n in ignore:
                 continue
             visited.add(n)
             q.append((dist+1, n))
     return avail
 
-input = open("../input/18", "r").readlines()
-
-map = {}
-map_keys = {}
-map_doors = {}
-map_keys_doors = {}
-walls = set()
-tiles = set()
-
-for y in range(len(input)):
-    for x in range(len(input[y].strip())):
-        c = input[y][x]
-        p = (x,y)
-        if c == "@":
-            start = p
-            map[p] = "."
-        elif c.isalpha():
-            if c.isupper():
-                map_doors[p] = c
-            else:
-                map_keys[p] = c
-            map[p] = "."
-        elif c == "#":
-            walls.add(p)
-            map[p] = c
-        elif c == ".":
-            tiles.add(p)
-            map[p] = c
-map_keys_doors.update(map_keys)
-map_keys_doors.update(map_doors)
-
-dead = set()
-for _ in range(10):
-    ends = set()
-    intersections = set()
-    for tile in tiles:
-        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)
-        elif num_walls < 2:
-            intersections.add(tile)
-
-    for end in ends:
-        cur = end
-        while cur not in intersections and cur not in map_keys and cur not in map_doors:
-            dead.add(cur)
-            if cur in tiles:
-                tiles.remove(cur)
-            for n in neighbours(cur):
-                if n not in walls and n not in dead:
-                    cur = n
-                    break
-
-paths = {}  # every path available between a door and a key
-start_paths = {}  # every path available from the starting point
-
-graph = {}  # {node: [children as tuples with name and distance]}
-for ent, s in map_keys_doors.items():
-    for a in avail(map, ent, map_keys_doors, dead):
-        paths[(s, a[2])] = a[0]
-        graph[s] = graph.get(s, []) + [(a[2], a[0])]
-for a in avail(map, start, map_keys, dead, map_doors):
-    start_paths[("@", map_keys[a[1]])] = a[0]
-
-def v_from_k(items: dict, item: str):
-    for k,v in items.items():
-        if item == v:
-            return k
-    return None
-
-def pos_from_item(item, keys, doors):
-    return v_from_k((keys if item.islower() else doors), item)
-
 def avail_keys(map, keys, doors, graph, start, keys_left, unlocked_doors):
     visited = set()
     avail = []
@@ -187,40 +77,104 @@ def avail_keys(map, keys, doors, graph, start, keys_left, unlocked_doors):
             heap.heappush(h, (dist + n[1], n[0]))
     return avail
 
-h = []
-
-for path, dist in start_paths.items():
-    cur = path[1]
-    keys_left = set(map_keys.values()).copy()
-    keys_left.remove(cur)
-    unlocked = set()
-    unlocked.add(cur.upper())
-    key_path = [cur]
-    heap.heappush(h, (dist, cur, keys_left, unlocked, key_path))
+def pt1(input):
+    map = {}
+    map_keys = {}
+    map_doors = {}
+    map_keys_doors = {}
+    walls = set()
+    tiles = set()
+
+    for y in range(len(input)):
+        for x in range(len(input[y].strip())):
+            c = input[y][x]
+            p = (x,y)
+            if c == "@":
+                start = p
+                map[p] = "."
+            elif c.isalpha():
+                if c.isupper():
+                    map_doors[p] = c
+                else:
+                    map_keys[p] = c
+                map[p] = "."
+            elif c == "#":
+                walls.add(p)
+                map[p] = c
+            elif c == ".":
+                tiles.add(p)
+                map[p] = c
+    map_keys_doors.update(map_keys)
+    map_keys_doors.update(map_doors)
+
+    dead = set()
+    for _ in range(10):
+        #TODO repeat until no further changes are done
+        ends = set()
+        intersections = set()
+        for tile in tiles:
+            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)
+            elif num_walls < 2:
+                intersections.add(tile)
+
+        for end in ends:
+            cur = end
+            while cur not in intersections and cur not in map_keys and cur not in map_doors:
+                dead.add(cur)
+                if cur in tiles:
+                    tiles.remove(cur)
+                for n in neighbours(cur):
+                    if n not in walls and n not in dead:
+                        cur = n
+                        break
+
+    paths = {}  # every path available between a door and a key
+    start_paths = {}  # every path available from the starting point
+
+    graph = {}  # {node: [children as tuples with name and distance]}
+    for ent, s in map_keys_doors.items():
+        for a in avail(map, ent, map_keys_doors, dead):
+            paths[(s, a[2])] = a[0]
+            graph[s] = graph.get(s, []) + [(a[2], a[0])]
+    for a in avail(map, start, map_keys, dead, map_doors):
+        start_paths[("@", map_keys[a[1]])] = a[0]
 
-best = len(map_keys)
-seen = set()
+    h = []
+    for path, dist in start_paths.items():
+        cur = path[1]
+        keys_left = set(map_keys.values()).copy()
+        keys_left.remove(cur)
+        unlocked = set()
+        unlocked.add(cur.upper())
+        key_path = [cur]
+        heap.heappush(h, (dist, cur, keys_left, unlocked, key_path))
+
+    best = len(map_keys)
+    seen = set()
 
-while True:
-    dist, key, keys_left, unlocked, key_path = heap.heappop(h)
-    #print("\nnode", dist, key, keys_left, unlocked, key_path)
-    if (frozenset(key_path), key) in seen:
-        #print("skipping", key_path, key)
-        continue
-    seen.add((frozenset(key_path), key))
-    if len(keys_left) == 0:
-        print(dist, "with path", key_path)
-        sys.exit()
-    if len(keys_left) < best:
-        best = len(keys_left)
-        print("best", len(unlocked), "with dist", dist, "and path", key_path)
-    for new_dist, new_key in avail_keys(map, map_keys, map_doors, graph, key, keys_left, unlocked):
-        #print("edge", new_dist, new_key)
-        new_keys_left = keys_left.copy()
-        new_keys_left.remove(new_key)
-        new_unlocked = unlocked.copy()
-        new_unlocked.add(new_key.upper())
-        new_key_path = key_path.copy()
-        new_key_path.append(new_key)
-        #print("adding", dist+new_dist, new_key, new_keys_left, new_unlocked, new_key_path)
-        heap.heappush(h, (dist + new_dist, new_key, new_keys_left, new_unlocked, new_key_path))
+    while True:
+        dist, key, keys_left, unlocked, key_path = heap.heappop(h)
+        if (frozenset(key_path), key) in seen:
+            continue
+        seen.add((frozenset(key_path), key))
+        if len(keys_left) == 0:
+            return dist
+        if len(keys_left) < best:
+            best = len(keys_left)
+        for new_dist, new_key in avail_keys(map, map_keys, map_doors, graph, key, keys_left, unlocked):
+            new_keys_left = keys_left.copy()
+            new_keys_left.remove(new_key)
+            new_unlocked = unlocked.copy()
+            new_unlocked.add(new_key.upper())
+            new_key_path = key_path.copy()
+            new_key_path.append(new_key)
+            heap.heappush(h, (dist + new_dist, new_key, new_keys_left, new_unlocked, new_key_path))
+
+if __name__ == "__main__":
+    print(pt1(open("../input/18-1", "r").readlines()))
+    print(pt2(open("../input/18-2", "r").readlines()))