1 files changed, 118 insertions, 0 deletions
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', '.', '.')])