Trace through the direction matrix in R

I have a matrix like this:

You can download it like this:

matrix = structure(c("-", "-", "C", "G", "C", "A", "-", "0", "V", "V", 
"V", "V", "C", "H", "D", "V", "DV", "V", "A", "H", "H", "D", 
"DV", "D", "C", "H", "DH", "DH", "D", "V", "G", "H", "H", "D", 
"H", "D", "T", "H", "H", "H", "DH", "DH", "A", "H", "H", "H", 
"DH", "D", "T", "H", "H", "H", "DH", "H"), .Dim = c(6L, 9L))


Starting at the bottom right corner, the goal is to follow the directions (D = move diagonally to 0, H = move left, V = move to above) so that all paths reach zero. As you can see, there are multiple multi-directional cells (like DH).

I'm trying to find ALL possible paths through a matrix like this. I did it with recursion. But I have a hard time keeping the path (s). It seems that when the function goes back to the old cell to go in the other direction, it adds the path to the wrong list.

Here's my code for the recursive function:

threading = function(matrix,i,j,list) { #Function wants the matrix to be threaded, number of rows and cols, and an empty list
  if (matrix[i,j] == 0) { #If the recursion has arrived at zero, stop and print out the path that arrived there
  else { #If still elsewhere inside the matrix...
    for (move in strsplit(matrix[i,j],"")[[1]]) { #Iterate through each move in that cell
      if (move == "D") { #If a move is D...
        list = paste(list, "D", sep="") #Append that to the path
        threading(matrix,i-1,j-1,list) #Send the function to the diagonal cell
      if (move == "V") { #If a move is V...
        list = paste(list, "V", sep="") #Append that to the path
        threading(matrix,i-1,j,list) #Send the function to the above cell
      if (move == "H") { #If a move is H...
        list = paste(list, "H", sep="") #Append that to the path
        threading(matrix,i,j-1,list) #Send the function to the left cell


So when I run it with the above matrix it gives this as a result:

> threading(matrix, 6,9, emptylist)


The kicker is that the second character of the second two paths is wrong, but everything else is correct. How to avoid this? I can't figure out how to save the path correctly without going back to the old path. I think it has to do with the ordering of adding and sending the function to the next cell, but if I cancel them then the addition never happens ...


source to share

1 answer

The problem is this:

list = paste(list, "*", sep="")


When you click on a cell with two choices, for example. "VH", the loop for

will go through two iterations: it is list

changed by the first iteration, then this modified value is passed to the second iteration. Instead, each iteration must use the original value. Therefore, you can replace with:

l = paste(list, "*", sep="")


and pass l

instead list

to the call threading


On a separate note, it is recommended that you avoid naming your variables matrix

or list

because they are also the name of functions.



All Articles