#! /usr/bin/gawk -f
# Last edited on 1999-07-22 15:16:59 by stolfi

# Brute-force traveling salesman problem
#
# Reads a weight matrix M[a,b] indexed by a list of letters, and a
# list of permutations on those letters. Outputs every letter
# permutation "p[1..n]" that minimizes the sum "M[p[i-1],p[i]]" over
# "i=2..n".

BEGIN {
  abort = -1;
  if (matrixFile == "") { error("must define \"matrixFile\""); }
  read_matrix(matrixFile);
  printf "num elements = %d\n\n", nf;
  printf "natural score = %.6f\n", compute_score(pz);
  printf "natural perm = %s\n\n", pz;
 
  split("", pbest); nb = 0; sbest = 999999999;
  # "pbest[0..nb-1]" are the best permutations, and "sbest" is their weight.
}
  
(abort >= 0) { exit abort; }

/^ *$/ { next; }

/^[#]/ { next; }

/./ {
  if (NF != 1) { error("bad NF"); }
  ps = $1;
  if (length(ps) > nf) { error("perm too long"); }
  # Convert score to integer to avoid fuzzy comparison of 
  # fractional values.
  s = int(compute_score(ps)*1000000 + 0.5);
  if (s <= sbest)
    { if (s < sbest) { nb = 0; sbest = s; }
      pbest[nb] = ps; nb++;
    }
}

END {
  if (abort >= 0) { exit abort; }
  printf "best score = %.6f\n", sbest/1000000;
  printf "best perms =\n";
  for (k=0; k<nb; k++)
    { printf "%s\n", pbest[k]; }
}

function read_matrix(file,  lin,fld,nfld,i,j)
{
  # Defines the following global variables:
  # number of elements "nf", the element 
  # codes "f[1..nf]", their concatenation as strings "pz",
  # and the distance matrix "M" (indexed with element codes).
  
  split("", f);
  split("", M);
  i = 0; nf = 0;
  while (getline lin < file)
    { if (match(lin, /^[#]/)) { continue; }
      if (match(lin, /^[- ]*$/)) { continue; }
      nfld = split(lin, fld);
      if (nf == 0)
        { # Assume it is a header line; fetch folio codes
          pz = "";
          for (j=1; j<=nfld; j++)
            {
              f[j] = fld[j];
              if (length(f[j]) != 1) { error(("elem name not single letter " f[j])); }
              pz = (pz f[j]);
            }
          nf = nfld;
        }
      else
        { i++; 
          # Read line "i" of the matrix
          if (nfld != nf+1) { error((file ": bad num fields in line")); } 
          if (fld[1] != f[i]) { error((file ": rows out of order?")); }
          for (j=1; j<=nf; j++) { 
            v = fld[j+1];
            if ((v == ".")||(v == "-")) { v = 0; }
            if (v == "*") { v = 9999; }
            M[f[i],f[j]] = v;
          }
        }
    }
  if (ERRNO != "0") { error((file ": " ERRNO)); }
  # Check if symmstric
  if (i != nf) { error(("matrix not square " i " " nf)); }
  for(i=1; i<=nf; i++)
    { for(j=i+1; j<=nf; j++)
        { if (M[f[i],f[j]] != M[f[j],f[i]])
            { error((file ": matrix is not symmetric")); }
        }
    }
  # printf "f = " > "/dev/stderr"; 
  # for(j=1; j<=nf; j++) { printf "%s", f[j] > "/dev/stderr"; }
  # printf "\n" > "/dev/stderr";
}

function compute_score(ps,  i,sum,fa,fb,n)
{
  # The score of permutation "ps" is the sum "M[p[i-1],p[i]]" over
  # "i=2..n".
  n = length(ps);
  if (n == 0) { return 0; }
  sum = 0;
  fa = substr(ps,1,1);
  for(i=2; i<=n; i++)
    { fb = substr(ps,i,1);
      if(! ((fa,fb) in M)) { error("bad code in perm"); } 
      sum += M[fa,fb];
      fa = fb;
    }
  return(sum);
}
  
function error(msg)
{ 
  printf "line %d: %s\n", NR, msg > "/dev/stderr";
  abort = 1;
  exit 1;
}