## 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: interview

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:
        # Deal ends and current player wins common pile
        if deal_start == player:
            hands[player] = common[::-1] + hands[player]
            deal_start, deal_value, common = None, 0, []
            continue
        # Cards are drawn and deal begins if penalty occurs
        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

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
    game = True
    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)}
    #print(hands)
    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
        # Play as many cards as mandated by punishments
        for i in range(punishments[v]):
            if player_won():
                return
            # If next card is special, stop and punish opponent
            val = play_card(index)
            if val in punishments:
                punish(opponent_index(index), val)
                return
        # Player completed their punishment so other player wins common
        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)
            
    # Driver code
    while(not player_won() and cards_played < MAX_PLAYED):
        # Play next card and set next player
        val = play_card(player_index)
        player_index = opponent_index(player_index)
        # If val is special, set next player with punish
        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