/*  POTM ENTRY:  Knight_Errant			*/
/*  Your Name:   Andre' Wilhelmus		*/
/*  Your email:  awilhelm@hvsag01.att.com	*/

/*  Version:	 4 (951231)			*/

#define DEBUG 0
#define TEST 0
#define PRINT 1

#include 
#if __MWERKS__
#include 
#include 
#else
#include 
#include 
#include 
#include 
#include 
#include 
#endif

#define false 0
#define true 1

typedef int bool;

#define MAX_TIME 570
#define MAX_MEMORY 45000000L

#define MAX_POINT 101
#define MAX_XY_CUSTOMER 101
#define MAX_XY_HOPS 103
#define MAX_TRAVEL 150

extern char *optarg;		/* The address of the option argument */
extern int errno;		/* The error number */
extern int optind;		/* The index to the next argument */
	
static unsigned int max_time = MAX_TIME;
static bool time_out = false;

extern void exit();
long random();

typedef struct XY
{
  int x;
  int y;
} XY;

XY knight[8] =	/* relative jumps */
{
  2,  1,
  1,  2,
  -1,  2,
  -2,  1,
  -2, -1,
  -1, -2,
  1, -2,
  2, -1
};

int max_customer = 1;
int hops[MAX_POINT][MAX_POINT];	/* number of hops from (0,0) */
XY point[MAX_POINT];	/* XYs from input file */
int visited[MAX_TRAVEL][MAX_TRAVEL];
int journey[MAX_POINT+1];
int best_journey[MAX_POINT+1];
int distance[MAX_POINT][MAX_POINT];	/* hop distance between two fields */
int nr_of_fields = 0;	/* number of unique visited fields */

/* time's up */

#if __MWERKS__
#else
static void
alarm_signal(i)
int i;
{
  struct rusage rusage;
  long time_left = 0;

#if DEBUG
  if (debug(db_entry, db_alarm_signal))
    fprintf(stderr, "alarm_signal()\n");
#endif  
  i = i;
  if (getrusage(0, &rusage) == 0) /* get used cpu time */
    time_left = max_time - rusage.ru_utime.tv_sec - rusage.ru_stime.tv_sec;
  if (time_left > 0)		/* still some time left? */
  {
    (void) signal(SIGALRM, alarm_signal);
    (void) alarm((unsigned int) time_left);
  }
  else				/* time's really up */
    time_out = true;
#if DEBUG
  if (debug(db_exit, db_alarm_signal))
    fprintf(stderr, "alarm_signal: %ld\n", time_left);
#endif  
}
#endif

/* allocate memory */

static char *my_malloc(bytes)
long bytes;
{
  char *p;
  p = malloc(bytes);
  if (p == 0)
  {
    fprintf(stdout, "malloc(%d) failed\n", bytes);
    exit(1);
  }
  return p;
}

/* validate the journey */

static void
validate()
{
  int i;
  int j;
  
  if (journey[0] != journey[max_customer])
  {
    fprintf(stdout, "ERROR: 0 != max_customer\n");
    exit(0);
  }
  for (i = 0; i < max_customer; i++)
  {
    for (j = i+1; j < max_customer; j++)
    {
      if (journey[i] == journey[j])
      {
        fprintf(stdout, "ERROR: %d == %d\n", i, j);
        exit(0);
      }
    }
  }
}

/* print the best journey */

static void
print_best()
{
  int i;
  for (i = 0; i < max_customer; i++)
    fprintf(stdout, "%d ", best_journey[i]);
  fprintf(stdout, "\n");
}

/* print the number of hops */

#if TEST
static void
print_hops()
{
  int x;
  int y;
  
  for (y = MAX_POINT-1; y >= 0; --y)
  {
    for (x = 0; x < MAX_POINT; x++)
      fprintf(stdout, "%2d ", hops[x][y]);
    fprintf(stdout, "\n");
  }
}
#endif

/* get the total number of hops */

static int
get_total()
{
  int i;
  int nr_of_hops = 0;
  for (i = 0; i < max_customer; i++)
    nr_of_hops += distance[journey[i]][journey[i+1]];
  return nr_of_hops;
}

/* print the points */

#if TEST
static void
print_points()
{
  int i;
  int j;
  
  for (i = 0; i < max_customer; i++)
  {
    j = journey[i];
    fprintf(stdout, "%d = (%d,%d) hops = %d\n",
      j, point[j].x, point[j].y, distance[j][journey[i+1]]);
  }
}
#endif

/* read the customer points */

static void
read_customers(point_file)
char *point_file;
{
  FILE *fp;
	
  if ((fp = fopen(point_file, "r")) == 0)
  {
    fprintf(stderr, "Gambit: error on fopen(%s)\n",
	    point_file);
    exit(1);
  }
  while (fscanf(fp, "%d %d",
		&point[max_customer].x, &point[max_customer].y) != -1)
    max_customer++;
}

#define EMPTY -1

/* create a matrix with the number of hops */

static void
fill_hops()
{
  XY *pending;
  int i;
  int j;
  int max_pending = 1;
  int x;
  int y;
  int hop_distance;
	
  pending = (XY *) my_malloc((long) MAX_XY_CUSTOMER*MAX_XY_CUSTOMER*sizeof(XY));
  for (x = 0; x < MAX_XY_CUSTOMER; x++)
  {
    for (y = 0; y < MAX_XY_CUSTOMER; y++)
      hops[x][y] = EMPTY;
  }

  hops[0][0] = 0;
  pending[0].x = pending[0].y = 0;
  for (i = 0; i < max_pending; i++)
  {
    hop_distance = hops[pending[i].x][pending[i].y]+1;
    for (j = 0; j < 8; j++)
    {
      x = pending[i].x + knight[j].x;
      y = pending[i].y + knight[j].y;
      if (x >= 0 && y >= 0 && x < MAX_XY_CUSTOMER && y < MAX_XY_CUSTOMER &&
	      hops[x][y] == EMPTY)
      {
	      hops[x][y] = hop_distance;
        pending[max_pending].x = x;
        pending[max_pending].y = y;
        max_pending++;
      }
    }
  }
  free((char *) pending);
}

/* randomize a cluster */

static void
random_cluster(cluster, start)
int cluster;
int start;
{
  int j;
  int t;
  int stop;
  int s;
  
  if (cluster > max_customer-1)
    cluster = max_customer-1;
  start = start % max_customer;
  stop = start+cluster;
  for (; start < stop; start++)
  {
#if __MWERKS__
    j = rand();
#else
    j = random();
#endif
    j = (j % (stop-start))+start;
    j = j % max_customer;
    s = start % max_customer;
    t = journey[s];
    journey[s] = journey[j];
    journey[j] = t;
  }
  journey[max_customer] = journey[0];
}

/* randomize some points */

static void
random_some()
{
  int i;
  int j;
  int t;
  int k;

#if __MWERKS__
  k = rand();
#else
  k = random();
#endif
  k = (k % (max_customer-1))+1;
  t = journey[k];
  for (i = 0; i < 3; i++)
  {
#if __MWERKS__
    j = rand();
#else
    j = random();
#endif
    j = (j % (max_customer-2))+1;
    if (j >= k)
      j++;
    journey[k] = journey[j];
    k = j;
  }
  journey[k] = t;
}

/* ??? */

static void
near_journey(cluslen, customer)
int cluslen;
int customer;
{
  int cluster[101];
  int count = 0;
  int i;
  int j;
  int t;
  int journey_customer;
  int distance_customer;
  
  journey_customer = journey[customer];
  for (i = 0; i < max_customer; i++)
  {
    distance_customer = distance[journey[i]][journey_customer];
    for (j = count-1; j >= 0; --j)
    {
      if (distance_customer <
          distance[journey[cluster[j]]][journey_customer])
        cluster[j+1] = cluster[j];
      else
        break;
    }
    j++;
    if (j < cluslen)
    {
      cluster[j] = i;
      if (count < cluslen)
        count++;
    }
  }
  for (i = 0; i < count; i++)
  {
#if __MWERKS__
    j = rand();
#else
    j = random();
#endif
    j = j % (count-i);
    t = journey[cluster[i]];
    journey[cluster[i]] = journey[cluster[i+j]];
    journey[cluster[i+j]] = t;
  }
  journey[max_customer] = journey[0];
}

XY pending[MAX_TRAVEL*MAX_TRAVEL];
XY route[MAX_TRAVEL][MAX_TRAVEL];
  
/* print the alternate route */

static void
print_alt_route(from, to)
XY from;
XY to;
{
  XY field;
  int i;
  int j;
  int max_pending = 1;
  int x;
  int y;
  
  fprintf(stdout, "print alternate %d - %d\n", from, to);
  for (x = 0; x < MAX_TRAVEL; x++)
  {
    for (y = 0; y < MAX_TRAVEL; y++)
      route[x][y].x = EMPTY;
  }
  
  route[to.x][to.y].x = 1;
  pending[0] = to;
  for (i = 0; i < max_pending; i++)
  {
    for (j = 0; j < 8; j++) /* try 8 directions */
    {
      field.x = pending[i].x + knight[j].x;
      field.y = pending[i].y + knight[j].y;
      if (field.x >= 0 && field.y >= 0 &&
	      field.x < MAX_TRAVEL && field.y < MAX_TRAVEL &&
	      route[field.x][field.y].x == EMPTY)
      {
	      route[field.x][field.y] = pending[i];
	      if (field.x == from.x && field.y == from.y)	/* print route? */
	      {
	        /* count unique */
	        /* unique less then save route */
	        while (from.x != to.x || from.y != to.y)
	        {
#if PRINT
	          fprintf(stdout, "%d %d\n", from.x, from.y);
#endif	          
#if TEST
	          if (visited[from.x][from.y]++ == 0)
	            nr_of_fields++;
#endif
	          from = route[from.x][from.y];
	        }
	        return;
	      }
	      if (max_pending >= MAX_TRAVEL*MAX_TRAVEL)
	      {
	        fprintf(stderr, "max_pending overflow\n");
	        exit(1);
	      }
	      pending[max_pending] = field;
	      max_pending++;
      }
    }
  }
  fprintf(stderr, "print_route() failed\n");
  exit(1);
}

/* print the route */

static bool
print_route(from, to)
XY from;
XY to;
{
  XY field;
  int i;
  int j;
  int max_pending = 1;
  int x;
  int y;
  
  for (x = 0; x < MAX_TRAVEL; x++)
  {
    for (y = 0; y < MAX_TRAVEL; y++)
      route[x][y].x = EMPTY;
  }
  
  route[to.x][to.y].x = 1;
  pending[0] = to;
  for (i = 0; i < max_pending; i++)
  {
    for (j = 0; j < 8; j++) /* try 8 directions */
    {
      field.x = pending[i].x + knight[j].x;
      field.y = pending[i].y + knight[j].y;
      if (field.x >= 0 && field.y >= 0 &&
	      field.x < MAX_TRAVEL && field.y < MAX_TRAVEL &&
	      route[field.x][field.y].x == EMPTY &&
	      visited[field.x][field.y] == 0)
      {
	      route[field.x][field.y] = pending[i];
	      if (field.x == from.x && field.y == from.y)	/* print route? */
	      {
	        while (from.x != to.x || from.y != to.y)
	        {
#if PRINT
	          fprintf(stdout, "%d %d\n", from.x, from.y);
#endif	          
#if TEST
	          if (visited[from.x][from.y]++ == 0)
	            nr_of_fields++;
#endif
	          from = route[from.x][from.y];
	        }
	        return true;
	      }
	      if (max_pending >= MAX_TRAVEL*MAX_TRAVEL)
	      {
	        fprintf(stderr, "max_pending overflow\n");
	        exit(1);
	      }
	      pending[max_pending] = field;
	      max_pending++;
      }
    }
  }
  return false;
}

/* print the journey */

static void
print_journey()
{
  int customer;
  int x;
  int y;
  
  for (x = 0; x < MAX_TRAVEL; x++)
  {
    for (y = 0; y < MAX_TRAVEL; y++)
      visited[x][y] = 0;
  }
	
  for (customer = 0; customer < max_customer; customer++)
  {
    if (!print_route(point[best_journey[customer]], point[best_journey[customer+1]]))
      print_alt_route(point[best_journey[customer]], point[best_journey[customer+1]]);
  }
#if PRINT
  fprintf(stdout, "0 0\n");
#endif
#if TEST
  fprintf(stdout, "unique %d\n", nr_of_fields);
  fprintf(stdout, "total hops %d\n", get_total());
#endif
}

/* create the distance matrix */

static void
get_distance()
{
  int from;
  int to;
  XY shift;
  XY dest;
  XY rel_dest;
  
  for (from = 0; from < max_customer; from++)
  {
    /* the distance between (0,0) and (1,1) is 4 */
    /* the distance between (x,y) and (x+1,y+1) is 2 */
    hops[1][1] = (from == 0 ? 4 : 2);
    distance[from][from] = 0;
    for (to = from+1; to < max_customer; to++)
    {
      shift.x = point[from].x;
      shift.y = point[from].y;
      dest.x = point[to].x;
      dest.y = point[to].y;
      rel_dest.x = dest.x - shift.x;	/* shift (x0,y0) to (0,0) */
      rel_dest.y = dest.y - shift.y;
		
      if (rel_dest.x < 0)	/* to (-,?) */
	      rel_dest.x = -rel_dest.x;
      if (rel_dest.y < 0)	/* to (?,-) */
        rel_dest.y = -rel_dest.y;
      distance[from][to] = distance[to][from] = hops[rel_dest.x][rel_dest.y];
#if 0
      fprintf(stdout, "(%d,%d) (%d,%d) %d %d %d\n",
      	point[from].x, point[from].y, point[to].x, point[to].y,
      	rel_dest.x, rel_dest.y, hops[rel_dest.x][rel_dest.y]);
#endif
    }
  }
}

/* print the distance matrix */
 
static void
print_distance()
{
  int x;
  int y;
  
  for (y = 0; y < max_customer; y++)
  {
    for (x = 0; x < max_customer; x++)
      fprintf(stdout, "%2d ", distance[x][y]);
    fprintf(stdout, "\n");
  }
}

/* find a shorter journey using 2-opt moves until failure */

static bool
two_opt()
{
  int i;
  int k;
  int c1;
  int c2;
  int c3;
  int c4;
  bool swap = true;
  int ct;
  int s;
  int t;
  bool swap2 = false;
  while (swap)
  {
    swap = false;
    for (k = 2; k < max_customer; k++)
    {
      for (i = 0; i+k < max_customer; i++)
      {
        c1 = journey[i];
        c2 = journey[i+1];
        c3 = journey[i+k];
        c4 = journey[i+k+1];
        if (distance[c1][c2] + distance[c3][c4] > 
            distance[c1][c3] + distance[c2][c4])
        {
          for (s = i+1, t = i+k; s < t; s++, --t)
          {
            ct = journey[s];
            journey[s] = journey[t];
            journey[t] = ct;
          }
          swap = true;
          swap2 = true;
        }
      }
    }
  }
  return swap2;
}

/* perform node insertion */

static bool
node_insertion()
{
  int shorter;
  int im1;
  int i0;
  int i;
  int i1;
  int j;
  int j1;
  int j0;
  int delta;
  int js;
  int oi;
  int k;
  bool swap = true;
  bool swap2 = false;
  
  while (swap)
  {
    swap = false;
  for (i = 1; i < max_customer; i++)
  {
    shorter = 0;
    for (j = 0; j < max_customer; j++)
    {
      if (j == i || j == i-1)
        continue;
      im1 = journey[i-1];
      i0 = journey[i];
      i1 = journey[i+1];
      j0 = journey[j];
      j1 = journey[j+1];
      delta = distance[im1][i1] + distance[j0][i0] + distance[j1][i0]
              - distance[im1][i0] - distance[i0][i1] - distance[j0][j1];
      if (delta < shorter)
      {
        shorter = delta;
        js = j;
      }
    }
    if (shorter < 0)
    {
/*      fprintf(stdout, "%d: %d -> %d, %d\n", get_total(), i, js, shorter);*/
      swap = true;
      swap2 = true;
      oi = journey[i];
      if (i < js)
      {
        for (k = i+1; k <= js; k++)
          journey[k-1] = journey[k];
        journey[js] = oi;
        --i;
      }
      else
      {
        for (k = i-1; k > js; --k)
          journey[k+1] = journey[k];
        journey[js+1] = oi;
        journey[max_customer] = journey[0];
      }
    }
  }
  }
  return swap2;
}

/* perform edge insertion */

static bool
edge_insertion()
{
  int shorter;
  int im1;
  int i0;
  int i;
  int i1;
  int j;
  int j1;
  int j0;
  int delta;
  int js;
  int oi;
  int oi1;
  int k;
  bool swap = true;
  int i2;
  bool normal_edge;
  bool swap2 = false;
  
  while (swap)
  {
    swap = false;
  for (i = 1; i < max_customer-1; i++)
  {
    shorter = 0;
    for (j = 0; j < max_customer; j++)
    {
      if (j == i || j == i-1 || j == i+1)
        continue;
      im1 = journey[i-1];
      i0 = journey[i];
      i1 = journey[i+1];
      i2 = journey[i+2];
      j0 = journey[j];
      j1 = journey[j+1];
      delta = distance[im1][i2] + distance[j0][i0] + distance[j1][i1]
              - distance[im1][i0] - distance[i1][i2] - distance[j0][j1];
      if (delta < shorter)
      {
        shorter = delta;
        js = j;
        normal_edge = true;
      }
      /* try reverse edge */
      delta = distance[im1][i2] + distance[j0][i1] + distance[j1][i0]
              - distance[im1][i0] - distance[i1][i2] - distance[j0][j1];
      if (delta < shorter)
      {
        shorter = delta;
        js = j;
        normal_edge = false;
      }
    }
    if (shorter < 0)
    {
 /*     fprintf(stdout, "%d: %d -> %d, %d, %d\n", get_total(), i, js, shorter, normal_edge);*/
      swap = true;
      swap2 = true;
      oi = journey[i];
      oi1 = journey[i+1];
      if (i < js)
      {
        for (k = i+2; k <= js; k++)
          journey[k-2] = journey[k];
      if (normal_edge)
      {
        journey[js-1] = oi;
        journey[js] = oi1;
      }
      else
      {
        journey[js-1] = oi1;
        journey[js] = oi;
      }
        --i;
      }
      else
      {
        for (k = i-1; k > js; --k)
          journey[k+2] = journey[k];
      if (normal_edge)
      {
        journey[js+1] = oi;
        journey[js+2] = oi1;
      }
      else
      {
        journey[js+1] = oi1;
        journey[js+2] = oi;
      }
        journey[max_customer] = journey[0];
      }
    }
  }
  }
  return swap2;
}

/* perform 4-opt move */

static void
opt()
{
  int optp[4];
  int k;
  int i;
  int j;
  
  for (k = 0; k < 4; k++)
  {
loop:
#if __MWERKS__
    i = rand();
#else
    i = random();
#endif
    i = i % max_customer;
    for (j = 0; j < k; j++)
    {
      if (optp[j] == i)
        goto loop;
    }
    optp[k] = i;
  }
}

/* save the best journey */

static void
copy_journey()
{
  int i;

  for (i = 0; i <= max_customer; i++)
    best_journey[i] = journey[i];
}

/* restore the best journey */

static void
copy_back()
{
  int i;

  for (i = 0; i <= max_customer; i++)
    journey[i] = best_journey[i];
}

/* try to find a shorter journey */

static void
try_journey()
{
  int j;
  int min_hops;
  int nr_of_hops;
  int i;
  bool first = true;
  
  min_hops = 32000;
#if __MWERKS__
  for (i = 15; i >= 5; i--)
#else
  while (!time_out)
#endif
  {
  for (j = 0; j < max_customer && !time_out; j++)
  {
    if (!first)
      near_journey(15, j);
    first = false;
    two_opt();
/*    edge_insertion();
    node_insertion();*/
    nr_of_hops = get_total();
    if (nr_of_hops < min_hops)
    {
#if TEST
      fprintf(stdout, "%d\n", nr_of_hops);
#endif
      validate();
      copy_journey();
      min_hops = nr_of_hops;
    }
    else
      copy_back();
  }
  }
}

/* rotate the points to make (0,0) the first point */

static void
copy_zero()
{
  int zero;
  int j;
  for (zero = 0; zero < max_customer; zero++)
  {
    if (journey[zero] == 0)
      break;
  }
  for (j = 0; j < max_customer; j++)
    best_journey[(max_customer+j-zero) % max_customer] = journey[j];
  best_journey[max_customer] = best_journey[0];
}

/* perform the savings algorithm */

static void
savings()
{
  int *tours[MAX_POINT];
  int nr_of_points[MAX_POINT];
  int nr_of_tours = max_customer-1;
  int i;
  int j;
  int k;
  int save_len;
  int save_j;
  int save_k;
  bool j_rev;
  bool k_rev;
  int save;
  int j0;
  int j1;
  int k0;
  int k1;
  int *new_tour;
  int *np;
  
  for (i = 0; i < max_customer; i++)
  {
    tours[i] = (int *) malloc(sizeof(int));
    *tours[i] = i+1;
    nr_of_points[i] = 1;
  }
  while (nr_of_tours > 1)
  {
    /* calculate largest savings */
    save_len = -1;
    for (j = 0; j < nr_of_tours; j++)
    {
      for (k = j+1; k < nr_of_tours; k++)
      {
        j0 = *tours[j];
        j1 = *(tours[j]+nr_of_points[j]-1);
        k0 = *tours[k];
        k1 = *(tours[k]+nr_of_points[k]-1);
        save = distance[0][j0] + distance[0][k0] - distance[j0][k0];
        if (save > save_len)
        {
          save_len = save;
          j_rev = true;
          k_rev = false;
          save_j = j;
          save_k = k;
        }
        save = distance[0][j1] + distance[0][k0] - distance[j1][k0];
        if (save > save_len)
        {
          save_len = save;
          j_rev = false;
          k_rev = false;
          save_j = j;
          save_k = k;
        }
        save = distance[0][j0] + distance[0][k1] - distance[j0][k1];
        if (save > save_len)
        {
          save_len = save;
          j_rev = true;
          k_rev = true;
          save_j = j;
          save_k = k;
        }
        save = distance[0][j1] + distance[0][k1] - distance[j1][k1];
        if (save > save_len)
        {
          save_len = save;
          j_rev = false;
          k_rev = true;
          save_j = j;
          save_k = k;
        }
      }
    }
    /* join the two tours */
    new_tour = (int *) malloc(sizeof(int)*(nr_of_points[save_j] +
      nr_of_points[save_k]));
    np = new_tour;
    if (j_rev)
    {
      for (k = nr_of_points[save_j]-1; k >= 0; --k)
        *np++ = *(tours[save_j]+k);
    }
    else
    {
      for (k = 0; k < nr_of_points[save_j]; k++)
        *np++ = *(tours[save_j]+k);
    }
    if (k_rev)
    {
      for (k = nr_of_points[save_k]-1; k >= 0; --k)
        *np++ = *(tours[save_k]+k);
    }
    else
    {
      for (k = 0; k < nr_of_points[save_k]; k++)
        *np++ = *(tours[save_k]+k);
    }
    tours[save_j] = new_tour;
    nr_of_points[save_j] += nr_of_points[save_k];
    nr_of_tours--;
    tours[save_k] = tours[nr_of_tours];
    nr_of_points[save_k] = nr_of_points[nr_of_tours];
  }
  best_journey[0] = 0;
  for (i = 1; i < max_customer; i++)
    best_journey[i] = *(tours[0]+i-1);
  best_journey[i] = 0;
  copy_back();
#if TEST
 fprintf(stderr, "%d\n", get_total());
#endif
}

static void
init_journey()
{
  int i;
  
  best_journey[0] = 0;
  for (i = 1; i < max_customer; i++)
    best_journey[i] = i;
  best_journey[i] = 0;
  copy_back();
#if TEST
  fprintf(stderr, "%d\n", get_total());
#endif
}

int
#if __MWERKS__
main()
#else
main(argc, argv)
int argc;
char *argv[];
#endif
{
  char *in_file;
#if __MWERKS__
  in_file = "point100";
#else
  int option;
  while ((option = getopt(argc, argv, "d:t:")) != EOF)
  {
    switch (option)
    {
#if DEBUG     
    case 'd':		/* a higher number gives more debugging output */
      debug(db_enable, atoi(optarg));
      break;
#endif
    case 't':		/* maximum cpu time in seconds, default 600 */
      max_time = atoi(optarg);
      break;
    default:
      fprintf(stderr, "%s: invalid option: %c\n", argv[0], option);
      exit(1);
    }
  }

  in_file = argv[optind];
  signal(SIGALRM, alarm_signal);
  alarm(max_time);
#endif
  
  point[0].x = point[0].y = 0;
  read_customers(in_file);
  fill_hops();
  get_distance();
#if 0
  init_journey();
#else
  savings();
#endif
/*  print_distance();*/
/*  print_points();*/
  try_journey();
  copy_journey();
  copy_back();
  copy_zero();
  print_journey();
#if TEST
  printf("end of program\n");
#endif
  return 0;
}