|
|
POTM: Programmer of the Month: GLOSSY: The Details
In general, if you have a question about the detailed rules,
the simplest choice is usually
the right choice - the goal being to encourage participation.
If you have questions - please post them to the forum.
Any change made after the initial post
will be marked (and dated) in red.
Deadline for GLOSSY is September 30, 2005.
I love taking digital pictures, but that nice glossy photo
paper is expensive! So when my lovely wife asks for prints
of a bunch of pictures, I always try and fit them onto a
single piece of paper.
Of course, I can make each picture
bigger or smaller but I still want it to look "natural" so
I can't "stretch" them too much,
and my wife insists that they are some minimum size.
Your POTM task, should
you choose to accept it, will be to arrange some pictures
to make full use of a sheet of printer paper.
I'll give you the width and height of several pictures.
Your program will then tell me how (or if) to modify the
size of each and where to place it on the page. The winner
will be the one that leaves the least white space on the
page - subject of course to all the rules and regulations
presented below.
errata
POTM is pronounced "PAH-TUM"
The M stands for Month - but problems are posed irregularly
The POTM-MASTER is omnipotent, but is allowed to change his
mind whenever he sees fit.
Have fun ... if you're not having fun, do something else for a while!
SPECIAL RULES FOR GLOSSY
A QUICK EXAMPLE
The intermediate moves do NOT need to be shown - they are provided
only to give a visual example of possible movement and size change.
The input will define the starting shapes, and your output will describe
how they are to be modified and placed on the paper. The "starting" position
is arbitrary simply to show the original sizes.
WINNING THE GLOSSY POTM
The solution with the least "white space" (fewest uncovered
pixels) will be the "best" solution.
Three final runs will be made, with overall winner
being determined by sum of relative placements on each of
the runs. (finishing 1st, 5th, and 1st for a total of seven
would be beaten by someone finishing 2nd on all three for
a total of six).
Within each final test, ties will be resolved in favor of
the solution that minimizes the area of the largest minus smallest
picture. This tiebreaker will be used ONLY
if two solutions have the same amount of white space. If two
solutions are still tied, they will share the finishing position.
07/03:
If there are remaining ties after the three final tests, those
entries tieing for first place will be subjected to additional tests
in order to determine a winner.
Entries successfully completing the system test will be
eligible to participate in the final tests.
Solutions that do not provide valid solutions will all
tie for the last position on that test.
SOME DEFINITIONS
The Coordinate system
as used for this POTM will be defined
by the following diagram ... with "horizontal" (X) and "vertical" (Y)
defined as shown and the origin taken to be the lower left hand
corner with coordinates (X,Y) = (0,0). Thus, if the page size
is given as HMAX = 1600 in the horizontal dimension and VMAX = 2100 in the
vertical dimension, the upper right hand corner of the workspace
should be taken to be (X,Y) = (1599,2099). Values outside these
bounds cannot be used for picture placement.
The rectangle defined thusly is your "workspace" as measured in "pixels".
The "corner" of a picture or the workspace will be a pixel position
within the object at a point on the border where two sides meet.
| |
The Aspect Ratio
as used for this POTM will be defined as the ratio of the
larger dimension to the shorter dimension. Thus, Aspect Ratio
will always be greater than or equal to 1.00.
| |
HOW YOU MAY PLACE AND MODIFY A PICTURE
You may place a picture anywhere within the workspace, provided
it does not extend beyond the workspace or overlap (share one or more pixels)
with any other picture in your final output.
The lower left corner of your picture may end up
on the origin or on an axis (X = 0 or Y = 0).
The upper right hand corner of your picture must
end up at some point with X < HMAX and Y < VMAX as defined by the
size of the PAGE in the input file.
You may rotate a picture 90 degrees, thus exchanging the horizontal
and vertical components of the picture. Note that the aspect ratio
does not change during a rotation.
You may resize the picture, maintaining the same aspect ratio
before and after the resizing but making the picture "larger" or "smaller".
Note that the final picture must have a minimum "area" as defined below.
You may "stretch" the picture - but only a little bit! The aspect
ratio of your FINAL picture in your output must be "close" to the aspect
ratio of the original picture as provided in the input file. How close?
Absolute Value ( Original AR - Final AR ) <= ARLIMIT
Where AR is the aspect ratio and ARLIMIT is the limit given below.
Note that this is NOT a percentage of the aspect ratio but rather a
difference in the actual values of the original input picture
and your final output picture.
PROBLEM PARAMETERS
There will be at least two pictures defined in the input file.
There will be at most 26 pictures defined in the input file.
Each picture in the INPUT file will have an area of at least
1000 pixels (horizontal times vertical dimension greater than
or equal to 1000).
An INPUT picture may be larger than the workspace, but will be
no larger than 5000 pixels in either dimension.
06/27: (modified from original 1000 pixel limit)
Each picture in your OUTPUT must have area greater than
or equal to one percent of the PAGE.
The area of any picture must be greater than or equal to PAGEAREA / 100
or one percent of the available workspace. (integer arithmetic rounded down;
for example if the page area is 1009 by 1009 = 1,018,081 pixels then
the minimum area of any picture would be 10,180)
Pictures in your OUTPUT must fit within the workspace.
The aspect ratio of each input picture will be less than
or equal to 10.00.
Each dimension of the PAGE defined in the first line of the
input file will be
at least 500 pixels and at most 5000 pixels. It will be
rectangular (not necessarily square).
The difference between a picture's INPUT aspect ratio and the
same picture's OUTPUT aspect ratio must be <= 0.02 (ARLIMIT above).
THE INPUT FILE
will be provided as a full pathname argument to your executable, as in:
my_entry /tmp/inputfile
The first line of the input file will define the size of the
"paper" in terms of "pixels". This will be your workspace. It will
take the form:
PAGE 1600 2100
where the first field will always be "PAGE", the second field will be an
integer defining the horizontal dimension of the workspace, and the third
field will define the vertical dimension of the workspace.
Each of the lines that follow will define a single "picture". The first
field will be a "label" for the picture and will be an upper case letter.
A 500 300
B 238 151
The two numbers will be the size of the picture in "pixels".
They are the horizontal and vertical size of the
picture in its original orientation respectively.
There will be no blank lines.
There will always be a "PAGE" line as the first line.
There will always be at least two "picture" lines following the
"PAGE" line.
The picture labels will be labelled alphabetically beginning with "A"
with no omitted letter labels.
There will be at most 26 "picture" lines ... the last possible
label being "Z".
There WILL be a solution to the problem presented by the INPUT file.
OUTPUT OF YOUR ENTRY
Your output will be written to standard output and must
conform to the following format definition.
Each of the output lines will define a single "picture" and its
placement. The first
field will be the "label" for the picture (as provided by the input)
and will be an upper case letter.
A 550 330 0 0
B 150 237 600 900
There must be one output line corresponding to each "picture"
input line - ALL pictures must be placed in the workspace.
There is no line corresponding to the "PAGE" input line thus the
output will have one less line than the input file.
Output should be alphabetical (as the input) with the first line
describing picture "A", the second "B", etc.
The four numeric fields are the horizontal size, the vertical
size, the horizontal coordinate of the lower left corner, and the
vertical coordinate of the lower left corner. Thus, in the example
above picture "B" covers the area defined by the four corners:
(X,Y) = (600,900), (749,900), (749,1136), (600,1136)
Each line must contain five fields, separated by white space and
ending with a line feed ( X(0a) or '\n' ).
No additional output is permitted to either standard output
or standard error.
COMMON RULES FOR POTM PROBLEMS
WINNING
Entries completing system test will be eligible for the final runs.
one entry per forum login
multiple submissions of the same algorithm by the same person or team will NOT be tolerated - please don't do this - it will be obvious in the end and only cause pain for the other participants
Your official entry must be submitted for system test by the
deadline (23:59 Eastern time on the deadline date) using the sandbox tools
in order to participate in the finals.
Specific winning criteria will vary for each POTM and should be
clear from the above sections. If there are questions, use the forums please.
Personal info, Consolation Awards and Other Fun Stuff
Your email will never be made public and will not be shared
with anyone. To communicate, use the "private message" capabilities
in the forums.
Your full name (provided for the sandbox) will not be revealed
unless you happen to win - in which case it will appear on the trophy
as you are announced with pride as the winner. Of course, I will have
no way of knowing if it is your real name.
Your code will be publicly available via the website (if you are worthy)
and the top finishers are usually given an opportunity to make their
code "pretty".
The POTM is for fun. In that spirit, there are generally
awards for things like best program name and the like ...
basically anything that I feel like at the end of a contest.
Participants are also encouraged to provide an exposition
on their algorithm after the deadline passes ... these responses are
often the most fun to read and offer insights into the foibles and
quirks of the participants.
Running The Tests - the POTM-MASTER's job
I will subject all entries to a "system test" to qualify them
for the actual event - these are run hourly on the hour via cron (in general).
Scores on the system test problem may (or may not) be public - this
will vary by POTM at my discretion.
System test results are sent to the participant via email including
whatever might be of use for debugging purposes.
For some POTMs, if you pass the system test a slightly more difficult
run with random input data will be executed and the results mailed to you.
If asked nicely (via private message in the forums) it may be
possible to make a debugging run and supply the output, but in general
all debugging should be done on YOUR machine.
Programming Stuff
Input will (most frequently) be provided as a full path argument
to your entry
my_entry /tmp/inputfile
Input file format will be explicitly defined for each POTM problem.
Your POTM problem output (with no extra output) goes to stdout
Explicit required output format will be defined for each POTM problem.
Nothing should be written to stderr
You may "save" information in small temp files in
the local directory (at present there is no enforced size limit)
if not explicitly prohibited by a particular problem.
There will be a per execution time limit (60 sec. sys+user time
as measured by /usr/bin/time unless otherwise stated).
Entries that exceed the time limit will receive a default score.
A signal (9) is sent to the program by the host when the time limit is
exceeded but by then it is too late!
any attempt to do anything whatever outside of your personal
run directory will be cause for disqualification and banning.
C and C++ programs will be compiled with only the math library
added to the standard libraries and no optimization.
Non C/C++ entries must contain a first line beginning with "#!" as
specified in the sandbox instructions.
|
