import random

def move_toward_closest_factory(whoami, width, height, board, rx, ry, capture_types):
    if board[rx, ry].allegiance != whoami and board[rx, ry].city in capture_types:
        return 'P'
    to_do = [
        (rx + 1, ry, 'R'),
        (rx - 1, ry, 'L'),
        (rx, ry - 1, 'U'),
        (rx, ry + 1, 'D')
    ]
    random.shuffle(to_do)
    seen = []
    while to_do:
        (x, y, move) = to_do.pop(0)
        x %= width
        y %= height
        if (x, y) in seen or board[x, y].city not in ['+', '.']:
            continue
        seen.append((x, y))
        if board[x, y].allegiance != whoami and board[x, y].city in capture_types:
            return move
        else:
            to_add = [(x + 1, y, move),
                      (x - 1, y, move),
                      (x, y + 1, move),
                      (x, y - 1, move)]
            random.shuffle(to_add)
            to_do += to_add

def calculate_orders(whoami, state):
    # In order to start painting, we need to be leading by at least
    # this percentage (per opposing player).
    leading_factor_per_opponent = 0.1 # 10%
    opponents = (len(state.robots_by_player) - 1)
    factor = 1 - (leading_factor_per_opponent * opponents)

    orders = []

    board = state.board
    width = state.width
    height = state.height
    my_robots = state.robots_by_player[whoami]
    max_robots = max(
        len(robots)
        for player, robots in state.robots_by_player.items()
        if player != whoami
    )
    my_factories = state.factories_by_player[whoami]
    max_factories = max(
        len(factories)
        for player, factories in state.factories_by_player.items()
        if player != whoami
    )
    if factor * len(my_robots) < max_robots or factor * len(my_factories) < max_factories:
        capture_types = ['+']
    else:
        capture_types = ['+', '.']
    for rx, ry, energy in my_robots:
        move = move_toward_closest_factory(whoami, width, height, board, rx, ry, capture_types)
        orders.append(move or random.choice('UDLRP'))

    return orders