diff options
Diffstat (limited to '19')
| -rw-r--r-- | 19/py/d18.py | 105 |
1 files changed, 62 insertions, 43 deletions
diff --git a/19/py/d18.py b/19/py/d18.py index 1c25b12..144eb4e 100644 --- a/19/py/d18.py +++ b/19/py/d18.py @@ -1,5 +1,6 @@ import collections import heapq as heap +import sys def neighbours(p): return [(p[0]+1, p[1]), (p[0]-1, p[1]), \ @@ -47,7 +48,6 @@ def path(start: tuple, end:tuple, board:dict, keys={}, doors={}, draw_search=Fal 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]): @@ -66,11 +66,8 @@ def path(start: tuple, end:tuple, board:dict, keys={}, doors={}, draw_search=Fal 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(map, start, items, dead): +def avail(map, start, items, dead, ignore=set(), ignore_except=set()): visited = set() avail = [] q = collections.deque() @@ -83,6 +80,8 @@ def avail(map, start, items, dead): 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: @@ -93,12 +92,6 @@ def avail(map, start, items, dead): q.append((dist+1, n)) return avail -def seen_before(keys, paths): - for path in paths: - if set(keys) == set(path) and keys[-1] == path[-1]: - return True - return False - input = open("../input/18", "r").readlines() map = {} @@ -143,7 +136,7 @@ for _ in range(10): 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: @@ -154,6 +147,7 @@ for _ in range(10): 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 @@ -162,46 +156,71 @@ 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): +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 = [] + h = [] + heap.heappush(h, (0, start)) + while len(h) > 0: + dist, cur_key = heap.heappop(h) + if cur_key != start and cur_key.islower() and cur_key in keys_left: + avail.append((dist, cur_key)) + continue + for n in graph[cur_key]: + if n[0].isupper() and n[0] not in unlocked_doors: + continue + if n[0] in visited: + continue + visited.add(n[0]) + heap.heappush(h, (dist + n[1], n[0])) + return avail + h = [] for path, dist in start_paths.items(): cur = path[1] - keys = [path[1]] + keys_left = set(map_keys.values()).copy() + keys_left.remove(cur) unlocked = set() unlocked.add(cur.upper()) - heap.heappush(h, (dist, cur, keys, unlocked)) + key_path = [cur] + heap.heappush(h, (dist, cur, keys_left, unlocked, key_path)) -m = 0 -seen = [] +best = len(map_keys) +seen = set() while True: - print(len(h)) - candidate = heap.heappop(h) - dist = candidate[0] - cur = candidate[1] - keys = candidate[2] - unlocked = candidate[3] - - # if seen_before - if seen_before(keys, seen): + 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.append(keys) - - if len(unlocked) > m: - m = len(unlocked) - print(m, keys) - if len(unlocked) == len(map_doors): - break - - for n in graph[cur]: - if n[0].isupper() and n[0] not in unlocked: - continue - keys = keys.copy() - unlocked = unlocked.copy() - if n[0].islower(): - keys.append(n[0]) - unlocked.add(n[0].upper()) - heap.heappush(h, (dist+n[1], n[0], keys, unlocked)) + 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)) |