# Background

My pet bridge-maker ants are marching across a terrain from left to right.

If they encounter a gap, the first one stops and then next one climbs over him, then the next, and the next, until a bridge is formed across the gap. 

What clever little things they are!

Now all the other ants can walk over the ant-bridge.

When the last ant is across, the ant-bridge dismantles itself similar to how it was constructed.

This process repeats as many times as necessary (there may be more than one gap to cross) until all the ants reach the right hand side.

# Kata Task

My little ants are marching across the terrain from left-to-right in the order ```A``` then ```B``` then ```C```...

What order do they exit on the right hand side?

# Notes

* ```-``` = solid ground
* ```.``` = a gap
* The number of ants may differ but there are always enough ants to bridge the gaps
* The terrain never starts or ends with a gap
* Ants cannot pass other ants except by going over ant-bridges
* If there is ever ambiguity which ant should move, then the ant at the **back** moves first

# Example

## Input
* ants = ````GFEDCBA````
* terrain = ```------------...-----------```

## Output
* result = ```EDCBAGF```

## Details


Ants moving left to right.
GFEDCBA
------------...-----------

The first one arrives at a gap.
GFEDCB     A
------------...-----------

They start to bridge over the gap...
GFED       ABC
------------...-----------

...until the ant-bridge is completed!
GF         ABCDE
------------...-----------

And then the remaining ants can walk across the bridge.
               F
G          ABCDE
------------...-----------

And when no more ants need to cross...
           ABCDE        GF
------------...-----------

... the bridge dismantles itself one ant at a time....                
             CDE      BAGF
------------...-----------

...until all ants get to the other side                
                   EDCBAGF
------------...-----------

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def find_next_bridge_end(position, terrain):\n    next_bridge_end_position = \'\'.join(terrain[position:]).find(\'---\')\n    if next_bridge_end_position == -1:\n        return len(terrain)+1\n    \n    return next_bridge_end_position + position\n    \ndef check_if_bridge_position(i, terrain):\n    if i == 0:\n        previous_terrain = \'-\'\n        next_terrain = terrain[i+1]\n    elif i >= len(terrain)-1:\n        previous_terrain = terrain[i-1]\n        next_terrain = \'-\'\n    else:\n        previous_terrain = terrain[i-1]\n        next_terrain = terrain[i+1]\n\n    if previous_terrain == \'-\' and terrain[i] == \'-\' and next_terrain == \'-\':\n        return False\n    return True\n\ndef create_terrain_with_ants(ant_positions, terrain):\n    terrain_with_ants = terrain[:]\n    for ant, position in list(ant_positions.items()):\n        terrain_with_ants[position] = ant\n    return \'\'.join(terrain_with_ants)\n\ndef ant_bridge(ants, terrain):\n    platform = \'\'.join([\'-\' for _ in range(len(ants))])\n    terrain = platform + terrain + platform\n    terrain = list(terrain)\n    terrain_length = len(terrain)\n    \n    ant_positions = list(range(len(ants)))\n\n    print(ants)\n    print((\'\'.join(terrain)))\n\n    initial_states = []\n    \n    if len(ants) >= len(terrain):\n        return ants\n    \n    for i in range(len(ants)):\n        if i <= 0:\n            previous_terrain = \'-\'\n            current_terrain = terrain[i]\n            next_terrain = terrain[i+1]\n        elif i >= len(terrain)-1:\n            previous_terrain = terrain[i-1]\n            current_terrain = terrain[i]\n            next_terrain = \'-\'\n        else:\n            previous_terrain = terrain[i-1]\n            current_terrain = terrain[i]\n            next_terrain = terrain[i+1]\n            \n        if not previous_terrain == \'.\' and current_terrain == \'-\' and not next_terrain == \'.\':\n            initial_states.append(\'\')\n        else:\n            initial_states.append(\'b\')\n    \n    ant_states = dict(list(zip(ants, initial_states)))\n    ant_positions = dict(list(zip(ants[::-1], list(range(len(ants)-1, -1, -1)))))\n    \n    for k in range(len(ants), terrain_length):\n        #print("Iteration " + str(k))\n        max_ant_position = max(ant_positions.values())\n        min_ant_position = min(ant_positions.values())\n    \n        #print(create_terrain_with_ants(ant_positions, terrain))\n    \n        for ant in ants:\n            i = ant_positions[ant]\n            s = ant_states[ant]\n        \n            is_end_of_terrain_reached = i >= len(terrain)-2\n        \n            if is_end_of_terrain_reached:\n                terrain = terrain + [\'-\', \'-\']\n\n            # ant is not part of a bridge and next position cannot be part of a bridge => increment by 1    \n            if terrain[i] == \'-\' and terrain[i+1] == \'-\' and terrain[i+2] == \'-\' and s == \'\':\n                ant_positions[ant] = i+1\n                ant_states[ant] = \'\'\n            # ant is not part of a bridge and it is at the front of the queue and next position is start of a bridge => increment by 1 and start a bridge\n            if terrain[i] == \'-\' and terrain[i+1] == \'-\' and terrain[i+2] == \'.\' and s == \'\' and i == max_ant_position:\n                ant_positions[ant] = i+1\n                ant_states[ant] = \'b\'     \n            # ant is not part of a bridge and it is not at the front of the queue and next position is start of a bridge => jump ahead to the front of the queue\n            if terrain[i] == \'-\' and terrain[i+1] == \'-\' and terrain[i+2] == \'.\' and s == \'\' and not i == max_ant_position:\n                # DUPLICATED CODE\n                next_bridge_end = find_next_bridge_end(i, terrain)\n                if next_bridge_end < max_ant_position:\n                    ant_positions[ant] = next_bridge_end + 1\n                else:           \n                    ant_positions[ant] = max_ant_position + 1\n                ant_states[ant] = \'\'\n                if check_if_bridge_position(ant_positions[ant], terrain):\n                    ant_states[ant] = \'b\'      \n            # ant is part of a bridge and it is at the back of the queue => jump ahead to the next bridge end or to the front of the queue\n            if s == \'b\' and i == min_ant_position:\n                next_bridge_end = find_next_bridge_end(i, terrain)\n                if next_bridge_end < max_ant_position:\n                    ant_positions[ant] = next_bridge_end + 1\n                else:           \n                    ant_positions[ant] = max_ant_position + 1\n                \n                ant_states[ant] = \'\'\n                if check_if_bridge_position(ant_positions[ant], terrain):\n                    ant_states[ant] = \'b\'\n            \n            if is_end_of_terrain_reached:\n                terrain = terrain[:len(terrain)-2]\n            \n            #print(create_terrain_with_ants(ant_positions, terrain))      \n    \n    return \'\'.join(sorted(ant_positions, key=ant_positions.get))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'ant_bridge'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 9692