|
|
POTM: Programmer of the Month: XWORDS: 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 XWORDS is February 28th, 2005.
You will be given a list of words and an empty grid with
16 rows and 32 columns. Your task is to place these words
in crossword puzzle fashion into the grid. You may re-use
the words and there is a single "flipper" square which may
be placed on the grid if you choose. Fill grids better
than the other folks, and you'll win the XWORDS POTM. Full
details are below - please read them!
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 XWORDS
The Starting Grid
The grid will consist of 32 columns and 16 rows as follows:
The Word List
There will be at least one word and fewer than 512 words in the wordlist
Each word will be two letters long or more (WORDLENGTH >= 2)
Each word will be sixteen letters long or less (WORDLENGTH <= 16)
Words in the wordlist will contain only letters "A" through "Z" in upper case letters with no white space
Words will appear in the wordlist with one word per line
Words will not be repeated in the wordlist, but they may be used multiple times in your solution
Do not assume anything (like sorting) about arrangement of the words in the list
Do not assume anything about whether a "word" is contained in any dictionary: POTM, ABCDEFG, and XYZZY are all possible "words"
Words in the list may be subsets of one another: SCAT, CAT, CATS and XCATS may all appear in the same wordlist ... there is no bonus for
using words containing other words ... see scoring note below
There may be words in the wordlist which are not possible to connect to
any other words in the wordlist
Placement of the Words onto the Grid
Any word from the word list may be used in your solution as many times as you wish
You may use any subset of words in the wordlist, or all of them
All words placed on the grid must read left-to-right or downwards
All words placed on the grid must be connected to one another ...
this forum thread may help you with programs to test connectedness.
ONLY words on the wordlist may be used and empty squares or grid boundaries must be used immediately before and after all words
Words may not "wrap-around" the grid boundaries in any sense
Your solution does not need to be symmetric in any sense
Output which is not connected, or contains words which do not appear
in the wordlist, will receive a score of zero
The Flipper Square
There is one (and only one) "flipper" square
(denoted by an asterisk) permitted in your output
You may place the flipper square within any word you place on the grid
When used, it may represent a different letter in the horizontal
and vertical words of which it is a part
Any words formed using the "flipper" square must be part of the wordlist (if C*T is placed on the grid, then there must be a three letter word in the
wordlist that begins with "C" and ends in "T")
The "flipper" will likely be used at a word intersection, although
this is not required (why would you use it elsewhere??)
WINNING XWORDS - Judging of the output
Your "SCORE" will be the total number of letters in all the
words used in your solution
If a word is contained within a longer word, only the longer
word will contribute to the score ... for example, using POTM would
not score for the word POT even if both are in the wordlist
The four segments below would score 12, 6, 6, and 6 respectively.
(obviously any segments would need to be connected somehow - these are examples to demonstrate scoring only and presume "CAT" is in the wordlist.)
The "flipper" square contributes to the word length as though it
was a part of each word
THREE different wordlists will be used to determine the winner, with
the winner being determined based on the sum of the three scores
achieved on the individual wordlists
Tiebreakers will be applied ONLY to those entries that
achieve the highest total after three wordlists are run:
| First tiebreaker: Sum of number of DIFFERENT
words used in each of the three solutions. Words containing the
flipper square will NOT contribute at all to the unique word count.
Largest sum will move to the next tiebreaker, which follows.
|
| Final tiebreaker: Hoping never to get here - I'm
thinking that if we get this far
then the solutions found are likely identical. Smallest executable as
measured by " ls -l " ... or, if there are only TWO entries remaining a
shared place on the POTM trophy since I'd really hate to use this tiebreaker!
|
THE INPUT FILE
will contain available words, in upper case, one per line
words will contain no whitespace or characters other than [A-Z]
will be provided as a full pathname argument to your executable, as in:
my_entry /tmp/inputfile
OUTPUT OF YOUR ENTRY
Important: Your output must contain exactly 16 lines with
32 characters followed by a line feed as in printf("\n") on each line
The letters in your output must be upper case [A-Z} as in the wordlist
The "Flipper" (if used) in your output should be an asterisk "*" (Ascii Oct(052), Dec(42), Hex(2A))
Squares that do not contain a letter or a flipper should contain
an underbar "_" (Ascii Oct(137), Dec(95), Hex(5F))
There should be no white space in your output
An "ls -l" of your output file should show 528 characters total, the
512 squares plus one "line feed" for each output row. This will be checked
and a file of the incorrect size will receive a score of zero.
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 via email 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 overnight 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.
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 a small temp file (at present there is no enforced size limit) if necessary for multi-execution POTMs.
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 zero score. (Note that the sandbox imposes a ten second
limit but that system testing and finals use the full 60 second limit.)
A signal (9) is sent to the program when the time limit is exceeded.
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.
|
