Programming challenges – War!

The book programming challenges is one I see recommended quite often – so, I decided to give it a try. The first problem I’ve encountered involves replicating a children’s card game called war, which I’d honestly never heard before. The problem is stated as such:

A standard 52-card deck is dealt to two players (1 and 2) such that each player has 26 cards.
Players do not look at their cards, but keep them in a packet face down.
The object of the game is to win all the cards. Both players play by turning their top cards face up and putting them on the table.
Whoever turned the higher card takes both cards and adds them (face down) to the bottom of their packet. Cards rank as usual from high to low: A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3, 2.
Suits are ignored.
Both players then turn up their next card and repeat.
The game continues until one player wins by taking all the cards.
When the face up cards are of equal rank there is a war.
These cards stay on the table as both players play the next card of their pile face down and then another card face up.
Whoever has the higher of the new face up cards wins the war, and adds all six cards to the bottom of his or her packet.
If the new face up cards are equal as well, the war continues: each player puts another card face down and one face up.
The war goes on like this as long as the face up cards continue to be equal.
As soon as they are different, the player with the higher face up card wins all the cards on the table.
If someone runs out of cards in the middle of a war, the other player automatically wins.
The cards are added to the back of the winner’s hand in the exact order they were dealt, specifically 1’s first card, 2’s first card, 1’s second card, etc.

Nothing complex so far. So, I scroll down to see the solution and I’m welcomed by this snippet:

#define NCARDS 52 /* number of cards */
#define NSUITS 4 /* number of suits */

char values[] = "23456789TJQKA";
char suits[] = "cdhs";

int rank_card(char value, char suit)
{
    int i,j; /* counters */
    for (i=0; i<(NCARDS/NSUITS); i++)
        if (values[i]==value)
            for (j=0; j<NSUITS; j++)
                if (suits[j]==suit)
                    return( i*NSUITS + j );
    printf("Warning: bad input value=%d, suit=%d\n",value,suit);
}

Ugly! 5 (FIVE) levels of nesting! I understand that it’s C we’re talking about here but that seems a bit more complex than it should be. I stopped right there and rolled my own solution in Ruby (yeah, I’ve got nothing better to do tonight). This is the result:

Let’s define some constants first:

A = 14

SPADES = :s
DIAMONDS = :d
HEARTS = :h
CLUBS = :c

SUITS = [SPADES, DIAMONDS, HEARTS, CLUBS]

We’ll have to deal with cards – so let’s define a class for them

class Card

  attr_reader :rank
  
  def initialize(rank, suit)
    @rank = rank
    @suit = suit #unused
  end
    
end

Modelling the card like this (with a rank and a suit) makes little sense but the problem specification suggested to do so (as does the C snippet above), so that’s it – cards could have been integers.

Cards will have to be divided into two decks, from which we’ll have to draw and to which we’ll have to add conquered cards. Let’s make a class for them as well. Its methods are quite self explanatory.

class Deck

  def initialize(cards)
    @cards = cards
  end
  
  def draw
    return @cards.pop
  end
  
  def collect(stack)
    while(!stack.empty?) do
      @cards.insert(0, stack.shift)
    end
  end
  
  def empty?
    return !@cards.any?
  end

end

Now let’s generate the two starting decks (this is the equivalent of the C snippet above. It’s not straightforward, but I find it way more readable written this way.)

def create_decks
  all_cards = ((2..A).to_a).product(SUITS).map { |x| Card.new(*x) }.shuffle
  return [all_cards[0..(all_cards.count/2 - 1)], all_cards[(all_cards.count/2)..all_cards.count]].map { |x| Deck.new(x) }
end

And now the game logic. If one of the two players can’t draw, he or she loses. If the two players draw cards with different ranks, the winning player is the one who drew the card with the highest rank. If the ranks are equal, then we get into a war. Let’s wrap this piece of logic like so:

def determine_outcome(card1, card2)
  return @deck2 unless card1 #if player 1 can't draw player 2 wins 
  return @deck1 unless card2 #and vice versa
  return war if(card1.rank == card2.rank) 
  return card1.rank > card2.rank ? @deck1 : @deck2
end

Where do card1 and card2 come from? We drew them from the respective player’s deck. The cards go on the table (here represented by the @stack), and the winner takes all the cards after resolution.

def combat
  @stack << @deck1.draw
  @stack << @deck2.draw	
  winner = determine_outcome(@stack[-2], @stack[-1])	
  winner.collect(@stack)	
  return winner
end

Note that, since a war might have happened, there might be more than just the two cards added here in the @stack.
Let’s now see how #war is implemented:

def war
  @stack << @deck1.draw #facedown
  @stack << @deck1.draw
  @stack << @deck2.draw #facedown
  @stack << @deck2.draw
  return determine_outcome(@stack[-3], @stack[-1])
end

We add four cards in total to the stack: first, the first player draws a card, face down. This card is not used at all in the game, except for beling “pillaged” by the winning player. Then the first player draws another card, this one face up – this is the one that will be used for the comparison. The second player does the same. Then we pass the topmost and the third from top card on the @stack (table) to the comparison function – those are the cards played face up.

The game loop goes like this:

def play
  turns = 0
  while [@deck1, @deck2].all? { |x| !x.empty? }
    winner = combat	  
    turns += 1
  end
  print "TURNS : #{turns}\n"
  print "WINNER : player#{winner == @deck1 ? 1 : 2}\n"
end

So, we count the turns passed and we keep drawing until one of the decks is empty. The winner is the last player winning a “fight”.

You can find the complete listing as a gist here. Note that the program will sometime go into an infinite loop – that’s not a bug, it’s actually likely that the game itself as it’s stated is undecisive, and the two player keep drawing forever without having a winner!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s