The Winner

The winner is Steve Mitchell who will shortly receive a signed copy of Danny Thorpe's book: Delphi Component Design. Well done, Steve!

Special mention goes to John MacDonald for producing the fastest and (in the judges opinion) a very well written OO solution - unfortunately John's entry was ruled out of contention for returning an incorrect count on one of the test cases.

Entries were received from:

Don Macrae
George Kozaderov
John MacDonald
Ralf Wenske
Roger Connell
Scott Sedgwick
Steven Mitchell
Udo Nesshoever

Thank you to all entrants for submitting an entry. Hopefully you learned some useful string handling techniques and had a bit of fun as well. The judges discovered some interesting code and side-effects which will be discussed in more detail at the November Melbourne ADUG meeting.

The Rules

For the definition and rules of the competition click here.

Judging

Each submission was run through a very small file contrived to catch "boundary conditions" such as the word to be searched being at the start or end of the file. 

A number of words were then searched in Dicken's "Great Expectations" text. The returned counts had to be correct for all searches in both small and large files. The average time to perform the searches on the large file is reported below and in detail in the next section.

Finally, those entries that were within 4 times the fastest result were evaluated for coding style. This was very interesting and more will be said at the November Melbourne ADUG meeting.

Entrant	UN	DM	SS	GK	RW	RC	SM	JM
Small file:
Large file: average (ms)	27100	25733	419	133	81	76	65	40
Style	*	*	*			*
Overall							Prize

*  Not considered as more than 4 times slower than fastest or entrant on judging panel.

Coding style was judged on the following criteria:
a) Maintenance and Readability
b) Structure
c) Robustness
d) Originality

Detailed timings

The following times were obtained on a Celeron 900MHz laptop running Windows XP Home. Each word was searched for 3 times and the overall accumulated score was averaged. The choice of search words was quite arbitrary. Some algorithms are sensitive to the choice of search words, however, the relative average timings are not substantially changed by the choice of search words.

Search word	Correct count	UN	DM	SS	GK	RW	RC	SM	JM
the	8217	178867	170996	441	130	100	101	80	50
king	14	11326	10094	421	120	90	80	60	51
working	26	701	621	420	131	70	70	71	30
kings	1	321	301	421	140	81	80	60	40
King	14	11446	10074	410	140	90	80	70	40
KING	14	10375	10085	411	130	80	80	70	50
Pumblechookian	2	231	200	421	140	70	60	60	30
Pumblechook	163	3535	3495	410	131	70	60	50	30
Average (ms)		27100	25733	419	133	81	76	65	40

Interesting observations (amongst many others):
a) All algorithms found "working" relatively quickly, but "king" (in lower/upper/mixed case) took some algorithms a lot longer; and yet the single occurrence of "kings" was always found very quickly. 
b) Most algorithms were largely independent of the number of occurrences of the search word.
c) The faster algorithms were fastest on longer words; typically they implemented a variation of the Boyer-Moore algorithm.

Not all entries returned the search word in the same case as was passed to the function - even though the parameters were defined as const. No entry was rejected because of this. The ability to change const parameters will be discussed at the November Melbourne ADUG meeting. 

The code - as submitted with only a file name change to make all files unique - is available by clicking the column headers of the table above. One file requires a minor change to make it compile (a dependency on its original test harness has to be removed).

Richard's testing code is here (Note: substitute your own ADUGStringInFile.pas or put one of the other submitted xx_ADUGStringInFile.pas files in the same folder to test different algorithms. You will also need to have a text file to search - grexp10.txt is the default file). 

Roger's testing code is here (Note: This test harness tests all submissions of the Find String ADUG Competition. It is not an application as such and tests are installed at compile time by changing constants in the code. Read the Read Me file). 

Examination of the submitted code identified a number of programming topics of general interest which will be discussed at the November 2003 Melbourne ADUG meeting. The topics are:

Andrea: Procedure size and naming
Natalie: Use of Initialise, Warnings.
Richard: Objects, Sub procedures, defined sets
Roger: PChars with StrLower(), StrUpper()  

These short sessions will be very informative. You will learn something you did not know about Delphi.