#!/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', '.', '.')])