3 Apr
2006
3 Apr
'06
9:49 a.m.
In article <4431353C.6090002 at pacbell.net>,
Jim Battle <frustum at pacbell.net> writes:
The clever answer is to have two pointers. At each
step of the=20
algorithm, one pointer advances two steps and the other pointer advances=20
three steps (any relatively prime pair of increments would work). After=20
the pointers are advanced, check if they are the same. If there is a=20
loop, eventually the two pointers will coincide, even if they have to=20
race around the loop a few times before their phases align. Never mind=20
the fact that actually coding it is a bit of a mess since at each of the=20
places where the pointers must be advanced, each intermediate step must=20
be checked for the end of list condition.
This algorithm for loop detection is in Knuth's Art of Computer
Programming.
I think MS asked me *this* question too (or maybe it was the game
company) and I recognized the pattern and the appropriate algorithm
and where to look it up. I just didn't have the algorithm memorized.
I too felt I was "dinged" for not having memorized the algorithm, but
it seemed that I was mildly forgiven for knowing where to look it up.
--
"The Direct3D Graphics Pipeline"-- code samples, sample chapter, FAQ:
<http://www.xmission.com/~legalize/book/>
Pilgrimage: Utah's annual demoparty
<http://pilgrimage.scene.org>