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!