473,320 Members | 2,092 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

An interesting problem...

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

me***********@hotmail.com
Nov 20 '05 #1
2 1228
Hi Micheal

You just need to check out the use of debug.writeline, debug.assert
statements/methods.
System.Diagnostics.

hth
Richard
Nov 20 '05 #2
Hi Michael,

The first thing I would do when I was you was setting an elsecase as well
when I as you where still in this testing situation. The change on an
infinity loop is very sure in this situation.

I hope this helps?

Cor
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

me***********@hotmail.com

Nov 20 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

56
by: Dave Vandervies | last post by:
I just fixed a bug that some of the correctness pedants around here may find useful as ammunition. The problem was that some code would, very occasionally, die with a segmentation violation...
23
by: Bruno R. Dias | last post by:
Perhaps it would be interesting to program a virtual machine simulating an ancient computer (such as the pdp-7). Then, it would be rather interesting to code for it (porting gcc to it maybe?). I...
7
by: David Sworder | last post by:
Hi, I'm developing an application that will support several thousand simultaneous connections on the server-side. I'm trying to maximize throughput. The client (WinForms) and server communicate...
1
by: Rakesh Roberts | last post by:
I think I have a very interesting cookie problem. I use form authentications on my application. Through out my application I started using a toggle control that persists its value for the session...
2
by: sasifiqbal | last post by:
Hi, One of my developers are facing an interesting problem regarding UserControl invalidation. The problem is: We have two forms in our application. Form A does nothing except loading of...
27
by: Frederick Gotham | last post by:
I thought it might be interesting to share experiences of tracking down a subtle or mysterious bug. I myself haven't much experience with tracking down bugs, but there's one in particular which...
6
by: per9000 | last post by:
An interesting/annoying problem. I created a small example to provoke an exception I keep getting. Basically I have a C-struct (Container) with a function-pointer in it. I perform repeated calls...
5
by: Will Honea | last post by:
I've hit an interesting trap trying to migrate data off an OS/2 server running version 7.2 (fp14) over to 8.2 on Linux. Seems that one table has a column defined in the DDL as "BIGINT NOT NULL...
11
by: onkar.n.mahajan | last post by:
Is it possible to from function call on fly in C programming language ? I am faced with an interesting problem in that I need to take function name and arguments on fly (actually from Database...
4
by: Andrew | last post by:
I am having an interesting namespace conflict. When we use a third party lib we create a company assembly for any descending classes to go in. I have simplified the problem into the example...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.