Apr 01 Challenge
Volume Number: 17
Issue Number: 4
Column Tag: Programmer's Challenge
Programmer's Challenge
By Bob Boonstra, Westford, MA
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:
char *theWord; /* null terminated string */
short value; /* points value for theWord */
typedef struct WordPositions {
short whichWord; [TOKEN:12074] 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; [TOKEN:12074] 0==down, 1==across */
long /* numberOfWordPositions */ CrosswordII (
short puzzleSize, [TOKEN:12074] 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[] [TOKEN:12074] 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.
Three Months Ago Winner
Congratulations to Willeke Rieken for winning the January Tetris Challenge. The
Tetris Challenge required readers to provide a player for the classic Tetris game.
Willeke actually won by default, as his was the only entry. As I've said before, you
can't win if you don't play. With this win, Willeke vaults into second place in our
Challenge points standings.
Willeke describes his solution as "low tech". The heavy lifting is done in his MovePiece
routine, where he determines the position and orientation of the current piece that
provides the best fit. His heuristic for best fit takes into consideration the number of
unreachable empty spaces created by placing a piece, with special weighting against
placements that create "deep pits". The solution does not take advantage of the
opportunity to move a piece after it has been dropped, nor does it use the information
provided about the next piece to be placed.
Top Contestants...
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 20 or more points during the past two years. The
numbers below include points awarded over the 24 most recent contests, including
points earned by this month's entrants.
Rank Name Points
1. Munter, Ernst 281
2. Rieken, Willeke 85
3. Saxton, Tom 76
4. Maurer, Sebastian 68
5. Boring, Randy 52
6. Shearer, Rob 48
7. Taylor, Jonathan 36
8. Wihlborg, Charles 29
... and the Top Contestants Looking For a Recent Win
Starting this month, in order to give some recognition to other participants in the
Challenge, we are also going to list the high scores for contestants who have
accumulated points without taking first place in a Challenge. Listed here are all of
those contestants who have accumulated 6 or more points during the past two years.
9. Downs, Andrew 12
10. Jones, Dennis 12
11. Day, Mark 10
12. Duga, Brady 10
13. Fazekas, Miklos 10
14. Flowers, Sue 10
15. Sadetsky, Gregory 10
16. Selengut, Jared 10
17. Strout, Joe 10
18. Hala, Ladislav 7
19. Miller, Mike 7
20. Nicolle, Ludovic 7
21. Schotsman, Jan 7
22. Widyyatama, Yudhi 7
23. Heithcock, JG 6
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the