PASCAL MACRO COMPILER
Case Study: Crossword Puzzle Constructor
I had written a program to generate crossword puzzles, and I
was seeking a market for the resulting puzzles.
One publishing company indicated that it would accept my puzzles, but offered
a very low price for each puzzle.
The only way to produce a worthwhile amount of revenue was to generate
bulk quantities of puzzles and sell them in large lots.
The general-purpose crossword constructor that I had written was
too slow for this.
To obtain the speed I wanted, I decided to select a single puzzle diagram
and write a program that would generate puzzles with that specific layout.
Writing this program was slow and tedious.
The general-purpose crossword puzzle constructor works by placing
a single word at a time.
It scans the space where the word belongs to find the word length
and any letters that have already been placed.
It then searches its word lists for matching words.
After it places each candidate word, it scans to each side to see
if there are any letters placed in the crossing word.
Then it checks if there are any words that match these existing letters
plus the letter from the new word.
If not, the candidate word is rejected.
The new program would take advantage of the fixed diagram.
As each word is chosen, the program will know the length of the word,
the positions where existing letters would be, and the positions of
all known letters in the crossing words.
There will be separate arrays giving all the valid combinations of
2 and 3 letters in words of each length, so the tests for valid
crossing words can be done by a single lookup.
For example, the array t6p235 would tell whether a given combination of
letters occurs in positions 2, 3 and 5 in any 6-letter words.
Thus t6p235[ord('L'),ord('P'),ord('C')] would be true because the
word ALPACA has the letters LPC in positions 2, 3 and 5.
All of this is simple in principle, but very lengthy to
program and debug.
In just a little 15x15 crossword puzzle layout there about 40 words in each
direction containing about 195 letters.
This means there are about 80 word searches to write and 190 tests
for valid letters.
There are also more than 50 letter-combination arrays to generate.
Much of this can be done by copying the routines and editing them
for each new word, but this is tedious, and difficult to get 100%
correct.
The Pascal Macro Compiler can eliminate all of the repetitious work.
The macro program makes two passes through the puzzle.
On the first pass, the macro program marks each square where a new letter
is placed in each word.
Then it scans to the side to see what letters had already been placed
in each crossing word.
The macro program keeps a table of each such combination of letters.
At the end of this exploratory pass, the macro program generates
a Pascal procedure to build an array for each unique combination
of word length and letter positions.
On the second pass, the macro program again marks each square where
a new letter is placed in each word.
This time, it generates the code to search for words fitting the existing
letters, and the code to test the crossing words, using the arrays
that have been built.
Those are the main operations.
The macro program also generates declarations for the arrays and
other variables, generates the ends of FOR loops, generates code
to set and test flags so a word does not get used twice,
and generates some standard code to read the dictionary files and print
the resulting puzzle.
The only part of the process that the macro program does not
perform is choosing the order for placing the words.
I choose the order myself, and specify it in an integer array
in the macro program.
One great work-saver is that much of the macro code can be created from
the Pascal code in my original general-purpose crossword puzzle constructor.
An advantage of this approach is that the same macro program can generate
crossword programs for any other puzzle layout I may want later.
A crossword puzzle constructor generated by this approach
is more than 100 times faster that using the general-purpose crossword
constructor.
© Copyright 2005 Frank Rubin