Here's an interesting problem I've come across.
I'm writing a program that essentially generates random strings (its a
simulator of the game Boggle) and sends them to a function that does a
binary search on a word list to see if that string is listed. However, at
seemingly random intervals (I've seen it happen on everything from a few
dozen calls to the function to a few thousand) I get a
system.stackoverflowexception. I'm assuming I've got a logic problem
somewhere in the function that sends it into deep recursion on very rare
occasions (like one in a thousand). Fortunately, the program is mostly just
a toy, and it serves my needs as it is. I figured someone might have a fun
time trying their hand at spotting the problem, though. I myself am deeply
puzzled over the fact that the exception seems to occur at random intervals;
I have detected absolutely no pattern. So, here's the function where the
exception is thrown:
Here's the function call. WordCount is an accumulator that kept track of
exactly how many words were read into the WordList array. str is the string
that the simulator has generated.
....
Select Case DictCheck(str, 0, CInt(Int(WordCount / 2)), WordCount)
....
Private Function DictCheck(ByVal word As String, ByVal LowBound As Integer,
ByVal Center As Integer, ByVal HighBound As Integer) As Short
Select Case String.Compare(word, 0, WordList(Center), 0, Len(word))
'Specifically, Visual Studio highlights this line when the exception is
thrown.
Case -1
If (HighBound - LowBound > 2) Then
Return DictCheck(word, LowBound, CInt(Int(LowBound + ((Center -
LowBound) / 2))), Center)
End If
Case 0
If Len(word) < Len(WordList(Center)) Then
Select Case (DictCheck(word, LowBound, CInt(Int(LowBound +
((Center - LowBound) / 2))), Center))
Case 0
Return 2
Case 1
Return 1
End Select
Return 2
End If
If Len(word) = Len(WordList(Center)) Then
Return 1
End If
Case 1
If (HighBound - LowBound > 2) Then
Return DictCheck(word, Center, CInt(Int(Center + ((HighBound -
Center) / 2))), HighBound)
End If
End Select
End Function
For your information, the WordList array ends up having a bit under 60,000
elements, so theoretically the recursion shouldn't ever go any deeper than
15 to 17 executions. The list is arranged alphabetically. Also, I return
three different possible values with this function. 0 means the string had
no match in the array. 1 means the string had an exact match in the array. 2
means the string matched the beginning part of the element, but that the
word in the element is longer than the string to which it is compared. The
way the program is set up, this function is called literelly thousands of
times a minute.
If you like a challenge, then happy hunting!
BTW, my system doesn't allow me to respond to posts; if you want to know if
your solution works, make sure I get your e-mail address.
Michael Sutherland
(e-mail address removed)
