C R O Z Z L E
Simple: Make a crossword puzzle from a word list.
I'll provide a list of words in a file. you will work on a blank
20x20 square grid. Your program will try to link together as many
words as possible from the wordlist in "crossword-puzzle" fashion.
If you can manage to create the most "complex" crossword using the
words I provide, you may just win this POTM!
=========== THE DETAILS - SINCE YOU ASKED ========================
Welcome to the first 1996 POTM ... deadline midnight on 4/1/96 !!!
** items were added via the FAQ following the initial version
I. WHAT DOES YOUR PROGRAM HAVE TO DO?
Your program must take a pathname as an argument, read the
file that is referenced to get a list of up to 200 words,
and use some of these words to create a crossword puzzle
no larger than 20x20.
II. TELL ME MORE ABOUT THE WORD LIST
o The wordlist will be contained in a file whose pathname
will be used as the argument to your entry
o The wordlist file will contain one word per line
o each word will be provided in lower case letters (a-z)
o there will be no special characters (like ' or - or
whitespace) in any of the words ... strictly a-z
o words will be at least two letters long and there will
be no words longer than 20 letters long
o there will be more than 100 words and less than 201 words
in the wordlist
o the words will not be ordered in any particular way
o the words may or may not be "real" words
o the words for the final test will be chosen from a page
of a randomly selected book from my immense library
just prior to the contest deadline
**o there will be no identically duplicated entries in the list
III. WHAT EXACTLY DOES "crossword-puzzle fashion" MEAN?
o the output grid will be 20x20 - you may distribute words
within the full grid or you may choose to use
fewer than 20 rows or columns. If you choose a
smaller grid, you must still show output for all
rows and columns (see IV below).
o all words in the grid must be "connected" to one another:
there must be a horizontal and vertical path of
letters connecting any two letters in the grid.
o all words in the grid must be from the provided wordlist
referenced by the pathname in the argument
o no words may be used more than once in the grid
o embedded words (like "and" in "random") will not count
as separate words for purposes of scoring should
both appear on the wordlist. Should this occur,
they MAY be used at DIFFERENT places in the grid.
o all letter sequences of two or more letters appearing
horizontally or vertically in the grid MUST form
words that are in the wordlist
**o words must read from left to right or top to bottom
**o words must be separated by at least one empty square.
That is, if "one" and "two" are in the wordlist, this
does NOT imply that the six letter "onetwo" may appear
in the grid.
o in short - your output should look like the solution
to a crossword puzzle - with the exception that
it does not need to be symmetrical in any way.
IV. THE SCORING - HOW TO WIN!
The input to your program will be provided in a file whose
pathname is contained in the argument to the executable.
This pathname is the only required argument - and your
program must run if a single argument is provided. Your
program should not look to stdin for input.
The output of your program will be to standard output and
must create output of exactly 420 characters (20 lines of
20 characters plus a newline on each line). Your output
should contain only lower case letters (a through z) and
should use a hyphen (dash, minus, "-") to represent the
blank spaces in your crossword grid. For example:
incredible---------- line 1 .... 20 characters per line
---e-e-------------- line 2 plus a newline
---dive-------------
-----i---p----------
-----o---o----------
-----u---t---------- the wordlist may contain non-words
-----scrambled------ (like potm, or xyzzy, or sfortz)
-------------a------
-------------n------
-------------d------
-------potatoe------ The wordlist may contain incorrectly
--------u----l------ spelled words - or non-English words
----hawaii---i------ or names (non-capitalized)
-------------of-----
-------------nine---
--------------n----- all 20 rows and columns must be output
--------------a----- even if they are not used
----------equalized-
--------------------
-------------------- line 20
Of course - ONLY words contained in the provided wordlist may
appear in your grid, and words may not appear more than once
in the crossword grid.
** Each program will be run three times for the final runs ... all programs
** will use the same three wordlists and the outputs of each run will
** be evaluated according to the following scores (which will be summed
** over the three different wordlists used for the final runs):
First Score: The number of words from the wordlist that
appear in the grid your program outputs - high is good.
In the event of entries tieing on this score, we use:
Second Score: The number of "connectors" in the grid.
a connector letter is a letter that is used in two words.
For example, the "i" that links "final" and "nine" in the
grid above. There are 15 connectors in the sample grid.
Again - high is good ... thus rewarding intricate solutions.
In the event of entries tieing on this score, we use:
Third Score: The number of filled in squares - those squares
out of the 400 that contain letters in your final solution.
High is good ... rewarding the use of longer words - but its
always better to use two short words rather than one long one!
In the event of entries tieing on this score, we use:
Final Tiebreaker will be the execution time as measured by
timex time taken on the final test.
Fast is good .... long is bad. 10 minutes
time as measured on MY box is the limit! Programs
running longer than 10.5 minutes will be disqualified.
V. READ THE Frequently Asked Questions (FAQ) list distributed every
week ... it often contains corrections to this problem statement!
VI. While the ideas for this puzzle go back 6 years (when we tried
solving them without computers), I was reminded of this puzzle
when I ran across a web page in Australia. The page is from
Gary Capell and talks about a puzzle called "crozzle" that
appears in an Australian magazine "Women's Weekly". Gary has
given me permission to reference his web page (thanks Gary!):
http://www.cs.su.oz.au/~gary/hobby/crozzle.html
While you're at it, here's a reminder about the POTM pages:
http://potm.ffast.att.com/ if you're INSIDE AT&T
http://www.cs.washington.edu/homes/corin/POTM.PAGES/ USofA
http://www.strath.ac.uk/Students/WebSoc/POTM/ for Europe
=============================================================================
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/g++ 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.
also perl, version 5.000
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!!!!
This implies that you must allocate large structures with malloc().
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) mail 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 on the system test problem.
e) your program must perform the task specified within ten minutes
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). Ask for a C code remnant that will help you
measure the time on MY box as you execute if you need one.
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
hicinbothem@att.com 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) */
/* compile 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 in a day or so)
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 or hicinbothem@att.com ....
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 ... please!
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