Recursively Iterate through Grid and Return Result in an Array

I'm struggling with the logic to do the Recursion.

For the grid below I need to search a word and return an array of indexes that form the word if it exists or an empty array [] if it doesn't exist.

The word may start anywhere in the grid, and consecutive letters can be either immediately below or immediately to the right of the previous letter.

grid = [
  ['c', 'c', 'x', 't', 'i', 'b'],
  ['c', 'c', 'a', 't', 'n', 'i'],
  ['a', 'c', 'n', 'n', 't', 't'],
  ['t', 'c', 's', 'i', 'p', 't'],
  ['a', 'o', 'o', 'o', 'a', 'a'],
  ['o', 'a', 'a', 'a', 'o', 'o'],
  ['k', 'a', 'i', 'c', 'k', 'i'],
];

word = "catnip"

find_word_location(grid, word)
// OUTPUT [ (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4) ]

This is what I have so far but it's not working.

function find_word_location (grid, word) {
  const dfs = (i, j, wordIndex, res) => {
    if (wordIndex == word.length) return;

    if (
      i > grid.length - 1 ||
      j > grid[0].length - 1 ||
      grid[i][j] !== word[wordIndex]
    )
      return;

    if (grid[i][j] == word[wordIndex]) {
      res.push(`(${i},${j})`);
      grid[i][j] = "#";
    }

    dfs(i   1, j, wordIndex   1, res);
    dfs(i, j   1, wordIndex   1, res);

    grid[i][j] = word[wordIndex];

    return res;
  };

  for (let i = 0; i < grid.length; i  ) {
    for (let j = 0; j < grid[0].length; j  ) {
      if (grid[i][j] == word[0]) {
        let result = dfs(i, j, 0, []);
        return result;
      }
    }
  }
  return [];
}

CodePudding user response：

Some of the issues:

After the initial call of dfs your code always returns the result. This means that it assumes that if the first letter matches, the whole word must be matched starting at that cell. But this is not true. It might not find a match there, while there might be other places in the grid with that first letter which do give a full word match. So this return statement should be conditional (only when there is success).
The array referenced by res only grows. It never shrinks. Realise there is only one res array -- referenced by all res variables that live in the dfs execution contexts. So all partial matches (that eventually fail to lead to a full match) are collected in it, and concatenated one after the other. There is no backtracking applied to it.

I find it more elegant to actually only start building an array when the whole word has been matched, and then fill up an array while getting out of the recursive calls (as opposed to doing this while deepening the recursion).
The recursive calls of dfs completely ignore the values that those calls return, so no distinction is made between failure and success. You'd need to check the result of the first recursive call and if it was successful, the second one should not even be made.
Not a problem, but the condition in if (grid[i][j] == word[wordIndex]) { will always be true, given you already tested the opposite condition in the preceding if statement.

Here is a correction to your code, also implementing the idea I expressed in the second point, i.e. only filling up an array when it is already known there was a success:

// No res argument. res will be populated "inside-out" via the return value
function find_word_location (grid, word) {
  const dfs = (i, j, wordIndex) => {
    if (wordIndex == word.length) return []; // Start a solution with this res

    if (
      i > grid.length - 1 ||
      j > grid[0].length - 1 ||
      grid[i][j] !== word[wordIndex]
    )
      return;

    grid[i][j] = "#";

    // Use the returned value 
    //    and apply short-circuit to avoid useless second call
    const res = dfs(i   1, j, wordIndex   1) || dfs(i, j   1, wordIndex   1);

    grid[i][j] = word[wordIndex];
    
    if (res) res.unshift([i, j]); // Extend the path we got from recursion
    return res;
  };

  for (let i = 0; i < grid.length; i  ) {
    for (let j = 0; j < grid[0].length; j  ) {
      if (grid[i][j] == word[0]) {
        let result = dfs(i, j, 0, []);
        if (result) return result; // conditionally
      }
    }
  }
  return [];    
}

var grid = [
  ['c', 'c', 'x', 't', 'i', 'b'],
  ['c', 'c', 'a', 't', 'n', 'i'],
  ['a', 'c', 'n', 'n', 't', 't'],
  ['t', 'c', 's', 'i', 'p', 't'],
  ['a', 'o', 'o', 'o', 'a', 'a'],
  ['o', 'a', 'a', 'a', 'o', 'o'],
  ['k', 'a', 'i', 'c', 'k', 'i'],
];

var word = "catnip";
var result = find_word_location(grid, word);
console.log(result);

CodePudding user response：

This approach does not hand over the result to the recursive call.

The function takes grid, the word or the left over word part, and the actual indices, which has zero as default value.

Inside, the exit condition comes first by checking boundaries.

Then a check for the wanted character follows.

Inside it check with new word length, without actual character and if an empty string, it returns the indices.

The rest is nearly identically without the part for checking the found indices and if they are adjacent to the actual elememnt.

Roughly, get sub indices, check if there are indices and return the result either with actual indices (letter match) or just the rest.

const
    findWord = (grid, word, i = 0, j = 0) => {
        const isAdjacent = (x, y) => x === i && y === j   1 || x === i   1 && y === j;
        let sub;

        if (i   1 === grid.length || j   1 === grid[i].length) return [];

        if (grid[i][j] === word[0]) {
            const w = word.slice(1);
            
            if (!w.length) return [[i, j]];
            
            sub = findWord(grid, w, i   1, j);
            if (sub.length && isAdjacent(...sub[0])) return [[i, j], ...sub];
        
            sub = findWord(grid, w, i, j   1);
            if (sub.length && isAdjacent(...sub[0])) return [[i, j], ...sub];
        }
 
        sub = findWord(grid, word, i   1, j);
        if (sub.length) return sub;
        
        sub = findWord(grid, word, i, j   1);
        if (sub.length) return sub;

        return [];
    },
    grid = [['c', 'c', 'x', 't', 'i', 'b'], ['c', 'c', 'a', 't', 'n', 'i'], ['a', 'c', 'n', 'n', 't', 't'], ['t', 'c', 's', 'i', 'p', 't'], ['a', 'o', 'o', 'o', 'a', 'a'], ['o', 'a', 'a', 'a', 'o', 'o'], ['k', 'a', 'i', 'c', 'k', 'i']],
    word = "catnip",
    result = findWord(grid, word);
    
console.log(result.map(p => p.join('-')));

.as-console-wrapper { max-height: 100% !important; top: 0; }