#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <sys/select.h>
#include <termios.h>
#include <ctype.h>

// adjustable parameters
#define POPULATION_SIZE     10         // total population size
#define NUM_SURVIVORS       4          // number of survivors per generation (must be less than POP_SIZE)
#define GENOME_LEN          13         // number of loci in each genome (each locus is one character)
#define MUTATION_RATE       0.5        // probability that a genome is mutated per generation
#define FITNESS_THRESHOLD   843503     // program stops when this fitness threshold is met or exceeded
#define DISPLAY_INTERVAL    1          // display results every n generations, where n == DISPLAY_INTERVAL
#define PAUSE_TIME          50000      // pause time in microseconds
#define GENOMES_TO_DISPLAY  1          // in STEP_MODE, number of (the fittest) genomes to display at each step
#define STEP_MODE           1          // if set, program will pause every n generations and display the genomes
#define ENABLE_SELECTION    1          // if set, enable selection; otherwise, select survivors randomly

#define NUM_LINES           300        // number of lines in the program's display "window"
#define CHARS_PER_LINE      120        // for each line in the "window"

// A genome consists of a character string plus the associated fitness value
typedef struct {
  char string[GENOME_LEN];
  int fitness;
} genome_t;

genome_t genome_array[POPULATION_SIZE]; // genomes of all members of the population

// Swap two genomes given their indices.
void swap_genomes(int g1, int g2) {
  genome_t temp_genome;
  if (g1 == g2) {
    return;
  } else {
    temp_genome = genome_array[g1];
    genome_array[g1] = genome_array[g2];
    genome_array[g2] = temp_genome;
  }
}

// Thoroughly and randomly scramble the population within the genome array.
void scramble_genomes() {
  for (int i=0; i < 4*POPULATION_SIZE; i++) {
    swap_genomes(rand()%POPULATION_SIZE, rand()%POPULATION_SIZE);
  }
}

// Determine whether a character represents one of the four legal operators.
int is_op(char c) {
  if (c=='+'||c=='-'||c=='*'||c=='/') {
    return 1;
  } else {
    return 0;
  }
}

// Determine whether a genome contains a legal string.
int is_legal(genome_t *genome) {
  if (is_op(genome->string[0])) {
    return 0;
  } else if (is_op(genome->string[GENOME_LEN-1])) {
    return 0;
  }
  else {
    for (int i = 0; i<GENOME_LEN-1; i++) {
      if (is_op(genome->string[i]) && is_op(genome->string[i+1])) {
        return 0;
      }
    }
  }
  return 1;
}

// Split a string into two pieces, one to the left of the specified delimiter character and
// one to the right. Discard the delimiter.
void split(char *str, char delim, char *left, char *right) {
  int i = 0;
  while (str[i] != delim) {
    left[i] = str[i++];
  }
  left[i++] = '\0';
  int j = 0;
  while(str[i] != '\0') {
    right[j++] = str[i++];
  }
  right[j] = '\0';
}

// Evaluate an expression involving integers and the four binary operators +, -, *, and /.
int eval(char *str) {
  char left[GENOME_LEN+1];
  char right[GENOME_LEN+1];
  long num;
  if (strchr(str, '-') != NULL) { // subtraction has the lowest precedence
    split(str, '-', left, right);
    return (eval(left) - eval(right));
  } else if (strchr(str, '+') != NULL) {
    split(str, '+', left, right);
    return (eval(left) + eval(right));
  } else if (strchr(str, '/') != NULL) {
    split(str, '/', left, right);
    return (eval(left) / eval(right));
  } else if (strchr(str, '*') != NULL) {
    split(str, '*', left, right); // multiplication has the highest precedence
    return (eval(left) * eval(right));
  } else {
    sscanf(str, "%d", &num);
    return(num);
  }
}

// Calculate a genome's fitness by evaluating its character string.
int fitness(genome_t *genome) {
  return eval(genome->string);
}

// Display a genome as a character string.
void display_genome(genome_t *genome) {
  printf("%s", genome->string);
}

// move cursor to the home position
void cursor_home() {
  printf("\x1b[H");
}

// overwrite everything on the screen with spaces
void clear_screen() {
  cursor_home();
  for (int i=0; i < NUM_LINES; i++) {
    for (int j=0; j < CHARS_PER_LINE; j++) {
      putchar(' ');
    }
    printf("\n\r");
  }
}

// Mutate genome by swapping two loci
void transpose(genome_t *genome) {
  int idx1, idx2;
  int temp;

  idx1 = rand()%GENOME_LEN;
  idx2 = rand()%GENOME_LEN;
  if (idx1 != idx2) {
    temp = genome->string[idx1];
    genome->string[idx1] = genome->string[idx2];
    genome->string[idx2] = temp;
  }
}

// Mutate genome by moving a char from one location to another.
void move_char(genome_t *genome) {
  char c;
  int old_pos, new_pos;

  old_pos = rand()%GENOME_LEN;
  new_pos = rand()%GENOME_LEN;
  if (old_pos == new_pos) {
    return;
  }
  c = genome->string[old_pos];
  if (old_pos < new_pos) {
    for (int i=old_pos; i<=new_pos; i++) {
        genome->string[i] = genome->string[i+1];
    }
  } else {
    for (int i=old_pos; i>=new_pos; i--) {
      genome->string[i] = genome->string[i-1];
    }
  }
  genome->string[new_pos] = c;
}

// Perform one of two types of mutation with 50% probability each.
void mutate(genome_t *genome) {
  if (rand()%2) {
    transpose(genome);
  } else {
    move_char(genome);
  }
}

// Copy old genome to new, mutating conditionally.
void reproduce(genome_t *old, genome_t *new) {
  if ((double)rand()/(double)RAND_MAX < MUTATION_RATE) {
    do {
      for (int i=0; i < GENOME_LEN; i++) {
        new->string[i] = old->string[i];
      }
      mutate(new);
    } while (!is_legal(new));
  }
  new->fitness = fitness(new);
}

// Initialize a genome randomly
void init_genome_rand(genome_t *genome) {
  strcpy(genome->string, "123456789+-*/");
  for (int i=0; i < 200; i++) {
    mutate(genome);
  }
  while (!is_legal(genome)) {
    mutate(genome);
  }
  genome->fitness = fitness(genome);
}

// Comparison function for use by qsort() library routine
int compare_fitness (const void * elem1, const void * elem2) {
    if (((genome_t *)elem2)->fitness  > ((genome_t *)elem1)->fitness) return 1;
    if (((genome_t *)elem2)->fitness == ((genome_t *)elem1)->fitness) return 0;
    return -1;
}

//
// From http://stackoverflow.com/questions/448944/c-non-blocking-keyboard-input
//

struct termios orig_termios;

void reset_terminal_mode()
{
    tcsetattr(0, TCSANOW, &orig_termios);
}

void set_conio_terminal_mode()
{
    struct termios new_termios;

    /* take two copies - one for now, one for later */
    tcgetattr(0, &orig_termios);
    memcpy(&new_termios, &orig_termios, sizeof(new_termios));

    /* register cleanup handler, and set the new terminal mode */
    atexit(reset_terminal_mode);
    cfmakeraw(&new_termios);
    tcsetattr(0, TCSANOW, &new_termios);
}

int kbhit()
{
    struct timeval tv = { 0L, 0L };
    fd_set fds;
    FD_ZERO(&fds);
    FD_SET(0, &fds);
    return select(1, &fds, NULL, NULL, &tv);
}

int getch()
{
    int r;
    unsigned char c;
    if ((r = read(0, &c, sizeof(c))) < 0) {
        return r;
    } else {
        return c;
    }
}

int main() {

  long long generation = 0;               // generation count
  int i;
  int selection_enabled = ENABLE_SELECTION;
  char ascii_target[GENOME_LEN+1];
  char c;

  set_conio_terminal_mode();

  printf("\n\n\n\n\r");

  // set cursor to home position, clear screen, and rehome
  clear_screen();
  cursor_home();

  // seed the random number generator with the current time
  srand(time(NULL));

  // randomly initialize the genomes of the entire population
  for (i=0; i < POPULATION_SIZE; i++) {
    init_genome_rand(&genome_array[i]);
  }
  printf("\n\n\rInitial Organism 0 Genome:\n\n\r");
  display_genome(&genome_array[0]);
  printf("\n\n\n\r");

  while (genome_array[0].fitness < FITNESS_THRESHOLD) {

    // preserve the survivors, but convert the rest into mutated copies of the survivors
    for (i=0; i < POPULATION_SIZE - NUM_SURVIVORS; i++) {
      reproduce(&genome_array[i%NUM_SURVIVORS], &genome_array[i+NUM_SURVIVORS]);
    }

    if (selection_enabled) {
      // sort the genomes into descending order by fitness
      qsort(genome_array, POPULATION_SIZE, sizeof(genome_t), compare_fitness);
    } else {
      // randomly scramble the genome array
      scramble_genomes();
    }

    ++generation;

    // in step mode, pause and display all genomes periodically
    if (STEP_MODE && generation % DISPLAY_INTERVAL == 0) {
      clear_screen();
      cursor_home();
      printf("\n\n\rGeneration: %lld\n\r", generation);
      printf("\n\rSelection: %s\n\n\r", selection_enabled ? "ON" : "OFF");
      for (i = 0; i < GENOMES_TO_DISPLAY; i++) {
        printf("Organism %d  Fitness %d\n\n\r", i, genome_array[i].fitness);
        display_genome(&genome_array[i]);
        printf("\r\n\n\n");
      }
      usleep(PAUSE_TIME); // pause briefly before continuing
    }

    if (!STEP_MODE && generation % DISPLAY_INTERVAL == 0) {
      printf("generation = %lld  fitness = %d \n\r", generation, genome_array[0].fitness);
    }

    if (kbhit()) { // keystroke detected
      switch(getch()) {
        case 'q': // quit the program
          exit(0);

        case 'p': // pause until next keystroke
          printf("Paused: Hit any key to continue\r\n");
          while(!kbhit()){
            ;
          }
          (void)getch(); // consume character
          break;

        case 'r': // restart with a new set of randomized genomes
          for (i=0; i < POPULATION_SIZE; i++) {
            init_genome_rand(&genome_array[i]);
          }
          generation = 0;
          break;

        case 's': // toggle selection on and off
          selection_enabled = !selection_enabled;
          break;
      }
    }
  }

  printf("\n\n\rWinning generation = %lld  fitness = %d \n\r", generation, genome_array[0].fitness);
  printf("\n\rWinning genome:\n\n\r");
  display_genome(&genome_array[0]);
  printf("\n\n\r");
  tcsetattr(0, TCSANOW, &orig_termios);
}