# 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
------------...-----------

Difficulty: introductory

Starter code:

def ant_bridge(ants, terrain):
	

Solutions:
import re

def ant_bridge(ants, terrain):
    nGap = sum( 2 + len(gap) - (free == '-') for free,gap in re.findall(r'(-+)(\.+)', '-'+terrain) ) % len(ants)
    return ants[-nGap:] + ants[:-nGap]

def ant_bridge(ants, terrain):
    n_ants = len(ants)
    
    terrain = terrain.replace('-.', '..')
    terrain = terrain.replace('.-', '..')
    
    count = terrain.count('.') % n_ants
    
    return ants[-count:] + ants[:-count]

def ant_bridge(ants, s):
    remain, i = list(ants), 0

    while True:
        next_stop = next((k for k, l in enumerate(s[i:-1], i) if s[k + 1] == '.'), None)
    
        if next_stop is None:
            return ''.join(remain)
    
        if next_stop != i or not i : remain.insert(0,remain.pop())
        i = next_stop + 1
    
        while s[i] == '.':
            remain.insert(0,remain.pop())
            i += 1
        remain.insert(0,remain.pop())    

def find_next_bridge_end(position, terrain):
    next_bridge_end_position = ''.join(terrain[position:]).find('---')
    if next_bridge_end_position == -1:
        return len(terrain)+1
    
    return next_bridge_end_position + position
    
def check_if_bridge_position(i, terrain):
    if i == 0:
        previous_terrain = '-'
        next_terrain = terrain[i+1]
    elif i >= len(terrain)-1:
        previous_terrain = terrain[i-1]
        next_terrain = '-'
    else:
        previous_terrain = terrain[i-1]
        next_terrain = terrain[i+1]

    if previous_terrain == '-' and terrain[i] == '-' and next_terrain == '-':
        return False
    return True

def create_terrain_with_ants(ant_positions, terrain):
    terrain_with_ants = terrain[:]
    for ant, position in list(ant_positions.items()):
        terrain_with_ants[position] = ant
    return ''.join(terrain_with_ants)

def ant_bridge(ants, terrain):
    platform = ''.join(['-' for _ in range(len(ants))])
    terrain = platform + terrain + platform
    terrain = list(terrain)
    terrain_length = len(terrain)
    
    ant_positions = list(range(len(ants)))

    print(ants)
    print((''.join(terrain)))

    initial_states = []
    
    if len(ants) >= len(terrain):
        return ants
    
    for i in range(len(ants)):
        if i <= 0:
            previous_terrain = '-'
            current_terrain = terrain[i]
            next_terrain = terrain[i+1]
        elif i >= len(terrain)-1:
            previous_terrain = terrain[i-1]
            current_terrain = terrain[i]
            next_terrain = '-'
        else:
            previous_terrain = terrain[i-1]
            current_terrain = terrain[i]
            next_terrain = terrain[i+1]
            
        if not previous_terrain == '.' and current_terrain == '-' and not next_terrain == '.':
            initial_states.append('')
        else:
            initial_states.append('b')
    
    ant_states = dict(list(zip(ants, initial_states)))
    ant_positions = dict(list(zip(ants[::-1], list(range(len(ants)-1, -1, -1)))))
    
    for k in range(len(ants), terrain_length):
        #print("Iteration " + str(k))
        max_ant_position = max(ant_positions.values())
        min_ant_position = min(ant_positions.values())
    
        #print(create_terrain_with_ants(ant_positions, terrain))
    
        for ant in ants:
            i = ant_positions[ant]
            s = ant_states[ant]
        
            is_end_of_terrain_reached = i >= len(terrain)-2
        
            if is_end_of_terrain_reached:
                terrain = terrain + ['-', '-']

            # ant is not part of a bridge and next position cannot be part of a bridge => increment by 1    
            if terrain[i] == '-' and terrain[i+1] == '-' and terrain[i+2] == '-' and s == '':
                ant_positions[ant] = i+1
                ant_states[ant] = ''
            # 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
            if terrain[i] == '-' and terrain[i+1] == '-' and terrain[i+2] == '.' and s == '' and i == max_ant_position:
                ant_positions[ant] = i+1
                ant_states[ant] = 'b'     
            # 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
            if terrain[i] == '-' and terrain[i+1] == '-' and terrain[i+2] == '.' and s == '' and not i == max_ant_position:
                # DUPLICATED CODE
                next_bridge_end = find_next_bridge_end(i, terrain)
                if next_bridge_end < max_ant_position:
                    ant_positions[ant] = next_bridge_end + 1
                else:           
                    ant_positions[ant] = max_ant_position + 1
                ant_states[ant] = ''
                if check_if_bridge_position(ant_positions[ant], terrain):
                    ant_states[ant] = 'b'      
            # 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
            if s == 'b' and i == min_ant_position:
                next_bridge_end = find_next_bridge_end(i, terrain)
                if next_bridge_end < max_ant_position:
                    ant_positions[ant] = next_bridge_end + 1
                else:           
                    ant_positions[ant] = max_ant_position + 1
                
                ant_states[ant] = ''
                if check_if_bridge_position(ant_positions[ant], terrain):
                    ant_states[ant] = 'b'
            
            if is_end_of_terrain_reached:
                terrain = terrain[:len(terrain)-2]
            
            #print(create_terrain_with_ants(ant_positions, terrain))      
    
    return ''.join(sorted(ant_positions, key=ant_positions.get))


from queue import deque


def ant_bridge(ants, terrain):
    terrains = '-' + terrain + '-'
    marching_ants = deque([ant, -len(ants)+count+1] for count, ant in enumerate(ants))
    print(marching_ants)
    bridge_ants = deque()
    # 在地形上前进
    for pos in range(1, len(terrains)-1):
        if '.' in terrains[pos-1:pos+2]:
            # 当前位置是坑，拿最前面的行进蚁填坑，其他的前移一步,并检查是否要拆掉最尾端的桥蚁
            leading_ant = marching_ants.pop()
            leading_ant[1] = pos
            bridge_ants.append(leading_ant)
            march_forward(marching_ants, bridge_ants)
        else:
            # 当前位置不是坑，所有行进蚁前移一步，并检查是否要拆掉最尾端的桥蚁
            march_forward(marching_ants, bridge_ants)
    # 到达最右端后，继续行进所有的蚂蚁，直到没有桥蚁为止
    while len(bridge_ants) > 0:
        march_forward(marching_ants, bridge_ants)
    return ''.join(ant[0] for ant in marching_ants)


def march_forward(marching_ants, bridge_ants):
    """
    将整个行进蚁前移一格，并拆掉最尾端空闲的桥蚁
    :param marching_ants: 行进蚁队列
    :param bridge_ants: 桥蚁队列
    """
    print(marching_ants, bridge_ants)
    for ant in marching_ants:
        ant[1] += 1
    if len(marching_ants) == 0 or (len(bridge_ants) > 0 and bridge_ants[0][1] < marching_ants[0][1]):
        marching_ants.appendleft(bridge_ants.popleft())

def ant_bridge(ants, terrain):
    q = [ c for c in ants ]
    terrain = [ c for c in terrain ] + ['-']
    for i in range(len(terrain)-1):
        if terrain[i] == '-' and terrain[i+1] == '.':
                terrain[i] = q.pop()
                q.insert(0, terrain[i])
        elif terrain[i] == '.':
            terrain[i] = q.pop()
            q.insert(0, terrain[i])
            if terrain[i+1] == '-':
                terrain[i+1] = q.pop()
                q.insert(0, terrain[i+1])

    rest = "".join(q)
    return rest


def ant_bridge(ants, terrain):
    b = 0
    for i, c in enumerate(terrain):
        if c == '.':
            b += 1
        elif b:        
            b = b + (1 if terrain[i-2-b] == '.' else 2)
            ants, b = ants[-b:] + ants[:-b], 0

    return ants

ant_bridge=lambda w,s:(lambda n:w[n:]+w[:n])(-len(''.join(__import__('re').findall('(?:-\.+)+-',s)))%len(w))

def ant_bridge(ants, terrain):
    n = terrain.replace('-.', '..').replace('.-', '..').count('.') % len(ants)
    return ants[-n:] + ants[:-n]

def ant_bridge(a, t):
    t=t.replace('-.','..').replace('.-','..').strip('-')
    A,B=list(a),[]
    while t:
        t=t.lstrip('-')[1:]
        B+=[A.pop()if A else B.pop(0)]
    return ''.join(B[::-1]+A)