1

Problem Statement:

I have a tree with node values ( i , j ) where i , j < 1. The children of each node take on the values (i - 1, j), (i - 1, j - 1), and (i, j - 1) respectively. Now, i and j have constraints where they cannot be less than zero, so, given i (or j WLOG) == 0 for a node, its only child becomes (0, j - 1) (assuming j > 0).

These nodes represent the indices of a matrix, and what the children represent are either the index to the West, the North, or the North West of the currently selected index. (Notice 0 either represents the West edge or the North edge of the matrix)

I have written a recursive algorithm that will produce the number of different directions you can walk to get from node_0 (i, j) to the beginning.

def backtrackrecursion( currentnode, counter ):
    if currentnode.getindex() == (0 , 0):
        return counter++
    if currentnode.geti() > 0:
        currentnode.addchild(Node(index=(i - 1, j)))
    if currentnode.getj() > 0:
        currentnode.addchild(Node(index=(i, j - 1)))
    if currentnode.getindex() >= ( 1 , 1 ):
        currentnode.addchild(Node(index=(i - 1, j - 1)))
    for child in currentnode.getchildren():
        counter += backtrackrecursion(child, counter)
    return counter

I understand why this works. My girlfriend wrote another algorithm, and to my astonishment, it works as well.

def btr(cnode, cou):
    if cnode.getindex() == ( 0 , 0 ):
        return cou++
    if cnode.getindex() != (0 , 0):
        cou = btr(cnode.inddecr( -1, 0), cou) + btr(cnode.inddecr(0, -1), cou) + btr(cnode.inddrec( -1 , -1 ), cou)
    return cou

now I might have missed a property in her class that deletes all children with index i or j < 0, but shouldn't this be an infinite call? Where is the logic that I am missing?

  • Do a test: what does her cnode.inddecr (-1, -1) return for node (1,0)? what about cnode.inddecr (0, -1) on (1,0)? – caveman Feb 21 '15 at 18:29
  • Im going to do the test tonight when I see her. Thank you for the brilliant idea. – user71666 Feb 22 '15 at 7:21
-2

If i and j have to be less then one but not less then zero then no recursion is possible because if 0<=i<1 and 0<=j<1 then i-1<0 and j-1<0, so no new nodes can appear.

  • 1
    This would be a better answer if you made it a complete explanation, rather than an out-of-context response to something the OP said. In other words, this reads more like a comment than it does an answer. – Robert Harvey Feb 21 '15 at 18:35
  • He asked why it is not an infinite call and I answered it, what exactly is wrong? – k-l Feb 22 '15 at 1:40
  • You're just going to focus on the last 10 words of his question? – Robert Harvey Feb 22 '15 at 1:41
  • Maybe I am missing something, what exactly is 71666 asking? – k-l Feb 22 '15 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.