/*  POTM ENTRY:   Sir_Sot						      */
/*  Name:	  Bob Ashenfelter					      */
/*  Email:	  ash@hotsoup.att.com					      */
/*  Compilation:  cc -o Sir_Sot Sir_Sot.c				      */

#include 
#include 
#include 
#include 
#include 

double	t, tlx, TL =	275			;/*   Time limit (seconds).   */
int	NS =	11				;/*   Sameness limit.	      */
static	struct	tms   TMS			;
double  drand48()				;

int	n, ns, done()				;
int	np,	px[101],  py[101],  po[101]	;/*   Input points, order.    */
int	nm, nh, mx[1001], my[1001], h[151][151]	;/*   Output moves, hits.     */
int	qm, qh, qx[1001], qy[1001], qo[101]	;/*   Trial moves, order.     */
int	rm, ro[101]				;/*   Intermediate order.     */
int	dp[101][101], dm[101], dd[101], dn	;/*   Distance between points.*/
int	kx[8] = { 2,-2, 1, 1,-2, 2,-1,-1}	;/*   Knight's moves.	      */
int	ky[8] = { 1, 1,-2, 2,-1,-1, 2,-2}	;

main(argc,argv)	    int argc;	char *argv[];	{/* KNIGHTCRAWLER POTM	      */
    FILE    *fp, *fopen()			;
    int	    i, j, jn, k				;

    signal(SIGINT,done)				;/*   Catch interrupt.	      */
    if (argc>2)		TL = atof(argv[2])	;/*   Set time limit.	      */
    if (TL==0)		TL = 9E9		;/*     Infinite.	      */
    tlx = TL/(TL + 2.0)				;
    if (argc>3)	  srand48((long)atoi(argv[3]))	;/*   Seed random # generator.*/
    else	  srand48((long)time((long *)0));/*     Default = time.       */

    if (argc<2)		fp = stdin		;/*   Input the points.	      */
    else if ((fp = fopen(argv[1],"r"))==NULL) exit(1);
    for (np=1; np<=101; np++)			{
	if (fscanf(fp,"%d",&px[np])==EOF) break	;
	if (fscanf(fp,"%d",&py[np])==EOF) break	;
	qo[np] = np;	h[px[np]][py[np]] = 1	;}
    qo[0] = 0;		h[0][0] = 1		;

    for (i=0; i0.5)||(nm==dn)||(ns>NS)) break;}
	if ((t>0.5)||(nm==dn)||(ns>NS))	  break	;}

    if (nmtlx)||(nm==dn))	break	;}
	if ((t>tlx)||(nm==dn)||(++ns>NS)) break;}

    ns = 0					;
    while (++n)					{/*   Compute final moves.    */
	for (jn=0; jn<2*np; jn++)		{
	    improve2(j=((j+=14)%np))		;/*	Use 2 improvers only. */
	    improve3(j=((j+=17)%np))		;}
	if (qh!=qm)				{/*	If multiple hits,     */
	    for (jn=0; jnnh)))	{/*	If better,	      */
	    for (i=0; i<=qm; i++)		{/*		     save it. */
		mx[i] = qx[i]			;
		my[i] = qy[i]			;}
	    nm = qm;	nh = qh			;}
	if ((nh==nm)&&((nm==dn)||(++ns>NS))) done();
	if ((nh==nm-1)&&(ns>2*NS))	done()	;
	times(&TMS)				;
	t = (double)(TMS.tms_stime+TMS.tms_utime)/TL/HZ;
	if (t>=1.0)			done()	;}
						}
done()						{/* Print answer and quit.    */
    int	    i, j				;
    if (nh==0)					{/*   Compute moves if none.  */
	allmoves((nmk)  {	x = k;	k = l;	l = x;		}
    x = (l>k/2)?((k+l)/3+(k+l)%3):(k/2+((((l&1)?(k+2):k)%4)+1)/2);
    if (((k==1)&&(l==0))||((k==2)&&(l==2))) x += 2;
    if ((i==0)&&(j==0)&&(k==1)&&(l==1))	    x += 2;
    return(x)					;
						}
allmoves(xo)		int	xo[];		{/* Compute all moves.	      */
    int	    i, j				;
    static int	m				;
    m = (m>0)?-1:1;	j = np*drand48()	;/*   Direction, random start.*/
    qm = qh = 0					;
    qx[0] = px[xo[j]];	qy[0] = py[xo[j]]	;/*   Save starting point.    */
    for (i=0; i0)?((++j==np)?(j-=np):j):((--j<0)?(j+=np):j));}/*  points.*/
    for (i=0; i0; j--)			{/*   For each move toward i: */
	r = 8*drand48()				;/*	Random index to kx,ky.*/
	for (k=0; k<8; k++)			{/*	For all 8 moves:      */
	    x = qx[qm] + kx[(r+k)%8]		;
	    y = qy[qm] + ky[(r+k)%8]		;
	    if ((x<0)||(y<0))		continue;/*	  NG - Out of bounds. */
	    if (j==dist(x,y,px[xo[i]],py[xo[i]])){/*	  OK - Right direction*/
		if (h[x][y]==0)		break	;/*	    Not hit - take it!*/
		xx = x;		yy = y		;}}
	if (k==8)  {x = xx;	y = yy;		}/*	Must revisit...	      */
	if (++h[qx[++qm]=x][qy[qm]=y]==1)  ++qh	;}/*	Save chosen move,     */
    ++h[qx[++qm]=px[xo[i]]][qy[qm]=py[xo[i]]]; ++qh;/*		count the hit.*/
						}
shakeup()					{/* Randomize the point order.*/
    int	    i, j, k				;
    qm = 8E8;		qh = 0			;
    for (i=0; i<(np-1); i++)			{
	j = qo[i]; qo[i] = qo[k=i+(np-i)*drand48()]; qo[k] = j;}
						}
solve1()					{/* Compute Traveling Salesman*/
    int	    i, j, k, x, y, z			;/*		     solution.*/
    qm = qh = 0					;
    j = qo[0]; qo[0] = qo[k=np*drand48()]; qo[k] = j;/*Pick random start point*/
    for (i=1; i<(np-1); i++)			{/*   For remaining points:   */
	x = 999;		z = 0		;
	for (j=i; jkk+1; j--)			{
	    qo[j] = qo[j-1]			;}
	qo[kk+1] = qo[jj];	qo[jj] = x	;}/*		  in path kk. */
    qm = dp[qo[np-1]][qo[0]];			;/*	Compute total distance*/
    for (i=0; inp-1)			n = np-1	;
    x[0] = qo[(i?i:np)-1]			;
    x[n+1] = qo[(i+n=10)				{
	    times(&TMS)				;
	    if (TMS.tms_stime+TMS.tms_utime>=tlx*TL*HZ) return(999);}
	for (i=1; i<=n; i++)  z[i] = y[i] = x[i];
	for (i=1; i<=n; i++)			{/*   For all n points	      */
	    dx = dp[x[i]][x[n+1]]		;
	    ex = e - dd[x[i]] + dm[x[i]] - dm[x[n+1]];
	    if (2*(d-dx)<=ex)	continue	;
	    xx = x[i];  x[i] = x[n];  x[n] = xx	;/*	     in last position:*/
	    dx += improver(n-1,x,d-dx,ex)	;/*    Improve n-1 recursively*/
	    if (dx < d)				{/*	Save best improvement.*/
		for (j=1; j<=n; j++) y[j] = x[j];
		d = dx				;}
	    for (j=1; j<=n; j++)     x[j] = z[j];}
	for (j=1; j<=n; j++)			{/*   Recall best point order.*/
	    x[j] = y[j]				;}
	return(d)				;}
						}
improve2(i)		int	i;		{/* Improve by moving point i.*/
    int     j, k, d, e, f, x			;
    d = dp[qo[(i?i:np)-1]][qo[i]] + dp[qo[i]][qo[(i+1 f)				{/*	Find best place for i.*/
	    f = e;		k = j		;}}
    if (f>=0)					{/*   If no distance penalty: */
	x = qo[i]				;/*	Move point i	      */
	for (j=i ;; j++)			{
	    if (j==np)		j = 0		;
	    if (j==k)		break		;
	    qo[j] = qo[(j+1 e)				{/*	Find best other conn. */
	    e = d;		k = j		;}}
    if (e>=0)					{/*   If no distance penalty: */
	while (1)				{/*	Exchange connections  */
	    if (++i==np)	i = 0		;/*	    to points i, k    */
	    if (i==k)	break			;/*	    by reversing order*/
	    if (--k < 0)	k = np - 1	;/*	    of intervening    */
	    if (i==k)	break			;/*	    points.	      */
	    x = qo[i]; qo[i] = qo[k]; qo[k] = x;}
	qm -= e					;}
						}
improve4(i,n)		int	i, n;		{/* Improve by moving n points*/
    int	    d, e, f, g, h, j, k, l, ll, m, x[51];/*	starting with point i.*/
    if ((n < 2)||(2*n>np))	return		;
    h = (i?i:np)-1; k = (i+n f)				{/*	Find best destination.*/
	    f = e;	ll = l;		g = 1	;}
	e = d - dp[qo[i]][qo[m]] - dp[qo[j]][qo[l]] + dp[qo[l]][qo[m]];
	if (e > f)				{/*	Ditto (reverse order).*/
	    f = e;	ll = l;		g = -1	;}}
    if (f>=0)					{/*   If no distance penalty: */
	m = (ll+10)?((i+l=0)			return		;/*   Not out of order.	      */
    x = (px[qo[h]]-px[qo[i]])*(px[qo[h]]-px[qo[j]])
      + (py[qo[h]]-py[qo[i]])*(py[qo[h]]-py[qo[j]]);
    if (x<0)					{/*   Choose end to swap.     */
	k = j;  j = i;  i = h;  h = (i?i:np)-1	;}
    else					{
	k = (j+1-->











Make your own free website on Tripod.com