April 2001 Programmer's Challenge
Crossword II
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Sunday, 1 April 2001
Due Date: 11:59pm ET, Sunday, 1 April 2001
Crossword II
Several years ago we held a Programmers Challenge based on crossword puzzles. So when my son came home from school with an idea for a crossword Challenge, my first thought was that we had been there and done that. The old Challenge required readers to solve a crossword puzzle, fitting the available words into a predefined pattern, without the benefit of clues. My son’s problem, to generate a crossword puzzle, is sufficiently different to make a potentially interesting Challenge.
The prototype for the code you should write is:
typedef struct Words {
char *theWord;
short value; /* points value for theWord */
} Words;
typedef struct WordPositions {
short whichWord; /* index in Words array of word being placed */
short row; /* row in which the first letter of the word is placed */
short col; /* col in which the first letter of the word is placed */
short orientation; /* 0==down, 1==across */
} WordPositions;
long /* numberOfWordPositions */ CrosswordII (
short puzzleSize, /* puzzle has puzzleSize rows and columns */
const Words words[], /* words to be used to form the puzzle */
short numWords, /* number of words[] available */
WordPositions positions[] /* placement of words in puzzle */
);
The homework assignment that inspired this Challenge was from Chemistry class. Students were required to generate a 20x20 crossword puzzle using the names of the first 103 elements from the periodic table. Each word placed had a value equal to the atomic number for that element. So placing the word "lawrencium" earns you 103 points, "molybdenum" is worth only 42, but "lead" is worth 82. The assignment was to generate a crossword puzzle worth as many points as possible.
For the Challenge, we’ll generalize the problem to work with an arbitrary list of
words and arbitrarily assigned values. The puzzle dimension will be puzzleSize x puzzleSize instead of 20x20. You should decide which words to place where in the puzzle and return your word placements in the positions array, specifying in positions[].whichWord the index in words of the word being placed, the cell in which the first letter of the word is placed in positions[].row and positions[].col, and the direction the word is being placed in positions[].orientation. Your CrosswordII routine should return the number of words placed in the puzzle.A few constraints: Each of the words will be at least 3 letters long and terminated with a zero byte. Every pair of adjacent letters in the puzzle you form must be part of some word. No word may occur more than once in the puzzle. Words may be placed horizontally or vertically, but not diagonally.
The winner will be the solution that earns the most points. Points will be based on the value of the words you place in your crossword puzzle, minus a penalty of 1% for each minute of execution time. The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal. You may provide a solution in Java instead, provided you also provide a test driver equivalent to the C code provided on the web for this problem.
