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