diff options
Diffstat (limited to '19')
| -rw-r--r-- | 19/input/18-1 (renamed from 19/input/18) | 2 | ||||
| -rw-r--r-- | 19/input/18-2 | 81 | ||||
| -rw-r--r-- | 19/py/d18.py | 248 |
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())) |