Robert Eisele
Engineer, Systems Architect and DBA

Codingame: War

The Goal

Let's go back to basics with this simple card game: war!

Your goal is to write a program which finds out which player is the winner for a given card distribution of the "war" game.

Rules

War is a card game played between two players. Each player gets a variable number of cards of the beginning of the game: that's the player's deck. Cards are placed face down on top of each deck.
Step 1 : the fight
At each game round, in unison, each player reveals the top card of their deck – this is a "battle" – and the player with the higher card takes both the cards played and moves them to the bottom of their stack. The cards are ordered by value as follows, from weakest to strongest:
2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A.
Step 2 : war
If the two cards played are of equal value, then there is a "war". First, both players place the three next cards of their pile face down. Then they go back to step 1 to decide who is going to win the war (several "wars" can be chained). As soon as a player wins a "war", the winner adds all the cards from the "war" to their deck.
Special cases:
  • If a player runs out of cards during a "war" (when giving up the three cards or when doing the battle), then the game ends and both players are placed equally first.
  • The test cases provided in this puzzle are built in such a way that a game always ends (you do not have to deal with infinite games)
Each card is represented by its value followed by its suit: D, H, C, S. For example: 4H, 8C, AS.

When a player wins a battle, they put back the cards at the bottom of their deck in a precise order. First the cards from the first player, then the one from the second player (for a "war", all the cards from the first player then all the cards from the second player).

For example, if the card distribution is the following:
Player 1 : 10D 9S 8D KH 7D 5H 6S
Player 2 : 10H 7H 5C QC 2C 4H 6D
Then after one game turn, it will be:
Player 1 : 5H 6S 10D 9S 8D KH 7D 10H 7H 5C QC 2C
Player 2 : 4H 6D
Victory Conditions
A player wins when the other player no longer has cards in their deck.

Game Input

Input

Line 1: the number N of cards for player one.

N next lines: the cards of player one.

Next line: the number M of cards for player two.

M next lines: the cards of player two.

Output
  • If players are equally first: PAT
  • Otherwise, the player number (1 or 2) followed by the number of game rounds separated by a space character. A war or a succession of wars count as one game round.
Constraints
0 < N, M < 1000

Solution

We are interested in the value of the cards only, so stripping the color when reading in the decks at the beginning is totally fine:

var deck1 = [];
var deck2 = [];

function parse(a) {
  var cards = ["2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"];
  return cards.indexOf(a.substr(0, a.length - 1));
}

var n = +readline();
for (var i = 0; i < n; i++) {
  deck1.push(parse(readline()));
}
var n = +readline();
for (var i = 0; i < n; i++) {
  deck2.push(parse(readline()));
}

What now follows is just a translation of the verbal description of the algorithm. We take the first card of both decks, if they are equal we check the size of the decks to make a PAT if necessary. After that three additional cards will be placed into each pot. If a deck gets empty this way, we finish the game, if not we go into round two. We continue this algorithm until the played cards are different. If they are, we choose the winner and attribute the pot to the winners deck. Implemented in JavaScript, the algorithm looks like this:

var round = 1;

var pot1 = [];
var pot2 = [];

while (1) {

  // Battle
  var card1 = deck1.shift();
  var card2 = deck2.shift();

  if (card1 !== card2) {

    pot1.push(card1);
    pot2.push(card2);

    // Atribute gain
    if (card1 > card2) deck1 = deck1.concat(pot1, pot2);
                  else deck2 = deck2.concat(pot1, pot2);
    pot1 = [];
    pot2 = [];

    if (deck2.length === 0) {
      print("1 " + round);
      break;
    }

    if (deck1.length === 0) {
      print("2 " + round);
      break;
    }

    round++;

  } else if (deck1.length < 3 || deck2.length < 3) {
    print('PAT');
    break;
  } else {

    pot1.push(card1);
    pot2.push(card2);

    pot1.push(deck1.shift());
    pot1.push(deck1.shift());
    pot1.push(deck1.shift());

    pot2.push(deck2.shift());
    pot2.push(deck2.shift());
    pot2.push(deck2.shift());
  }
}

Go to overview