Dec 97 Challenge
Volume Number: 13
Issue Number: 12
Column Tag: Programmer's Challenge
by Bob Boonstra, Westford, MA
Clueless Crosswords
A couple of months ago, Bob Noll sent me a Challenge suggestion involving a crossword
puzzle variant published by one of his local newspapers. The difficulty in using that
suggestion was deciding how to provide the clues to the puzzle in a usable form. I
thought about providing some sort of thesaurus, but giving simple synonyms as clues
didn't seem to capture the crossword spirit. Then it occurred to me that clues serve
only to make the crossword easy to solve, an advantage that certainly wouldn't be
needed by our skilled Challenge readers or by the code they write. So the Challenge this
month is to write code that will solve a crossword puzzle without clues. The prototype
for the code you should write is:
#define kMaxSize 32
typedef char Puzzle[kMaxSize][kMaxSize];
void Crossword(
Puzzle thePuzzle, /* return solved puzzle here */
char *dictionary[], /* array of words to choose from */
long puzzleSize, /* number of rows/cols in puzzle */
long dictSize /* number of words in dictionary */
);
Your Crossword routine will be provided with thePuzzle, where cell
thePuzzle[row][col] will be initialized to a zero if you are to fill in that cell, or
initialized to 0xFF if the cell is blacked out. The first puzzleSize rows and columns
constitute the puzzle; the remaining cells in the Puzzle array are padding and should
be ignored. You are to fill in the empty cells of thePuzzle with words from the
dictionary provided, such that each uninterrupted sequence of blank cells, both
horizontal and vertical, forms a word from the dictionary. The dictionary will contain
all of the words needed to solve thePuzzle, but, to make things more interesting, it will
also contain extra words not needed to solve thePuzzle. The dictionary may contain only
a few extra words, or it may contain as many as 10 extra words for each word used in
thePuzzle. Words in the dictionary are not guaranteed to be in any order, and any word
might be used more than once in thePuzzle.
Each puzzle is guaranteed to have at least one solution using the dictionary provided.
You will be guaranteed 20MB of memory for your code, static data, and any
dynamically allocated memory. You may use more memory if it is available, but your
code should detect and respond to memory allocation failures if you ask for more than
the guaranteed amount of memory. As always, you must deallocate any dynamically
allocated memory before returning.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions may be coded in C, C++, or Pascal. The Challenge winner will be the entry
that provides a correct solution to a set of crossword puzzles in the minimum time.
Thanks to Bob Noll for suggesting a crossword puzzle problem -- he wins two
Challenge points for the suggestion.
Three Months Ago Winner
Congratulations to Ludovic Nicolle (St-Nicolas, Quebec) for submitting the winning
entry to the Image Detector Challenge. The problem was to find all occurrences of a
given pattern bitmap in a sequence of background bitmaps, subject to a specified
allowable error rate. Five people submitted entries, and all but one of them performed
correctly in my tests.
Both the winning entry and the close second place entry by Ernst Munter used 64K of
static memory to look up the number of bits set in a given 16-bit value, as part of
calculating the number of mismatched bits. Ludo gained some advantage by optimizing
the detection routine DetectCenter, used to examine most of the background image, to
process 16 potential matches in parallel and thus take advantage of the many registers
available in the 604 processor. He also used an interesting technique to trick the
compiler into keeping other local variables in registers, by declaring them to be
parameters. Finally, Ludo notes in his commentary that the branch prediction
capability of the 604 caused him to select a different code construct than the one that
worked best on a 601-based machine.
The table below lists the execution time, code size, data size, and programming
language for each entry. The number in parentheses after the entrant's name is the
total number of Challenge points earned in all Challenges to date prior to this one.
Name Time Code Data Language
Ludovic Nicolle (28) 13.74 8606 65860 C
Ernst Munter (290) 5.96 5276 65896 C++
Greg Cooper (54) 87.04 2420 2045 C
ACC Murphy (30) 252.71 2596 120 C++
A.H. 431.30 4076 164 C
Looking Back to May - Equation Evaluator
Ron Avitzur, author of the Graphing Calculator that inspired the May Equation
Evaluator Challenge, wrote to mention a technique that was not used by any of the
entries in that Challenge. Ron pointed me to
http://symbolicnet.mcs.kent.edu/areas/cr, which discusses a technique called Chains
of Recurrence for optimizing function evaluation. The technique can provide speedups
of a factor of 50 when evaluating functions over a range of uniformly spaced points.
The web page allows you to enter an equation and then demonstrates the improvement.
Thanks for the tip, Ron!
... and Back to July - Disambiguator
Ernst Munter wrote to point out a low-memory bug in his winning entry for the July
Disambiguator Challenge that did not show up in my tests. Ernst wrote to say that "the
published program works fine when tested with a generous allowance for private
storage, as originally specified, i.e. at least 21 bytes/word + 1 byte per character of
each word. However, the program was designed to require only about half as much
memory. Unfortunately this has resulted in a bug which will occur with a findstring of
"*" (return all words) because the function SendAll() will start scanning from
pageGroup[0]. But pageGroup[0] was aliased to nextPage, just a temporary pointer
variable, and never properly initialized. If memory was plentiful, the memory pointed
to by pageGroup[0] would still be 0, and nothing bad happens, but otherwise it is
likely to contain some data and result in an unmapped memory exception." Ernst
provided the following replacement function to fix this bug:
ulong SendAll(CCC* matchList[],ulong minLen) {
// Sends all words >= minimum length from all pages
ulong numMatch=0;
/* insert the following line to fix bug */
if (minLen<1) minLen=1;
for (int len=MIN(31,minLen);len<32;len++) {
Page* page=pageGroup[len];
numMatch=page->SendAll(matchList,numMatch);
page=page->next;
}
}
return numMatch;
}
Top 20 Contestants
Here are the Top Contestants for the Programmer's Challenge. 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 210
2. Cooper, Greg 61
3. Lewis, Peter 57
4. Gregg, Xan 53
5. Nicolle, Ludovic 48
6. Boring, Randy 41
8. Murphy, ACC 34
7. Mallett, Jeff 30
9. Larsson, Gustav 27
10. Antoniewicz, Andy 24
11 Picao, Miguel Cruz 21
12. Day, Mark 20
13. Higgins, Charles 20
14. Lengyel, Eric 20
15. Studer, Thomas 20
16. Saxton, Tom 17
17. Gundrum, Eric 15
18. Hart, Alan 14
19. O'Connor, Turlough 14
20. Karsh, Bill 12
Here is Ludo's winning solution:
ImgDetector.c
© 1997 Ludovic Nicolle
/*
General issues:
The code uses 3 functions, DetectLeft/Center/Right to find matches on each side and in
the middle. The same three functions are used for the top/center/bottom on each
column.
Algorithmic considerations:
the fundamental operation for each bit of the mask at any particular location on the
image is the following one and referred as the xor/and later in this discussion:
mismatch = (pattern ^ background) & mask;
if mismatch == 1, you got a bit mismatch.
Since it was assumed the code would more naturally be called with (noise <0.5) than
greater, it made sense to count the mismatches. The code actually substract any
mismatch from the maximum allowed. (The variables names are maxBad for the
maximum and remBad for the remaining allowed bad bits at any time in the process.)
The first natural step of optimization was to treat the data in parallel, either 8, 16 or
32 bits at a time. I chose to work on a 16 bits basis. After the entire operation of
xor/and has been done on 16 bits, the number of 1's in the 16 bits is loaded from a
64k static array (named gBitsOn) containing a 2^16 chars (this method proved to be
statistically much faster than anything else).
Since we needed to "move" the mask and pattern in parallel over the background, I
choosed to move the background instead so I had only one variable to shift each time.
In the DectectLeft/Right functions, the code reflects only those considerations, with a
special treatment for the border when it is not flush.
The DetectCenter function uses a more sophisticated algorithm derived form the simple
one described above. While written in pure C portable code, is is really optimized for