/*-----------------------------------------------------------------------
 * pvccoco-01
 *
 * Dans cette version : simple "2-opt" appliqué au 8 balles
 * Voir les fichier README.francais et COPYING
 * 
 * Auteur : Alexandre AUPETIT (aaupetit@club-internet.fr)
 * Web : http://home.alex.tuxfamily.org/pvc.html
 *       http://home.alex.tuxfamily.org/pvc/robotique/coconut.html
 * 
 * Important : Ce logiciel est soumis à la licence de logiciel libre GPL
 *-----------------------------------------------------------------------*/

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

#define NB_BALLES 8
#define MAX_LENLINE 255

double pos_x[NB_BALLES+1]; // tableau des position en X des balles (en 0 : pos initiale du robot)
double pos_y[NB_BALLES+1]; // tableau des position en Y des balles (en 0 : pos initiale du robot)

int parcours[NB_BALLES+1]; // parcours (numéros des balles) (en 0 : pos initiale du robot)
double score_parcours;     // coût du parcours  == distance totale

// retourne un chiffre au hasard entre 0 et max
int hasard(int max) {
        return (int)((rand()/(RAND_MAX + 1.0))*max);
}

// distance entre deux points dont les coordonnées sont définies dans pos_x et pos_y
// distance euclidienne
double distance_point(int point1, int point2) {
        return sqrt((pos_x[point2]-pos_x[point1])*(pos_x[point2]-pos_x[point1])
                +(pos_y[point2]-pos_y[point1])*(pos_y[point2]-pos_y[point1]));
}

// distance totale du parcours
// attention on prend en compte le parcours entre le robot et la première balle 
// (parcours[0] à parcours[1]) mais on ne revient pas à la position initiale
// contrairement au PVC classique
double distance_parcours() {
        int i;
        double d=0;
        for (i=1;i<NB_BALLES+1;i++) {
                d+=distance_point(parcours[i-1], parcours[i]);
        }
        return d;
}

// affichage du parcours (et de son score) à l'écran
// avec aussi un message d'info
void affiche_parcours(char *message_info) {
        int i;
        printf("%s", message_info);
        for (i=0;i<NB_BALLES+1;i++) {
                        printf("%d-", parcours[i]);
        }
        printf("(d=%lf)\n", score_parcours);
}

// initialisation de la position des balles par lecture du fichier pos.txt
// le fichier pos_balles.txt doit contenir les positions au format :
// x_robot;y_robot
// x_balle1;y_balle1
// x_balle2;y_balle2
// x_balle3;y_balle3
// ...
// x_balle8;y_balle8
void init_pos() {
        FILE *ficPos;
        char sLine[MAX_LENLINE + 1];
        char *sPos;
        int i;

        ficPos=fopen("pos_balles.txt", "rt");
        if (ficPos != NULL) {
                i=0;
                do {
                        fgets(sLine, MAX_LENLINE, ficPos);
                        sPos = strtok(sLine, ";\n");
                        //printf("%s-\n",sPos);
                        if (sPos != NULL) {pos_x[i] = atoi(sPos);}
                        sPos = strtok(NULL, ";\n");
                        //printf("%s-\n",sPos);
                        if (sPos != NULL) {pos_y[i] = atoi(sPos);}
                        i++;
                } while ( !feof(ficPos) );

                if (i != NB_BALLES+2) {
                        printf("Erreur dans le nombre de villes du fichier pos.txt !");
                        exit(1);
                }
        } else {
                printf("Erreur d'ouverture du fichier pos.txt !");
                exit(1);
        }

        /*
        // pour tester...
        // position du robot
        pos_x[0] = 0;
        pos_y[0] = 0;
        // position des balles 
        int i;
        for (i=1;i<NB_BALLES+1;i++) {
                pos_x[i] = i;
                pos_y[i] = 0;
        }
        */
}

// echange l'odre de parcours entre 2 balles
void echange_parcours(int ordre1, int ordre2) {
        int inter;

        inter=parcours[ordre2];
        parcours[ordre2]=parcours[ordre1];
        parcours[ordre1]=inter;
}

// renverse le parcours entre les balles i et j
// il s'agit de la transformation la plus simple d'un parcours
// voir graphiquement ce que ça représente
// c'est la transformation de base du 2-opt : le 2-change
void renverse_parcours(int i, int j) {
  int a, b;

  if (i < j) {
    a = i;
    b = j;
  } else {
    a = j;
    b = i;
  }

  while (a < b) {
    echange_parcours (a, b);
    a++;
    b--;
  }
}

// initialise un parcours au hasard
void calcule_parcours_hasard() {
        int i;
        for (i=1;i<NB_BALLES+1;i++) {
                parcours[i] = i;
        }

        int a,b;
        for (i=1;i<NB_BALLES+1;i++) {
                a=hasard(NB_BALLES)+1;
                b=hasard(NB_BALLES)+1;
                echange_parcours(a, b);
        }
}

// différence de cout du parcours si on renversait le parcours entre les balles i et j
// on "casse" 2 liens entre 2 balles et on les remplace par 2 autres
double difference_cout(int i, int j) {
        if (j+1<NB_BALLES+1) {
                return (distance_point(parcours[i], parcours[j+1])
                 + distance_point(parcours[i-1], parcours[j])
                 - distance_point(parcours[i-1], parcours[i])
                 - distance_point(parcours[j], parcours[j+1]));
        } else {
                return (
                 distance_point(parcours[i-1], parcours[j])
                 - distance_point(parcours[i-1], parcours[i])
                 );
        }
}


// calcule un parcours 2-opt, c'est à dire qu'aucune permutation 
// de l'odre de parcours ne rend ce parcours plus court
void calcule_parcours_2opt() {
        int i, j;

        for (i=1;i<NB_BALLES+1;i++) {
                for (j=i+1;j<NB_BALLES+1;j++) {
                        if (difference_cout(i, j) < 0.0) {
                                renverse_parcours(i, j);
                        }
                }
        }
}


// ----------------------------------------------------------------------------
// prog principal
// ----------------------------------------------------------------------------
int main(void) {
        srand (time (NULL));

        init_pos();

        calcule_parcours_hasard();
        score_parcours=distance_parcours();
        affiche_parcours("Chemin aléatoire   : ");

        calcule_parcours_2opt();
        score_parcours=distance_parcours();
        affiche_parcours("Après optimisation : ");

        return 0;
}