def is_legal(order, units, owns, season):
    builds = builds_available(units, owns)

    if not order['actor']:
        if season != 'FA':
            return False
        unit = ()
    else:
        unit = [u for u in units if u['subregion'] == order['actor']]

    if not order['actor'] or not order['action']:
        return (season == 'FA' and
                builds.get(order['government'], 0) > 0)
    if order['action'] != 'B' and not unit:
        return False

    if season in ('S', 'F'):
        if unit[0]['government'] != order['government']:
            return False
    elif season in ('SR', 'FR'):
        unit = [u for u in unit if u['dislodged']]
        if not unit:
            return False
        if unit[0]['government'] != order['government']:
            return False
    elif order['action'] == 'D':
        if unit and unit[0]['government'] != order['government']:
            return False
    elif order['action'] == 'B':
        if not any(o['territory'] == get_territory(order['actor'])
                   and o['government'] == order['government']
                   for o in owns):
            return False

    actions = {'H': valid_hold,
               'M': valid_move,
               'S': valid_support,
               'C': valid_convoy,
               'B': valid_build,
               'D': valid_disband}
    tree = actions[order['action']](order['actor'], units, owns, season)
    if not tree or order['assist'] not in tree:
        return False
    tree = tree[order['assist']]
    if order['target'] not in tree:
        return False
    return True def assist(T1, o1, T2, o2):
    return get_territory(o2['assist']) == T1 def construct_dependencies(orders):
    dep = defaultdict(list)
    for (T1, o1), (T2, o2) in permutations(orders.items(), 2):
        depend = False
        act1, act2 = o1['action'], o2['action']
        if (act1, act2) in DEPENDENCIES:
            depend = any(f(T1, o1, T2, o2) for f in DEPENDENCIES[(act1, act2)])

        if depend:
            dep[T1].append(T2)

    return dep def actionable_subregions(turn, units, owns):
    """Returns lists of subregions that would be legal actors this turn,
    indexed by government.  These lists are not constrained by the
    number of builds available during Fall Adjustment turns, merely by
    whether the home supply center would fit the criteria.

    """
    if turn['season'] in ('S', 'F'):
        return {
            government: [u['subregion'] for u in units
                         if u['government'] == government]
            for government in standard.powers
        }
    elif turn['season'] in ('SR', 'FR'):
        return {
            government: [u['subregion'] for u in units
                         if u['dislodged'] and u['government'] == government]
            for government in standard.powers
        }
    elif turn['season'] == 'FA':
        builds = builds_available(units, owns)
        actors_index = {}
        for government in standard.powers:
            if builds.get(government, 0) > 0:
                # If we have more supply centers than units, we can build.  If,
                # - we own a supply center
                # - that is one of our original supply centers
                # - and that is not occupied by a unit
                owned_sc = (o['territory'] for o in owns
                            if o['is_supply'] and o['government'] == government)
                occupied = {get_territory(u['subregion']) for u in units}
                actors_index[government] = [
                    sr for T in owned_sc
                    for sr in territory_parts(T)
                    if standard.starting_state[T][0] == government
                    and T not in occupied
                ]
            elif builds.get(government, 0) == 0:
                actors_index[government] = []
            else:
                actors_index[government] = [u['subregion'] for u in units
                                            if u['government'] == government]

        return actors_index
    return {} def builds_available(units, owns):
    builds = defaultdict(int)
    builds.update(supplycenters(owns))

    for u in units:
        builds[u['government']] -= 1

    return builds def detect_paradox(orders, dep):
    """
    Implements Tarjan's strongly connected components algorithm to
    find the paradoxical convoys.

    """
    dep = dict(dep)

    low = {}
    stack = []
    result = set()

    def visit(node, orders, dep):
        if node in low:
            return

        index = len(low)
        low[node] = index
        stack_pos = len(stack)
        stack.append(node)

        for w in dep.get(node, ()):
            visit(w, orders, dep)
            low[node] = min(low[node], low[w])

        if low[node] == index:
            component = tuple(stack[stack_pos:])
            del stack[stack_pos:]
            if len(component) > 1:
                result.update(c for c in component
                              if orders[c]['action'] == 'C')
            for item in component:
                low[item] = len(orders)

    for node in orders:
        visit(node, orders, dep)
    return result def immediate_fails(orders, units):
    results = set()
    for T, o in orders.items():
        if o['action'] == 'M':
            if o['target'] not in borders(o['actor']):
                matching = [
                    o2['actor']
                    for T2, o2 in orders.items()
                    if o2['action'] == 'C'
                    and o2['assist'] == o['actor']
                    and o2['target'] == o['target']
                ]
                if any(o['actor'] in L and o['target'] in L
                       for F, L in find_convoys(units, matching)):
                    continue
            else:
                continue
        elif o['action'] not in ('S', 'C'):
            continue
        else:
            assist = orders[get_territory(o['assist'])]
            if o['target']:
                if assist['action'] == 'M' and assist['target'] == o['target']:
                    continue
            else:
                if assist['action'] in ('H', 'C', 'S'):
                    continue
        results.add(T)

    return results def resolve(state, orders, dep, fails, paradox, units):
    _state = set(T for T, d in state)

    # Only bother calculating whether the hypothetical solution is
    # consistent if all orders within it have no remaining
    # unresolved dependencies.
    if all(all(o in _state for o in dep[T]) for T, d in state):
        if not consistent(state, orders, fails, paradox, units):
            return None

    # For those orders not already in 'state', sort from least to
    # most remaining dependencies.
    remaining_deps = sorted(
        (sum(1 for o in dep[T] if o not in _state), T)
        for T in orders
        if T not in _state
    )
    if not remaining_deps:
        return state
    # Go with the order with the fewest remaining deps.
    q, T = remaining_deps[0]

    # Unresolved dependencies might be circular, so it isn't
    # obvious how to resolve them.  Try both ways, with preference
    # for 'success'.
    resolutions = (None, False) if T in paradox else (True, False)
    for S in resolutions:
        result = resolve(state + ((T, S),), orders, dep, fails, paradox, units)
        if result:
            return result

    return None def resolve_retreats(orders):
    decisions = []
    target_count = defaultdict(int)
    for T, order in orders.items():
        if order['action'] == 'M':
            target_count[get_territory(order['target'])] += 1
        else:
            decisions.append((T, None))
    for T, order in orders.items():
        if order['action'] != 'M':
            continue
        if target_count[get_territory(order['target'])] == 1:
            decisions.append((T, True))
        else:
            decisions.append((T, False))
    return decisions def resolve_adjusts(orders):
    return [(T, bool(order.get('action')))
            for T, order in orders.items()] def get_territory(sr_token):
def territory_parts(t_token):
def borders(sr_token):
def unit_in(sr_token, units):
def territory_display(t_token):
def subregion_display(sr_token):
def unit_display(sr_token):
def power_token(p_str):
def territory_token(t_str):
def subregion_token(sr_tuple):
def is_supply(sr_token):
def is_land(sr_token):
def is_sea(sr_token):
def has_land(sr_token):
def has_sea(sr_token):
from collections import defaultdict
from . import standard
from .check import is_legal
from .compare import assist, construct_dependencies
from .digest import actionable_subregions, builds_available
from .resolver import (detect_paradox, immediate_fails, resolve, resolve_retreats,
                       resolve_adjusts)
from .utils import (convert, get_territory, borders, territory_parts,
                    has_land, is_land, is_sea, is_army, is_fleet)



def normalize_orders(turn, orders, units, owns):
    """Returns a list of order dicts, taken from the orders previously
    submitted this turn, filtered down by legality and refilled with
    defaults.  This list is exhaustive, no units not covered by the
    list or number of builds in excess will be permitted.

    """
    actors = actionable_subregions(turn, units, owns)

    # Construct the set of default orders.  This will be the fully constrained set.
    if turn['season'] == 'FA':
        builds = builds_available(units, owns)
        orders_index = {
            (government, index): {
                'government': government, 'actor': '',
                'action': '', 'assist': '', 'target': '',
                'via_convoy': False, 'convoy': False, 'user_issued': False
            }
            for government, B in builds.items()
            for index in range(-B if B < 0 else min(B, len(actors.get(government, ()))))
        }
    else:
        action = 'H' if turn['season'] in ('S', 'F') else ''
        orders_index = {
            (government, a): {
                'government': government, 'actor': a,
                'action': action, 'assist': '', 'target': '',
                'via_convoy': False, 'convoy': False, 'user_issued': False
            }
            for government, actor_set in actors.items()
            for a in actor_set
        }

    # For orders that were explicitly given, replace the default order if
    # the given order is legal.  Illegal orders are dropped.
    index = {}
    for o in orders:
        if is_legal(o, units, owns, turn['season']):
            i = o['actor']
            if turn['season'] == 'FA':
                index.setdefault(o['government'], 0)
                i = index[o['government']]
                index[o['government']] += 1

            # Drop the order if it falls outside of the set of
            # allowable acting units or build quantity.
            if (o['government'], i) not in orders_index:
                continue

            o['user_issued'], o['convoy'] = True, False
            orders_index[(o['government'], i)] = o

    if turn['season'] in ('S', 'F'):
        for (g, i), o in orders_index.items():
            # This block concerns the convoyability of units, so if the unit
            # isn't moving or isn't an army, ignore it.

            if o['action'] != 'M' or not is_land(o['actor']):