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