summaryrefslogtreecommitdiffstats
path: root/19
diff options
context:
space:
mode:
Diffstat (limited to '19')
-rw-r--r--19/input/1881
-rw-r--r--19/py/d18.gv89
-rw-r--r--19/py/d18.py246
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()))
generated by cgit v1.2.1 (git 2.18.0) at 2025-12-13 23:46:16 +0100