// Michael S. Branicky, 18 February 2008: Translation into Java of
// Michael S. Branicky, 04 February 2005
// compiles with g++ -lc -lm
//
// This code offered with no guarantees whatsoever.
// 

/*
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
*/


public class rrhc {

public static final int TEST=0;
public static final int ELITISM=1;
public static final int NUMTRIALS=100;

public static int    N=100000000;         // number of generations
public static int    k=1;      // number of individuals
public static int    EVALS;        // number of fitness evaluations
public static double pmut=0.01;     // mutation probability

// returns a uniformly distributed random double between 0.0 and 1.0
public static double myrand() {
  return Math.random();
}

// returns 1 if queens q1 and q2 are attacking each other, 0 o.w.
public static int attacking(int q1col, int q1row, int q2col, int q2row) {
  if (q1col==q2col) return(1); // same column
  if (q1row==q2row) return(1); // same row
  int coldiff=q1col-q2col;
  int rowdiff=q1row-q2row;
  if (Math.abs(coldiff)==Math.abs(rowdiff)) return(1); // same diagonal
  return(0);
}

// evaluates the fitness of an encoding, defined as the number of
// non-attacking pairs of queens (28 - number of attacking pairs)
//
// the global variable EVALS keeps track of the number of times called
public static int fitness(int encoding[]) {
  EVALS++;
  int E=28;
  for (int i=1; i<8; i++) {
    for (int j=i+1; j<=8; j++) {
      E-=attacking(i, encoding[i-1], j, encoding[j-1]);
    }
  }
  return(E);
}

// the following is useful in a variety of 
// returns the nth successor of an encoding
public static void getsuccessor(int init[], int n, int succ[]) {
  n--;
  int remainder=(n%7); 
  int quotient=(n-remainder)/7; 
  // int newrow=1+((remainder+init[quotient]-1)%8);
  int newrow=init[quotient]+remainder+1;
  if (newrow>8) newrow-=8;
  for (int j=0; j<8; j++) {
    if (j==quotient) succ[j]=newrow;
    else succ[j]=init[j];
  }
}

// copy each digit of an encoding with a prob. of error p (in place)
// thus, if p=0., the string does not change; if p=1, it is randomized
public static void mutate(int enc[], double p) {
  for(int i=1; i<=8; i++) {
    double r=myrand();
    if (r<p) enc[i-1]=(int) Math.ceil(myrand()*8);
  }
}

// copy each digit of an encoding with a prob. of error p
// thus, if p=0., the encoding is copied; if p=1, a random instance is produced
public static void mutate2(int src[], int dest[], double p) {
  for(int i=1; i<=8; i++) {
    double r=myrand();
    if (r<p) dest[i-1]=(int) Math.ceil(myrand()*8);
    else dest[i-1]=src[i-1];
  }
}

// produces TWO offspring via crossover at a random location on two encodings (in place)
public static void xover(int e1[], int e2[]) {
  // choose a andom integer c between 1 and 7, inclusive
  int c=(int) Math.ceil(myrand()*7);
  if(TEST==1)
    System.out.println(c);
  for (int i=(c+1); i<=8; i++) {
    int tmp=e1[i-1];
    e1[i-1]=e2[i-1];
    e2[i-1]=tmp;
  }
}

public static String printenc(int encoding[]) {
  String s = new String();
  for(int i=0; i<8; i++) s += encoding[i];
  return s;
}

// test the routines
public static void test() {
  String s = new String();
  String s2 = new String();

  // configs from R&N, p 112
  int enc1[]={5, 6, 7, 4, 5, 6, 7, 6};
  int enc2[]={8, 3, 7, 4, 2, 5, 1, 6};

  // configs from R&N, p 117
  int enc3[]={2, 4, 7, 4, 8, 5, 5, 2};
  int enc4[]={3, 2, 7, 5, 2, 4, 1, 1};
  int enc5[]={2, 4, 4, 1, 5, 1, 2, 4};
  int enc6[]={3, 2, 5, 4, 3, 2, 1, 3};

  // test fitness
  s=printenc(enc1); System.out.println("Fitness ( " + s + " ) = " + fitness(enc1));
  s=printenc(enc2); System.out.println("Fitness ( " + s + " ) = " + fitness(enc2) + "\n");
  s=printenc(enc3); System.out.println("Fitness ( " + s + " ) = " + fitness(enc3));
  s=printenc(enc4); System.out.println("Fitness ( " + s + " ) = " + fitness(enc4));
  s=printenc(enc5); System.out.println("Fitness ( " + s + " ) = " + fitness(enc5));
  s=printenc(enc6); System.out.println("Fitness ( " + s + " ) = " + fitness(enc6) + "\n");

  // test mutate
  mutate2(enc1,enc2,1.0); s=printenc(enc2); System.out.println("Random Encoding: " + s);
  mutate2(enc1,enc2,0.5); s=printenc(enc2); System.out.println("Random Encoding: " + s);
  mutate2(enc1,enc2,0.0); s=printenc(enc2); System.out.println("Random Encoding: " + s + "\n");
  mutate(enc1,1.0); s=printenc(enc1); System.out.println("Random Encoding: " + s);
  mutate(enc1,0.5); s=printenc(enc1); System.out.println("Random Encoding: " + s);
  mutate(enc1,0.0); s=printenc(enc1); System.out.println("Random Encoding: " + s + "\n");

  // test xover
  xover(enc3,enc4);
  s=printenc(enc3); s2=printenc(enc4); System.out.println("Offspring = " + s + ", " + s2);
  xover(enc5,enc6);
  s=printenc(enc5); s2=printenc(enc6); System.out.println("Offspring = " + s + ", " + s2);

  // test successor function
  int enc7[]={1, 2, 3, 4, 5, 6, 7, 8};
  int enc8[]= new int[8];
  for (int i=1; i<=56; i++) {
    getsuccessor(enc7, i, enc8);
    s=printenc(enc8); System.out.println("Successor ( " + i + " ) = " + s);
  }
  // generate a random successor
  int RandomSuccIndex=(int) Math.ceil(myrand()*56); // random int in {1, 2, ..., 56}
  getsuccessor(enc7, RandomSuccIndex, enc8);
  s=printenc(enc8); System.out.println("Successor ( " + RandomSuccIndex + " ) = " + s);
  
}

public static void main(String[] args) {
  int curr[]=new int[8];
  int succ[]=new int[8];
  int currE;
  int bestE, bestsofar;
  String s = new String();
  int trials;
  int sumEVALS=0;

  // srand48((long) getpid());

  if (TEST==1)
    test();

  for (trials=0; trials<NUMTRIALS; trials++) {
    EVALS=0;
    // pick a random board configuration
    mutate(curr,1.0);
    currE=fitness(curr);
    bestsofar=0;
  
    for (int t=1; t<=N; t++) {
      if (currE>bestsofar) {
        bestsofar=currE;
        s=printenc(curr);
        System.out.println("New Best ( " + s + " ): " + EVALS + ", " + currE);
      }
      if (currE==28) {
        s = printenc(curr);
        System.out.println("Solution Found: " + s);
        break;
      }
      // find all its successors, remembering the best one
      bestE=0;
      int bestSuccIndex = -1;   // to be index in {1, ..., 56} of highest fitness successor
      for (int i=1; i<=56; i++) {
        getsuccessor(curr, i, succ); 
        int f=fitness(succ);
        if (f > bestE) { bestE=f; bestSuccIndex=i; }
        // The following line would add some randomness for equally-good ones
        // if ((f>bestE)||((f==bestE)&&(myrand()<0.1))) { bestE=f; bestSuccIndex=i; }
      } 
      if (bestE>currE) {  // climb hill
        // reassign current <-- best successor
        getsuccessor(curr, bestSuccIndex, succ); 
        mutate2(succ, curr, 0.0);
        currE=bestE;
      }
      else { // random restart
        // pick a random board configuration
        mutate(curr,1.0);
        currE=fitness(curr);
        }
    }
    // for (int i=ELITISM; i<k; i++) mutate2(newpop[i], pop[i], pmut);
    System.out.println("EVALS ( " + trials + " ): " + EVALS);
    sumEVALS+=EVALS;
  }
  System.out.println("Average: ");
  System.out.println(((double) sumEVALS)/((double) NUMTRIALS));
}

}