/******************************************************************************
 * AUTHOR     : Tim Morrow                                                    *
 * DATE       : Feb 2002                                                      *
 * USAGE      : A 32 bit console program run by typing 'NineNines' at the     *
 *              command prompt.                                               *
 ******************************************************************************
 * DESCRIPTION:                                                               *
 * Combining nine 9's with any number of the operators +, -, *, /, (, ),      *
 * what is the smallest positive integer that cannot be expressed?            *
 * You cannot concatenate (for example, put two 9s together to make 99).      *
 * The minus operator can be used in either its binary or unary form.         *
 *                                                                            *
 * Dave Rusin showed me an elegant recursive solution to this problem.        *
 * The algorithm is as follows:                                               *
 *                                                                            *
 * Define recursively the sets  S_i  by                                       *
 * S_1 := {9}                                                                 *
 * S_n := Union of sets ( S_i % S_{n-i} ) for i=1 to n-1, where               *
 *   A%B = union of A+B, A-B, A*C, A/D, where                                 *
 *   A+B = set of all  a+b  for a in A, b in B                                *
 *   A-B, A*B are similar                                                     *
 *   A/B is similar but the denominators must come from B\{0}.                *
 ******************************************************************************
 * WARNING:                                                                   *
 * It appears that the storage requirements grow as 4^(DEPTH-1). This will    *
 * quickly chew up your memory in no time for values of DEPTH>9.              *
 * You can expect the program to take a long time for DEPTH>9.                *
 ******************************************************************************/
#include <windows.h>
#include <stdio.h>
#include <math.h>
#include <time.h>


// Constants
const unsigned int DEPTH=9;                // Number of 9's to be combined
const unsigned int STORAGE=1<<(2*DEPTH-2); // Storage needed for expressions
const double       e=pow(9.0,-1.0-DEPTH);  // Epsilon used for floating point


// Data types
struct Expression{
  double val;        // Value of expresion. Floating point needed 
  char str[5*DEPTH]; // The expression as a string
};


// Globals
Expression S[DEPTH][STORAGE]; // S[n][] is the program equivalent of Sn
unsigned int Size[DEPTH];     // Records number of elements in each S[n] array


// Add an element to the set (if it is not already in the set)
bool AddToSet(
  Expression Set[],        // Array is the current set
  unsigned int *ArraySize, // Size of the array
  double val)              // Value to add to set
{
  for (unsigned int i=0; i<*ArraySize; i++)
    if (fabs(Set[i].val-val)<e) // Two values within epsilon are the same
      break;
  if (i==*ArraySize) {
    Set[*ArraySize].val=val;
    (*ArraySize)++;
    return(true);
  }
  return(false);
}


// Recursion function that generates all possible expressions from the 9's
void SolveNines(
  unsigned int d) // Depth d=0 for 1 nine, ... , d=8 for 9 nines
{
  unsigned int i,j,k; // Loop indexes
  double tmp1,tmp2;   // Temp values
  unsigned int c=0;   // Counter tracking number of different values found

  if (d==0) {
    // Initialise S[0][]
    S[d][0].val=9.0;
    strcpy(S[d][0].str,"9");
    Size[d]=1;
  }
  else {
    // Recursion step
    SolveNines(d-1);
    // Union over the S_i % S_{n-i} sets
    for (k=0; k<d; k++) {
      // Union of A+B, A-B, A*C, A/D
      for (i=0; i<Size[k]; i++) {
        for (j=0; j<Size[d-1-k]; j++) {
          tmp1=S[k][i].val;
          tmp2=S[d-1-k][j].val;
          if (AddToSet(S[d],&c,tmp1+tmp2))
            sprintf(S[d][c-1].str,"(%s%c%s)",S[k][i].str,'+',S[d-1-k][j].str);
          if (AddToSet(S[d],&c,tmp1-tmp2))
            sprintf(S[d][c-1].str,"(%s%c%s)",S[k][i].str,'-',S[d-1-k][j].str);
          if (AddToSet(S[d],&c,tmp1*tmp2))
            sprintf(S[d][c-1].str,"(%s%c%s)",S[k][i].str,'*',S[d-1-k][j].str);
          if (fabs(tmp2)>e)
            if (AddToSet(S[d],&c,tmp1/tmp2))
              sprintf(S[d][c-1].str,"(%s%c%s)",S[k][i].str,'/',S[d-1-k][j].str);
        }
      }
    }
    Size[d]=c;
    printf("Size[%d]=%d\n",d+1,Size[d]);
  }
} // SolveNines


// Compare function used by qsort
int compare(
  const void *a,
  const void *b)
{
  return(*(double *)a>=*(double *)b ? 1 : -1);
} // compare


/************
 Main program
 ************/
int main(
  void)
{
  unsigned int i;    // Loop index
  double tmp;        // Temp value
  clock_t start,end; // Timer values
  char filename[30]; // File is "NineNines<NUM_NINES>.txt"
  FILE *out;         // Handle to the file

  // Start timer
  start=clock();

  // Open a file to output results
  sprintf(filename,"NineNines%d.txt",DEPTH);
  if ((out=fopen(filename,"w"))==NULL) {
    printf("Cannot open %s.\n",filename);
    return(1);
  }

  // Solve it
  SolveNines(DEPTH-1);

  // Sort the results
  qsort(S[DEPTH-1],Size[DEPTH-1],sizeof(Expression),compare);

  // Output the results
  for (i=0; i<Size[DEPTH-1]; i++) {
    tmp=fabs(S[DEPTH-1][i].val);
    // tmp+e is required due to imprecision of floating point
    if (fabs(tmp-floor(tmp+e))<e)
      fprintf(out,"%-*.0f = %s\n",DEPTH+1,S[DEPTH-1][i].val,S[DEPTH-1][i].str);
  }
  printf("Results stored in file \"%s\"\n",filename);

  // Stop timer
  end=clock();
  printf("Running time = %.2f minutes\n",(float)(end-start)/(60*CLK_TCK));

  // Close down
  fclose(out);
  return(0);
} // main