/* 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
#ifdef _WIN32                // 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_SIZE 32
int   wt[MAX_SIZE][MAX_SIZE];// Matrix of edge weights
int   n;                     // Dimension for wt and city
char *city[MAX_SIZE];        // Vector of city names
int   solution[MAX_SIZE];    // Best tour so far
int   tourCost;
int   wtBound[MAX_SIZE];     // Sums of lowest weights
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 linear(char* value, char** array, int n)
{
   int idx;

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

// Allow using qsort to sort a vector of ints
int intcmp(const void *elem1, const void *elem2)
{  int *left  = (int *) elem1,
       *right = (int *) elem2;
   return *left - *right;
}

// 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];
   int *lngth, nxt = 0;

   fscanf(inp, "%d", &n);
/**/ printf("Reading in %d\n", n);
   // Overkill on length, but will cover a FULLY-CONNECTED graph
   lngth = (int*) calloc(n*(n-1)/2, sizeof *lngth);

   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);
/**/  puts(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

      // 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 = linear(src, city, n);
      sub2 = linear(dst, city, n);
      wt[sub1][sub2] = wt[sub2][sub1] = dist;   // Symmetric
      lngth[nxt++] = dist;
      line[0] = '\0';        // Flag as empty prior to
      fgets(line, 128, inp); // Next record
   }
   // Force zeroes in the global vector
   memset(wtBound, 0, n * sizeof *wtBound);
   qsort(lngth, nxt, sizeof *lngth, intcmp);
// for (sub1 = 1; sub1 < nxt; sub1++)
//    if (lngth[sub1-1] > lngth[sub1]) { printf("Error at %d\n", sub1); exit(-1);  }
   // Note:  fill [0] through [n-2], leaving [n-1] as zero.
   for (sub1 = 0; sub1 < n-1; sub1++)
   // Sum into cells.  Note PREdecrement of sub2 in the condition
      for ( sub2 = n-sub1-1; --sub2 >= 0; )
         wtBound[sub2] += lngth[sub1];
   free(lngth);
}

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 = linear("Spokane", city, n);
   }

   // 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);
   if (inp == NULL)
   {  puts("Failed to open file."); exit(0);  }
   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.");
}