K N I G H T C R A W L E R

A cross between the classic knight's tour problem and the traveling
salesman problem to entice you this time.  Your program will plan the
route of a traveling salesman with a strange affliction causing him
to move in the manner of a chess knight.  Your job will be to visit
a collection of locations and then return home.  But each move you make
must be the classic "L" of the chess knight.  I'll give you a bunch of
places to visit and you give me the best route.  Cover all the spots with
the smallest number of knight's moves and you just may win!!!

=======================  THE DETAILS - SINCE YOU ASKED ========================

Welcome to the FALL POTM ... deadline midnight on 12/31/95 !!!

You are a knight who has fallen on hard times.  Ever since dragons
were declared an endangered species you have been looking for ways
to supplement your income.  An opportunity to become the regional
representative for a recently spun-off telecommunications equipment
company has come to your attention.  However, in order to maintain
their ISO certification, this company is only hiring those people
who can most efficiently complete their sales rounds.  This is your
employment test ... 

I.  Your TERRITORY .... 
                                  ^
    o Your home base is at        |
      the origin (0,0)            |
                               4  +     +     +     +     +
    o Your territory extends      |
      infinitely to the right     |
      and upwards from home    3  +     +     +     +     +
                                  |
    o Your territory includes     |
      the axes but does NOT    2  +     +     +     +     +
      include area to the left    |
      or beneath the axes.        |
                               1  +     +     +     +     +
    o Moves take place only on    |
      the integer grid points     |
      (as indicated by + )     0  +-----+-----+-----+-----+-->
                             
                                  0     1     2     3     4

II.  Your Affliction ....

     Your days as a dragonslayer have left you with a unique gait ...
     as you move around, you find that you cannot simply move to an
     adjacent grid point.  In fact, it seems that every move you make
     takes you 2 points horizontally or vertically, and then one point
     at right angles.  Your moves resemble those of a chess knight.

     ^                                
     |                                In short, if you are currently
     |                                at the grid point marked by
  4  +     O     +     O     +        the X (2,2), then there are
     |                                eight possible points that you
     |                                can reach - as marked by the Os.
  3  O     +     +     +     O
     |
     |                                Ordinarily, this might be viewed
  2  +     +     X     +     +        as a handicap.  BUT, as it turns
     |                                out, your competition for this
     |                                position are all ex-knights and
  1  O     +     +     +     O        all move in exactly the same way!
     |
     |
  0  +-----O-----+-----O-----+--->

     0     1     2     3     4

III.  Your CUSTOMERS will be specified by grid points.  All your
	customers will be located within your territory.  Your 
	customers MAY be on either axis or out in the positive grid
	area.

	o Your customers (as it turns out) all lie within the square
	  defined by (100,100) and (0,0) ... all your customers will
	  thus be on grid points defined by (X,Y) where 0<=X<=100 and
	  0<=Y<=100

	o You may TRAVEL outside the (100,100) grid if you so choose
	  as long as you stay on non-negative grid points

	o Your program will be presented with a list of customer
	  grid points ... it must then determine your route.

	o Your program must handle a list of up to 100 different
	  customer points - there will be no duplicate customers in
	  the list.  The home positon will NOT be on the list.  The
	  input list will be in no particular order.

IV.  THE TASK and THE SCORING - HOW TO WIN!

	The input to your program will be a list of customer grid points.

	The output of your program will be the route you will take
	to cover the customer sites defined by the input.

	The FINAL will present ONE collection of customer points for which
	your program must deduce a route.

	First Score:  The number of customers you visit on your trip.
		HIGH numbers are good - try to visit ALL the customers.
		(I expect that everyone will visit all customers, so:)

	Second Score:  The total number of moves you take on your trip.
		Your trip starts at home, hits all the customers, and
		then returns home.  LOW numbers are good, the boss is
		looking for efficiency. (If there are ties to be resolved:)

	Third Score:  The total number of DIFFERENT grid points visited.
		The boss is always looking for new customers, so it is
		good to visit as many different places as possible.  In
		this case, HIGH numbers are good!
	
	Final Tiebreaker will be the execution time as measured by
		 timex time taken on the final test.

V.  INPUT/OUTPUT

	o your program should take a filename as the first (and only)
	  argument.
	o your program should generate output to standard output
	o there should be no output to standard error
	o Thus, if a.out is the name of the executable:

		a.out INPUT > OUTPUT

	a) The INPUT file will contain one customer location per line
	   with that customer location being defined by a pair of
	   numbers separated by a single space.  There will be at most
	   100 lines in this file.  No grid coordinates will be greater
	   than 100.  There will be no negative grid coordinates.

	b) The OUTPUT file will contain one grid point coordinate pair
	   per line with that grid point being defined by a pair of
	   numbers separated by a single space.  There may be no negative 
	   grid coordinates.  There is no maximum value of a grid
	   coordinate.  The OUTPUT file MUST have the home point as the
	   FIRST entry and the home pint as the LAST entry.  Note that
	   although grid points may be specified as (x,y) in this 
	   document, they should NOT be represented with parentheses and
	   commas in your program output.

=================  here's a sample to clear it all up !!! ========

     Let us assume that the input to your program is two lines long:

			1 2
			1 1

	This means that you must start at (0,0) as always, find a path
	that touches the points (1,2) and (1,1), and returns to (0,0).
	One possible solution might be the following sequence of points:

    ^                                    
    |                                    0 0    this is the starting point A
    |                                    2 1    this is B
 4  +     +     G     +     +            4 0    this is C (you may touch zero)
    |                                    3 2    this is D
    |                                    1 1    this is E (one of the required)
 3  +     +     +     +     +            3 2    this is F (you may repeat)
    |                                    2 4    this is G
    |                                    1 2    this is H (the other required)
 2  +     H     +    D,F    +            0 0    this is A again ... back to go
    |                                    
    |                                     ^
 1  +     E     B     +     +          The above sequence of number pairs
    |                                  represents the output of your program.
    |                                    (without the comments of course)
 0  A-----+-----+-----+-----C------>   There were 8 moves made, with all
                                         customers visited and 7 different
    0     1     2     3     4            locations visited.


VI.  READ THE Frequently Asked Questions (FAQ) list distributed every
     week ... it often contains corrections to this problem statement!

=============================================================================
    The following items are standard stuff for ALL the POTMs ....
    (but they occasionally will change ... so READ 'EM!)
=============================================================================
I.  About your programming:

	a) I compile on one machine (usually) and execute on another as follows:

		compilation machine: SunOS 5.3 Generic_101318-59 sun4m sparc
		execution machine  : SunOS 5.3 Generic           sun4c sparc

	b) The compilers I have available are (at least):

		SPARCompiler C++ 4.0
		SPARCompiler C   ANSI C compiler
				 SVID compliant under SunOS 5.x
		gcc version 2.6.2

	   All compilation will be done WITHOUT ANY OPTIMIZATION, and the
	   standard math library will be loaded (even if not used).  While
	   this might not reflect the real world, it is at least consistent.
	   No makefiles are permitted, if there are special instructions
	   please so indicate in your program header comments.

		Plus: ... whatever else I can support on the compilation 
		machine ... just ask and I'll try to find it!!!
		I have the ability to compile on several different
		boxes, so don't hesitate to ask!

		IMPORTANT:  submit early so we can resolve any
		portability problems!!!  

	   NOTE: assembly code submissions are NOT acceptable.  I must be
	   the one to compile your code so I can check for cheating!

	c) if you wish to submit a shell program, Bourne, Korn, and csh are
		available ... along with any bin or /usr/bin tools that
		are available as generic Unix tools - my judgement!!!
		(again - submit early in case there are version differences)

	d) Temporary files may be created in /tmp, but MUST be removed
		when you are done ... creation of files anywhere else is
		strictly prohibited.

	e) Maximum size of the source code is roughly 25K characters - 
		different rules may apply for specific POTMS, and 
		comments don't count against you.

	f) Maximum size of executable is 1 Megabyte ... please!!!!

	g) Maximum malloc'able space is a bit over 50 Meg ....

	h) sizeof(short)=2 ; sizeof(int)=4 ; sizeof(long)=4 ; sizeof(char)=1

	i)	a     = 0x80000000  = -2147483648
		a - 1 		    =  2147483647
		a + 1 		    = -2147483647
		{a} is true.	{a == 0} is false.

II.  The system testing ....
	
	a) ship me an entry as soon as possible - you can always submit
		another entry if you improve your solution .. but try and
		keep it down to no more than two a week please!

	b) one entry per person (or team) please.  I associate each entry
		name with an email address and a person for communication
		purposes.  Communication is fine - and encouraged - but
		everyone's code should be their own unless there is a
		stated collaboration and a single team entry.  Honor system!

	c) on receipt of your entry, I'll run a system test to make sure
		your program works ... you'll receive the results and
		a weekly standing of how you fared against other entries.
		(I usually will get to them once a night but perhaps not!)

	d) please make sure your program works with the system test problem.

	e) your program must perform the task specified within a reasonable 
		time (varies with problem - but ten minutes is the norm)
		(sys+user time as measured by timex on MY execution system).
		Your time will be provided along with your system test run
		so you can see the differences in speed between yours and mine.
		All execution time measurements used for tiebreakers (if any)
		will be measured using  time via timex (similar to
		time command).

III.  SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!

	Please email (not uuto, no attachments) your source code to me at:

		enter@potm.ffast.att.com		(preferred)
		attmail!hicinbothem		(will forward correctly but
						 use only as a last resort!)

	IMPORTANT:  Please use the following (or equivalent) lines at the
	front of the program you mail to me (this will help immeasurably!):

	/*  POTM ENTRY:  entryname (something clever please!)		*/
	/*  Your Name:   First Last					*/
	/*  Your email:  log@machine.att.com (or whatever)		*/
	/*  compilation instructions (if other than "make entryname")	*/

	NOTE:  If you submit a shell program, please include these lines
	with a leading "#" and indicate which shell to run it under!  

	IMPORTANT:  ENTER EARLY - you will receive weekly standings and
	you will resolve any portability issues early.  You may improve
	your entry at any time by simply sending me another entry - so it
	pays to enter earlier!  (I process most everything within a day or two.)

	IMPORTANT:  If you don't hear from me within a few days - it may mean
	that the mail got screwed up .... please follow up with an inquiry to
	attmail!hicinbothem .... hopefully all my mail-path bugs are worked out!

Thanks!  If you have any questions, mail 'em to me - if I answer them I'll 
include them in the Frequently Asked Questions (FAQ) list I circulate with 
the weekly standings!!!  Don't call me ... even on the phone.

WATCH THE FAQ - ESPECIALLY IN THE FIRST FEW WEEKS AS ALL THE STUPID ERRORS
  I MAKE IN THE PROBLEM STATEMENT TURN UP!!!!

Looking forward to your entry!		(remember:  enter@potm.ffast.att.com)
=Fred
Make your own free website on Tripod.com