SCENIC TOUR

The Spring POTM - deadline midnight June 26, 1998

These are the long rules for the latest POTM. I have tried to be as clear as possible but if there are any questions please ask them as soon as possible so I can correct errors in the weekly FAQ mailings. My goal is to eliminate loopholes - if you have a question about wording, I probably meant the statement to have the simplest possible interpretation.
To get the weekly mailings, SEND MAIL to fah@potm.ffast.att.com WITH THE WORD ENTER IN THE Subject LINE.


I will give you a file providing the altitudes for every point 
within a square grid.  Your trip starts at the upper left, 
goes to the lower right, and then returns.  Each move you make 
will take you to an adjacent grid point. I'll tell you how many 
moves you may make to accomplish the round trip.  

Your task:  within the given number of moves, both minimize and 
maximize the "vertical" distance traveled.  Think of it as a map 
of mountain ranges ... do as little climbing as possible while going, 
then take the "scenic tour" on your return home.


==================  T H E   L O N G   R U L E S  =================

I.  YOUR PROGRAM AND YOUR TASK IN SUMMARY

	a.  Your program must take a single argument which will
	      be the name of an input file in the format 
	      described below.

        b.  Your program must read the input file to deduce the
	      parameters of the problem.  The input file format
	      is given below in detail.

        c.  Once your program has read the input file, it will
	      have the following information:

	      1.  LIMIT = the maximum number of moves you may make
	      2.  WIDTH = SIZE the number of "east-west" grid points
	      3.  HEIGHT = SIZE the number of "north-south" grid points
		     * note that WIDTH=HEIGHT=SIZE for this POTM
	      4.  ALT[row][col] = the "altitude" of the grid point at
		   east-west coordinate column where col = (0 through SIZE-1)
		   north-south coordinate row where row = (0 through SIZE-1)

	d.  Your program then computes a round-trip path which begins and
	      ends at grid point (0,0) and passes through grid point
	      (SIZE-1, SIZE-1) with no more than LIMIT moves in it.

	e.  Your program outputs no more than LIMIT lines of output, with
	      each line being the row and col coordinate of the next move.
	      The starting point (0,0) is NOT included but all others are.
	      The final point MUST be (0,0) and the path must pass through
	      (SIZE-1,SIZE-1) and conform to all the rules below.

	f.  I score your program based on my analysis of the standard
	      output and you are ranked against other competitors based
	      on the criteria given below.  Proudly display your trophy
	      when you win!

II.  SCORING AND WINNING - SYSTEM TESTING and THE FINALS

	a.  I will examine your output file and determine if it conforms
	      to a legal solution as indicated in the "restrictions" below.

	b.  Some definitions to get us rolling

      Definition:  A "move" is the transition from any legal grid
         point to an adjacent legal grid point which is within the
         defined field of play.  There are eight possible moves from
         all central (non-border) grid points - by compass they are
         N, NE, E, SE, S, SW, W, and NW (horizontal, vertical, and
	 diagonal moves are permitted).   Moves may NOT exit the
         defined square and they may NOT "wrap-around" the borders.

      Definition:  The "distance of a move" is defined as the
         absolute difference between the "altitudes" of the adjacent
         grid points.  Thus, if grid point (17,6) has an altitude of
         50 and (18,7) has an altitude of 30, the "distance" traveled
         by moving between these grid points in either direction is 20.
	 Note that if two adjacent grid points have the SAME altitude,
	 the "distance" between them is ZERO.

      Definition:  A "path" is a collection of sequential moves.

      Definition:  The "distance of a path" is the sum of the
         distances of the moves which comprise the path.

	c.  Assuming that the path is "legal", I will compute the following
	      measures in order to score your entry.

	      1.  SHORT_SCORE = the distance of your path between the
		  starting point (0,0) and the point (SIZE-1, SIZE-1)

	      2.  LONG_SCORE = the distance of your return path beginning
		  at (SIZE-1, SIZE-1) and ending at (0,0)

	      3.  GRID_SCORE = LONG_SCORE / SHORT_SCORE

	    A high GRID_SCORE is better than a low GRID_SCORE

	d.  A system test file is provided for your pleasure.  When you
	    submit an entry, your GRID_SCORE will be ranked against other
	    contestants in the weekly mailing.  Your SHORT_SCORE and
	    LONG_SCORE will NOT be shown.  If your system test solution
	    is valid and your program executes within the 10 minute
	    time limit, you will qualify for participation in the finals.

	e.  For the FINAL test, I will execute your entry against three
	    different (and likely larger) squares.  Your final POTM score
	    will be the sum of the three individual GRID_SCOREs.  The
	    highest sum will win the POTM.

	    In the event of a tie (which I hope is unlikely) the winner
	    will be determined by the shortest run time taken over the
	    three final runs.  Run time is defined as sys+user time as
	    measured by timex.

III.  RESTRICTIONS ON YOUR PATH AND YOUR OUTPUT
	
	a.  The first coordinate in your path must be one of the following:
		(1,0), (0,1), or (1,1) since you start at (0,0) - note that
		(0,0) is NOT printed at the beginning of your path.

	b.  The FINAL coordinate in your path must be (0,0)

	c.  Your path must pass through (SIZE-1,SIZE-1)

	d.  No point in your path may be re-used.  Once you use a coordinate
	      point in your solution, you may not use it again.  THIS IS
	      IMPORTANT!!!  Your path may loop but it may not re-use ANY
	      single coordinate point in the grid.

	e.  No more than LIMIT coordinate pairs (lines) may be output
	      for the entire round trip, where LIMIT is provided in 
	      the input file.

	f.  All coordinate pairs must lie within the defined square.
		row >= 0  AND  row less than SIZE
		col >= 0  AND  col less than SIZE
	    where SIZE is both the HEIGHT and WIDTH defined in the input file.

	g.  Your program must output your path precisely as follows:

		* each coordinate pair appears on a separate line
		* each coordinate pair is output as two integers, separated
		    only by white space  as in printf("%d %d\n",row,col)
		* the vertical (north-south row) coordinate is first
		    followed by the horizontal (east-west column) coordinate
		* no additional output is permitted either on standard
		    output or standard error.  No debug, no commas, no
		    parentheses, no final scores, nothing but the path.

IV.  RESTRICTIONS ON THE PARAMETERS I'LL GIVE YOU

	a.  The grid will be square ... SIZE by SIZE grid points

	b.  SIZE will not exceed 255  (note that your program MUST
		complete execution in less than ten minutes sys+user
		time even on this largest problem)

	c.  SIZE will not be less than 10

	d.  LIMIT will be greater than 4*SIZE and less
		than 20*SIZE

	e.  The altitude of the (0,0) point and the (SIZE-1,SIZE-1)
		point will be different - thus insuring a minimum
		path length (of leg one) greater than zero.

V.  THE INPUT FILE

	a.  Your program must take a file name as the first argument.  Your
		entry will be executed as "yourprogram filename"
		where filename is an ASCII file conforming to the format
		listed in the following items.

	b.  The input file is in Portable GrayMap (pgm) format.  An internet
		search for "Poskanzer AND pgm" should turn up some
		references ...  JUST CHECK HERE .
		We use a comment line to pass one parameter.  The input
		file must conform to the following for the POTM:

   LINE 1:  contains ONLY the two characters "P2" ... 
   		this is the magic number
   LINE 2:  has two fields:  a "#" in the first column, followed by white
   		space, followed by the integer value of LIMIT
   LINE 3:  contains two integer fields separated by white 
   		space:  WIDTH and HEIGHT (which will both be equal to SIZE
		for this particular POTM)
   LINE 4:  the maximum altitude value of the numbers that follow.  For the
   		POTM this will be 255 implying that all altitude values
   		will be 0 through 255.
   LINE 5 through the end contain the altitude values corresponding to
		each grid point.  There are WIDTH*HEIGHT (or SIZE*SIZE) of them.
		They start at the top-left corner of the graymap, 
		proceeding in normal English reading order.  There will
		be at least one value on each line - just keep reading
		until the end-of-file is reached.


	c. THE FOLLOWING IS THE ACTUAL SYSTEM TEST FILE THAT WILL BE USED!

AVAILABLE HERE IN GRAPHICS FORMAT (systest.pgm) suitable for reading with a graphics viewer like Paintshop Pro,
or in TEXT FILE FORMAT FOR DOWNLOADING (systest.txt).


===============  BEGIN FILE ON FOLLOWING LINE =====================
P2
# 130
30 30
255
89 110 137 169 197 214 219 213 199 179 159 143 132 128 134 149 170 193 
213 227 255 255 214 194 173 154 143 255 146 153 85 106 133 164 192 209 
215 0 194 173 153 136 124 121 127 142 163 185 0 222 255 222 209 189 168 
149 138 135 137 142 79 100 126 157 185 202 208 203 188 166 145 127 114 
110 115 129 149 171 192 207 213 208 195 177 154 132 122 118 118 125 71 
91 116 0 174 193 200 195 181 159 137 117 103 97 100 111 129 150 169 184 
190 186 176 160 136 255 104 100 98 106 61 80 105 135 162 182 191 189 176 
156 133 111 95 86 86 94 108 126 142 155 161 159 151 141 121 103 96 91 89 
96 51 0 94 124 152 174 186 187 176 158 135 113 95 83 0 83 93 106 119 129 
135 135 130 124 109 95 90 87 85 92 43 60 85 115 145 255 187 191 184 168 
147 123 104 90 83 82 88 96 105 112 117 118 117 115 105 94 92 89 86 92 34 
53 78 111 142 169 189 197 194 181 163 140 121 105 96 93 95 99 105 0 112 
113 115 117 115 111 109 255 102 101 29 48 76 110 143 173 195 206 206 196 
180 159 140 125 114 109 109 112 115 118 120 120 122 126 130 131 130 126 
119 113 29 49 76 111 145 176 200 255 255 207 192 173 156 141 130 125 124 
126 129 132 134 133 135 138 142 143 141 136 129 122 32 51 78 112 146 177 
201 255 255 209 195 177 160 146 135 130 130 133 137 142 144 144 145 147 
150 150 149 144 138 132 35 53 79 112 144 173 193 205 206 199 185 169 153 
138 128 124 124 129 135 142 146 148 149 151 152 152 151 149 144 139 41 
57 79 108 136 162 180 190 190 182 167 151 134 120 111 0 108 115 124 133 
141 145 146 148 148 148 148 148 0 145 255 59 77 100 124 144 159 166 165 
156 143 128 113 100 91 87 90 97 108 120 130 137 255 0 255 139 141 144 147 
149 50 59 72 90 108 124 134 139 137 130 119 106 94 83 75 72 75 83 95 108 
120 127 130 130 129 130 134 139 145 150 52 58 67 79 91 102 109 111 109 
104 97 90 82 75 70 68 70 77 89 102 113 120 122 121 120 120 125 133 141 
147 54 58 63 70 76 255 85 86 85 84 82 81 79 77 75 74 76 82 93 104 114 118 
118 114 110 110 114 123 132 140 57 58 60 63 65 66 66 66 67 69 73 78 82 
0 87 88 91 96 105 114 120 122 118 255 103 100 102 110 119 127 61 61 60 
60 58 55 53 52 53 58 68 79 89 97 102 106 109 115 122 128 131 129 120 108 
97 91 91 96 104 111 67 66 63 60 56 50 46 44 46 54 67 82 96 108 118 125 
130 135 141 144 143 136 124 109 96 86 83 85 90 93 75 73 69 63 56 48 43 
41 44 53 69 87 104 120 133 145 152 157 161 160 153 142 127 109 96 85 79 
78 80 78 84 80 75 68 59 50 43 41 45 55 73 93 112 130 146 160 168 173 174 
170 158 144 126 108 97 0 81 78 75 68 93 89 82 74 64 52 45 43 47 59 79 100 
121 140 157 171 179 255 180 172 157 140 120 105 96 89 85 80 72 61 106 100 
92 82 70 58 51 48 255 66 85 107 128 148 164 177 182 183 178 167 149 130 
110 94 90 88 84 77 67 51 125 118 107 94 79 65 56 54 59 72 90 112 132 150 
164 175 178 175 167 153 134 114 95 81 80 79 76 69 59 41 150 141 127 110 
92 75 64 60 64 75 92 112 130 146 156 161 161 156 145 131 114 96 78 66 65 
63 60 54 44 28 177 0 149 129 107 87 73 67 68 76 89 105 121 133 140 142 
139 131 120 106 0 76 61 50 48 45 40 34 28 15 204 192 173 148 123 99 82 
72 70 74 83 94 106 115 120 120 114 105 94 82 69 57 45 34 32 27 20 255 13 
4 225 213 191 164 136 110 89 77 71 71 75 83 91 0 101 99 93 83 72 62 52 
43 33 25 20 13 8 5 4 0 255 225 204 175 146 118 95 79 71 68 68 73 79 84 
86 83 76 66 56 47 39 33 25 18 11 5 1 0 0 0 
===================  END FILE ON PREVIOUS LINE  ========================

	The above file should be interpreted as having 900 values
	arranged in a square array with WIDTH=30 and HEIGHT=30
	(SIZE=30).

	The altitude for grid point (0,0) (=89) is read first, then (0,1),
	then (0,2) ... (0,29), (1,0), (1,1), ... etc. until the
	altitude for the final point (29,29) (=0) is read.

	The value of 130 in line 2 indicates that your total path
	solution must not exceed 130 moves.


The following items are standard links for ALL the POTMs ....
(but they occasionally will change ... so READ 'EM!)



COMMON RULES that are generally applied to all the POTMs ... take a look to find out what languages are supported, what machines I run on, how the contest is run, etc.

TIMING CODE in C/C++/PERL to help you write portable timing code for your entry. really helpful since most POTMs are required to run in less than 10 minutes on MY machine - NOT YOURS! This one is a text file (.txt) since it contains many HTML-sensitive characters.
Make your own free website on Tripod.com