#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* Try out different strategies for "finding the cheapest gas".
   Looks at 
      the average price that a strategy finds (expected price) 
      how often it gets the best price in town
   &  how often it gets a better price than the other strategy.
   Steve Witham <sw@tiac.net>

   Calculemus -- "Let us calculate":
      http://www.tiac.net/~sw/2003/08/calculemus.html

   To let understanding stop at what cannot be understood
         is a high attainment.
    Those who cannot do it will be destroyed on the lathe of heaven.
     -- Chuang Tse
   [Steve's note: Imagine pushing the tool too hard against the
    piece in a lathe.  Editing and running this program
    reminded me of adjusting the cutter in a lathe.]
*/

#define N_STRATEGIES 2

#define PRICE 0
#define GOT_MIN 1
#define GOT_BETTER 2
#define N_RESULTS 3
char *result_names[ N_RESULTS ] = { "price", "got min", "got better" };
double max_or_min[ N_RESULTS ] = { -1.0, +1.0, +1.0 };

double total [ N_RESULTS ] [ N_STRATEGIES ];

char *strategy_names[ N_STRATEGIES ];
double *prices;
double e;  /* initialized in main() */


double hold_out( int strategy, int n_gather, int n ) {
  int i;
  double min;

  strategy_names[ strategy ] = "hold_out";

  min = prices[ 0 ];
  for( i = 1;  i < n_gather;  i++ ) {
    if( prices[i] < min )  min = prices[i];
  }
  for( ;  i < n - 1;  i++ ) {
    if( prices[i] <= min )  return( prices[i] );
  }
  return( prices[ n - 1 ] );
}


double linear_slide( int strategy, int n_gather, int n ) {
  int i, i0;
  double min, t, x;

  strategy_names[ strategy ] = "linear_slide";

  min = t = prices[ 0 ];
  for( i = 1;  i < n_gather;  i++ ) {
    t += prices[i];
    if( prices[i] < min )  min = prices[i];
  }
  i0 = i;  /* Start of the slide.  End is n - 2. */
  for( ;  i < n - 1;  i++ ) {
    t += prices[i];
    /* x = between 0.0 and 1.0, how far along we are: */
    if( i0 == n - 2 )  x = 1.0;
    else  x = (double) ( i - i0 ) / (double) ( (n - 2) - i0 );
    if( prices[i] <= (1.0-x)*min + x*(t/(i+1)) )  return( prices[i] );
  }
  return( prices[ n - 1 ] );
}


double strategy_result( int strategy, int n_gather, int n ) {
  if( strategy == 0 )  
    return( hold_out( strategy, n_gather, n ) );
  else                 
    return( linear_slide( strategy, n_gather, n ) );
}


double generate_prices( int n ) {
  int i;
  double min;

  for( i = 0;  i < n;  i++ ) {
    prices[i] = (double) rand() / RAND_MAX;
    if( i == 0  ||  prices[i] < min )  min = prices[i];
  }
  return( min );
}


void one_run( int n, int n_gather ) {
  int strategy;
  double price[ N_STRATEGIES ], worst, min;

  min = generate_prices( n );
  worst = price[ 0 ] = strategy_result( 0, n_gather, n );
  for( strategy = 1;  strategy < N_STRATEGIES;  strategy++ ) {
      price[ strategy ] = strategy_result( strategy, n_gather, n );
      if( price[ strategy ] > worst )  worst = price[ strategy ];
  }
  for( strategy = 0;  strategy < N_STRATEGIES;  strategy++ ) {
    total[PRICE][strategy] += price[ strategy ];
    total[GOT_MIN][strategy] += price[ strategy ] == min? 1.0 : 0.0;
    total[GOT_BETTER][strategy] += price[strategy] < worst? 1.0 : 0.0;
  }    
}


void many_runs( int n, int n_runs ) {
  int i, j, n_gather;
  double winners[ N_RESULTS ];

  n_gather = ( n / e + .3 );  /* rounding seems about right empirically... */

  prices = (double *) malloc( n * sizeof(double) );
  if( prices == NULL ) {
    fprintf( stderr, "Not enough memory for %d prices.\n", n );
    exit( 1 );
  }
  for( i = 0;  i < N_STRATEGIES;  i++ ) {
    total[PRICE][i] = 0.0;
    total[GOT_MIN][i] = 0.0;
    total[GOT_BETTER][i] = 0.0;
  }
  for( i = 0;  i < n_runs;  i++ ) {
    one_run( n, n_gather );
  }
  printf( "n = %d, %d runs    (< = minimize, > = maximize, * = winner)\n", 
	  n, n_runs );
  printf( "  " );
  for( j = 0;  j < N_RESULTS;  j++ ) {
    printf( "%c %13s    ", 
	    max_or_min[ j ] > 0? '>' : '<', result_names[ j ] );
  }
  printf( "\n" );

  /* This may seem a strange way to initialize variables,
     but it's independent of the loop ranges: */
  for( i = 0;  i < N_STRATEGIES;  i++ ) {
    for( j = 0;  j < N_RESULTS;  j++ ) {
      winners[ j ] = total[j][i];
    }
  }

  for( i = 0;  i < N_STRATEGIES;  i++ ) {
    for( j = 0;  j < N_RESULTS;  j++ ) {
      if( total[ j ][ i ] * max_or_min[j] > winners[ j ] * max_or_min[j] ) {
	winners[ j ] = total[ j ][ i ];
      }
    }
  }

  for( i = 0;  i < N_STRATEGIES;  i++ ) {
    printf( "  " );
    for( j = 0;  j < N_RESULTS;  j++ ) {
      printf( "%c %13e    ",
	      total[ j ][ i ] == winners[ j ]? '*' : ' ',
	      total[ j ][ i ] / n_runs
	      );
    }
    printf( "%s\n", strategy_names[ i ] );
  }
  printf( "\n" );
  free( prices );
}  


int main( ) {
  int i, n, g;
  double r;

  e = exp( 1.0 );

  many_runs( 3, 10000000 );
  many_runs( 4,  7500000 );
  many_runs( 6,  5000000 );
  many_runs( 10, 3000000 );
  many_runs( 30, 1000000 );
  many_runs( 100, 300000 );
  many_runs( 1000, 30000 );
  many_runs( 10000, 3000 );
}