From 605de102a57d01970e7086fdfda50eccc405c0e0 Mon Sep 17 00:00:00 2001
From: Brian Chu <brianmchu42@gmail.com>
Date: Thu, 23 Dec 2021 14:32:19 -0800
Subject: solutions for days 22 and 23

---
 day22.py |  48 ++++++++++++++++++++++++++
 day23.py | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 166 insertions(+)
 create mode 100644 day22.py
 create mode 100644 day23.py

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', '.', '.')])
-- 
cgit 1.4.1-2-gfad0