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

Learning and open source projects

Learning is a very subjective matter and surely there are many different ways one can improve her skill, ranging from attending lectures all the way to open your favourite editor and hack randomly until you get it. Anyway, no matter how you learn the craft, the goal of practice is to add new tools to your belt so your can deal better with Real World™ problems.
Much easier said than done, though. There is often a wide gap between what you learn “by yourself” and what needs to be done in a production environment: that new technology/pattern/feature you just learnt of might look so cool that you really have to use it everywhere, just to find out some time later that your approach was too naïve and needs a rewrite, or that the technology was just not suited to the problem and you need to switch back to the old one, or that the guy who’s in charge of support really does not have a clue of what the code you wrote is supposed to do (you know, the fact you are willing to give up some of your spare time and learn new things outside work doesn’t mean everyone is).
One of the ways you can find out if you’re doing something that makes sense outside your devbox would be to go and take a look at what others have done in a similar situation and – guess what – open source projects are a great source of tested and reliable code, but the size of the projects can be sometime overwhelming: at first you just don’t know where to start looking and, without a sound approach, you can spend a lot of time before finding out how a feature is implemented from start to end.
I’ve been delving into open source code for a while now. I didn’t find much guidance around so I had to learn the hard way. I hope the following tips will be of some help to you:

start from tests – tests are often a great starting point: if they’re well written you can understand what a method is supposed to do without even looking at the implementation. You can use tests as they were a map (or an index) of the project.

start small – pick a minor feature at first, or even just a method if you can’t find a feature small enough. It might not be extremely interesting to know that datamapper checks for properties to be present on the model before querying but at least now you’ve got an handle, you can explore deeper from there.

when in doubt, debug – more than often the code will be not clear enough or not commented enough to be understandable. In those case debugging a test makes everything easier: both VS and NetBeans have great debugging capabilities, if you don’t know how to take advantage of the debugger already I strongly suggest you to learn how to. If you are debugging ruby with NetBeans you should install the gem ruby-debug-ide for greatly improved debugging speed.

tinker with the code – a great way to know if you’ve learnt your way into the project is to make some small changes and see if the resulting change in behaviour is the same you were expecting. I suggest you to implement your changes strictly with TDD in this particular case, and to make sure all the project tests are green before and after your modifications so to lower the chances of creating uncatched side effects.

bug fixes come later – I believe that rushing through the learning stage and trying to create a patch to submit without having a deep understanding of the whole project first is a waste not just of your time but also of the guy who is checking your broken patch, so get a grip on your ego and take it easy. I think bug reports are much more useful to submit, and if you’re learning the right way you probably will have plenty of them to send in much before the time you are ready to fix them yourself.