1. Technology

Programming Challenge 11 - Find Matching Sets of Cards

By

Cards from the game Set
This programming Challenge ran until the end of April 2008 and is about matching cards from the card game Set. Invented in 1991 by geneticist Marsha Falco; you can't find a simpler type of game that really stretches your brain.

The game has 81 cards each with four varying characteristics.

  1. Number of symbols (One, Two or Three- all the same shape)
  2. Color (One of red, green and purple)
  3. Shape (One of diamond, squiggle, or oval)
  4. Shading (Filled in, empty or cross hatched).
The combinations of 3 x 3 x 3 x 3 = 81 different cards and that's what you get when you buy the Set game. I bought a copy myself years ago and can testify to the fact that when you play it, your brain's CPU gets pretty busy!

The game rules are simple- 12 cards are put down on the table in front of the players and you have to identify a matching set of three before anyone else. The player who spots a set first gets those cards. Then three more cards are put down on the table and it continues until all cards are out and no more sets can be found. The player with the most sets wins.

A matching set is one where the three cards have each of the 4 characteristics all the same or different. For example you can have a set where the shapes and colors are different but the shading and numbers are the same. The picture from Wikipedia shows a set where all 4 characteristics are different.

You can try the game out online at the Set website or play it online at the New York Times Set Game. (Note About.com is owned by the New York Times)

The Challenge

Write a program that simulates the Set game. Specifically it
  • Generates the 81 cards and holds them in memory.
  • Plays 10,000 games of Set.
  • Times how long it takes to play the 10,000 games.

Results

There were five entrants, 1 in C, 1 in C++ and three C#. The winner was the C++ version.
  1. Chris Runyan ( C++ ) in 0.155421 seconds
  2. Andre Prata ( C ) in 0.7865 seconds
  3. Makis ( C# ) in 0.99106 seconds
  4. Shashi Sadasivan ( C# ) in 1.98703 seconds
  5. Robert C. Cartaino ( C# ) in 0.076598 seconds*
Thanks to everyone who entered and congratulations for a very fast winning entry to Chris Runyan.
* My Apologies to Robert C Cartaino whose code I accidentally modified, leaving it limping along when in fact it was very very fast and should be counted as the winning entry (But as it's unfair to change winners due to my mistake...). I have also uploaded the unmodified code. Chris Runyan deservedly gets the title "Fastest C++ in the west".

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus@aboutguide.com?subject=Programming Challenge 11 email address with the subject line Programming Challenge 11.

It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 Express Edition. If it doesn't compile, it can't be run so is automatically disqualified

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is April 30 2008.

The top three entries will be listed according to speed with fastest is best. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

Have fun!

More Programming Challenges

©2014 About.com. All rights reserved.