// SET V1.2
// Will Kellogg
// Nov 8, 2004


/*
Program description

This program attempts to determine the largest number
of cards from the 256 card deck that can be dealt that
do not contain a set.  The algorithm is as follows:

1.  Randomly select a card from the main deck to the active deck
2.  Determine if active deck now contains a set
	a.  if the active deck does contain a set, then remove it
	b.  if the active deck does not contain a set, continue
*/


// Include statements
#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
#include <math.h>
#include <stdlib.h>
#include <dos.h>
#include <time.h>


// Stuctures and global declarations
typedef struct card
{
   int number;		// 1 - 256
   int dealt;           // 0 = no, 1 = yes
   int d1;   		// 1 - 4
   int d2;   		// 1 - 4
   int d3;   		// 1 - 4
   int d4;   		// 1 - 4
};


// Function prototypes

void initialize_deck(card []);
void re_initialize_deck(card []);
void print_card(card);
void print_set(int, int, int, int, card [], int);
int test_for_set(card [], int, int);

// Main program
int main ()
{

   card deck[256];
   card active_deck[256];
   card max_deck[256];
   int num;
   int set;		// 0 = no set, 1 = at least 1 set
   int card_num;
   int cards_dealt;
   int max = 0;
   int print = 0;
   int count;
   long int trials, x, y;


   clrscr();

   // initialize the deck
   initialize_deck(deck);

   // input a number of trials to run
   cout << "How many trials do you want to run?" << endl;
   cout << "> ";
   cin >> trials;

   clrscr();

   srand(time(0));
   for(x=0;x<trials;x++)
   {
      // initialize the deck
      re_initialize_deck(deck);

      num = 0;
      card_num = 0;
      set = 0;

      count=0;
      while(count != 50)
      {
	 // move 1 card from deck to active_deck
	 card_num = (rand() % 256);
	 if (deck[card_num].dealt == 0)
	 {
	    deck[card_num].dealt = 1;
	    active_deck[num] = deck[card_num];
	    num++;
	    if (num >= 4)
	    {
	       set = test_for_set(active_deck, num, print);
	    }
	 }
	 if(set==1)
	 {
	    num--;
	    count++;
	 }
      }


      /*
      if(((x+1)%30)==0)
      {
	 cout<<endl<<endl<<"Press any key to continue."<<endl;
	 getch();
	 cout<<endl<<endl;
      }
      */

      // check for new max
      if(num > max)
      {
	 max = num;
	 cout << "Trial #" << setw(8) << x+1 << ": " << num << endl;
	 for(y=0;y<num;y++)
	 {
	    max_deck[y]=active_deck[y];
	 }
      }
   }

   // display the maximum number of cards
   cout<<endl<<endl;
   cout<<"The maximum number of cards that do not" << endl;
   cout<<"contain a set out of " << trials << " trials was "
       << max << "." << endl << endl;
   cout<<"Press any key to continue."<<endl;
   getch();

   // display the cards that produced the maximum number
   cout<<endl;
   cout<< "The cards that produced the maximum number are as follows:" << endl << endl;
   for(y=0;y<max;y++)
   {
      print_card(max_deck[y]);
      if(((y+1)%30)==0)
      {
	 cout<<endl<<"Press any key to continue."<<endl;
	 getch();
	 cout<<endl;
      }
   }
   cout<<endl<<"Press any key to continue."<<endl;
   getch();

   // Exit program
   cout << endl << endl << "Press any key to exit.";
   getch();
   clrscr();
   return 0;
}


// FUNCTIONS


// initialize_deck
void initialize_deck(card d[])
{
   int w, x, y, z;
   int num = 1;

   for(w = 1; w <= 4; w++)
   {
      for(x = 1; x <= 4; x++)
      {
	 for(y = 1; y <= 4; y++)
	 {
	    for(z = 1; z <= 4; z++)
	    {
	       d[num].d1 = w;
	       d[num].d2 = x;
	       d[num].d3 = y;
	       d[num].d4 = z;
	       d[num].number = num+1;
	       d[num].dealt = 0;
	       num++;
	    }
	 }
      }
   }

   return;
}


// re_initialize_deck
void re_initialize_deck(card d[])
{
   for(int x = 0; x < 256; x++)
   {
      d[x].dealt = 0;
   }
}


// print_card
void print_card(card c)
{
   cout << "Card #" << setw(4) << c.number << ": "
	<< c.d1 << c.d2 << c.d3 << c.d4 << endl;
   return;
}


// print_set
void print_set(int w, int x, int y, int z, card d[], int n)
{
   print_card(d[w]);
   print_card(d[x]);
   print_card(d[y]);
   print_card(d[z]);

   return;
}


// test_for_set
int test_for_set(card d[], int n, int p)
{
   int set = 0;
   int w, x, y, z;


   for(w = 0; w < n - 3; w++)
   {
      for(x = w+1; x < n - 2; x++)
      {
	 for(y = x+1; y < n - 1; y++)
	 {
	    for(z = y+1; z < n; z++)
	    {
	       // #1:  1111
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4==d[x].d3)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))

	       {
		  set=1;
	       }
	       // #2:  1110
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4!=d[x].d4)&&(d[w].d4!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		   (d[x].d4!=d[y].d4)&&(d[x].d4!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set=1;
	       }
	       // #3:  1101
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		   (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		  ((d[w].d4==d[x].d3)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))
	       {
		  set=1;
	       }
	       // #4:  1011
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		   (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4==d[x].d3)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))
	       {
		  set=1;
	       }
	       // #5:  0111
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		   (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4==d[x].d3)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))
	       {
		  set=1;
	       }
	       // #6:  1100
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		   (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		  ((d[w].d4!=d[x].d4)&&(d[w].d4!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		   (d[x].d4!=d[y].d4)&&(d[x].d4!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set=1;
	       }
	       // #7:  1001
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		   (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		  ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		   (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		  ((d[w].d4==d[x].d4)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))
	       {
		  set=1;
	       }
	       // #8:  0011
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		   (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		  ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		   (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4==d[x].d4)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))
	       {
		  set=1;
	       }
	       // #9:  1010
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		   (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4!=d[x].d4)&&(d[w].d3!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		   (d[x].d4!=d[y].d4)&&(d[x].d3!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set=1;
	       }
	       // #10: 0101
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		   (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		   (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		  ((d[w].d4==d[x].d4)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))
	       {
		  set=1;
	       }
	       // #11: 0110
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		   (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4!=d[x].d4)&&(d[w].d4!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		   (d[x].d4!=d[y].d4)&&(d[x].d4!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set=1;
	       }

	       // #12: 0001
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		   (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		  ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		   (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		  ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		   (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		  ((d[w].d4==d[x].d4)&&(d[x].d4==d[y].d4)&&(d[y].d4==d[z].d4)))
	       {
		  set = 1;
	       }
	       // #13: 0010
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		   (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		  ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		   (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		  ((d[w].d3==d[x].d3)&&(d[x].d3==d[y].d3)&&(d[y].d3==d[z].d3))&&
		  ((d[w].d4!=d[x].d4)&&(d[w].d4!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		   (d[x].d4!=d[y].d4)&&(d[x].d4!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set = 1;
	       }
	       // #14: 0100
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		   (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		  ((d[w].d2==d[x].d2)&&(d[x].d2==d[y].d2)&&(d[y].d2==d[z].d2))&&
		  ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		   (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		  ((d[w].d4!=d[x].d4)&&(d[w].d4!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		   (d[x].d4!=d[y].d4)&&(d[x].d4!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set = 1;
	       }

	       // #15: 1000
	       if(((d[w].d1==d[x].d1)&&(d[x].d1==d[y].d1)&&(d[y].d1==d[z].d1))&&
		  ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		   (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		  ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		   (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		  ((d[w].d4!=d[x].d4)&&(d[w].d4!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		   (d[x].d4!=d[y].d4)&&(d[x].d4!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set = 1;
	       }
	       // #16: 0000
	       if(((d[w].d1!=d[x].d1)&&(d[w].d1!=d[y].d1)&&(d[w].d1!=d[z].d1)&&
		      (d[x].d1!=d[y].d1)&&(d[x].d1!=d[z].d1)&&(d[y].d1!=d[z].d1))&&
		     ((d[w].d2!=d[x].d2)&&(d[w].d2!=d[y].d2)&&(d[w].d2!=d[z].d2)&&
		      (d[x].d2!=d[y].d2)&&(d[x].d2!=d[z].d2)&&(d[y].d2!=d[z].d2))&&
		     ((d[w].d3!=d[x].d3)&&(d[w].d3!=d[y].d3)&&(d[w].d3!=d[z].d3)&&
		      (d[x].d3!=d[y].d3)&&(d[x].d3!=d[z].d3)&&(d[y].d3!=d[z].d3))&&
		     ((d[w].d4!=d[x].d4)&&(d[w].d4!=d[y].d4)&&(d[w].d4!=d[z].d4)&&
		      (d[x].d4!=d[y].d4)&&(d[x].d4!=d[z].d4)&&(d[y].d4!=d[z].d4)))
	       {
		  set = 1;
	       }
	       if(set==1)
	       {
		  if(p==1)
		  {
		     print_set(w,x,y,z,d,n);
		  }
		  w=n;
		  x=n;
		  y=n;
		  z=n;
	       }
	    } // z
	 } // y
      } // x
   } // w

   return(set);
}