/* Bare backtracking solution to the Traveling Salesman Problem:
 * at each vertex, traverse the available edges, passing along a
 * permutation vector, new cell, and total distance traveled so far
 * --- if there is no solution yet OR the distance so far is less
 * than the present solution.
 *
 * Input file expectation:
 *   Number of vertices in the graph (crossroads in the map)
 *   That many lines giving names
 *   one blank line
 *   Lines specifying roads:  two double-quoted names and an integer
 *
 * Language:  ANSI C
 *
 * Author:  Timothy Rolfe
 */
#include <ctype.h>           // isblank
#include <stdio.h>
#include <stdlib.h>
#include <string.h>          // memcpy
#if defined(_WIN32) | defined(__TURBOC__)               // NOT the Unix environment
#include <time.h>
// Use a macro to get double seconds from clock()
#define wallClock() ((double)clock()/CLOCKS_PER_SEC)
#define  cpuClock() ((double)clock()/CLOCKS_PER_SEC)
#else
#include "cpuTimes.h"
#endif

// Global data
#define MAX_N 32
int    wt[MAX_N][MAX_N];     // Matrix of edge weights
int    n;                    // Dimension for wt and city
char **city;                 // Vector of city names
int   *solution;             // Best tour so far
int    tourCost;
enum BOOL {FALSE, TRUE} DEBUG = FALSE;

void partial(int *vect, int index)
{  int dist = index == n ? wt[vect[n-1]][vect[0]] : 0,
       k;

   fputs (city[vect[0]], stdout);
   for ( k = 1; k < index; k++ )
   {  printf (", %s", city[vect[k]]);
      dist += wt[vect[k-1]][vect[k]];
   }
   printf(" for %d\n", dist);
}

int find(char* value)
{
   int idx;

   for (idx = 0; idx < n; idx++)
   {
      int val = strcmp(value, city[idx]);
      if (val == 0)
         return idx;
   }
   return -1;
}

// Initialize the global variables based on the file passed through
// the Scanner inp.  See the header documentation for the
// specifications for the input file.
void init(FILE *inp)
{  int  sub1,
        sub2;
   char line[128];

   fscanf(inp, "%d", &n);
   city = (char**) calloc(n, sizeof *city);
   solution = (int*) calloc(n, sizeof *solution);

   fgets(line, 128, inp);    // Discard rest of first line
   for ( sub1 = 0; sub1 < n; sub1++ )
   {  int tail;
      fgets(line, 128, inp);
      tail = strlen(line)-1;
      while (line[tail] < 32) // I.e., a control character
         line[tail--] = '\0';// Discard trailing \n --- or trailing \r
      city[sub1] = (char*) calloc(strlen(line)+1, sizeof(char*));
      strcpy (city[sub1], line);
   }

   fgets(line, 128, inp);    // Discard blank spacing line;

   fgets(line, 128, inp);    // Priming read
   while ( strlen(line) > 0 )
   {  char  *head, *tail;
      int    dist;           // Edge distance
      char   src[128], dst[128];
      char  *inwork = line;  // Currently unprocessed part

      line[strlen(line)-1] = '\0';
      // Specimen record:  "George" "Pasco" 91
      // Chop out the double-quoted substrings.
      head = strstr(inwork,"\"") + 1;
      tail = strstr(head,"\"");
      memset (src, '\0', 128);
      strncpy(src, head, tail-head);
      inwork = tail+1;
      head = strstr(inwork,"\"") + 1;
      tail = strstr(head,"\"");
      memset (dst, '\0', 128);
      strncpy(dst, head, tail-head);
      inwork = tail+1;
      while (isspace(*inwork))
         inwork++;
      dist = atoi(inwork);
      sub1 = find(src);
      if (sub1 < 0)
      {  printf("Failed to find %s\n", src); continue;  }
      sub2 = find(dst);
      if (sub2 < 0)
      {  printf("Failed to find %s\n", dst); continue;  }
      wt[sub1][sub2] = wt[sub2][sub1] = dist;   // Symmetric
      line[0] = '\0';        // Flag as empty prior to
      fgets(line, 128, inp); // Next record
   }
}

void tour(int, int*, int);
// Public access for generating the tours.
// Generate the initial permutation vector, then call recursive tour
void tourstart()
{
   static int *vect = NULL,
          start;
   int k;

   if (vect == NULL)
   {  vect  = (int*) calloc (n, sizeof *vect);
      start = find("Spokane");
   }

   // First permutation n vector.
   for ( k = 0; k < n; k++ )
      vect[k] = k;
   // We will, however, start from Spokane, not Coulee City
   // --- IF the data file is the one for the inland Pacific NW
   if ( start >= 0 ) // Complete the swap
   {  vect[start] = 0; vect[0] = start;  }
   tour(1, vect, 0);
}

// Used below in generating permutations.
void swap ( int *x, int p, int q )
{  int tmp = x[p];  x[p] = x[q]; x[q] = tmp;  }

// Recursive generation of the permutation vectors that constitute
// possible paths.
void tour(int index, int *vect, int so_far)
{
   if ( index == n )      // I.e., we have a full permutation vector
   {
      if ( wt[vect[n-1]][vect[0]] > 0 )  // IS there a return edge?
      {
         so_far = so_far + wt[vect[n-1]][vect[0]]; // Total tour distance
         if ( so_far < tourCost )        // Note initial flag value
         {
            memcpy(solution, vect, n * sizeof *vect);
            tourCost = so_far;
            if ( DEBUG )
            {  fputs ("Accept ", stdout); partial ( vect, n );  }
         }
         else if (DEBUG)
         {  fputs ("Not shorter ", stdout); partial ( vect, n );  }
      }
      else if (DEBUG)
      {  fputs("No return ", stdout); partial ( vect, n );  }
   }
   else                   // Continue generating permutations
   {
      int k;         // Loop variable
      int hold;      // Used in regenerating the original state

      for (k = index; k < n; k++)
      {
         int  testLength;

         swap (vect, index, k);
         if ( wt[vect[index-1]][vect[index]] > 0 )
         {
            testLength = so_far + wt[vect[index-1]][vect[index]];
            if (testLength < tourCost)
               tour (index+1, vect, testLength);
            else if (DEBUG)
               printf("Cut at %d\n", index);
         }
      }
      // Regenerate the permutation vector
      hold = vect[index];
      for ( k = index+1; k < n; k++ )
         vect[k-1] = vect[k];
      vect[n-1] = hold;
   }
}

int main (int argc, char* argv[])
{
   const char *filename = argc < 2 ? "InlandNW.txt"
                              : argv[1];
   FILE   *inp = fopen(filename, "r");
   double  start;
   int     pass, nPasses = argc < 3 ? 100
                                    : atoi(argv[2]);

   printf("Data read from file %s\n", filename);
   init(inp);
   start = cpuClock();
   for (pass = 0; pass < nPasses; pass++)
   {
      tourCost = RAND_MAX;
      tourstart();
   }
   printf ("Total time:  %3.3f seconds\n",
      cpuClock() - start);

   if ( tourCost < RAND_MAX )
   {  printf("Best tour (length %d):  ", tourCost);
      partial ( solution, n );
   }
   else
      puts("NO tours discovered.  Exiting.");
   return 0;
}