def assign_cross_keys(dungeon_builders, world, player):
    start = time.process_time()
    total_keys = remaining = 29
    total_candidates = 0
    start_regions_map = {}
    for (name, builder) in dungeon_builders.items():
        dungeon = world.get_dungeon(name, player)
        if ((not builder.bk_required) or builder.bk_provided):
            dungeon.big_key = None
        elif (builder.bk_required and (not builder.bk_provided)):
            dungeon.big_key = ItemFactory(dungeon_bigs[name], player)
        start_regions = convert_regions(builder.path_entrances, world, player)
        find_small_key_door_candidates(builder, start_regions, world, player)
        builder.key_doors_num = max(0, (len(builder.candidates) - builder.key_drop_cnt))
        total_candidates += builder.key_doors_num
        start_regions_map[name] = start_regions
    for (name, builder) in dungeon_builders.items():
        calculated = int(round(((builder.key_doors_num * total_keys) / total_candidates)))
        max_keys = (builder.location_cnt - calc_used_dungeon_items(builder))
        cand_len = max(0, (len(builder.candidates) - builder.key_drop_cnt))
        limit = min(max_keys, cand_len)
        suggested = min(calculated, limit)
        combo_size = ncr(len(builder.candidates), (suggested + builder.key_drop_cnt))
        while ((combo_size > 500000) and (suggested > 0)):
            suggested -= 1
            combo_size = ncr(len(builder.candidates), (suggested + builder.key_drop_cnt))
        builder.key_doors_num = (suggested + builder.key_drop_cnt)
        remaining -= suggested
        builder.combo_size = combo_size
        if (suggested < limit):
            builder.flex = (limit - suggested)
    for (name, builder) in dungeon_builders.items():
        suggested = (builder.key_doors_num - builder.key_drop_cnt)
        find_valid_combination(builder, start_regions_map[name], world, player)
        actual_chest_keys = (builder.key_doors_num - builder.key_drop_cnt)
        if (actual_chest_keys < suggested):
            remaining += (suggested - actual_chest_keys)
            builder.flex = 0
    builder_order = [x for x in dungeon_builders.values() if (x.flex > 0)]
    builder_order.sort(key=(lambda b: b.combo_size))
    queue = deque(builder_order)
    logger = logging.getLogger('')
    while ((len(queue) > 0) and (remaining > 0)):
        builder = queue.popleft()
        name = builder.name
        logger.info('Cross Dungeon: Increasing key count by 1 for %s', name)
        builder.key_doors_num += 1
        result = find_valid_combination(builder, start_regions_map[name], world, player, drop_keys=False)
        if result:
            remaining -= 1
            builder.flex -= 1
            if (builder.flex > 0):
                builder.combo_size = ncr(len(builder.candidates), builder.key_doors_num)
                queue.append(builder)
                queue = deque(sorted(queue, key=(lambda b: b.combo_size)))
        else:
            logger.info('Cross Dungeon: Increase failed for %s', name)
            builder.key_doors_num -= 1
            builder.flex = 0
    logger.info('Cross Dungeon: Keys unable to assign in pool %s', remaining)
    if (not world.retro[player]):
        for (name, builder) in dungeon_builders.items():
            reassign_key_doors(builder, world, player)
            log_key_logic(builder.name, world.key_logic[player][builder.name])
            actual_chest_keys = max((builder.key_doors_num - builder.key_drop_cnt), 0)
            dungeon = world.get_dungeon(name, player)
            if (actual_chest_keys == 0):
                dungeon.small_keys = []
            else:
                dungeon.small_keys = ([ItemFactory(dungeon_keys[name], player)] * actual_chest_keys)
    logging.getLogger('').info('Cross Dungeon: Key door shuffle time: %s', (time.process_time() - start))
def assign_cross_keys(dungeon_builders, world, player):
    start = time.process_time()
    total_keys = remaining = 29
    total_candidates = 0
    start_regions_map = {}
    for (name, builder) in dungeon_builders.items():
        dungeon = world.get_dungeon(name, player)
        if ((not builder.bk_required) or builder.bk_provided):
            dungeon.big_key = None
        elif (builder.bk_required and (not builder.bk_provided)):
            dungeon.big_key = ItemFactory(dungeon_bigs[name], player)
        start_regions = convert_regions(builder.path_entrances, world, player)
        find_small_key_door_candidates(builder, start_regions, world, player)
        builder.key_doors_num = max(0, (len(builder.candidates) - builder.key_drop_cnt))
        total_candidates += builder.key_doors_num
        start_regions_map[name] = start_regions
    for (name, builder) in dungeon_builders.items():
        calculated = int(round(((builder.key_doors_num * total_keys) / total_candidates)))
        max_keys = (builder.location_cnt - calc_used_dungeon_items(builder))
        cand_len = max(0, (len(builder.candidates) - builder.key_drop_cnt))
        limit = min(max_keys, cand_len)
        suggested = min(calculated, limit)
        combo_size = ncr(len(builder.candidates), (suggested + builder.key_drop_cnt))
        while ((combo_size > 500000) and (suggested > 0)):
            suggested -= 1
            combo_size = ncr(len(builder.candidates), (suggested + builder.key_drop_cnt))
        builder.key_doors_num = (suggested + builder.key_drop_cnt)
        remaining -= suggested
        builder.combo_size = combo_size
        if (suggested < limit):
            builder.flex = (limit - suggested)
    for (name, builder) in dungeon_builders.items():
        suggested = (builder.key_doors_num - builder.key_drop_cnt)
        find_valid_combination(builder, start_regions_map[name], world, player)
        actual_chest_keys = (builder.key_doors_num - builder.key_drop_cnt)
        if (actual_chest_keys < suggested):
            remaining += (suggested - actual_chest_keys)
            builder.flex = 0
    builder_order = [x for x in dungeon_builders.values() if (x.flex > 0)]
    builder_order.sort(key=(lambda b: b.combo_size))
    queue = deque(builder_order)
    logger = logging.getLogger()
    while ((len(queue) > 0) and (remaining > 0)):
        builder = queue.popleft()
        name = builder.name
        logger.info('Cross Dungeon: Increasing key count by 1 for %s', name)
        builder.key_doors_num += 1
        result = find_valid_combination(builder, start_regions_map[name], world, player, drop_keys=False)
        if result:
            remaining -= 1
            builder.flex -= 1
            if (builder.flex > 0):
                builder.combo_size = ncr(len(builder.candidates), builder.key_doors_num)
                queue.append(builder)
                queue = deque(sorted(queue, key=(lambda b: b.combo_size)))
        else:
            logger.info('Cross Dungeon: Increase failed for %s', name)
            builder.key_doors_num -= 1
            builder.flex = 0
    logger.info('Cross Dungeon: Keys unable to assign in pool %s', remaining)
    if (not world.retro[player]):
        for (name, builder) in dungeon_builders.items():
            reassign_key_doors(builder, world, player)
            log_key_logic(builder.name, world.key_logic[player][builder.name])
            actual_chest_keys = max((builder.key_doors_num - builder.key_drop_cnt), 0)
            dungeon = world.get_dungeon(name, player)
            if (actual_chest_keys == 0):
                dungeon.small_keys = []
            else:
                dungeon.small_keys = ([ItemFactory(dungeon_keys[name], player)] * actual_chest_keys)
    logging.getLogger().info('Cross Dungeon: Key door shuffle time: %s', (time.process_time() - start))