summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--day22.py48
-rw-r--r--day23.py118
2 files changed, 166 insertions, 0 deletions
diff --git a/day22.py b/day22.py
new file mode 100644
index 0000000..f2428da
--- /dev/null
+++ b/day22.py
@@ -0,0 +1,48 @@
+#!/usr/bin/env python
+import re
+import numpy as np
+
+coords_regex = re.compile(r'(\-?\d*)\.\.(\-?\d*)')
+with open('day22.txt') as data:
+ instructions = []
+ for line in data:
+ on, coords = line.strip().split()
+ on = (on == 'on')
+ coords = np.array(coords_regex.findall(coords), dtype=int)
+ instructions.append((on, coords))
+
+
+# part 1
+
+reactor = np.zeros((101, 101, 101)).astype(bool)
+for on, coords in instructions:
+ coords = np.copy(coords)
+ coords += 50
+ if np.any(coords > 100) or np.any(coords < 0): break
+ coords[:, 1] += 1
+ coords = tuple(slice(start, stop) for start, stop in coords)
+ reactor[coords] = on
+
+print(np.count_nonzero(reactor))
+
+# part 2
+from collections import Counter
+
+cubes = Counter()
+for on, coords in instructions:
+ nSign = 1 if on else -1
+ nX0, nX1, nY0, nY1, nZ0, nZ1 = coords.flatten()
+
+ update = Counter()
+ for (eX0, eX1, eY0, eY1, eZ0, eZ1), eSign in cubes.items():
+ iX0 = max(nX0, eX0); iX1 = min(nX1, eX1)
+ iY0 = max(nY0, eY0); iY1 = min(nY1, eY1)
+ iZ0 = max(nZ0, eZ0); iZ1 = min(nZ1, eZ1)
+ if iX0 < iX1 and iY0 < iY1 and iZ0 < iZ1:
+ update[(iX0, iX1, iY0, iY1, iZ0, iZ1)] -= eSign
+
+ if nSign > 0:
+ update[(nX0, nX1, nY0, nY1, nZ0, nZ1)] += nSign
+ cubes.update(update)
+print(sum((x1-x0+1)*(y1-y0+1)*(z1-z0+1)*sgn
+ for (x0, x1, y0, y1, z0, z1), sgn in cubes.items()))
diff --git a/day23.py b/day23.py
new file mode 100644
index 0000000..204ba21
--- /dev/null
+++ b/day23.py
@@ -0,0 +1,118 @@
+#!/usr/bin/env python
+
+goals = {
+ 'A': 2,
+ 'B': 4,
+ 'C': 6,
+ 'D': 8
+}
+
+costs = {
+ 'A': 1,
+ 'B': 10,
+ 'C': 100,
+ 'D': 1000
+}
+
+def reachable(board, pos, dest):
+ a, b = min(pos, dest), max(pos, dest)
+ for i in range(a, b+1):
+ if i == pos or i in goals.values():
+ continue
+ elif board[i] != '.':
+ return False
+ return True
+
+def roomContainsGoal(board, piece, dest):
+ inRoom = board[dest]
+ return len(inRoom) == inRoom.count('.') + inRoom.count(piece)
+
+def getPieceFromRoom(room):
+ for c in room:
+ if c != '.':
+ return c
+
+def possibleMoves(board, pos):
+ piece = board[pos]
+ if pos not in goals.values():
+ if reachable(board, pos, goals[piece]) and roomContainsGoal(board, piece, goals[piece]):
+ return [goals[piece]]
+ return []
+
+ letter = getPieceFromRoom(piece)
+ if pos == goals[letter] and roomContainsGoal(board, letter, pos):
+ return []
+
+ possible = []
+ for dest in range(len(board)):
+ if dest == pos or (dest in goals.values() and goals[letter] != dest):
+ continue
+ elif goals[letter] == dest and not roomContainsGoal(board,letter,dest):
+ continue
+ elif reachable(board, pos, dest):
+ possible.append(dest)
+ return possible
+
+def addToRoom(letter, room):
+ room = list(room)
+ dist = list(room).count('.')
+ assert dist != 0
+ room[dist-1] = letter
+ return ''.join(room), dist
+
+def move(board, pos, dest):
+ new_board = board[:]
+ dist = 0
+ letter = getPieceFromRoom(board[pos])
+ if len(board[pos]) == 1:
+ new_board[pos] = '.'
+ else:
+ new_room = ''
+ found = False
+ for c in board[pos]:
+ if c == '.':
+ dist += 1
+ new_room += c
+ elif not found:
+ new_room += '.'
+ dist += 1
+ found = True
+ else:
+ new_room += c
+ new_board[pos] = new_room
+ dist += abs(pos - dest)
+
+ if len(board[dest]) == 1:
+ new_board[dest] = letter
+ return new_board, dist*costs[letter]
+ else:
+ new_board[dest], addl_dist = addToRoom(letter, board[dest])
+ dist += addl_dist
+ return new_board, dist*costs[letter]
+
+def solve(board):
+ states = {tuple(board): 0}
+ queue = [board]
+ while queue:
+ board = queue.pop()
+ for pos, piece in enumerate(board):
+ if getPieceFromRoom(piece) is None:
+ continue
+ dests = possibleMoves(board, pos)
+ for dest in dests:
+ new_board, addl_cost = move(board, pos, dest)
+ new_cost = states[tuple(board)] + addl_cost
+ new_board_tuple = tuple(new_board)
+ cost = states.get(new_board_tuple, 9999999)
+ if new_cost < cost:
+ states[new_board_tuple] = new_cost
+ queue.append(new_board)
+ return states
+
+board = ['.', '.', 'DD', '.', 'AC', '.', 'CB', '.', 'AB', '.', '.']
+states = solve(board)
+print(states[('.', '.', 'AA', '.', 'BB', '.', 'CC', '.', 'DD', '.', '.')])
+
+board = ['.', '.', 'DDDD', '.', 'ACBC', '.', 'CBAB', '.', 'AACB', '.', '.']
+states = solve(board)
+print(states[('.', '.', 'AAAA', '.', 'BBBB', '.', 'CCCC', '.', 'DDDD', '.', '.')])