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!
=============== 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.