1

While I have a matrix as below, from top left corner to find all paths until get '0'. 'D' stands for the bottom element is the next step in trace. 'R' stands for the right element. 'B' stands for both the bottom and the right elements are alternative. 'C' stands for the element on the bottom right corner.

[['R' 'C' 'D' 'B' 'D' 'C' '0']
 ['C' 'B' 'C' 'B' 'D' 'D' '0']
 ['B' 'D' 'B' 'B' 'C' 'D' '0']
 ['R' 'C' 'B' 'D' 'B' 'C' '0']
 ['B' 'B' 'R' 'C' 'B' 'D' '0']
 ['R' 'C' 'B' 'R' 'R' 'C' '0']
 ['C' 'R' 'C' 'B' 'B' 'B' '0']
 ['0' '0' '0' '0' '0' '0' '0']]

In this case, there are two paths meet requirement, which are

(0, 0)R(0, 1)C(1, 2)C(2, 3)B(2, 4)C(3, 5)C(4, 6)0
(0, 0)R(0, 1)C(1, 2)C(2, 3)B(3, 3)D(4, 3)C(5, 4)R(5, 5)C(6, 6)0

I attempted to use recursive function to find all 'C' in these two paths, since there is a fork in (2, 3)B, the function only returns one of paths completely after joint.

(5, 5)C(4, 3)C
(3, 5)C(2, 4)C(1, 2)C(0, 1)C

So how could I revise my code to obtain whole result?

def printC(matrix, i=0, j=0):
    if matrix[i][j] == '0':
        print()
        return None
    elif matrix[i][j] == 'B':
        printC(matrix, i+1, j)
        printC(matrix, i, j+1)
    elif matrix[i][j] == 'D':
        printC(matrix, i+1, j)
    elif matrix[i][j] == 'R':
        printC(matrix, i, j+1)
    elif matrix[i][j] == 'C':
        printC(matrix, i+1, j+1)
        print((i,j), end='')
        print(matrix[i][j], end='')

printC(matrix)
print()

Thanks

ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152
Yuq S
  • 13
  • 3

2 Answers2

1

The natural algorithm to use for this problem is backtracking:

  • go forward, choosing the first option in all choices
  • after hitting an end, go back (backtrack) and choose the next option; go further back if no more options are available
  • after you backtrack from the initial element, you've exhausted all routes.

You "hit an end" in two cases:

  • You hit a 0 => add the current route to the result
  • You hit an element that is already in the route -- i.e. there's a loop.
    • With your rules, this is impossible: a step always goes down, right, or both. So we don't need to worry about this.

To track progress, we need:

  • current coordinates
    • integers

  • current route, with the ability to append to the end and pop from the end (i.e. a stack). We also need to store the last choice made.

    • Python list supports this:

      route = []
# go forward
route.append((new_x,new_ym,choice))
# backtrack
route.pop()
x,y,last_choice = route[-1]

  • a sequence of found routes, with the ability to append to the end

    • again, a list:

      results=[]
# add result
results.append(tuple(step[:2] for step in route))    # don't need choices in result

The full program will look something like this (in pseudocode):

initialization
while True:
    if can_step_forward:
        make_step_with_the_next_choice
        if hit_0:
            add_result
    else:
        backtrack
        if backtracked_past_the_beginning:
            break

return result

Using all this, can you now put the solution together?

ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152
  • You say backtracking is the "natural algorithm", but I would personally think of using some kind of tree structure and returning to the next branch when the previous one is finished, no backtracing required. That would be more efficient. – Graham Aug 07 '18 at 02:19
  • 1
    @Graham Yes, for a tree, this becomes a depth-first search. Backtracking is a bit more general: it accepts any number and logic for forward and backward steps and any underlying data structure (e.g. it can handle loops in arbitray ways). – ivan_pozdeev Aug 07 '18 at 02:25
  • Ah, so the logic for "backtrack" is not necessarily element by element checking, but could be a custom backtrack logic that finds the next branch immediately. – Graham Aug 07 '18 at 02:29
  • @Graham in principle, yes, though canonically, it should be just going one step back. Other possible logic should be seen as optimization of that. – ivan_pozdeev Aug 07 '18 at 02:33
0

I think this may be closer to what you want:

def printC(matrix, i=0, j=0, previous=None):
    if not previous:
        previous = []
    if matrix[i][j] == '0':
        print()
        return None
    elif matrix[i][j] == 'B':
        previous_branch = previous[:]
        printC(matrix, i+1, j, previous)
        print(''.join(reversed(previous_branch)), end='')
        printC(matrix, i, j+1, previous)
    elif matrix[i][j] == 'D':
        printC(matrix, i+1, j, previous)
    elif matrix[i][j] == 'R':
        printC(matrix, i, j+1, previous)
    elif matrix[i][j] == 'C':
        previous.append('{}{}'.format((i,j), matrix[i][j]))
        printC(matrix, i+1, j+1, previous)
        print((i,j), end='')
        print(matrix[i][j], end='')

The trick is to store previous commands and then reprimt them when traversing another branch. The reason why they have to be reversed is because the backtrace approach you've chosen in the recursion prints the commands after the path is taken, meaning the latest command is printed first because it is resolved first, et cetera.

Unfortunately, the code is kind of convoluted because of the recursive approach; in this case I actually think an iterative approach is much better suited.

Edit: here's an iterative approach, though I must note that nested lists are probably not the best tree substitute:

def printC(matrix, i=0, j=0):
    trace_root = [(i, j)]
    current_trace = trace_root
    trace_waiting = []
    while True:
        if matrix[i][j] == '0':
            if trace_waiting:
                current_trace = trace_waiting.pop()
                i, j = current_trace[-1]
            else:
                break
        elif matrix[i][j] == 'B':
            current_trace.extend([[(i+1, j)], [(i, j+1)]])
            trace_waiting.append(current_trace[-1])
            current_trace = current_trace[-2]
            i, j = current_trace[-1]
        else
            if matrix[i][j] == 'D':
                i += 1
            elif matrix[i][j] == 'R':
                j += 1
            elif matrix[i][j] == 'C':
                i, j = i+1, j+1
            current_trace.append((i,j))
    return trace_root
Graham
  • 3,153
  • 3
  • 16
  • 31