/*-------------------------------------------------------------

Copyright (C) 2000 Peter Clote. 
All Rights Reserved.

Permission to use, copy, modify, and distribute this
software and its documentation for NON-COMMERCIAL purposes
and without fee is hereby granted provided that this
copyright notice appears in all copies.


THE AUTHOR AND PUBLISHER MAKE NO REPRESENTATIONS OR
WARRANTIES ABOUT THE SUITABILITY OF THE SOFTWARE, EITHER
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHORS
AND PUBLISHER SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED
BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
THIS SOFTWARE OR ITS DERIVATIVES.

-------------------------------------------------------------*/


/*---------------------------------

randomWalkDistance.c

Computes mean and variance between corresponding
points between 2 random walks. Used for algorithms
problem.

Generates data on average distance between points of 2 random walks on
2 dimensional lattice.

Program rather similar to randomWalk.c,
except:
  compute mean distance instead of (root) mean square distance
  read in length of walks

--------------------------------*/

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

double rreal();
int randint(int);
 
main(int argc, char *argv[]) {
  int i,j;
  int M = 100000; // number of runs
  int n; // n points in walk
  int x,y,u,v;
  double distSum; // sum of distances between successive points on walk
  double sum=0,sumSq=0; 
    // used to compute mean and variance of distances between walks

  /*--------error handling for input */
  if (argc != 2) {
     fprintf(stderr,"%s int\n",argv[0]);
     exit(1);
     }
  
  n = atoi(argv[1]);

  for (i=0;i<M;i++){
    x=y=u=v=0; //start from origin
    distSum=0;
    for (j=0;j<n;j++) 
    {
       switch( randint(3) ) {
         case 0: x += 1; break;
         case 1: x -= 1; break;
         default: break;  // x = x
       } 
       switch( randint(3) ) {
         case 0: y += 1; break;
         case 1: y -= 1; break;
         default: break;  // y = y
       } 
       switch( randint(3) ) {
         case 0: u += 1; break;
         case 1: u -= 1; break;
         default: break;  // u = u
       } 
       switch( randint(3) ) {
         case 0: v += 1; break;
         case 1: v -= 1; break;
         default: break;  // v = v
       } 
       distSum += sqrt((x-u)*(x-u) + (y-v)*(y-v));
    }
    printf("%lf\n",distSum/n);
    sum += distSum/n;
    sumSq += (distSum/n * distSum/n);
  } 
  printf("\n\nExpected distance between 2 persons,\n");
  printf("both of whom perform a random walk of %d steps is:",n);
  printf(" %lf\n\n", sum/M);
  printf("\n\nVariance for this random variable is: %lf\n",
           sumSq/M - sum/M*sum/M);
}


double rreal() {
  return ((double)rand())  / (RAND_MAX+1.0);
}

int randint(int m) {
  return (int) (rreal()*m);
}