## Description

Beggar Thy Neighbour is a card game taught to me by my parents when I was a small child, and is a game I like to play with my young kids today.

In this kata you will be given two player hands to be played.  And must return the index of the player who will win.

## Rules of the game

- Special cards are: Jacks, Queens, Kings and Aces
- The object of the game is to win all the cards.
- Any player that cannot play a card is out of the game.

To start:

- The 52 cards in a standard deck are shuffled.
- The cards are dealt equally between all players.

To play:

- The first player turns over and plays the top card from their hand into a common pile.
- If the card is not special - then the second player plays their next card onto the pile, and play continues back to the first player.
- If the card is a Jack, Queen, King or Ace, the other player must play 1, 2, 3 or 4 penalty cards respectively.
- If no special cards are played during a penalty, then the player that played the special card, takes the common pile.
- If a special card is played during a penalty, then the penalty moves back to the previous player immediately with the size of the new penalty defined by the new special card.  It is possible for this process to repeat several times in one play.  Whoever played the last special card, wins the common pile.
- The winner of the common pile, places it on the bottom of their hand, and then starts the next common pile.

It is theorised that an initial deal may never end, though so far all of my games have ended!  For that reason, if 10,000 cards are played and no one has won, return `None`.

## Card Encoding

Cards are represented with a two character code.  The first characater will be one of A23456789TJQK representing Ace, 2 though 9, Ten, Jack, Queen, King respectively.  The second character is the suit, 'S', 'H', 'C', or 'D' representing Spades, Hearts, Clubs and Diamonds respectively.  

For example a hand of `["TD", "AC", "5H"]` would represent 10 of Diamonds, Ace of Clubs, and 5 of hearts.

## Mini Example Game

Given the following hands:

`Player 1: [9C, JC, 2H, QC], Player 2: [TD, JH, 6H, 9S]`

Play would flow as follows:

```
Start   - P1: [9C, JC, 2H, QC],   P2: [TD, JH, 6H, 9S],           Common: []
Turn  1 - P1: [JC, 2H, QC],       P2: [TD, JH, 6H, 9S],           Common: [9C]
Turn  2 - P1: [JC, 2H, QC],       P2: [JH, 6H, 9S],               Common: [9C, TD]
Turn  3 - P1: [2H, QC],           P2: [JH, 6H, 9S],               Common: [9C, TD, JC]
```
Player 1 plays a Jack, player 2 pays 1 penalty
```
Turn  4 - P1: [2H, QC],           P2: [6H, 9S],                   Common: [9C, TD, JC, JH]
```
Player 2 plays a Jack, player 1 pays 1 penalty
```
Turn  5 - P1: [QC],               P2: [6H, 9S],                   Common: [9C, TD, JC, JH, 2H]
```
Player 2 wins the common pool and starts the next game
```
Turn  6 - P1: [QC],               P2: [9S, 9C, TD, JC, JH, 2H],   Common: [6H]
Turn  7 - P1: [],                 P2: [9S, 9C, TD, JC, JH, 2H],   Common: [6H, QC]
```
Player 1 plays a Queen, player 2 pays 2 penalties
```
Turn  8 - P1: [],                 P2: [9C, TD, JC, JH, 2H],       Common: [6H, QC, 9S]
Turn  9 - P1: [],                 P2: [TD, JC, JH, 2H],           Common: [6H, QC, 9S, 9C]
```
Player 1 wins the common pool and starts the next game
```
Turn 10 - P1: [QC, 9S, 9C],       P2: [TD, JC, JH, 2H],           Common: [6H]

```
And so on... with player 2 eventually winning.


Good luck!

Difficulty: MEDIUM_HARD
Tags: Game theory

Starter code:
def who_wins_beggar_thy_neighbour(hand_1, hand_2):
	

Solutions:
def who_wins_beggar_thy_neighbour(*hands, special_cards='JQKA'):
	hands = [list(reversed(hand)) for hand in hands]
	(player, deck_length) = (0, sum(map(len, hands)))
	(deal_start, deal_value, common) = (None, 0, [])
	while len(hands[player]) < deck_length:
		if deal_start == player:
			hands[player] = common[::-1] + hands[player]
			(deal_start, deal_value, common) = (None, 0, [])
			continue
		for _ in range(min(deal_value or 1, len(hands[player]))):
			card = hands[player].pop()
			common.append(card)
			if card[0] in special_cards:
				(deal_start, deal_value) = (player, special_cards.index(card[0]) + 1)
				break
		player = (player + 1) % len(hands)
	return player


from collections import deque

def who_wins_beggar_thy_neighbour(hand_1, hand_2):
	return Game(hand_1, hand_2).play()

class Game(object):
	(LIMIT, SPECIALS) = (10000, {c: n for (n, c) in enumerate('JQKA', 1)})

	def __init__(self, h1, h2):
		self.count = 0
		self.player = 1
		self.piles = [deque(), deque(h1), deque(h2)]

	def play(self):
		while not self.endGame():
			self.playRound()
		return 2 - self.player if self.count < self.LIMIT else None

	def playRound(self):
		wasPenalty = self.getPenalty()
		for _ in range(wasPenalty or 1):
			self.drawCard()
			if self.endGame() or self.getPenalty():
				break
		else:
			if wasPenalty:
				self.otherGetCommon()
		self.player = 3 - self.player

	def endGame(self):
		return not self.piles[self.player] or self.count >= self.LIMIT

	def drawCard(self):
		self.piles[0].append(self.piles[self.player].popleft())
		self.count += 1

	def getPenalty(self):
		return 0 if not self.piles[0] else self.SPECIALS.get(self.piles[0][-1][0], 0)

	def otherGetCommon(self):
		self.piles[3 - self.player].extend(self.piles[0])
		self.piles[0] = deque()


def special(card):
	if card[0] == 'A':
		return 4
	if card[0] == 'K':
		return 3
	if card[0] == 'Q':
		return 2
	if card[0] == 'J':
		return 1
	return 0

def who_wins_beggar_thy_neighbour(player1, player2):
	common = []
	move = 1
	cards = 0
	while cards < 10000:
		while not common or not special(common[-1]):
			if move == 1:
				if not player1:
					return 1
				common.append(player1.pop(0))
				cards += 1
				move = 2
			else:
				if not player2:
					return 0
				common.append(player2.pop(0))
				cards += 1
				move = 1
		penalty = special(common[-1])
		while penalty:
			if move == 1:
				if not player1:
					return 1
				common.append(player1.pop(0))
				cards += 1
				if not special(common[-1]):
					penalty -= 1
				if special(common[-1]):
					penalty = special(common[-1])
					move = 2
			else:
				if not player2:
					return 0
				common.append(player2.pop(0))
				cards += 1
				if not special(common[-1]):
					penalty -= 1
				if special(common[-1]):
					penalty = special(common[-1])
					move = 1
		if move == 1:
			player2.extend(common)
			common = []
			move = 2
		else:
			player1.extend(common)
			common = []
			move = 1
	return None


from collections import deque

def who_wins_beggar_thy_neighbour(hand_1, hand_2):
	hands = [deque(hand_1), deque(hand_2)]
	common = deque()
	penalty = 0
	player = 0
	special = {'J': 1, 'Q': 2, 'K': 3, 'A': 4}
	for turn in range(100000):
		if len(common) == 0:
			if len(hands[0]) == 0:
				return 1
			if len(hands[1]) == 0:
				return 0
		if len(hands[player]) == 0:
			return 1 - player
		card = hands[player].popleft()
		common.append(card)
		if card[0] in special:
			player = 1 - player
			penalty = special[card[0]]
		elif penalty == 0:
			player = 1 - player
		else:
			penalty -= 1
			if penalty == 0:
				player = 1 - player
				while len(common) > 0:
					hands[player].append(common.popleft())
	return None


def who_wins_beggar_thy_neighbour(hand_1, hand_2):
	(hs, vs) = ((hand_1, hand_2), {'J': 1, 'Q': 2, 'K': 3, 'A': 4})
	hands = {player: [vs.get(card[0], 0) for card in hs[player]] for player in range(2)}
	player = 0
	draw = -1
	pile = []
	while hands[player]:
		pile.append(hands[player].pop(0))
		draw -= 1
		if pile[-1] > 0:
			draw = pile[-1]
			player = 1 - player
			continue
		if draw == 0:
			player = 1 - player
			hands[player].extend(pile)
			pile = []
			draw = -1
			continue
		if draw < 0:
			player = 1 - player
	return 1 - player


from collections import deque

def who_wins_beggar_thy_neighbour(*hands):
	special = {c: i + 1 for (i, c) in enumerate('JQKA')}
	hands = [deque((c[0] for c in h)) for h in hands]
	pile = []
	(player, penalty) = (0, 0)
	while hands[player]:
		pile.append(hands[player].popleft())
		penalty -= 1
		if penalty == 0 and (not pile[-1] in special):
			hands[player ^ 1].extend(pile)
			pile = []
		if penalty < 1 or pile[-1] in special:
			player ^= 1
			penalty = special.get(pile[-1], 0) if pile else 0
	return player ^ 1


special = {'J': 1, 'Q': 2, 'K': 3, 'A': 4}

def who_wins_beggar_thy_neighbour(hand_1, hand_2):
	h = [hand_1[:], hand_2[:]]
	pile = []
	turn = 0
	for _ in range(10000):
		while not pile or pile[-1][0] not in special:
			if not h[turn]:
				return turn ^ 1
			pile.append(h[turn].pop(0))
			turn ^= 1
		count = special[pile[-1][0]]
		while count > 0:
			if not h[turn]:
				return turn ^ 1
			pile.append(h[turn].pop(0))
			if pile[-1][0] in special:
				count = special[pile[-1][0]]
				turn ^= 1
				continue
			count -= 1
		turn ^= 1
		h[turn] += pile
		pile = []
	return None


def who_wins_beggar_thy_neighbour(hand_1, hand_2, MAX_PLAYED=10000):
	punishments = {'J': 1, 'Q': 2, 'K': 3, 'A': 4}
	(hands, common) = ([hand_1, hand_2], [])
	(cards_played, player_index) = (0, 0)

	def opponent_index(index):
		return (index + 1) % 2

	def play_card(index):
		nonlocal cards_played, common
		cards_played += 1
		card = hands[index][0]
		hands[index] = hands[index][1:]
		common.append(card)
		return card[0]

	def punish(index, v):
		nonlocal player_index, common
		for i in range(punishments[v]):
			if player_won():
				return
			val = play_card(index)
			if val in punishments:
				punish(opponent_index(index), val)
				return
		player_index = opponent_index(index)
		hands[player_index].extend(common)
		common = []
		return

	def player_won():
		return not hands[0] or not hands[1]

	def get_winner():
		assert player_won()
		if not hands[0]:
			return opponent_index(0)
		if not hands[1]:
			return opponent_index(1)
	while not player_won() and cards_played < MAX_PLAYED:
		val = play_card(player_index)
		player_index = opponent_index(player_index)
		if val in punishments:
			punish(player_index, val)
	if player_won():
		return get_winner()
	return None


SPECIAL = {'J': 1, 'Q': 2, 'K': 3, 'A': 4}

def who_wins_beggar_thy_neighbour(hand_1, hand_2):
	turn = 0
	players = [[SPECIAL.get(card[0], 0) for card in hand] for hand in (hand_1, hand_2)]
	pot = []
	penalty = 0
	time = 0
	while time < 10000:
		time += 1
		try:
			if penalty:
				for __ in range(penalty):
					card = players[turn].pop(0)
					pot.append(card)
					if card:
						break
				else:
					players[(turn + 1) % 2] += pot
					pot = []
			else:
				card = players[turn].pop(0)
				pot.append(card)
		except IndexError:
			return (turn + 1) % 2
		penalty = card
		turn = (turn + 1) % 2