Wrong exit condition in recursive solution

Question

There are a 2D char-array and a search word. The task is to find out if there's the word in the array. The word can be placed in the array in any curve with 4 directions: up, down, left, right. You can't reuse the letters. For example, from an array [a, b, c] you can't get a word "ababc". See the examples below.

function findWord(puzzle, word) {
  
}

const puzzle = [
  'ANGULAR',
  'REDNCAE',
  'RFIDTCL',
  'AGNEGSA',
  'YTIRTSP',
];

console.log(findWord(puzzle, 'ANGULAR')); // true
console.log(findWord(puzzle, 'REACT')); // true
console.log(findWord(puzzle, 'ARRAY')); // true
console.log(findWord(puzzle, 'UNDEFINED')); // true
console.log(findWord(puzzle, 'RED')); // true
console.log(findWord(puzzle, 'STRING')); // true
console.log(findWord(puzzle, 'CLASS')); // true
console.log(findWord(puzzle, 'FUNCTION')); // false
console.log(findWord(puzzle, 'NULL')); // false

My solution:

function findWord(puzzle, word) {
  puzzle = puzzle.map(e => e.split(""));
  const current = [];
  const clear = [];
  for (let y = 0; y < puzzle.length; y++) {
    for (let x = 0; x < puzzle[y].length; x++) {
      if (puzzle[y][x] === word[0]) {
        clear.push({x, y});        
        current.push(...getSurround(x, y, puzzle));
      }
    }
  }
  return nextTurn(puzzle, word.slice(1), clear, current);
}

function nextTurn(puzzle, word, clear, current) {
  const next = [];
  if (word.length === 0) return true;

  for (let v of clear) {puzzle[v.y][v.x] = "-"}
  clear.length = 0;

  for (let v of current) {
    if (v === null) continue;
    if (v.letter === word[0]) {
      clear.push({x: v.x, y: v.y});
      next.push(...getSurround(v.x, v.y, puzzle));      
    }
  }
  if (next.length === 0) return false;
  return nextTurn(puzzle, word.slice(1), clear, next);
}

function getSurround(x, y, puzzle) {
  const surround = [];
  const u = (y !== 0) ? {x, y: y - 1, letter: puzzle[y - 1][x]} : null;
  const r = (x !== puzzle[y].length - 1) ? {x: x + 1, y, letter: puzzle[y][x + 1]} : null;
  const d = (y !== puzzle.length - 1) ? {x, y: y + 1, letter: puzzle[y + 1][x]} : null;
  const l = (x !== 0) ? {x: x - 1, y, letter: puzzle[y][x - 1]} : null;
  surround.push(u, r, d, l);
  return surround;
}

It seems that solution works for finding the word, but the problem is in the recursion exit. I made a guess, that true is when the word is done, and false is when the word is not done and there is no other appropriate letter to end the word.

user_5648954 · Answer

Your issue seems to be with:

for (let v of clear) {puzzle[v.y][v.x] = "-"}
clear.length = 0;

for the word "angular", this will set all "a"s to "-", which you shouldn't be doing, you should only be setting "a" to blank if/when you use it. Currently you're setting all "a" characters to "-" which means that you wont be able to use "a" again (so the second a in "angular" wont be found).

I suggest removing the idea of your clear array, and instead updating your nextTurn function:

function nextTurn(puzzle, word, current) {
  if (word.length === 0) return true;

  for (const v of current) {
    if (v.letter === word[0]) {
      const nextCandidates = getSurround(v.x, v.y, puzzle);
      puzzle[v.y][v.x] = '-'; // mark letter as we're using it
      const turnResult = nextTurn(puzzle, word.slice(1), nextCandidates);
      if(turnResult) // recursive call returned true
        return turnResult;
      // If using the letter at x,y didn't work, "un-mark" it
      puzzle[v.y][v.x] = v.letter;
    }
  }
  
  return false;
}

The idea is to mark the current letter as "used" ("-") right before we recurse and call nextTurn(). This allows us to use the current letter right before we search its surrounding letters in the next call to nextTurn(). If searching that particular letter doesn't work, we backtrack and set the letter in the puzzle back to "available" by setting the letter back to its original value so that we can search the other possible options (and possible reuse this letter at some further point in the word).

In the below snippet I've also updated your findWord() function so that it converts your 2d puzzle array of letters to an array of vertices ({x, y, letter} objects), which can then be used by nextTurn() to calculate the next possible solution for each letter. Lastly, I've also updated your getSurround function to avoid the unneeded null values. This helps remove iterations over values which you know you won't be processing:

function findWord(puzzle, word) {
  puzzle = puzzle.map(str => Array.from(str));
  const candidates = puzzle.flatMap((row, y) => row.map((letter, x) => toVertex(x, y, letter)));
  return nextTurn(puzzle, word, candidates);
}

function nextTurn(puzzle, word, current) {
  if (word.length === 0) return true;

  for (const v of current) {
    if (v.letter === word[0]) {
      const nextCandidates = getSurround(v.x, v.y, puzzle);
      //console.log(v.y, v.x, puzzle[v.y]);
      puzzle[v.y][v.x] = '-'; // mark letter as we're using it
      const turnResult = nextTurn(puzzle, word.slice(1), nextCandidates);
      if(turnResult) // recursive call returned true
        return turnResult;
      // If using the letter at x,y didn't work, "un-mark" it
      puzzle[v.y][v.x] = v.letter;
    }
  }
  
  return false;
}

function getSurround(x, y, puzzle) {
  const surround = [];
  if(y !== 0)
    surround.push(toVertex(x, y-1, puzzle[y - 1][x]));
    
  if(x !== puzzle[y].length - 1)
    surround.push(toVertex(x+1, y, puzzle[y][x + 1]));
    
  if(y !== puzzle.length - 1)
    surround.push(toVertex(x, y+1, puzzle[y + 1][x]));
    
  if(x !== 0)
    surround.push(toVertex(x - 1, y, puzzle[y][x - 1]));
    
  return surround;
}

function toVertex(x, y, letter) {
  return {x, y, letter};
}

const puzzle = [
  'ANGULAR',
  'REDNCAE',
  'RFIDTCL',
  'AGNEGSA',
  'YTIRTSP',
];

console.log('ANGULAR', findWord(puzzle, 'ANGULAR')); // true
console.log('REACT', findWord(puzzle, 'REACT')); // true
console.log('ARRAY', findWord(puzzle, 'ARRAY')); // true
console.log('UNDEFINED', findWord(puzzle, 'UNDEFINED')); // true
console.log('RED', findWord(puzzle, 'RED')); // true
console.log('STRING', findWord(puzzle, 'STRING')); // true
console.log('CLASS', findWord(puzzle, 'CLASS')); // true
console.log('FUNCTION', findWord(puzzle, 'FUNCTION')); // false
console.log('NULL', findWord(puzzle, 'NULL')); // false
console.log('RANER', findWord(puzzle, 'RANER')); // false (additional test to try re-use)

Wrong exit condition in recursive solution

1 Answers