“"Forward!", he cried from the rear
And the front rank died
The general sat and the lines on the map
Moved from side to side”Us and Them -- Pink Floyd
A few army battalions from warring nations have met on an even battlefield. Each nation has one battalion present and all battalions have an equal number of soldiers. Every soldier is armed with one rifle and unlimited ammunition. Every soldier also has perfect shooting accuracy. And all armies follow the rules of engagement below.
Rules of Engagement
1. Each army battalion forms its own straight line queue
2. Each line is formed such that the head of each queue faces the head of the opposing army queue to its left (or when there are only two remaining armies, both queues face toward each other)
3. All queue heads maintain equal distance from their respective targets
4. There is a 1 second delay for each queue head to fire his weapon (time taken to lift weapon, aim, then fire)
5. If a queue head gets hit by any bullets during that 1 second delay (including at the exact moment the head is expected to shoot), he falls before he can fire his rifle. Otherwise, he shoots his rifle and immediately walks back to the end of his queue.
Note that the head will receive all bullets that reach his position during that round.
6. The next soldier in queue then takes his place as head at the start of the next round. If there is only one soldier remaining in a queue, he will stand in place and shoot his rifle every round until he falls or emerges victorious
7. An army is eliminated when all its soldiers have fallen. When an elimination occurs, the eliminator changes their target to the next army queue in sequence at the start of the next round.

8.A. If an elimination occurs during the round, then all remaining armies reposition themselves at the start of the next round and repeat the cycle from step 2. All bullets still in flight at the end of the round will miss all their targets when the repositioning occurs.

8.B If no elimination occurs in the round, start again from step 4.

The Rules of Engagement are followed until there are 0 or 1 surviving armies.
Each round (i.e. queue shift) has a one second duration and the heads of each queue shoot at the same time
Weapons

All nations purchase their munitions from the same supplier, Discount Rifles and Bullets, Inc. (aka DRABI)
All DRABI rifles have perfect firing accuracy. However, because many different machines are used to manufacture the rifles, rifles may or may not have different bullet speeds.

You have a master list of bullet speeds for each rifle and you also know the initial arrangement of all queues in battle. With those resources, you seek to find out which, if any, army survives.

Input

Your function will receive anywhere from `3` to `9` arguments:
- The first argument will always be positive integer representing the `distance` between each queue head and his target
- Any additional arguments will each be given as an array/tuple of positive integers; these arrays each represent an army battalion. Each `i`th value in a given array represents the bullet speed for the `i`th soldier's rifle in that battalion's queue. The bullet speed is measured as `distance / second`.

Output
Return the number of the surviving army, given as its argument position.
Also return an array/tuple of that army's surviving soldiers, by index position from its original list. This list should be sorted in queue order, starting with the queue head at time of victory.
If all battalions are wiped out and there are no survivors, return -1 and an empty array/tuple.
Test Example


The image above references the example given below.
In our example, we are given `3` armies that form their respective queues. Each head (green pointed indicators) faces and fires at the opponent head to the left.
In the tests, each queue head shoots at the head of the next queue that follows, and completes the loop with the last queue shooting at the first.

The image below represents the queues after army `C` is eliminated. Note they change formation and face each other while always maintaining the same distance.



```python
# in Python the first argument is given as a positive int
# subsequent arguments are given as tuples of positive ints
A = (98,112,121,95,63)
B = (120,94,90,88,30)
C = (116,144,45,200,32)

# the function should return a tuple of two elements: an integer and a tuple of integers
# In our example, the first army emerges as the sole survivor, and the remaining queue for that army consists of only the 3rd soldier
queue_battle(300,A,B,C) # returns the tuple (0,(2,))
```


Click here for a step-by-step of the first four rounds of our example test

We'll refer to units of distance as DU (distance units)
Round 1
After initial 1 second delay, each queue head fires, then goes to the back of their respective queue.

Round 2
The next soldier for each queue fires their weapon after a 1 second delay. At the moment each soldier fires, there are already 3 bullets in flight:
- Bullet 0: traveling at 98 DU per second, it has already traveled for 1 second and is now 202 DU away from its target (the head of queue B)
- Bullet 1: traveling at 120 DU per second, it is 180 DU away from its target.
- Bullet 2: traveling at 116 DU per second, it is 184 DU away from its target.

Round 3
At the moment when the next queue heads fire, there are 6 bullets in flight (not including the bullets fired this round).
The 1st round of bullets have now traveled 196, 240, and 232 DU, respectively.
The 2nd round of bullets have traveled 112, 94, and 144 DU, respectively.
Round 4
First blood is drawn during this round.
Before the head of queue C can fire, he is hit by the first bullet shot by queue B. The head of queue A is also shot before he can fire.
The only head that fires his rifle is from queue B.
At this point, there are 7 bullets in flight, excluding the bullet shot this round.
The first bullet shot by queue A has now traveled 294 DU, and is therefore 6 DU away from its target. It will reach its target in round 5, before the queue head can fire.



In our example, we saw the new positioning when going from 3 to 2 queues. Other tests will have a random number of queues (up to a max of 8).
The following diagrams serve as a visual guide to show other battle positions formed depending on the number of active queues.


Technical Details

- All tests will be valid
- Test constraints:
        - `2 <= number of queues <= 8`
        - `8 <= bullet speed < 2e6`
        - `80 <= distance < 1e6`
        - `bullet speed >= distance/10`
        - `5 <= queue length < 2000`
- Use Python 3.6+ for the Python translation
- In JavaScript, `module` and `require` are disabled
- Full Test Suite: `10` fixed tests and `150` random tests

If you enjoyed this kata, be sure to check out my other katas

Source: codewars | Difficulty: MEDIUM
Tags: Data structures

Game theory

Ad-hoc

Starter code: def queue_battle(dist,*armies):
	

Solutions:
from heapq import *
from itertools import starmap
from collections import deque, namedtuple
Army = namedtuple('Army', 'i,q')
Soldier = namedtuple('Soldier', 'i,speed')

def queue_battle(d, *args):
	armies = [Army(i, deque(starmap(Soldier, enumerate(q)))) for (i, q) in enumerate(args)]
	bullets = [[] for _ in range(len(armies))]
	t = 0
	while len(armies) > 1:
		t += 1
		alives = [1] * len(armies)
		for (i, q) in enumerate(bullets):
			if q and q[0] <= t:
				alives[(i + 1) % len(armies)] = 0
			while q and q[0] <= t:
				heappop(q)
		emptyArmies = False
		for (i, alive) in enumerate(alives):
			if alive:
				heappush(bullets[i], t + d / armies[i].q[0].speed)
				armies[i].q.rotate(-1)
			else:
				armies[i].q.popleft()
				emptyArmies |= not armies[i].q
		if emptyArmies:
			armies = [army for army in armies if army.q]
			bullets = [[] for _ in range(len(armies))]
	if not armies:
		return (-1, ())
	win = armies.pop()
	return (win.i, tuple((soldier.i for soldier in win.q)))


def queue_battle(dist, *armies):
	armies_copy = [*armies]
	armies = [[*a] for a in armies]
	armies_left = [i for i in range(len(armies))]
	soldiers_id = [[i for i in range(len(army))] for army in armies]
	bullets_between = [[] for i in armies_left]
	while True:
		bullets_between = [[[s, s + l] for (s, l) in bullets] for bullets in bullets_between]
		recovering_armies = []
		for i in range(len(bullets_between)):
			for j in range(len(bullets_between[i])):
				if bullets_between[i][j][1] >= dist:
					del armies[armies_left[(i + 1) % len(armies_left)]][0]
					del soldiers_id[armies_left[(i + 1) % len(armies_left)]][0]
					recovering_armies.append(armies_left[(i + 1) % len(armies_left)])
					break
			bullets = []
			for j in range(len(bullets_between[i])):
				if bullets_between[i][j][1] < dist:
					bullets.append(bullets_between[i][j])
			bullets_between[i] = bullets
		for i in range(len(armies_left)):
			if armies_left[i] not in recovering_armies:
				bullet_speed = armies[armies_left[i]][0]
				bullets_between[i].append([bullet_speed, 0])
		if len(armies_left) == 0:
			return (-1, ())
		if len(armies_left) == 1:
			return (armies_left[0], tuple(soldiers_id[armies_left[0]]))
		for i in range(len(armies_left)):
			if armies_left[i] not in recovering_armies:
				soldiers_id[armies_left[i]].append(soldiers_id[armies_left[i]].pop(0))
				armies[armies_left[i]].append(armies[armies_left[i]].pop(0))
		armies_left_new = [*armies_left]
		for i in range(len(armies_left)):
			if len(armies[armies_left[i]]) == 0:
				armies_left_new.remove(armies_left[i])
				bullets_between = [[] for i in armies_left_new]
		armies_left = armies_left_new
	return


def queue_battle(dist, *armies0):
	armies = [{'idx': idx, 'soldier': [{'idx': idx, 'speed': el, 'remove': False} for (idx, el) in enumerate(a)]} for (idx, a) in enumerate(armies0)]
	bullets = [[] for i in range(len(armies))]
	while len(armies) > 1:
		for i in range(len(bullets)):
			bullets2 = list(filter(lambda d: d['dist'] < dist, map(lambda d: {'dist': d['dist'] + d['speed'], 'speed': d['speed']}, bullets[i])))
			if len(bullets2) != len(bullets[i]):
				armies[(i + 1) % len(armies)]['soldier'][0]['remove'] = True
			bullets[i] = bullets2
		armies = list(filter(lambda a: not (len(a['soldier']) == 1 and a['soldier'][0]['remove']), armies))
		elimination = len(armies) != len(bullets)
		for i in range(len(armies)):
			el = armies[i]['soldier'].pop(0)
			if not el['remove']:
				bullets[i].append({'dist': 0, 'speed': el['speed']})
				armies[i]['soldier'].append(el)
		if elimination:
			bullets = [[] for i in range(len(armies))]
	if len(armies) > 0:
		return (armies[0]['idx'], tuple(map(lambda s: s['idx'], armies[0]['soldier'])))
	return (-1, ())


from collections import deque

class Bullet:

	def __init__(self, speed, target_army):
		self.time_to_hit = DIST / speed
		self.target_army = target_army

	def increment_time(self, seconds):
		self.time_to_hit -= seconds

	def has_hit(self):
		return self.time_to_hit <= 0.0

class Soldier:

	def __init__(self, original_index, bullet_speed):
		self.original_index = original_index
		self.bullet_speed = bullet_speed

	def fire_bullet(self, target_army):
		return Bullet(self.bullet_speed, target_army)

class Army:

	def __init__(self, original_index, soldiers):
		self.soldiers = deque(soldiers)
		self.original_index = original_index

	def fire_bullet(self, target_army):
		if self.is_wiped_out():
			raise Exception('tried to fire bullet on wiped out army!')
		bullet = self.soldiers[0].fire_bullet(target_army)
		self.soldiers.rotate(-1)
		return bullet

	def is_wiped_out(self):
		return len(self.soldiers) == 0

	def eliminate_head(self):
		if self.is_wiped_out():
			raise Exception('tried to kill someone on wiped out army!')
		self.soldiers.popleft()

class Battlefield:

	def __init__(self, armies):
		self.armies = armies
		self.bullets = []

	def increment_second(self):
		armies_hit = []
		for bullet in self.bullets:
			bullet.increment_time(1)
			if bullet.has_hit() and bullet.target_army not in armies_hit:
				target = self.armies[bullet.target_army]
				target.eliminate_head()
				armies_hit.append(bullet.target_army)
		for (i, army) in enumerate(self.armies):
			if not i in armies_hit:
				bullet = army.fire_bullet((i + 1) % len(self.armies))
				self.bullets.append(bullet)
		if any((army.is_wiped_out() for army in self.armies)):
			self.bullets = []
			self.armies = [army for army in self.armies if not army.is_wiped_out()]
		else:
			self.bullets = [bullet for bullet in self.bullets if not bullet.has_hit()]

	def do_battle(self):
		while len(self.armies) > 1:
			self.increment_second()
		return self.armies[0] if self.armies else None

def queue_battle(dist, *armies):
	nonlocal DIST, N_ARMIES
	DIST = dist
	N_ARMIES = len(armies)
	army_list = []
	for i in range(N_ARMIES):
		soldiers = [Soldier(j, speed) for (j, speed) in enumerate(armies[i])]
		army_list.append(Army(i, soldiers))
	battlefield = Battlefield(army_list)
	winner = battlefield.do_battle()
	if winner is None:
		return (-1, ())
	else:
		soldiers = tuple([soldier.original_index for soldier in winner.soldiers])
		return (winner.original_index, soldiers)


def queue_battle(dist, *armies):
	DIST = dist
	ARMY_COUNT = len(armies)
	active_armies = []
	for army in range(0, ARMY_COUNT):
		active_armies.append(army)
	queues = {}
	for (n, army) in enumerate(armies):
		if n == len(armies) - 1:
			target = 0
		else:
			target = n + 1
		queues[n] = {'target': target, 'army': {k: v for (k, v) in enumerate(list(army))}}
	bullet_count = 1
	bullets = {}
	no_victor = True
	while no_victor:
		bullets_hit = []
		targets_hit = []
		for (bullet, data) in bullets.items():
			bullets[bullet]['dist'] += bullets[bullet]['speed']
			if bullets[bullet]['dist'] >= DIST:
				bullets_hit.append(bullet)
				targets_hit.append(bullets[bullet]['target'])
		for bullet in bullets_hit:
			bullets.pop(bullet)
		armies_to_be_removed = []
		for army in queues:
			fk = list(queues[army]['army'].keys())[0]
			if army in targets_hit:
				queues[army]['army'].pop(fk)
				if len(queues[army]['army']) == 0:
					armies_to_be_removed.append(army)
			else:
				bullets[bullet_count] = {'dist': 0, 'speed': queues[army]['army'][fk], 'target': queues[army]['target']}
				bullet_count += 1
				x = queues[army]['army'][fk]
				queues[army]['army'].pop(fk)
				queues[army]['army'][fk] = x
		if len(armies_to_be_removed) > 0:
			bullets = {}
		for army in armies_to_be_removed:
			active_armies.remove(army)
			queues.pop(army)
		for army in queues:
			if queues[army]['target'] not in active_armies:
				new_target = active_armies.index(army) + 1
				if new_target > len(active_armies) - 1:
					new_target = 0
				queues[army]['target'] = active_armies[new_target]
		if len(queues) <= 1:
			no_victor = False
	if active_armies == []:
		return (-1, ())
	else:
		winning_army = active_armies[0]
		leftover_soldiers = list(queues[army]['army'].keys())
		return (winning_army, tuple(leftover_soldiers))


from collections import deque, namedtuple, defaultdict
Army = namedtuple('Army', ('num', 'soldiers'))
Soldier = namedtuple('Soldier', ('num', 'speed'))

def queue_battle(distance, *armies):
	bullets = defaultdict(set)
	now = 0
	armies = [Army(an, deque((Soldier(sn, sp) for (sn, sp) in enumerate(army)))) for (an, army) in enumerate(armies)]
	while len(armies) > 1:
		now += 1
		fallen = bullets.pop(now, {})
		eliminated = []
		for ai in fallen:
			armies[ai].soldiers.popleft()
			if not armies[ai].soldiers:
				eliminated.append(ai)
		for (ai, army) in enumerate(armies):
			if ai in fallen:
				continue
			target = (ai + 1) % len(armies)
			ttime = now + 1 + (distance - 1) // army.soldiers[0].speed
			bullets[ttime].add(target)
			army.soldiers.rotate(-1)
		if eliminated:
			armies = [army for (ai, army) in enumerate(armies) if ai not in eliminated]
			bullets.clear()
	if armies:
		return (armies[0].num, tuple((s.num for s in armies[0].soldiers)))
	else:
		return (-1, ())


from collections import deque

def play_round(dist, army_map):
	armies = list(army_map.keys())
	in_flight = {i: list() for i in armies}
	fires_at = {src: dst for (src, dst) in zip(armies, armies[1:] + [armies[0]])}
	while True:
		in_flight = {i: [(travel - speed, speed) for (travel, speed) in bullets] for (i, bullets) in list(in_flight.items())}
		for (i, bullets) in list(in_flight.items()):
			if any((travel <= 0 for (travel, _) in bullets)):
				in_flight[i] = [(travel, speed) for (travel, speed) in bullets if travel > 0]
				army_map[fires_at[i]][0] = (None, None)
		for (i, army) in list(army_map.items()):
			(j, head) = army.popleft()
			if head is not None:
				in_flight[i].append((dist, head))
				army.append((j, head))
		if any((len(army) == 0 for army in list(army_map.values()))):
			return {i: army for (i, army) in list(army_map.items()) if len(army) != 0}

def queue_battle(dist, *armies):
	army_map = {i: deque(enumerate(army)) for (i, army) in enumerate(armies)}
	while len(army_map) >= 2:
		army_map = play_round(dist, army_map)
	if len(army_map) == 0:
		return (-1, tuple())
	(i, army) = list(army_map.items())[0]
	return (i, tuple((j for (j, _) in army)))


from collections import deque

class Bullet:

	def __init__(self, speed):
		self.speed = speed
		self.location = 0

	def update(self):
		self.location += self.speed

class Soldier:

	def __init__(self, number, firing_speed):
		self.number = number
		self.firing_speed = firing_speed

class Army:

	def __init__(self, number, firing_speeds):
		self.number = number
		self.soldiers = deque()
		for (n, firing_speed) in enumerate(firing_speeds):
			self.soldiers.append(Soldier(n, firing_speed))

def queue_battle(distance, *args):
	armies = [Army(n, army) for (n, army) in enumerate(args)]
	while len(armies) > 1:
		bullets = {army: [] for army in range(len(armies))}
		an_army_eliminated = False
		while not an_army_eliminated:
			for army in range(len(armies)):
				for bullet in bullets[army]:
					bullet.update()
			for army in range(len(armies)):
				for bullet in bullets[army]:
					if bullet.location >= distance:
						armies[army].soldiers.popleft()
						if not armies[army].soldiers:
							an_army_eliminated = True
						break
				else:
					target = army + 1 if army + 1 < len(armies) else 0
					firing_soldier = armies[army].soldiers[0]
					bullets[target].append(Bullet(firing_soldier.firing_speed))
					armies[army].soldiers.append(armies[army].soldiers.popleft())
			for army in range(len(armies)):
				bullets[army] = [bullet for bullet in bullets[army] if bullet.location < distance]
		armies = [army for army in armies if army.soldiers]
	try:
		remaining_army = armies[0]
		return (remaining_army.number, tuple((soldier.number for soldier in remaining_army.soldiers)))
	except IndexError:
		return (-1, ())


class Battalion:

	def __init__(self, position, soldiers, hit):
		self.position = position
		self.soldiers = soldiers
		self.hit = hit

def queue_battle(dist, *armies):
	bullets = []
	armies = [list(((s, i) for (i, s) in enumerate(a))) for a in armies]
	battalions = [Battalion(i, list(a), False) for (i, a) in enumerate(armies)]
	while len(battalions) > 1:
		for b in reversed(bullets):
			target = battalions[b[2]]
			b[0] = b[0] + b[1][0]
			if b[0] >= dist:
				if not target.hit:
					target.soldiers.pop(0)
					target.hit = True
				bullets.remove(b)
		elim = 0
		for (idx, ba) in enumerate(reversed(battalions)):
			if not ba.soldiers:
				battalions.remove(ba)
				bullets = []
				elim += 1
			elif not ba.hit:
				if elim == 0:
					if idx == 0:
						target = 0
					else:
						target = len(battalions) - idx
						if target >= len(battalions):
							target = 0
					bullets.append([0, ba.soldiers[0], target])
				ba.soldiers.insert(len(ba.soldiers), ba.soldiers[0])
				ba.soldiers.pop(0)
			ba.hit = False
	if battalions:
		pos = battalions[0].position
		survivors = tuple([s[1] for s in battalions[0].soldiers])
		return (pos, survivors)
	else:
		return (-1, ())


log = False
from collections import deque

class Game:

	def __init__(self, distance, armies):
		self.round = 0
		self.victory = False
		self.distance = distance
		self.armies = deque([Army(position=i, members=army_tuple) for (i, army_tuple) in enumerate(armies)])
		self.bullets = set()

	def print_state(self):
		if log:
			print('Armies:')
			for army in self.armies:
				print(army)
			if self.bullets:
				print('Bullets:')
				for bullet in self.bullets:
					print(bullet)

	def assign_targets(self):
		if log:
			print('-> Assigning targets')
		for (army, target) in zip(self.armies, range(1, len(self.armies) + 1)):
			if target == len(self.armies):
				target = 0
			army.target = self.armies[target]
		self.print_state()

	def move_bullets(self):
		if log:
			print('-> Moving bullets')
		for bullet in self.bullets:
			bullet.move()
		self.print_state()

	def kill_leaders(self):
		if log:
			print('-> Killing army leaders')
		for bullet in self.bullets:
			if bullet.distance_to_target <= 0:
				bullet.target.leader.alive = False
		self.bullets = {b for b in self.bullets if b.distance_to_target > 0}
		self.print_state()

	def fire_bullets(self):
		if log:
			print('-> Firing bullets')
		for army in self.armies:
			if army.leader.alive:
				self.bullets.add(Bullet(target=army.target, speed=army.leader.bullet_speed, distance_to_target=self.distance))
		self.print_state()

	def regroup_armies(self):
		if log:
			print('-> Regrouping armies')
		for army in self.armies:
			army.regroup()
		original_armies_count = len(self.armies)
		self.armies = deque([army for army in self.armies if len(army.soldiers) > 0])
		if len(self.armies) < original_armies_count:
			self.bullets = set()
		if len(self.armies) <= 1:
			self.victory = True
		self.print_state()

	def render_victory(self):
		if len(self.armies) < 1:
			return (-1, ())
		else:
			return (self.armies[0].original_position, tuple([s.original_position for s in self.armies[0].soldiers]))

	def game_loop(self):
		while True:
			if log:
				print('--> Executing round {}'.format(self.round))
			self.print_state()
			self.assign_targets()
			self.move_bullets()
			self.kill_leaders()
			self.fire_bullets()
			self.regroup_armies()
			if self.victory:
				break
			self.round += 1

class Army:

	def __init__(self, position, members):
		self.original_position = position
		self.soldiers = deque([Soldier(position=i, bullet_speed=bs) for (i, bs) in enumerate(members)])
		self.leader = self.soldiers[0]
		self.target = None

	def regroup(self):
		if self.leader.alive:
			self.soldiers.append(self.soldiers.popleft())
		else:
			self.soldiers.popleft()
		if len(self.soldiers) > 0:
			self.leader = self.soldiers[0]
		else:
			self.leader = None

	def __str__(self):
		return 'Army {army_number} [Soldires: {soldiers}, Leader: {leader}, Target: {target}]'.format(army_number=self.original_position, soldiers=self.soldiers, leader=self.leader, target=repr(self.target))

	def __repr__(self):
		return 'Army {}'.format(self.original_position)

class Soldier:

	def __init__(self, position, bullet_speed):
		self.original_position = position
		self.bullet_speed = bullet_speed
		self.alive = True

	def __repr__(self):
		return '({bullet_speed}, {alive_status})'.format(bullet_speed=self.bullet_speed, alive_status='alive' if self.alive else 'dead')

class Bullet:

	def __init__(self, target, speed, distance_to_target):
		self.target = target
		self.speed = speed
		self.distance_to_target = distance_to_target

	def __str__(self):
		return 'Bullet [Target: {target}, Dist: {distance}, Speed: {speed}]'.format(target=repr(self.target), distance=self.distance_to_target, speed=self.speed)

	def move(self):
		self.distance_to_target -= self.speed

def queue_battle(dist, *armies):
	game = Game(dist, armies)
	game.game_loop()
	return game.render_victory()